# Computing/sketching essential bit content of a binary source

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.

• 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$. – D.W. Nov 20 '18 at 2:54
• @D.W. you are absolutely correct, it should be $\mathcal{A}_X^N$. I edited the question accordingly. Apologies for the confusion. – Dahlai Nov 20 '18 at 10:30