Why do typical sequences have probabilities $\sim2^{-nH(p)}$?

Question

I've been reading a bit about typical sequences (in particular from these notes (pdf alert), pages 3 and 4). Let us focus on the case of binary sequences for simplicity. As far as I understand the idea is to consider those sequences that are typical in the sense that the number of $1$s and $0$s in the sequence equals its expected number.

If the probability of a letter being $1$ is $p$, the expected number of $1$s for sequences of $n$ letters with $n\to\infty$ is $np$, and the number of such sequences is approximately equal to $$\binom{n}{np}\simeq 2^{n H(p)},\quad H(p)=-p\log_2 p-(1-p)\log_2(1-p).$$ So far, so good. The probability of a sequence being typical, that is, having $np$ $1$s, must then be $$p_t=\binom{n}{np} p^{np}(1-p)^{n(1-p)}.$$ Using Stirling I get $\log p_t\simeq0$. I guess this makes sense, as it means that in the $n\to\infty$ limit the probability of getting a typical sequence is one, hence its logarithm vanishes.

But then, where does the $p_t\simeq2^{-nH(p)}$ figure come from? Is it obtained by using the next terms in Stirling's formula, or does this require some other kind of approximation?

Answer 1

Using the approximation given, i.e. $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$, we have $${n\choose np}=\frac{n!}{(np)! (n-np)!}\approx \frac{1}{\sqrt{2\pi p(1-p)n}p^{np} (1-p)^{n-np}}$$ Substituting into the expression for $p_t$, yields: $$\begin{align}p_t&\approx \frac{1}{\sqrt{2\pi p(1-p)n}}\end{align}$$

You can see that as $p_t\rightarrow 0$ as $n$ goes to $\infty$.

Answer 2

As discussed e.g. in this other answer, the typical sequences are defined as those with probability close to $2^{-nH}$. The probability of finding a specific sequence with "typical length" $np$ is $p^{np}(1-p)^{n(1-p)}$, which is easily seen equal $2^{-nH}$: $$p^{np}q^{nq}= 2^{np\log p+nq\log q}=2^{-nH}.$$ My problem was that I was conflating the "probability of a sequence with $np$ $1$s", which is what I called $p_t$, with the "probability of sampling a sequence with $np$ $1$s", which is instead $p^{np}q^{nq}=2^{-nH}$ (well, and also that I was wrongly estimating $p_t$, but that was not the core of the issue). Because we want to identify typical sequences by their probability of being sampled, we of course need to define them using the $2^{-nH}$ figure, not $p_t$.