Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 28 / 4 / c / Solution

Let $U_m$ be the average over all $d=p+1$ coordinate tuples in part (a), and $V_m$ the distinct-tuple average in part (b). Every product summand lies in $[0,1]$. A proportion ${\alpha }_m=(N{)}_d/N^d$, where $N=m+1$, of all tuples have distinct coordinates. Thuswhere $W_m\in [0,1]$ is the average over the remaining tuples. If there are no remaining tuples, the error is zero. Hence $|U_m-V_m|\le 1-{\alpha }_m$.

For $d$ independent uniform choices from $N$ indices, any particular pair coincides with probability $1/N$. A union bound over the $\left(\genfrac{}{}{0ex}{}{d}{2}\right)$ pairs givesThis deterministic sampling with and without replacement comparison for bounded products is the needed link between the two averages.

Part (a) identifies the almost-sure limit of $U_m$ as ${\prod }_{k=0}^p\mathbb{E}[1_{A_k}(X_k)\mid \mathcal{S}]$. By part (b) and the reverse martingale convergence theorem, $V_m$ converges almost surely to $\mathbb{E}[{\prod }_{k=0}^p{1}_{A_k}(X_k)\mid \mathcal{S}]$. Their difference vanishes, soThis is precisely conditional independence. Exchangeability also makes the single-coordinate conditional laws identical, by applying a coordinate transposition and testing against invariant events. The result is the De Finetti theorem, established here by finite symmetrization and the vanishing collision fraction.