Граница Чернова — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
   |definition = '''Граница Чернова''' (англ. ''Chernoff bound'') дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения.
 
   |definition = '''Граница Чернова''' (англ. ''Chernoff bound'') дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения.
 +
}}
 +
 +
==Некоторые вспомогательные определения и леммы==
 +
 +
{{Определение
 +
  |definition = '''Производящая функция моментов''' (англ. ''moment-generating function'') случайной величины <tex>X</tex> {{---}} функция из <tex>\mathbb R</tex> в <tex>\mathbb R</tex>, определяемая как: <br>
 +
<tex>M_x(t) =</tex> <tex>{E}(e^{tX})</tex>.
 +
}}
 +
 +
{{Определение
 +
  |definition = Распишем производящую функцию моментов по формуле Тейлора: <br>
 +
<tex>M_x(t) =</tex> <tex>{E}(e^{tX}) =</tex> <tex>{E}(1 + tX + \dfrac{1}{2}t^2 X^2 + \cdots + \dfrac{1}{n!}t^n X^n + \cdots =</tex> <tex>\sum\limits_{1}^{\infty} \dfrac{1}{i!} {E}(X^i)</tex> <br>
 +
Величина <tex>{E}(X^i)</tex> называется '''моментом''' (англ. ''moment'') случайной величины <tex>X</tex>.
 +
}}
 +
 +
{{Лемма
 +
|id=lemma1
 +
|statement= Если <tex>X = \sum_{i=1}^{n} X_i</tex>, где <tex>X_1 X_2 \cdots X_n</tex> {{---}} независимые случайные величины, то:<br>
 +
<tex>M_X(t) =</tex><tex> \prod\limits_{i=1}^{n} M_{X_i} (t)</tex>
 +
|proof= <tex>M_X(t) =</tex> <tex>{E}(e^{tX}) =</tex> <tex>{E}(e^{t \sum_{i=1}^{n} {X_i}}) = </tex> <tex>{E}( {\prod_{i=1}^{n} {e^{t X_i}}}) =</tex> <tex>\prod_{i=1}^{n} {{E}( {e^{t X_i}}}) =</tex> <tex> \prod\limits_{i=1}^{n} M_{X_i} (t)</tex>
 +
}}
 +
 +
{{Лемма
 +
|id=lemma2
 +
|statement= <tex>X</tex> {{---}} независимая случайная величина принимающая значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(X = 1) = p</tex>, <tex>{P}{(X = 0) = 1 - p}</tex>, тогда для любого <tex>t \in \mathbb{R}</tex>: <br>
 +
<tex>M_X(t) =</tex><tex>{E}e^{t X} \leqslant e^{p(e^t - 1)}</tex>
 +
|proof= <tex>M_X(t) =</tex> <tex>{E}e^{t X} = </tex> <tex>pe^t + (1 - p) \cdot 1 =</tex> <tex>1 + p(e^t - 1) \leqslant e^{p(e^t - 1)}</tex>
 
}}
 
}}
  
Строка 33: Строка 60:
 
<tex>{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}}</tex>
 
<tex>{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}}</tex>
  
[[Математическое ожидание случайной величины| Матожидание]] можно преобразовать:
+
[[Математическое ожидание случайной величины| Матожидание]] можно преобразовать по :
  
<tex>{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = \prod\limits_{i = 1}^{n}{E}(e^{t \bar{X_i}})</tex>
+
<tex>{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = </tex> <tex>{E}(\prod\limits_{i = 1}{n}{e^{\bar{X_i}}}) = </tex> <tex>\prod\limits_{i = 1}^{n}{E}(e^{t \bar{X_i}})</tex>
  
 
Оценим <tex>{E}(e^{t \bar{X_i}})</tex> с учётом того, что <tex>p \in [0, 1]</tex>
 
Оценим <tex>{E}(e^{t \bar{X_i}})</tex> с учётом того, что <tex>p \in [0, 1]</tex>
  
<tex>{E}(e^{t \bar{X_i}}) = p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}</tex>
+
<tex>{E}(e^{t \bar{X_i}}) = </tex> <tex>p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}</tex>
  
 
<tex>{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}}</tex>
 
