Граница Чернова

Определение:

Граница Чернова (англ. Chernoff bound) дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения.

Производящая функция моментов

Определение:

Производящая функция моментов (англ. moment-generating function) случайной величины [math]X[/math] — функция из [math]\mathbb R[/math] в [math]\mathbb R[/math] и определяется как: [math]M_x(t) =[/math] [math]{E}(e^{tX}) =[/math] [math]{E}(1 + tX + \dfrac{1}{2}t^2 X^2 + \cdots + \dfrac{1}{n!}t^n X^n + \cdots) =[/math] [math]\sum\limits_{i = 1}^{\infty} \dfrac{1}{i!} {E}(X^i)[/math] [math]E(X^i)[/math] называется i-ым моментом (англ. i-th moment) случайной величины [math]X[/math]

Лемма (О производящей функции моментов суммы случайных величин):

Если [math]X = \sum\limits_{i=1}^{n} X_i[/math], где [math]X_1 X_2 \cdots X_n[/math] — независимые случайные величины, то: [math]M_X(t) =[/math][math] \prod\limits_{i=1}^{n} M_{X_i} (t)[/math]

Доказательство:

[math]\triangleright[/math]

[math]M_X(t) =[/math] [math]{E}(e^{tX}) =[/math] [math]{E}(e^{t \sum\limits_{i=1}^{n} {X_i}}) = [/math] [math]{E}( {\prod\limits_{i=1}^{n} {e^{t X_i}}}) =[/math] [math]\prod\limits_{i=1}^{n} {{E}( {e^{t X_i}}}) =[/math] [math] \prod\limits_{i=1}^{n} M_{X_i} (t)[/math]

[math]\triangleleft[/math]

Лемма (Об ограниченности производящей функции моментов):

[math]X[/math] — независимая случайная величина принимающая значения из множества [math]\{0, 1\}[/math], [math]{P}(X = 1) = p[/math], [math]{P}{(X = 0) = 1 - p}[/math], тогда для любого [math]t \in \mathbb{R}[/math]: [math]M_X(t) =[/math][math]{E}e^{t X} \leqslant e^{p(e^t - 1)}[/math]

Доказательство:

[math]\triangleright[/math]

[math]M_X(t) =[/math] [math]{E}e^{t X} = [/math] [math]pe^t + (1 - p) \cdot 1 =[/math] [math]1 + p(e^t - 1) \leqslant e^{p(e^t - 1)}[/math]

[math]\triangleleft[/math]

Абсолютная оценка

Теорема (Граница Чернова (аддитивная форма)):

Пусть даны [math]X_1 X_2 \ldots X_n[/math] — одинаково распределенные независимые случайные величины, принимающие значения из множества [math]\{0, 1\}[/math], [math]m = {E} \sum\limits_{i=1}^{n} X_i[/math], Тогда: [math]{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}[/math]

Доказательство:

[math]\triangleright[/math]

