4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Using Stirling (or any other method) you should conclude $\log p_t\to -\infty,$ not $0.$ $\endgroup$ – whuber Feb 4 at 21:02
  • $\begingroup$ @whuber I thought $p_t\to 1$ and thus $\log p_t\to 0$, reflecting the probability of finding a typical sequence being close to one? $\endgroup$ – glS Feb 4 at 21:07
  • $\begingroup$ There are subtleties. "Typical sequences" in your sense grow vanishingly rare as $n$ increases: it's just too unusual for the numbers of ones and zeros to balance perfectly. If, however, you fix a tiny positive number $\epsilon$ (to represent a relative amount of imbalance) and define a "typical sequence" to be one whose proportion of ones lies between $p(1-\epsilon)$ and $p(1+\epsilon),$ then no matter how small $\epsilon$ may be, the chance of a typical sequence does indeed approach $1$ as $n$ grows large. $\endgroup$ – whuber Feb 4 at 21:39
  • $\begingroup$ @whuber that makes sense, and gunes' answer does indeed show why I was wrong in my statement that $p_t\sim 1$. Still, where does the $2^{-nH}$ come from then? Is this the actual leading behaviour of $p_t$, or is it a more or less arbitrary figure used to define the typical set? $\endgroup$ – glS Feb 4 at 22:03
  • 1
    $\begingroup$ @whuber I'm afraid I don't have any source to blame, only myself. I was conflating "probability of a sequence having length $np$", which is $p_t$, with "probability of sampling a sequence with length $np$", which is only the $p^{np}q^{nq}$ term. It is, of course, the latter that has to be used in the definition. Thanks for the help in clarifying my misconception. $\endgroup$ – glS Feb 5 at 10:44
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.