4
$\begingroup$

In my class we were trying to derive Shannon's Source Theorem, first by proving the equivalent form in a weaker version.

The question is: Consider a biased coin with probability of heads $p \geq \frac{1}{2}$.We want to transfer this information with the code of minimum expected length.

To prove this, we can construct a code such that for any $\epsilon $, for large $n$, there exists a code such that average code length is less than $(1+\delta)nH(p) $ and also the lower limit of the code length is $(1-\delta)nH(p) $

We tried to prove it by first getting the inequalities $$ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} \leq 2^{nH(p)}$$ Both these inequalities are easy to derive. The problem comes with deriving the lower limit we try to prove that in an optimal code the length of the lower probability event is greater than equal to higher probability code, and then try to find the length of one of the events of higher probability an conclude by showing that since the lengths of events with lower probability is going to be more than this the expected length is more than $(1-\delta)nH(p) $

Hence, since $ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} $, one of the events containing $np $ heads will be of length greater than $log_{2}\frac{2^{nH(p)}}{n+1}$ . That is $ nH(p) -\log_{2}(n+1) $ . However to complete this part of the proof I need to prove the probability of all events with less than $np$ heads is a constant. Is it true for a binomial distribution that for an event with probability of success greater than $c$ where $c$ is some constant independent of $p$? By proving this we can prove that the expected length of the code is greater than $ c \times (nH(p) -\log_{2}(n+1)) $ which comes up to $(1-\delta)nH(p) $

$\endgroup$
  • $\begingroup$ Can you state what inequality you are stuck at? I can't follow your text. $\endgroup$ – Yuval Filmus Jan 11 '15 at 22:05
  • $\begingroup$ The last inequality to prove the lower bound. the proof will be done if we manage to prove that probability of all events with less than np heads is a constant or high . $\endgroup$ – Varun Jan 12 '15 at 8:59
  • $\begingroup$ Under what distribution exactly? Binomial with parameters $n$ and $p$? If so, are you familiar with the central limit theorem? $\endgroup$ – Yuval Filmus Jan 12 '15 at 16:33
  • $\begingroup$ Yes the distribution is a binomial with parameters n and p, i am aware of the Central Limit theorem however i am unable to link it with this problem. Could you help me with it. $\endgroup$ – Varun Jan 12 '15 at 17:25
  • $\begingroup$ the full proof is surely given in some ref somewhere, eg the original paper...? $\endgroup$ – vzn Jan 13 '15 at 2:07
2
$\begingroup$

For fixed $p$, the central limit theorem shows that $$ \begin{align*} \lim_{n\to\infty} \Pr[\mathrm{Bin}(n,p) \leq np] &= \lim_{n\to\infty} \Pr[\tfrac{1}{n}\mathrm{Bin}(n,p) \leq p] \\ &= \Pr[N(p,\tfrac{p(1-p)}{n}) \leq p] \\ &= \frac{1}{2}. \end{align*} $$ In this particular case you can get quantitative bounds in several ways, for example using the Berry–Esseen theorem or large deviation theorems such as the Chernoff bound.

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