= Typical-set concentration for a biased coin
The count $K_n$ has <binomial distribution> with <mean> $n/4$ and <variance> $3n/16$. The <information content> per symbol is an affine function of $K_n/n$, so its <variance> is
$$
\operatorname{Var}\left(\frac{\imath(K_n)}n\right)
=\frac{3(\log_2 3)^2}{16n}.
$$
<Chebyshev's inequality> therefore gives the finite-sample lower bound
$$
P(T_\varepsilon^{(n)})\geq
\max\left(0,1-\frac{3(\log_2 3)^2}{16n\varepsilon^2}\right).
$$
The bound is often loose, but it proves that every fixed positive tolerance eventually captures nearly all the <probability>. Direct summation of the <binomial distribution>'s <probability masses> gives $P(T_{0.1}^{(640)})\approx0.999779$. A finite sample does not need to have a nearly full <typical set>: the 40-symbol example above captures only about $0.639$.
\Image[/typical-set-concentration-and-size-bounds.png]
{title=Longer biased-coin messages concentrate in typical sets with controlled size}
{description=The left plot compares exact <typical set> probabilities with the lower bound from <Chebyshev's inequality>. The right shows $n^{-1}\log_2|T_{0.1}^{(n)}|$ and its finite-sample bounds. The tolerance stays fixed; the curve is not asserted to converge to exactly $H$. All points are exact finite-model calculations.}
Back to article page
