You are an expert at summarizing long articles. Proceed to summarize the following text: 
there are many well known probabilistic proofs that objects with some properties exist . such a proof estimates the probability for a random object to violate the requirements and shows that it is small ( or at least strictly less than @xmath0 ) let us look at a toy example .    consider a @xmath1 boolean matrix and its @xmath2 minor ( the intersection of @xmath3 rows and @xmath3 columns chosen arbitrarily ) . we say that the minor is _ monochromatic _ if all its elements are equal ( either all zeros or all ones ) .    for large enough @xmath4 and for @xmath5 , there exists a @xmath6-matrix that does not contain a monochromatic @xmath7-minor . we repeat the same simple proof three times , in three different languages . ( probabilistic language ) let us choose matrix elements using independent tosses of a fair coin . for a given @xmath3 colums and @xmath3 rows , the probability of getting a monochromatic minor at their intersection is @xmath8 . ( both zero - minor and one - minor have probability @xmath9 . ) there are at most @xmath10 choices for columns and the same number for rows , so by the union bound the probability of getting at least one monochromatic minor is bounded by @xmath11 and the last expression is less then @xmath0 if , say , @xmath12 and @xmath4 is suffuciently large . ( combinatorial language ) let us count the number of bad matrices . for a given choice of columns and rows we have @xmath13 possibilities for the minor and @xmath14 possibilities for the rest , and there is at most @xmath10 choices for raws and columns , so the total number of matrices with monochromatic minor is @xmath15 and this is less than @xmath16 , the total number of boolean @xmath6-matrices . ( compression language ) to specify the matrix that has a monochromatic minor , it is enough to specify @xmath17 numbers between @xmath0 and @xmath4 ( rows and column numbers ) , the color of the monochromatic minor ( @xmath18 or @xmath0 ) and the remaining @xmath19 bits in the matrix ( their positions are already known ) . so we save @xmath20 bits ( compared to the straightforward list of all @xmath21 bits ) using @xmath22 bits instead ( each number in the range @xmath23 requires @xmath24 bits ; to be exact , we may use @xmath25 ) , so we can compress the matrix with a monochromatic minor if @xmath26 , and not all matrices are compressible . of course , these three arguments are the same : in the second one we multiply probabilities by @xmath16 , and in the third one we take logarithms . however , the compression language provides some new viewpoint that may help our intuition . in this example we want to put bits ( zeros and ones ) around the circle in a `` essentially asymmetric '' way : each rotation of the circle should change at least a fixed percentage of bits . more precisely , we are interested in the following statement :    there exists @xmath27 such for every suffuciently large @xmath4 there exists a sequence @xmath28 of bits such that for every @xmath29 the cyclic shift by @xmath3 positions produces a sequence @xmath30 that differs from @xmath31 in at least @xmath32 positions ( the hamming distance between @xmath31 and @xmath33 is at least @xmath32 ) .     is bad if most of the dotted lines connect equal bits ] assume that some rotation ( cyclic shift by @xmath3 positions ) transforms @xmath31 into a string @xmath33 that coincides almost everywhere with @xmath31 . we may assume that @xmath34 : the cyclic shift by @xmath3 positions changes as many bits as the cyclic shift by @xmath35 ( the inverse one ) . imagine that we dictate the string @xmath31 from left to right . first @xmath3 bits we dictate normally . but then the bits start to repeat ( mostly ) the previous ones ( @xmath3 positions before ) , so we can just say `` the same '' or `` not the same '' , and if @xmath36 is small , we know that most of the time we say `` the same '' . technically , we have @xmath32 different bits , and at least @xmath37 bits to dictate after the first @xmath3 , so the fraction of `` not the same '' signals is at most @xmath38 . it is well known that strings of symbols where some symbols appear more often than others can be encoded efficiently . shannon tells us that a string with two symbols with frequencies @xmath39 and @xmath40 ( so @xmath41 ) can be encoded using @xmath42 bits per symbol and that @xmath43 only when @xmath44 . in our case , for small @xmath36 , one of the frequencies is close to @xmath18 ( at most @xmath38 ) , and the other one is close to @xmath0 , so @xmath45 is significantly less than @xmath0 . so we get a significant compression for every string that is bad for the theorem , therefore most string are good ( so good string do exist ) . more precisely , every string @xmath46 that does not satisfy the requirements , can be described by    * @xmath3 * @xmath47 * @xmath48    for @xmath49 and for large enough @xmath4 the economy in the third part ( compared to @xmath35 ) is more important than @xmath24 in the first part . of course , this is essentially a counting argument : the number of strings of length @xmath50 where the fraction of @xmath0s is at most @xmath38 , is bounded by @xmath51 and we show that the bound for the number of bad strings , @xmath52 is less than the total number of strings ( @xmath53 ) . still the compression metaphor makes the proof more intuitive , at least for some readers . in our examples of probabilistic proofs we proved the existence of objects that have some property by showing that _ most _ objects have this property ( in other words , that the probability of this property to be true is close to @xmath0 under some natural distribibution ) . not all probabilistic proofs go like that . one of the exceptions is the famous lovsz local lemma  ( see , e.g. ,  @xcite ) . it can be used in the situations where the union bound does not work : we have too many bad events , and the sum of their probabilities exceeds @xmath0 even if probability of each one is very small . still lovsz local lemma shows that these bad events do not cover the probability space entirely , assuming that the bad events are `` mainly independent '' . the probability of avoiding these bad events is exponentially small , still lovsz local lemma provides a positive lower bound for it . this means , in particular , that we can not hope to construct an object satisfying the requirements by random trials , so the bound provided by lovsz local lemma does not give us a randomized algorithm that constructs the object with required properties with probability close to @xmath0 . much later moser and tardos @xcite suggested such an algorithm  in fact a very simple one . in other terms , they suggested a different distribution under which good objects form a majority . we do not discuss the statement of lovsz local lemma and moser  tardos algorithm in general . instead , we provide two examples when they can be used , and the compression - language proofs that can be considered as ad hoc versions of moser  tardos argument . these two examples are ( 1 )  satisfiability of formulas in conjunctive normal form ( cnf ) and ( 2 )  strings without forbidden factors . a cnf ( _ conjunctive normal form _ ) is a propositional formula that is a conjuction of _ clauses_. each clause is a disjunction of _ literals _ ; a literal is a propositional variable or its negation . for example , cnf @xmath54 consists of two clauses . first one prohibits the case when @xmath55 , @xmath56 , @xmath57 ; the second one prohibits the case when @xmath58 , @xmath59 , @xmath60 . a cnf is _ satisfiable _ if it has a _ satisfying assigment _ ( that makes all clauses true , avoiding the prohibited combinations ) . in our example there are many satisfying assigments . for example , if @xmath61 and @xmath62 , all values of other variables are ok .    we will consider cnf where all clauses include @xmath4 literals with @xmath4 different variables ( from some pool of variables that may contain much more than @xmath4 variables ) . for a random assignment ( each variable is obtained by an independent tossing of a fair coin ) the probability to violate a clause of this type is @xmath63 ( one of @xmath53 combinations of values for @xmath4 variables is forbidden ) . therefore , _ if the number of clauses of this type is less than @xmath53 , then the formula is satisfiable_. this is a tight bound : using @xmath53 clauses with the same variables , we can forbid all the combinations and get an unsatisfiable cnf . the following result says that we can guarantee the satisfiability for formuli with much more clauses . in fact , the total number of clauses may be arbitrary ( but still we consider finite formulas , of course ) . the only thing we need is the `` limited dependence '' of clauses . let us say that two clauses are _ neighbors _ if they have a common variable ( or several common variables ) . the clauses that are not neighbors correspond to independent events ( for a random assignment ) . the following statement says that if the number of neighbors of each clause is bounded , then cnf is guaranteed to be satisfisable . assume that each clause in some cnf contains @xmath4 literals with different variables and has at most @xmath64 neighbor clauses . then the cnf is satisfiable . note that @xmath64 is a rather tight bound : to forbid all the combinations for some @xmath4 variables , we need only @xmath53 clauses . it is convenient to present a proof using the compression language , as suggested by lance fortnow . consider the following procedure @xmath65 whose argument is a clause ( from our cnf ) .    \ { @xmath66 is false } + @xmath65 : + @xmath67 + * for * all @xmath68 that are neighbors of @xmath66 : + * if * @xmath68 is false * then * @xmath69 + \ { @xmath66 is true ; other clauses that were true remain true }    here @xmath67 is the procedure that assigns fresh random values to all variables in @xmath66 . the pre - condition ( the first line ) says that the procedure is called only in the situation where @xmath66 is false . the post - condition ( the last line ) says that _ if the procedure terminates _ , then @xmath66 is true after termination , and , moreover , all other clauses of our cnf that were true before the call remain true . ( the ones that were false may be true or false . ) note that up to now we do not say anything about the termination : note that the procedure is randomized and it may happen that it does not terminate ( for example , if all resample calls are unlucky to choose the same old bad values ) . * simple observation * : if we have such a procedure , we may apply it to all clauses one by one and after all calls ( assuming they terminate and the procedure works according to the specification ) we get a satisfying assignment .    * another simple observation * : it is easy to prove the `` conditional correctness '' of the procedure @xmath65 . in other words , it achieves its goal assuming that ( 1 )  it terminates ; ( 2 )  all the recursive calls @xmath69 achieve their goals . it is almost obvious : the @xmath67 call may destroy ( = make false ) only clauses that are neighbors to @xmath66 , and all these clauses are fix - ed after that . note that @xmath66 is its own neighbor , so the * for*-loop includes also a recursive call @xmath65 , so after all these calls ( that terminate and satisfy the post - condition by assumption ) the clause @xmath66 and all its neighbors are true and no other clause is damaged . note that the last argument remains valid even if we delete the only line that really changes something , i.e. , the line @xmath67 . in this case the procedure never changes anything but still is conditionally correct ; it just does not terminate if one of the clauses is false . it remains to prove that the call @xmath65 terminates with high probability . in fact , it terminates with probability @xmath0 if there are no time limits and with probability exponentially close to @xmath0 in polynomial time . to prove this , one may use a compression argument : we show that _ if the procedure works for a long time without terminating , then the sequence of random bits used for resampling is compressible_. we assume that each call of @xmath70 uses @xmath4 fresh bits from the sequence . finally , we note that this compressibility may happen only with exponentially small probability . imagine that @xmath65 is called and during its recursive execution performs many calls @xmath71 ( in this order ) but does not terminate ( yet ) . we stop it at some moment and examine the values of all the variables .    knowing the values of the variables after these calls and the sequence @xmath72 , we can reconstruct all the @xmath73 random bits used for resampling . let us go backwards . by assumption we know the values of all variables after the calls . the procedure @xmath74 is called only when @xmath75 is false , and there is only one @xmath4-tuple of values that makes @xmath75 false . therefore we know the values of all variables before the last call , and also know the random bits used for the last resampling ( since we know the values of variables after resampling ) . the same argument shows that we can reconstruct the values of variables before the preceding call @xmath76 , and random bits used for the resampling in this call , etc . now we need to show that the sequence of clauses @xmath72 used for resampling can be described by less bits than @xmath77 ( the number of random bits used ) . here we use the assumption saying each clause has at most @xmath64 neighbors and that the clauses @xmath68 for which @xmath69 is called from @xmath65 , are neighbors of @xmath66 . one could try to say that since @xmath78 is a neighbor of @xmath79 , we need only @xmath80 bits to specify it ( there are at most @xmath64 neighbors by assumption ) , so we save @xmath81 bits per clause ( compared to @xmath4 random bits used by resampling ) . but this argument is wrong : @xmath78 is not always the neighbor of @xmath79 , since we may return from a recursive call that causes resampling of @xmath79 and then make a new recursive call that resamples @xmath78 .    to get a correct argument , we should look more closely at the tree of recursive calls generated by one call @xmath65 ( fig . [ pic : treecall ] ) . in this tree the sons of each vertex correspond to neighbor clauses of the father - clause . ( up to some moment ) ]    the sequence of calls is determined by a walk in this tree , but we go up and down , not only up ( as we assumed in the wrong argument ) . how many bits we need to encode this walk ( and therefore the sequence of calls ) ? we use one bit to distinguish between steps up and down . if we are going down , no other information is needed . if we are going up ( and resample a new clause ) , we need one bit to say that we are going up , and @xmath80 bits for the number of neighbor we are going to . for accounting purposes we combine these bits with a bit needed to encode the step back ( this may happen later or not happen at all ) , and we see that in total we need at most @xmath82 bits per each resampling . this is still less than @xmath4 , so we save one bit for each resampling . if @xmath83 is much bigger than the number of variables , we indeed compress the sequence of random bits used for resampling , and this happens with exponentially small probability . this argument finishes the proof . the next example is taken from word combinatorics . assume that a list of binary strings @xmath84 is given . these @xmath85 are considered as `` forbidden factors '' : this means that we want to construct a ( long ) string @xmath86 that does not have any of @xmath85 as a factor ( i.e. , none of @xmath85 is a substring of @xmath86 ) . this may be possible or not depending on the list . for example , if we consider two strings @xmath87 as forbidden factors , every string of length @xmath13 or more has a forbidden factor ( we can not use zeros at all , and two ones are forbidden ) . the more forbidden factors we have , the more chances that they block the growth in the sense that every sufficiently long string has a forbidden factor . of course , not only the number of factors matters : e.g. , if we consider @xmath88 as forbidden factors , then we have long strings of ones without forbidden factors . however , now we are interested in quantitative results of the following type : _ if the number of forbidden factors of length @xmath89 is @xmath90 , and the numbers @xmath90 are `` not too big '' , then there exists an arbitrarily long string without forbidden factors_.    this question can be analyzed with many different tools , including lovsz local lemma ( see  @xcite ) and kolmogorov complexity . using a complexity argument , levin proved that if @xmath91 for some constant @xmath92 , then there exists a constant @xmath93 and an infinite sequence that does not contain forbidden factors of length smaller than @xmath93 . ( see  ( * ? ? ? * section 8.5 ) for levin s argument and other related results . ) a nice sufficient condition was suggested by miller  @xcite : we formulate the statement for the arbitrary alphabet size . consider an alphabet with @xmath94 letters . assume that for each @xmath95 we have @xmath90 `` forbidden '' strings of length @xmath89 . assume that there exist some constant @xmath96 such that @xmath97 then there exist arbitrarily long strings that do not contain forbidden substrings . * remarks*. 1 . we do not consider @xmath98 , since this means that some letters are deleted from the alphabet . \2 . by compactness the statement implies that there exists an infinite sequence with no forbidden factors . the constant @xmath31 should be at least @xmath99 , otherwise the right hand side is negative . this means that @xmath100 should be small , and this corresponds to our intution ( @xmath90 should be significantly less than @xmath101 , the total number of strings of length @xmath89 ) . the original proof from  @xcite uses some ingenious potential function defined on strings : miller shows that if its value is less than @xmath0 , then one can add some letter preserving this property . it turned out ( rather misteriously ) that exactly the same condition can be obtained by a completely different argument ( following  @xcite )  so probably the inequality is more fundamental than it may seem ! this argument is based on compression . here is the idea . we start with an empty string and add randomly chosen letters to its right end . if some forbidden string appears as a suffix , it is immediately deleted . so forbidden strings may appear only as suffixes , and only for a short time . after this `` backtracking '' we continue adding new letters . ( this resembles the famous `` tetris game '' when blocks fall down and then disappear under some conditions . ) we want to show that if this process is unsuccessful in the sense that after many steps we still have a short string , then the sequence of added random letters is compressible , so this can not happen always , and therefore a long string without forbidden factors exists . let us consider a `` record '' ( log file ) for this process that is a sequence of symbols `` @xmath102 '' and `` @xmath103 '' ( for each forbidden string we have a symbol , plus one more symbol without a string ) . if a letter was added and no forbidden string appears , we just add ` @xmath102 ' to the record . if we have to delete some forbidden string @xmath104 after a letter was added , we write this string in brackets after the @xmath102 sign . note that we do _ not _ record the added letters , only the deleted substrings . ( it may happen that several forbidden suffixes appear ; in this case we may choose any of them . )    at every stage of the process the current string and the record uniquely determine the sequence of random letters used .    having this information , we can reconstruct the configuration going backwards . this reversed process has steps where a forbidden string is added ( and we know which one , since it is written in brackets in the record ) , and also steps when a letter is deleted ( and we know which letter is deleted , i.e. , which random letter was added when moving forwards ) . if after many ( say , @xmath105 ) steps we still have a short current string , then the sequence of random letters can be described by the record ( due to the lemma ; we ignore the current string part since it is short ) . as we will see , the record can be encoded with less bits than it should have been ( i.e. , less than @xmath106 bits ) . let us describe this encoding and show that it is efficient ( assuming the inequality @xmath107 ) . we use arithmetic encoding for the lengths . arithmetic encoding for @xmath93 symbols starts by choosing positive reals @xmath108 such that @xmath109 . then we split the interval @xmath110 $ ] into parts of length @xmath108 that correspond to these @xmath93 symbols . adding a new symbol corresponds to splitting the current interval in the same proportion and choosing the right subinterval . for example , the sequence @xmath111 corresponds to @xmath112th subinterval of @xmath113th interval ; this interval has length @xmath114 . the sequence @xmath115 corresponds to interval of length @xmath116 and can be reconstructed given any point of this interval ( assuming @xmath108 are fixed ) ; to specify some binary fraction in this interval we need at most @xmath117 bits , i.e. , @xmath118 bits . now let us apply this technique to our situation . for @xmath102 without brackets we use @xmath119 bits , and for @xmath120 where @xmath104 is of length @xmath89 , we use @xmath121 bits . here @xmath122 are some positive reals to be chosen later ; we need @xmath123 . indeed , we may split @xmath122 into @xmath90 equal parts ( of size @xmath124 ) and use these parts as @xmath125 in the description of arithmetical coding above ; splitting adds @xmath126 to the code length for strings of length @xmath89 .    to bound the total number of bits used for encoding the record , we perform amortised accounting and show that the average number of bits per letter is less than @xmath127 . note that the number of letters is equal to the number of @xmath102 signs in the record . each @xmath102 without brackets increases the length of the string by one letter , and we want to use less that @xmath128 bits for its encoding , where @xmath129 is some constant saying how much is saved as a reserve for amortized analysis . and @xmath120 for a string @xmath104 of length @xmath89 decreases the length by @xmath130 , so we want to use less than @xmath131 bits ( using the reserve ) . so we need : @xmath132 together with @xmath133    technically is it easier to use non - strict inequalities in the first two cases and a strict one in the last case ( and then increase @xmath134 a bit ) : @xmath135 then for a given @xmath136 we take minimal possible @xmath134 : @xmath137 and it remains to show that the sum is less than @xmath0 for a suitable choice of @xmath136 . let @xmath138 , then the inequality can be rewritten as @xmath139 or @xmath140 and this is our assumption .    now we see the role of this mystical @xmath31 in the condition : it is just a parameter that determines the constant used for the amortised analysis .    * acknowledgement*. author thanks his lirmm colleagues , in particular pascal ochem and daniel gonalves , as well as the participants of kolmogorov seminar in moscow . 9    n.  alon , j.h . spencer , _ the probabilistic method _ , wiley , 2004 . d.  gonalves , m.  montassier , a.  pinlou , _ entropy compression method applied to graph colorings _ , https://arxiv.org/pdf/1406.4380.pdf . j.  miller , two notes on subshifts , _ proceedings of the ams _ , * 140 * , 1617 - 1622 ( 2012 ) . r.  moser , _ a constructive proof of the lovsz local lemma _ , https://arxiv.org/abs/0810.4812 . r.  moser , g.  tardos , a constructive proof of the general lovsz local lemma , _ journal of the acm _ , * 57*(2 ) , 11.111.15 ( 2010 ) . p.  ochem , a.  pinlou , application of entropy compression in pattern avoidance , _ the electronic journal of combinatorics _ , * 21*:2 , paper p2.7 ( 2014 ) . a.  rumyantsev , a.  shen , probabilistic constructions of computable objects and a computable version of lovsz local lemma , _ fundamenta informaticae _ , * 132 * , 114 ( 2013 ) , see also https://arxiv.org/abs/1305.1535    a.  rumyantsev , m.  ushakov , forbidden substrings , kolmogorov complexity and almost periodic sequences , _ stacs 2006 proceedings _ , lecture notes in computer science , * 3884 * , 396407 , see also https://arxiv.org/abs/1009.4455 . a.  shen , v.a . uspensky , n.  vereshchagin , _ kolmogorov complexity and algorithmic randomness _ , to be published by the ams , www.lirmm.fr/~ashen/kolmbook-eng.pdf . ( russian version published by mccme ( moscow ) , 2013 . ) there is one more sufficient condition for the existence of arbitrarily long sequences that avoid forbidden substrings . here is it.[multiblock footnote omitted ] if the power series for @xmath141 ( where @xmath142 is the number of forbidden strings of length @xmath94 ) has all positive coefficients , then there exist arbitrarily long strings withour forbidden substrings . moreover , in this case the number of @xmath4-letter strings without forbidden substrings is at least @xmath143 , where @xmath143 is the @xmath4th coefficient of this inverse series .    to prove this result , consider the number @xmath144 of allowed strings of length @xmath3 . it is easy to see that @xmath145 indeed , we can add each of @xmath94 letters to each of @xmath144 strings of length @xmath3 , and then we should exclude the cases where there is a forbidden string at the end . this forbidden string may have length @xmath13 , then there are at most @xmath146 possibilities , or length @xmath81 , there are at most @xmath147 possibilities , etc . ( note that @xmath148 and @xmath149 ; note also that we can get a string with two forbidden suffixes , but this is ok , since we have an inequality . ) these inequalities can be rephrased as follows : the product @xmath150 has only non - negative coefficients . denote the second term by @xmath151 ; if @xmath152 has only positive coefficients @xmath153 , ( as our assumption says ) , then the first term is a product of two series with non - negative coefficients . the first factor ( @xmath154 ) starts with @xmath0 , so the @xmath4th coefficient of a product , i.e. , @xmath155 , is not less than @xmath4th coefficient of the second factor , i.e. , @xmath143 . assume that the series in the denominator does not have a root , but the inverse series has all positive coefficients . in fact , non - negative coefficients are enough to get a contradiction . for a series with all non - negative coefficients , or with finitely many negative coefficients , the radius of convergence is determined by behavior of the sum on the real line : when the argument approaches the convergence radius , the sum of the series goes to infinity . now we have the product of two series @xmath156 that is equal to @xmath0 . one of these series should have finite convergence radius , otherwise both are everywhere defined and the product is everywhere @xmath0 , but both are large for large @xmath31 . look at the minimal convergence radius ( of two ) ; one of the series goes to infinity near the corresponding point on the real line , so the other one converges to zero , so it has bigger convergence radius and reaches zero at the real line . finally , note that only the first factor ( the denominator ) may have a zero , since the other one has all non - negative coefficients . now assume that the denominator has a zero ; we have to prove that the inverse series has only positive coefficients . in general , the following result is true ( d.  piontkovsky ) : _ if the series @xmath157 has @xmath158 , and @xmath159 , and for some positive @xmath31 this series converges to @xmath18 , then the inverse series has all positive coefficients . _ to prove this statement , let @xmath160 be the root , so @xmath161 . recall the long division process that computes the inverse series . it produce the sequence of remainders : the first @xmath162 is @xmath0 ; then we subtract from the @xmath3th remainder @xmath163 the product @xmath164 to cancel the first term , and get the next remainder @xmath165 . by induction we prove that for each remainder @xmath166 :        the second claim : by induction assumption the first coefficient in @xmath171 was positive , so we subtract the series @xmath172 with positive first and non - negative third , fourth , etc . the first term cancels the first term in @xmath171 , the second term does not matter now , but all the subsequent coefficients are negative or zeros , since we subtract non - negative coefficients from non - positive ones .        note that we have shown that if all coefficients of the series @xmath154 are non - negative , then they are positive . also note that we get a bit stronger result compared to the entropy argument where we required the series to reach a negative value ( now the zero value is enough ) .
we consider several examples of probabilistic existence proofs using compressibility arguments , including some results that involve lovsz local lemma .