<tex>{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}}</tex>
Строка 52: Строка 79:
  
 
== Относительная оценка ==
 
== Относительная оценка ==
 
{{Определение
 
  |definition = '''Производящая функция моментов''' (англ. ''moment-generating function'') случайной величины <tex>X</tex> {{---}} функция из <tex>\mathbb R</tex> в <tex>\mathbb R</tex>, определяемая как: <br>
 
<tex>M_x(t) =</tex> <tex>{E}(e^{tX})</tex>.
 
}}
 
 
{{Определение
 
  |definition = Распишем производящую функцию моментов по формуле Тейлора: <br>
 
<tex>M_x(t) =</tex> <tex>{E}(e^{tX}) =</tex> <tex>{E}(1 + tX + \dfrac{1}{2}t^2 X^2 + \cdots + \dfrac{1}{n!}t^n X^n + \cdots =</tex> <tex>\sum\limits_{1}^{\infty} \dfrac{1}{i!} {E}(X^i)</tex> <br>
 
Величина <tex>{E}(X^i)</tex> называется '''моментом''' (англ. ''moment'') случайной величины <tex>X</tex>.
 
}}
 
 
{{Лемма
 
|id=lemma1
 
|statement= <tex>X</tex>, <tex>Y</tex> {{---}} независимые случайные величины, тогда:<br>
 
<tex>{E}(e^{tX}e^{tY}) = {E}(e^{tX}){E}(e^{tY})</tex>
 
}}
 
 
{{Лемма
 
|id=lemma2
 
|statement= <tex>X</tex> {{---}} независимая случайная величина принимающая значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(X = 1) = p</tex>, <tex>{P}{(X = 0) = 1 - p}</tex>, тогда для любого <tex>t \in \mathbb{R}</tex>: <br>
 
<tex>{E}e^{t X} \leqslant e^{p(e^t - 1)}</tex>
 
}}
 
  
 
{{Теорема
 
{{Теорема
Строка 113: Строка 117:
 
Второе неравенство доказывается аналогично.  
 
Второе неравенство доказывается аналогично.  
 
}}
 
}}
 +
 +
==Пример==
 +
 +
Честную монету подбросили <tex>1000</tex> раз. Оценим вероятность того, что выпало больше <tex>550</tex> орлов с помощью [[Неравенство Маркова#Неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Относительная оценка | мультипликативной формы границы Чернова]]
 +
 +
Пусть <tex>X</tex> {{---}} сумма результатов бросков.
 +
 +
По неравенству Чебышева: <tex>P(|\dfrac{X}{1000} - \dfrac{1}{2}| \geqslant \dfrac{11}{10}) \leqslant \dfrac{121}{400}</tex>
 +
 +
Оценка границей Чернова: <tex>P(X \geqslant (1 + \dfrac{1}{10}) \cdot 500) \leqslant e^{-\dfrac{50}{21}} \approx \dfrac{1}{100}</tex>
 +
 +
Граница Чернова даёт намного более точную оценку.
  
 
== См. также ==
 
== См. также ==

Версия 18:35, 24 апреля 2019

Определение:
Граница Чернова (англ. 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]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_{1}^{\infty} \dfrac{1}{i!} {E}(X^i)[/math]

Величина [math]{E}(X^i)[/math] называется моментом (англ. moment) случайной величины [math]X[/math].


Лемма:
Если [math]X = \sum_{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_{i=1}^{n} {X_i}}) = [/math] [math]{E}( {\prod_{i=1}^{n} {e^{t X_i}}}) =[/math] [math]\prod_{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_{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}}}{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]1000[/math] раз. Оценим вероятность того, что выпало больше [math]550[/math] орлов с помощью неравенства Чебышева и мультипликативной формы границы Чернова

Пусть [math]X[/math] — сумма результатов бросков.

По неравенству Чебышева: [math]P(|\dfrac{X}{1000} - \dfrac{1}{2}| \geqslant \dfrac{11}{10}) \leqslant \dfrac{121}{400}[/math]

Оценка границей Чернова: [math]P(X \geqslant (1 + \dfrac{1}{10}) \cdot 500) \leqslant e^{-\dfrac{50}{21}} \approx \dfrac{1}{100}[/math]

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

См. также

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