2
$\begingroup$

I'm given the Bernoulli distribution of a biased coin toss with probability distribution $P_X = \{0.2, 0.8\}$ over the alphabet $\mathcal{A}_X=\{0,1\}$.

I want to sketch the normalized essential bit content $\frac1N H_\delta(X^N)$ as a function of $\delta$ for $N=1000$, where:

  • $X^N = \{X_1, X_2,\dots,X_N\}$ is the outcome of $N$ independent repetitions of tossing the coin
  • $H_\delta(X^N)=\log_2 |S_\delta|$, with $S_\delta$ being the smallest $\delta$-sufficient subset of $\mathcal{A}_X^N$
  • the $\delta$-sufficient subset is chosen such that $P(x\in S_\delta)\geq 1-\delta$

To be able to sketch the function I have to compute $H_\delta(X^N)$ for different values of $|S_\delta|$. So I computed the mean $\mu$ and standard deviation $\sigma$ of $X^N$ and approximated the binomial distribution with a standard normal distribution to find the number of elements in $S_\delta$ ($s$ is the number of $0$'s):

$$P(-\alpha \leq \frac{s-\mu}{\sigma} \leq \alpha)\geq1-\delta$$

To find the the critical value $\alpha$, I rewrote the equation as follows to find $\alpha$:

$$P(\frac{s-\mu}{\sigma} \leq \alpha)\geq1-\frac{\delta}{2}$$ After determining $\alpha$ for a fixed $\delta$, $|S_\delta| = \sigma\cdot\alpha\cdot2$.

When plotting this for different values of $\delta$ I get the correct "flipped" sigmoidal shape. However, the values for $\frac{1}{N}H_\delta$ are about $150$ times too small compared to the solution.

It seems like I'm missing something. Can someone point out where my calculation is wrong?

Disclaimer: I'm working through David MacKay's book (Information Theory, Inference, and Learning Algorithms) by myself, I'm not asking for help with solving course homework. The exercise in question is 4.15.

$\endgroup$
  • $\begingroup$ Any chance you could edit the question to give us a self-contained definition of what it means for a set to be a "$\delta$-sufficient subset of $\mathcal{A}_X$"? And are you sure you have the definition of $H_\delta(X^N)$ right? I would have expected that definition to mention $\mathcal{A}_X^N$ instead of $\mathcal{A}_X$. $\endgroup$ – D.W. Nov 20 '18 at 2:54
  • $\begingroup$ @D.W. you are absolutely correct, it should be $\mathcal{A}_X^N$. I edited the question accordingly. Apologies for the confusion. $\endgroup$ – Dahlai Nov 20 '18 at 10:30

Your Answer

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

Browse other questions tagged or ask your own question.