Граница Чернова — различия между версиями
м |
|||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 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> <tex>{E}(1 + tX + \dfrac{1}{2}t^2 X^2 + \cdots + \dfrac{1}{n!}t^n X^n + \cdots) =</tex> <tex>\sum\limits_{i = 1}^{\infty} \dfrac{1}{i!} {E}(X^i)</tex> <br> | ||
+ | <tex>E(X^i)</tex> называется '''i-ым моментом''' (англ. ''i-th moment'') случайной величины <tex>X</tex> | ||
+ | }} | ||
+ | |||
+ | {{Лемма | ||
+ | |about= О производящей функции моментов суммы случайных величин | ||
+ | |id=lemma1 | ||
+ | |statement= Если <tex>X = \sum\limits_{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\limits_{i=1}^{n} {X_i}}) = </tex> <tex>{E}( {\prod\limits_{i=1}^{n} {e^{t X_i}}}) =</tex> <tex>\prod\limits_{i=1}^{n} {{E}( {e^{t X_i}}}) =</tex> <tex> \prod\limits_{i=1}^{n} M_{X_i} (t)</tex> | ||
+ | }} | ||
+ | |||
+ | {{Лемма | ||
+ | |about= Об ограниченности производящей функции моментов | ||
+ | |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: | Строка 57: | ||
<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: | Строка 76: | ||
== Относительная оценка == | == Относительная оценка == | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{Теорема | {{Теорема | ||
Строка 81: | Строка 82: | ||
| statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(X_i = 1) = p</tex>, <tex>{P}{(X_i = 0) = 1 - p}</tex> | | statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(X_i = 1) = p</tex>, <tex>{P}{(X_i = 0) = 1 - p}</tex> | ||
− | <tex>X = \ | + | <tex>X = \sum\limits_{i=1}^{n} X_i</tex> |
<tex>m = {E}X = np</tex> | <tex>m = {E}X = np</tex> | ||
Строка 91: | Строка 92: | ||
| proof = | | proof = | ||
По [[Неравенство Маркова| неравенству Маркова]]: | По [[Неравенство Маркова| неравенству Маркова]]: | ||
− | <tex>{P}(x \geqslant a) =</tex> <tex>{P}(e^x \geqslant e^a) \leqslant </tex> <tex>\dfrac{{E}(e^tX)}{e^a}</tex> | + | <tex>{P}(x \geqslant a) =</tex> <tex>{P}(e^x \geqslant e^a) \leqslant </tex> <tex>\dfrac{{E}(e^{tX})}{e^a}</tex> |
− | Воспользуемся [[#lemma1| | + | Воспользуемся [[#lemma1|леммой о производящей функции моментов суммы случайных величин ]] и [[#lemma2|леммой об ограниченности производящей функции моментов]]: |
− | <tex>\dfrac{{E}(e^tX)}{e^a} \leqslant</tex> <tex>\dfrac{\prod\ | + | <tex>\dfrac{{E}(e^{tX})}{e^a} \leqslant</tex> <tex>\dfrac{\prod\limits_{i = 1}^{n}e^{p(e^t - 1)}}{e^{a}} =</tex> <tex>\dfrac{e^{(e^t - 1)\sum\limits_{i = 1}^{n}p}}{e^{a}}</tex> |
− | Заметим, что <tex>\sum\ | + | Заметим, что <tex>\sum\limits_{i = 1}^{n} p = m</tex>, кроме того <tex>a = (1 + \delta)m</tex> (по замене). |
− | <tex>\dfrac{e^{(e^t - 1)\sum\ | + | <tex>\dfrac{e^{(e^t - 1)\sum\limits_{i = 1}^{n}p}}{e^{a}} = </tex> <tex>e^{m(e^t - 1 - t - t\delta)}</tex> |
Функция <tex>e^{m(e^t - 1 - t - t\delta)}</tex> принимает своё минимальное значение в точке <tex>t = \ln (1 + \delta)</tex> | Функция <tex>e^{m(e^t - 1 - t - t\delta)}</tex> принимает своё минимальное значение в точке <tex>t = \ln (1 + \delta)</tex> | ||
Строка 113: | Строка 114: | ||
Второе неравенство доказывается аналогично. | Второе неравенство доказывается аналогично. | ||
}} | }} | ||
+ | |||
+ | ==Пример== | ||
+ | |||
+ | Честную монету подбросили <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> | ||
+ | |||
+ | Граница Чернова даёт намного более точную оценку. | ||
== См. также == | == См. также == |
Версия 19:42, 24 апреля 2019
Определение: |
Граница Чернова (англ. Chernoff bound) дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения. |
Содержание
Производящая функция моментов
Определение: |
Производящая функция моментов (англ. moment-generating function) случайной величины
| — функция из в и определяется как:
Лемма (О производящей функции моментов суммы случайных величин): |
Если , где — независимые случайные величины, то: |
Доказательство: |
Лемма (Об ограниченности производящей функции моментов): |
Доказательство: |
Абсолютная оценка
Теорема (Граница Чернова (аддитивная форма)): |
Пусть даны — одинаково распределенные независимые случайные величины, принимающие значения из множества ,
, Тогда: |
Доказательство: |
Так как — одинаково распределенные и принимают значения из множества :
Преобразуем выражение . ( — любое положительное число):
Используем неравенство Маркова для оценки полученного выражения:
Матожидание можно преобразовать по :
Оценим с учётом того, что
При :Аналогично доказывается, что: Таким образом: |
Относительная оценка
Теорема (Граница Чернова (мультипликативная форма)): |
Пусть даны — независимые случайные величины, принимающие значения из множества , ,
Тогда: , для , для |
Доказательство: |
Воспользуемся леммой о производящей функции моментов суммы случайных величин и леммой об ограниченности производящей функции моментов:
Заметим, что , кроме того (по замене).
Функция принимает своё минимальное значение в точкеВоспользуемся неравенством ( ): , для оценки выражения :
Отсюда: Второе неравенство доказывается аналогично. , для |
Пример
Честную монету подбросили неравенства Чебышева и мультипликативной формы границы Чернова
раз. Оценим вероятность того, что выпало больше орлов с помощьюПусть
— сумма результатов бросков.По неравенству Чебышева:
Оценка границей Чернова:
Граница Чернова даёт намного более точную оценку.