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

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).

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:

• I see, it is ambiguous since some literature represents ${m\choose k}$ with $C_m^k$ instead. To make it clearer, I have changed the question elaboration yet. May 28 at 15:57

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})$$.