Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 13 / 6 / i / Solution

The Harris lemma says that, in any finite product of independent Bernoulli coordinates, two increasing events satisfyThe coordinates need not have the same parameter. For completeness, the same statement for increasing functions follows by induction on the number of coordinates. Conditional on the last bit, induction makes the conditional covariance nonnegative; the covariance of the two conditional means is $p(1-p)(a_1-a_0)(b_1-b_0)\ge 0$. The covariance decomposition proves the induction step. Complementing both events gives the inequality for decreasing events too. Finite-cylinder approximation extends it to the countable product setting when needed.

For increasing events $A_1,\dots ,A_r$ of a common probability $a$, their decreasing complements giveTherefore the nth root trick isThis is a lower bound for an individual success probability when a symmetric union is very likely. Without equality of the individual probabilities, the conclusion applies to their maximum. Independence among the $A_j$ is not required.