Вибірка якого розміру $n$ видає помилку не більше ніж $\epsilon$ з упевненістю щонайменше $1-\delta$?

Проби Бернулі: $X_1, X_2, \cdots, X_n = \begin{cases}1 & з\ імовірністю\ p,\\0 & з\ імовірністю\ q.\end{cases}$
Кількість успіхів: $S_n = X_1 + X_2 + \cdots + X_n \sim Binomial(n,p).$

Бажане співвідношення $\mbox{P}\{p-\epsilon\le\frac{S_n}{n}\le p+\epsilon\}\ge 1-\delta.$

Тобто якщо взяти $\epsilon = 0.03$ і $\delta = 0.05.$ То ми можемо озвучити це так: відносна частота успіхів $\frac{S_n}{n}$ буде в радіусі 3% від імовірності $p$, яка невідома нам, і це відбудеться в середньому в щонайменше 95% випадків.

Ми не можемо дати абсолютних гарантій щодо якоїсь конкретної вибірки. Усе, що ми можемо сказати, - якщо ми проводимо випадкові досліди, то певний відсоток від них, у нашому прикладі - 95%, матимуть якісні відповіді. Але якийсь окремий дослід може дати поганий результат, хоча й з малою на це ймовірністю.

Спростимо нашу формулу: $$\mbox{P}\{|\frac{S_n}{n}-p|\le \epsilon\}\ge 1-\delta$$ $$\mbox{P}\{|\frac{S_n}{n}-p|> \epsilon\}\le\delta$$ Тепер спробуймо дати відповідь на запитання: Якщо нам задані параметри $\epsilon$ і $\delta$, який розмір вибірки ми повинні обрати?

Як стартову точку ми використаємо формулу для дисперсії у випадку біноміального розподілу: $\Sigma_{k=0}^n(k-np)^2\cdot b_n(k;p) = npq$.

А ми хочемо оцінити:

$\mbox{P}\big\{|\frac{S_n}{n}-p| > \epsilon\big\}$	$= \mbox{P}\{|S_n-np|>n\epsilon\}$
	$=\Sigma_{k:|k-np|>n\epsilon}b_n(k;p)$
	і тут нам на допомогу приходить ідея російського математика Пафнутія Чебишова
	$=\Sigma_{k:|k-np|>n\epsilon}1\cdot b_n(k;p)$
	$\le\Sigma_{k:|k-np|>n\epsilon}\frac{(k-np)^2}{n^2\epsilon^2}\cdot b_n(k;p)$
	$= \frac{1}{n^2 \epsilon^2}\cdot npq = \frac{p(1-p)}{n \epsilon^2} \le \frac{1}{4n \epsilon^2}$
	тепер наш результат не залежить від $p$.

Неважливо наскільки маленьке $\epsilon$ ми оберемо, все одно ми зможемо вибрати настільки велике $n$, щоб імовірність помилки більше ніж $\epsilon$ була не більше ніж нам потрібно.

Хоча ми й могли б отримати точнішу верхню границю, важливість цього результату надзвичайно велика, тому що він дуже простий.