Lemma 3 (Hoeffding's inequality [1]}) 

Let \(X_{1}, \ldots , X_{n}\)  be independent random variables such that \(a \le X_{i} \le b\) . Let \(\bar{X} := \sum _{i=1}^m X_i / m\) , then for all \(t>0\) ,
\(\mathbb {P}\left(\left|\bar{X}-\mathbb {E}\left[\bar{X}\right]\right| \ge t\right) \le 2 \exp \left(-\frac{2 m t^{2}}{(b-a)^2}\right).\) 


Лемма 3 (неравенство Хеффдинга [1])



Пусть \(X_{1}, \ldots , X_{n}\) - независимые случайные величины, такие что \(a \le X_{i} \le b\). Пусть \(\bar{X} := \sum _{i=1}^m X_i / m\), тогда для всех \(t>0\),

\(\mathbb {P}\left(\left|\bar{X}-\mathbb {E}\left[\bar{X}\right]\right| \ge t\right) \le 2 \exp \left(-\frac{2 m t^{2}}{(b-a)^2}\right).\).