The Chaining Lemma and Its Application

We present a new information-theoretic result which we call the Chaining Lemma. It considers a so-called "chain" of random variables, defined by a source distribution X-(0) with high min-entropy and a number (say, t in total) of arbitrary functions (T-1,...,T-t) which are applied in succession to that source to generate the chain X-(0) (sic) X-(1) (sic) X-(2)...(sic) X-(t). Intuitively, the Chaining Lemma guarantees that, if the chain is not too long, then either (i) the entire chain is "highly random", in that every variable has high min-entropy; or (ii) it is possible to find a point j (1