What is the concentration result of the entropy?

85 Views Asked by At

Let $X_1, X_2, \ldots, X_n$ be i.i.d. binary variables with $Pr(X_i=1)=p$ and $Pr(X_i=0)=1-p$. The famous result about $p$ is $$Pr\left(\left|\frac{1}{n}\sum_{i=1}^n X_i-p\right|>\epsilon\right)\le 2\exp(-2n\epsilon^2).$$

Is there any concentration result about the entropy? Something like an upper bound of $$Pr\left(\left|h\left(\frac{1}{n}\sum_{i=1}^n X_i\right)-h(p)\right|>\epsilon\right),$$ with $h(p)=-p\log p-(1-p)\log (1-p)$.

1

There are 1 best solutions below

0
On

\begin{align} P(h(\overline{X})-h(p)\geq \varepsilon)&\leq E[e^{-plog(\overline{X})-(1-p)log(1-\overline{X})}e^{plog(p)+(1-p)log(1-p)}]e^{-\varepsilon}\\ &=E[\frac{1}{\overline{X}^{p}(1-\overline{X})^{1-p}}]\frac{1}{p^{p}(1-p)^{1-p}}e^{-\varepsilon}\\ \end{align}

So now we have to compute

$$E[\frac{1}{(\sum X_{i})^{p}(n-\sum X_{i})^{1-p}}].$$

We will ignore the cases $X_{i}=1$ or 0 for all i, since then $h(\overline{X})=\infty$ and so the probability is one. So we restrict the integral to their complement and write it as f. So we have that

\begin{align} E[f(\sum X_{i})]=\sum_{1}^{n-1} \frac{1}{k^{p}(n-k)^{1-p}}\binom{n}{k}p^{k}(1-p)^{n-k}. \end{align}