Vrftjkry

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.