Так как [math]X_1 X_2 \ldots X_n[/math] — одинаково распределенные и принимают значения из множества [math]\{0, 1\}[/math]: [math]{P}(X_i = 1) = p[/math] [math]{P}{(X_i = 0) = 1 - p = q}[/math] [math]{E} X_i = p[/math] Пусть [math]\bar{X_i} = X_i - p[/math], тогда [math]{E}\bar{X_i} = 0[/math] Преобразуем выражение [math]{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta)[/math]. ([math]t[/math] — любое положительное число): [math]{P}(\dfrac{1}{n}\sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta) = {P} (\dfrac{1}{n}\sum\limits_{i=1}^{n}\bar{X_i} \geqslant \delta) = {P}(e^{t\sum\limits_{i=1}^{n} \bar{X_i}} \geqslant e^{t \delta n})[/math] Используем неравенство Маркова для оценки полученного выражения: [math]{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}})}{e^{t \delta n}}[/math] Матожидание можно преобразовать по : [math]{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = [/math] [math]{E}(\prod\limits_{i = 1}^{n}{e^{\bar{X_i}}}) = [/math] [math]\prod\limits_{i = 1}^{n}{E}(e^{t \bar{X_i}})[/math] Оценим [math]{E}(e^{t \bar{X_i}})[/math] с учётом того, что [math]p \in [0, 1][/math] [math]{E}(e^{t \bar{X_i}}) = [/math] [math]p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}[/math] [math]{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{e^{n\frac{t^2}{8}}}{e^{t \delta n}}[/math] При [math]t = 4\delta[/math]: [math]\mathbb {P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant e^{-2 \delta^2 n}[/math] Аналогично доказывается, что: [math]{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \leqslant -\delta) \leqslant e^{-2 \delta^2 n}[/math] Таким образом: [math]{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}[/math]

[math]\triangleleft[/math]

Относительная оценка

Теорема (Граница Чернова (мультипликативная форма)):

Пусть даны [math]X_1 X_2 \ldots X_n[/math] — независимые случайные величины, принимающие значения из множества [math]\{0, 1\}[/math], [math]{P}(X_i = 1) = p[/math], [math]{P}{(X_i = 0) = 1 - p}[/math] [math]X = \sum\limits_{i=1}^{n} X_i[/math] [math]m = {E}X = np[/math] Тогда: [math]{P} (X \geqslant (1 + \delta)m) \leqslant e^{- \frac{\delta^2}{2 + \delta}m }[/math], для [math]\delta \gt 0[/math] [math]{P} (X \leqslant (1 - \delta)m) \leqslant e^{- \frac{\delta^2}{2}m }[/math], для [math]0 \lt \delta \lt 1[/math]

Доказательство:

[math]\triangleright[/math]

По неравенству Маркова: [math]{P}(x \geqslant a) =[/math] [math]{P}(e^x \geqslant e^a) \leqslant [/math] [math]\dfrac{{E}(e^{tX})}{e^a}[/math] Воспользуемся леммой о производящей функции моментов суммы случайных величин и леммой об ограниченности производящей функции моментов: [math]\dfrac{{E}(e^{tX})}{e^a} \leqslant[/math] [math]\dfrac{\prod\limits_{i = 1}^{n}e^{p(e^t - 1)}}{e^{a}} =[/math] [math]\dfrac{e^{(e^t - 1)\sum\limits_{i = 1}^{n}p}}{e^{a}}[/math] Заметим, что [math]\sum\limits_{i = 1}^{n} p = m[/math], кроме того [math]a = (1 + \delta)m[/math] (по замене). [math]\dfrac{e^{(e^t - 1)\sum\limits_{i = 1}^{n}p}}{e^{a}} = [/math] [math]e^{m(e^t - 1 - t - t\delta)}[/math] Функция [math]e^{m(e^t - 1 - t - t\delta)}[/math] принимает своё минимальное значение в точке [math]t = \ln (1 + \delta)[/math] Воспользуемся неравенством ([math]x \gt 0[/math]): [math]\ln(1 + x) \geqslant \dfrac{x}{1 + x^2}[/math], для оценки выражения [math]m(\delta - (1 + \delta)\ln(1 + \delta))[/math]: [math]m(\delta - (1 + \delta)\ln(1 + \delta)) \leqslant[/math] [math]- \dfrac{\delta^2}{2 + \delta}m[/math] Отсюда: [math]{P} (X \geqslant (1 + \delta)m) \leqslant e^{- \frac{\delta^2}{2 + \delta}m }[/math], для [math]\delta \gt 0[/math] Второе неравенство доказывается аналогично.

[math]\triangleleft[/math]

Сравнение с оценкой неравенством Чебышева

Граница Чернова даёт намного более точную оценку, чем неравенство Чебышева.

Пусть честную монету подбросили [math]N[/math] раз. Оценим вероятность того, что сумма бросков [math]S[/math] отклонилась от матожидания больше, чем на [math]\delta = \sqrt{\dfrac{\ln N}{N}}[/math] с помощью неравенства Чебышева и аддитивной формы границы Чернова

По неравенству Чебышева: [math]P(|\dfrac{S}{N} - \dfrac{1}{2}| \geqslant \delta) \leqslant \dfrac{1}{4N\delta^2} = \dfrac{1}{4\ln N}[/math]

Оценка границей Чернова: [math]P(|\dfrac{S}{N} - \dfrac{1}{2}| \geqslant \delta) \leqslant 2e^{-2N\delta^2} = \dfrac{2}{N^2}[/math]

Применение

Оценка границей Чернова используется в решении проблем уравновешивания множеств и маршрутизации пакетов в разреженных сетях.

Задача уравновешивания двух множеств возникает при планировании статистических экспериментов. Обычно при планировании эксперимента известны свойства каждого участника, задача состоит в том, чтобы разделить участников на две группы: контрольную и тестовую, так, чтобы каждое свойство было как можно более сбалансированно между двумя группами.

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

См. также

• Неравенство Маркова
• Математическое ожидание случайной величины

Источники информации

• Лекториум CS-центра — Лекция Дмитрия Ицыксона
• Wikipedia — Chernoff bound
• Michael Mitzenmacher, Eli Upfal. «Probability and Computing: Randomized Algorithms and Probabilistic Analysis» — «Cambridge University Press», 2005 г. — 61-83 стр. — ISBN 0-521-83540-2
• M. Kearns, U. Vazirani. «An Introduction to Computational Learning Theory» — «MIT Press», 1994 г. — 190-192 стр. — ISBN 0-262-11193-4