CHAPTER SIXThe Probabilistic Method"lhe probab,ilisti, m"thod is away of proving the existence of objects. The underly-ing principle is simple: to prove the existence of an object with certain properties, wedemonstrate a sample space of objects in which the probability is positive that a ran-domly selected object has the required properties. If the probability of selecting anobject with the required properties is positive, then the sample space must contain suchan object, and therefore such an object exists. For example, if there is a positive proba-bility of winning a million-dollar pize in a raffle, then there must be at least one raffleticket that wins that Prize.Although the basic principle of the probabilistic method is simple, its application tospecific problems often involves sophisticated combinatorial arguments. In this chap-ter we study a number of techniques for constructing proofs based on the probabilisticmethod, starting with simple counting and averaging arguments and then introducingtwo more advanced tools, the Lovasz local lemma and the second moment method.In the context of algorithms we are generally interested in explicit constructionsof objects, not merely in proofs'of existence. In many cases the proofs of existenceobtained by the probabiliqtienethod can be converted into efficient randomized con-struction algorithms. In some cases, these proofs can be converted into efficient de-terministic construction algorithms; this process is called derandomization, since itconverts a probabilistic argument into a deterministic one. We give examples of bothrandomized and deterministic construction algorithms arising from the probabilisticmethod.The Basic Counting ArgumentTo prove the existence of an object with specific properties, we construct an appropri-ate probability space S of objects and then show that the probability that an object in.S with the required properties is selected is strictly greater than 0.For our first example, we consider the problem of coloring the edges of a graph withtwo colors so that there are no large cliques with all edges having the same colQr. Let126\.t_fB{ir irtr,.sl i#i:*: i.'r:. I,i# i.tt1 i]?i:i';;i}''rit:I :l'1,1.tr,lli:;,yi.ii'l'ara,t1:.i,,r-::.T;,:,:',:t'';!tt:-l,a:i,j,i:erly-;' wgran-gansuchoba-'affle)n tohap-listicicingd.tionsencecon-t de-ce itbothlistic)pn-ct inwithLetff,,6.I THE BA,SIC COUNTING ARGUMENTKnbea complete graph 1*lttr utt (i) edges) on n vertices. A clique of k vertices in K,,is a complete subgraPh K7,.Theorem 6.1: If (b)Z-fi>*t <. l, then it is possible to color the edges of Kn with rwo (l)colors so that it has no monochromatic Kp subgraph.Proof: Define a sample space consisting of all possible colorings of the edges of Knusing two colors. There ur.2(D possible colorings, so if one is chosen uniformly atrandom then the probability of choosing each coloring in our probability space is 2-Q) .A nice way to think about this probability space is: if we color each edge of the graphindependently, with each edge taking each of the two colors with probability Il2,thenwe obtain a random coloring chosen uniformly from this sample space. That is, we flipan independent fair coin to determine the color of each edge.Fix an arbitrary ordering of all of ttre (f ) different k-vertex cliques of Kn, and fori : I, .. ., (il let A; be the event that cliqtie'i 'is monochromatic. Once the first edgein clique i is colored, the remaining (!) - 1 edges must all be given the same color. Itfollows thatPr(Ai) : 2-(5)+r 'Using a union bound then yields(f)I e'ia,y:j:lwhere the last inequality follows from the'a3'sumptions of the theorem. HenceSince the probability of choosing a coloring with no monochromatic k-vertex cliquefrom our sample space is strictly greater thaq.-Q, there must exist a coloring with nomonochromatic ft -vertex clique.As an example, consider whether the edges of K16ss can be 2-colored in such a waythat there is no monochromatic K2s. Our calculations are simplified if we note that, forn<2k/2andk>3,tn .-(ktk. I)/2)+lkt2k/2+lkt1.Observing that for our example n = 1000 < 2ro : 2k/2, we see that by Theorem 6.1there exists a 2-coloring of the edges of K166e with no monochromatic K2s.127"(, ,) =(i)'-".r= 1'-(f,') :'*(ga,) ,o(i)'-r:>.''. THE PROBABILISTIC METHODCan we use this proof to design an efficient algorithm to construct such a coloring?Let us consider a general approach that gives a randomized construction algorithm.First, we require that we can efficiently sample a coloring from the sample space. Inthis case sampling is easy, because we can simply color each edge independently witha randomly chosen color. In general, however, there might not be an etficient samplingalgorithm.If we have an efficient sampling algorithm, the next question is: How many sam-ples must we generate before obtaining a sample that satisfies our requirements? Ifthe probability of obtaining a sample with the desired properties is p and if we sampleindependently at each trial, then the number of samples needed before finding a sam-ple with the required properties is a geometric random variable with expectation l/p.Hence we need thatl/p be polynomial in the problem size in order to have an algorithmthat finds a suitable sample in polynomial expected time.lf p : | - o(1), then sampling once gives a Monte Carlo construction algorithmthat is incorrect with probability o(1). In our specific example of finding a coloring ona graph of 1000 vertices with no monochromatic K2s, we know that the probability thata random coloring has a monochromatic K26 is at most22o/2+l2U < g.5.10-16.Hence we have'*Monte carlo. algorithm with a small probability of failure.If we want a Las Vegas algorithrn - that is, one that always gives a correct construc-tion - then we need a third ingredient. We require a polynomial time procedure forverifying that a sample object satisfies the requirements; then we can test samples untilwe find one that does so. An upfier bound on the expected time for this constructioncan be found by multiplying together the expected number of samples rf p, an upperbound on the time to generate each sample, and an upper bound on the time to checkeach sample.l For the coloring problem, there is a polynomial time verification algo-rithm when ft is a constant: simply check arr (f ) .iiqu", and make sure they are iotmonochromatic. It does not seem that this approach can be extended to yield polyno-mial time algorithms when k grows with n.6.2.