A simple proof of the blowing-up lemma (Corresp.)

Abstract

The blowing-up lemma says that if the probability with respect to a product measure of a set <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A\subseteq {\cal X}^{n} ({\cal X}</tex> finite, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> large) is not exponentially small, then its <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l_{n}</tex> -neighborhood has probability almost one for some <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l_{n} = O(n)</tex> . Here an information-theoretic proof of the blowing-up lemma, generalizing it to continuous alphabets, is given.