Timeline for Why do typical sequences have probabilities $\sim2^{-nH(p)}$?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 9, 2021 at 15:23 | vote | accept | glS | ||
| Feb 5, 2020 at 12:00 | history | tweeted | twitter.com/StackStats/status/1225026397095239683 | ||
| Feb 5, 2020 at 10:53 | answer | added | glS | timeline score: 1 | |
| Feb 5, 2020 at 10:44 | comment | added | glS | @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. | |
| Feb 4, 2020 at 22:39 | comment | added | whuber♦ | Right--and that's why I suspect you might have misinterpreted whatever your source is. The simple algebraic fact remains that $2^{-nH} = p^{np}(1-p)^{n(1-p)},$ without any Binomial coefficient appearing, demonstrating that "$p_t\simeq2^{-nH(p)}$" is a poor approximation (to the point of being misleading). | |
| Feb 4, 2020 at 22:35 | comment | added | glS | @whuber I might just be missing something obvious here, apologies for that, but if I'm not mistaken, $\log\binom{n}{np}\simeq nH-1/2\log n$, thus I get $\log p_t\simeq -1/2\log n$, with the $nH$ term cancelling between the binomial factor and the other part of $p_t$. This is also consistent with gunes' answer | |
| Feb 4, 2020 at 22:26 | comment | added | whuber♦ | Evidently $2^{-nH}$ is just the $p^{np}(1-p)^{n(1-p)}$ part of $p_t.$ This leads one to suspect you might be misquoting some source: what exactly does the original source assert? Is $p_t$ perhaps the chance of one particular sequence rather than the set of all sequences with $np$ ones? | |
| Feb 4, 2020 at 22:03 | comment | added | glS | @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? | |
| Feb 4, 2020 at 21:39 | comment | added | whuber♦ | 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. | |
| Feb 4, 2020 at 21:31 | history | edited | gunes |
edited tags
|
|
| Feb 4, 2020 at 21:29 | answer | added | gunes | timeline score: 3 | |
| Feb 4, 2020 at 21:07 | comment | added | glS | @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? | |
| Feb 4, 2020 at 21:02 | comment | added | whuber♦ | Using Stirling (or any other method) you should conclude $\log p_t\to -\infty,$ not $0.$ | |
| Feb 4, 2020 at 20:17 | history | asked | glS | CC BY-SA 4.0 |