Draw $X_1^n$ uniformly from $B$ and let $J$ be uniform on $\{1,\ldots,n\}$ independently. Then
$$
\mathbb P(X_J=a)
=\frac1{|B|}\sum_{x_1^n\in B}\widehat P_{x_1^n}(a)
=P_B(a).
$$
If $P_i$ denotes the marginal law of $X_i$, this also says $P_B=n^{-1}\sum_iP_i$. Since $X_1^n$ is uniform on $B$,
$$
\log_2|B|=H(X_1^n).
$$
<Subadditivity of information entropy> followed by <concavity of information entropy> gives
$$
H(X_1^n)
\leq\sum_{i=1}^nH(P_i)
\leq nH\!\left(\frac1n\sum_{i=1}^nP_i\right)
=nH(P_B).
$$
Exponentiating proves $|B|\leq2^{nH(P_B)}$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 224 / 3 / c / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-224/3/c/solution