Spreading of Sets in Product Spaces and Hypercontraction of the Markov Operator

For a pair of random variables, $(X, Y)$ on the space X × Y and a positive constant, λ, it is an important problem of information theory to look for subsets A of X and B of Y such that the conditional probability of Y being in B supposed X is in A is larger than λ. In many typical situations in order to satisfy this condition, B must be chosen much larger than A. We shall deal with the most frequently investigated case when X = (X₁,⋯, Xₙ), Y = (Y₁,⋯, Yₙ) and (Xᵢ, Yᵢ) are independent, identically distributed pairs of random variables with a finite range. Suppose that the distribution of $(X, Y)$ is positive for all pairs of values $(x, y)$. We show that if A and B satisfy the above condition with a constant λ and the probability of B goes to 0, then the probability of A goes even faster to 0. Generalizations and some exact estimates of the exponents of probabilities are given. Our methods reveal an interesting connection with a so-called hypercontraction phenomenon in theoretical physics.