Strict Bernstein Inequality

Question

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

a) For integers $0\leq k\leq n$ prove that $$\binom{n}{k} \leq e^{n\cdot H(x)} \quad \text{ for } x=\frac{k}{n}. $$ $\textit{Hint}$: use that $$ \sum_{m=0}^n\binom{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^{n\cdot 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}(X\geq \alpha n)}=\sqrt{\frac{1}{(1-\alpha)^{1-\alpha}(1+\alpha)^{1+\alpha}}} $$

Attempt at a) we know $$ \sum_{m=0}^n\binom{n}{m}x^m(1-x)^{n-m}=1 $$ $$\begin{align} \binom{n}{m}x^m(1-x)^{n-m} \leq & \; 1 \\ \ln\left(\binom{n}{m}\right)+\ln\left(x^m\right)+\ln\left((1-x)^{n-m}\right)\leq & \; 0 \\ \ln\binom{n}{m}\leq &-(m)\ln(x)-(n-m)\ln(1-x) \\ \binom{n}{m} \leq & \; e^{-m\ln(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^{-k\ln(x)-(n-k)\ln(1-x)} \\ \binom{n}{k} \leq & \; e^{-n\left(\frac{k}{n}\ln(x)+(1-\frac{k}{n})\ln(1-x)\right)} \\ \binom{n}{k} \leq & \; e^{n\left(x\ln(\frac{1}{x})+(1-x)\ln(\frac{1}{1-x})\right)}\\ \binom{n}{k} \leq & \; e^{nH(x)}\end{align}$$

Answer 1

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

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

and taking logarithms:

$ln{n\choose{k}}\le -k ln(x)-(n-k)ln(1-x), 0\le 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.

Answer 2

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 follows by simple calculus. The derivative is positive for $x \in [0,x_k]$, it vanishes at $x_k$ and than is negative for $x \in [x_k,1]$. Evaluating at $x_k$ provides the value of the maximum.

and:

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

Proof: let $0 \le a \le n-k$. Then:

$\frac{B^n_k(k)}{B^n_k(k+a)}={n\choose k} (\frac{k}{n})^k(1- \frac{k}{n})^{n-k} / {n\choose k+a} (\frac{k}{n})^{k+a}(1- \frac{k}{n})^{n-k-a}$ $=\frac{(k+1)...(k+a)}{k^a}\frac{(n-k)^a}{(n-k-a+1)...(n-k-a+a)}\ge1 $

An analogous calculation can be performed choosing $0\le b \le k$ and investigating the ratio $\frac{B^n_k(k)}{B^n_k(k-b)}$, thus the conclutson.

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

$\sum_m {n\choose m} (x_k)^m(1-x_k)^{n-m} = \sum_m B^n_k(m)=1$

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

$B^n_k(k)={n\choose k} (x_k)^k(1-x_k)^{n-k} \ge \frac{1}{n+1}$ [1]

By lemma 1:

${n\choose k}(x_k)^k(1-x_k)^{n-k} \le {n\choose k}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!