Krdytkyu

We define the entropy function by
$$H(x)=xlnfrac{1}{x}+(1-x)lnfrac{1}{1-x} quad text{ for } 0 leq x leq 1 $$
where $H(0)=H(1)=0$.

a) For integers $0leq kleq n$ prove that
$$binom{n}{k} leq e^{ncdot H(x)} quad text{ for } x=frac{k}{n}. $$
$textit{Hint}$: use that $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$

b) For integers $0 leq k leq n$, prove that
$$binom{n}{k} geq frac{1}{n+1}e^{ncdot H(x)} quad text{ for } x=frac{k}{n}$$
$textit{Hint}$: use the hint for part a)

c) Let $X_1,X_2,...X_n$ be independent r.v. s.t. $$mathbf{P}(X_k=1)=frac{1}{2} text{ and } mathbf{P}(X_k=-1)=frac{1}{2} $$

Let $X=X_1+X_2+...+X_n$. Deduce from parts a) and b) that for any $0 leq alpha <1 $ $$lim_{n rightarrow infty}sqrt[n]{mathbf{P}(Xgeq alpha n)}=sqrt{frac{1}{(1-alpha)^{1-alpha}(1+alpha)^{1+alpha}}} $$

Attempt at a) we know $$ sum_{m=0}^nbinom{n}{m}x^m(1-x)^{n-m}=1 $$
$$begin{align} binom{n}{m}x^m(1-x)^{n-m} leq & ; 1 \ lnleft(binom{n}{m}right)+lnleft(x^mright)+lnleft((1-x)^{n-m}right)leq & ; 0 \ lnbinom{n}{m}leq &-(m)ln(x)-(n-m)ln(1-x) \ binom{n}{m} leq & ; e^{-mln(x)-(n-m)ln(1-x)}end{align}$$

Choosing $k=m$, and then letting $frac{k}{n}=x$:

$$begin{align} binom{n}{k} leq & ; e^{-kln(x)-(n-k)ln(1-x)} \ binom{n}{k} leq & ; e^{-nleft(frac{k}{n}ln(x)+(1-frac{k}{n})ln(1-x)right)} \ binom{n}{k} leq & ; e^{nleft(xln(frac{1}{x})+(1-x)ln(frac{1}{1-x})right)}\ binom{n}{k} leq & ; e^{nH(x)}end{align}$$

I start with part (a). From the suggestion one has:

${nchoose{k}}x^k(1-x)^{n-k}le 1, 0le x le 1$

and taking logarithms:

$ln{nchoose{k}}le -k ln(x)-(n-k)ln(1-x), 0le x le 1$

The right member dipends on $x$ and has a minimum and $x=k/n$. Plugging this value one has the first inequality.

I continue trying part (b). I write a separate answer because point (b) is much different than point (a) and the answer quite longer.

This solution is based on two lemmas. If $x_k=frac{k}{n}$

Lemma 1: $max_{0 le x le 1} x^{k}(1-x)^{n-k}=e^{-nH(x_k))}$. This should follow by simple calculus.

and:

Lemma 2: For every fixed $0 le k le n$, $argmax_{ 0 le m le n} {nchoose m} (x_k)^m(1-x_k)^{n-m}=k$ , i.e. the maximum is for $m=k$.

This should follow writing $m=k+a$ and verifying that the ratio between the quantity calculated for $a=0$ and $a$ different than zero is greater than one. This follows by writing the ratio and identifying it as a product of terms all greater than one.

Given Lemma 1 and Lemma2 we have the thesis. By the binomial theorem:

$sum_m {nchoose m} (x_k)^m(1-x_k)^{n-m} =1$

Therefore in particular the maximum addend, which is for $m=k$ by lemma 2, shall be greater than $frac{1}{n+1}$:

${nchoose m} (x_k)^m(1-x_k)^{n-m} ge frac{1}{n+1}$ [1]

By lemma 1:

${nchoose m}(x_k)^m(1-x_k)^{n-m} le {nchoose m}e^{-nH(x_k)}$ [2]

Comparing [1] and [2] we have the thesis.

I just outlined my procedure for proving the lammas but hopefully the are correct even if they require a bit of calculations!