Nima Hoda
Entropy compression is a new technique—introduced by Moser in his constructive proof of a specialized version of the Lovasz Local Lemma—for lower bounding the probability that certain kinds of iterative randomized algorithms will terminate in a given number of steps. The technique can be used to constructively prove the existence of discrete structures as well as to give upper bounds for the expected running times of the associated algorithms. We will discuss the technique from both a counting and an information theoretic perspective and will look at several examples simplified from the literature.