IID Lossless Source Coding and the AEP — Examples

Suppose $0<p<1$ and a word has $k$ ones, with $q=k\mathrm{/}n$. Its block probability is $p^k(1-p{)}^{n-k}$, so $I_n=-q\ln p-(1-q)\ln (1-p)$. Subtracting $h(p)$ gives $I_n-h(p)=(q-p)\ln ((1-p)\mathrm{/}p)$.

If $p=1\mathrm{/}2$, each supported word has probability $2^{-n}$, so $I_n=h(p)=\ln 2$ and all $2^n$ words are typical. If $p=0$ or $p=1$, the support consists of one symbol, its surprisal and entropy are zero, and the only supported length-$n$ word is typical.

If additionally $p\mathrm{\ne }1\mathrm{/}2$, the typicality condition in [F3] is exactly $\mathrm{\mid }q-p\mathrm{\mid }\le \eta$. There are $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ words of weight $k$, yielding the displayed sum with endpoints clipped to $0\le k\le n$. For the stated $p=1\mathrm{/}4,n=4$ check, the allowed weights are $k=0,1,2$, so the count is $1+4+6=11$ and the probability is $\frac{81+108+54}{256}=\frac{243}{256}$.

For $0<p<1$, the one-letter surprisal takes two values whose difference is $\ln ((1-p)\mathrm{/}p)$. Its variance is $p(1-p)(\ln ((1-p)\mathrm{/}p){)}^2$: writing the values as $a,b$, their mean is $pa+(1-p)b$, and the centered-square sum is $p(1-p{)}^2(a-b{)}^2+(1-p)p^2(a-b{)}^2=p(1-p)(a-b{)}^2$. At $p=0$ or $p=1$, the surprisal is zero on its singleton support, so [F1] gives $V=0$. Substituting these variances and $h(p)$ into [F6] gives the claimed quantitative probability and cardinality bounds.

Each $X_i$ has law $p$ on $\{0,1\}$, so $H(p)=-p\ln p-(1-p)\ln (1-p)>0$. For $0<p<1$, both summands are positive. Also $\mathbb{P}(X_1=0,X_2=0)=1-p\mathrm{\ne }(1-p{)}^2$, so the variables are not independent and hence are not IID.

The length-$n$ block has only two possible values: $0^n$ with probability $1-p$ and $1^n$ with probability $p$. Therefore its normalized self-information is either $-\ln (1-p)\mathrm{/}n$ or $-\ln p\mathrm{/}n$, and is bounded by $\max \{-\ln p,-\ln (1-p)\}\mathrm{/}n$. This tends to zero for both outcomes.

The limiting value $0$ differs from the positive marginal entropy in step 1.1. The IID conclusion [F3] therefore cannot be extended to all sequences with identical marginals after independence is removed.

Each $p_i$ is a probability law on $\{0,1\}$. The finite product $P_n(x^n)={\prod }_{i=1}^n{p}_i(x_i)$ is nonnegative and sums to ${\prod }_{i=1}^n{\sum }_{x_i\in \{0,1\}}{p}_i(x_i)=1$, so it is a well-defined finite law. Summing over the last coordinate gives $P_{n-1}$, proving consistency.

Let $F_n$ be the number of fair coordinates among $1,\dots ,n$. At every positive-probability word, each fair coordinate contributes $\ln 2$ to $-\ln P_n(x^n)$ and every point-mass coordinate contributes $0$. Hence $I_n(x^n):=-n^{-1}\ln P_n(x^n)=F_n\ln 2\mathrm{/}n$ on the entire support, so its law under $P_n$ is a point mass at this value.

If $k$ is even, the newest block is fair and $N_k-N_{k-1}\le F_{N_k}\le N_k$; since $N_{k-1}\mathrm{/}{N}_k=2^{-2k+1}\to 0$, $F_{N_k}\mathrm{/}{N}_k\to 1$. If $k$ is odd, the newest block is deterministic and $0\le F_{N_k}\le N_{k-1}$, so $F_{N_k}\mathrm{/}{N}_k\to 0$.

By step 2.1, $I_{N_k}$ is deterministic under $P_{N_k}$. Step 3.1 gives subsequential limits $\ln 2$ and $0$. For any constant $c$, at least one of $\mathrm{\mid }c\mathrm{\mid }$ and $\mathrm{\mid }c-\ln 2\mathrm{\mid }$ is at least $\ln 2\mathrm{/}2$; along that subsequence, for $\epsilon =\ln 2\mathrm{/}3$, the probability of $\mathrm{\mid }{I}_{N_k}-c\mathrm{\mid }>\epsilon$ is eventually $1$. Thus there is no limit in probability to a constant. The coordinate laws alternate, so the IID hypotheses of [F2] are absent.