An upper bound of the sum of factorial in Vapnik and Chervonenkis, 1971

Question

How to prove the following inequality: \begin{align*} \Gamma=\sum_{k\in[0,m]\wedge|\frac{2k}{l}-\frac{m}{l}|\ge\frac{\epsilon}{2}}\frac{{m\choose k}{2l-m\choose l-k}}{{2l\choose l}}\le2e^{-\frac{\epsilon^2 l}{8}},\epsilon\in[0,1],l\in\mathbb{N^+},m\in[0,2l] \end{align*}

My question arises from Page 271 proof omission in Vapnik, V. N.; Chervonenkis, A. Ya., On the uniform convergence of relative frequencies of events to their probabilities, Theor. Probab. Appl. 16, 264-280 (1971).

I appreciate it in advance!

Answer 1

Too long for a Comment:

You have the top and bottom variables flipped on the binomial coefficient in the quoted text; on the link I found it looks like this, which makes more sense:

Answer 2

To solve this inequality, we can use Hoeffding's inequality: $$ \mathbb{P} (|S_n - \mathrm{E} [S_n] | \geq t) \leq 2\exp (-\frac{2t^2}{\sum_{i=1}^n(b_i - a_i)^2}) $$

$X=2k\in[0,2m]$ can be interpreted as the sum of $2m$ independent and identically distributed Bernoulli random variables with $p = 0.5$.

$\Gamma$ can be seen as a sum over all outcomes where $X$ deviates from its expected value $\mathbb{E}(X)=m$ by more than $\frac{εl}{2}$. Applying Hoeffding's inequality and the constraint $m\le2l$, we have:

\begin{align*} \mathbb{P}(|X - m| \ge \frac{εl}{2})&\le2exp(-\frac{2(\frac{εl}{2})^2}{\sum_{i=1}^m(1-0)^2})\\ &=2exp(-\frac{ε^2l^2}{2m})\le2exp(-\frac{ε^2l^2}{4l})\\ &=2exp(-\frac{ε^2l}{4})\le2exp(-\frac{ε^2l}{8}) \end{align*}

Note that the inequality still holds if we replace the RHS with $2exp(-\frac{ε^2l}{4})$.