Фундаментальная матрица

2019-06-26T02:37:23Z

188.170.75.252:

{{Определение
|definition=
'''Фундаментальной матрицей''' (англ. ''Fundamental matrix'') цепи Маркова называется матрица <tex> N = \sum\limits_{i=0}^{\infty} Q^n</tex>, где <tex>Q</tex> — '''матрица переходов между непоглощающими состояниями''', в которой отсутствуют строки с [[Марковская цепь#Поглощающая цепь | поглощающими состояниями]]
}}

{{Теорема
|statement=
<tex> N = (I - Q) ^ {-1} </tex>
|proof=
Домножим обе части равенства в определении на <tex> (I - Q) </tex>:

<tex> (I - Q)N = (I - Q)(I + Q + Q^2 + \ldots) = I - Q + Q - Q^2 + Q^2 - Q^3 + \ldots = I</tex>

Так как <tex> \lim\limits_{n \rightarrow \infty} Q ^ n = 0 </tex>, то ряд действительно сходится.
Далее, домножив на <tex> (I - Q) ^ {-1} </tex>, получим требуемое равенство.

Осталось лишь доказать, что матрица <tex> (I - Q) ^ {-1} </tex> существует, то есть <tex>(I - Q) </tex> — невырожденная. Рассмотрим систему линейных уравнений вида:

<tex> (I - Q) x = 0 </tex>

<tex> Ix = Qx </tex>

<tex> x = Qx </tex>

Домножив слева последнее равенство на матрицу <tex> Q </tex> слева, получим:

<tex> Qx = Q^2x </tex>

Но <tex> x = Qx </tex>, значит, <tex> x = Q^2x </tex>

Аналогично, <tex> x = Q^nx </tex> для сколь угодно большого n.

Так как <tex> \lim\limits_{n \rightarrow \infty} Q ^ n = 0 </tex>, то обязательно <tex> x = 0</tex>. Значит, по альтернативе Фредгольма, матрица <tex> (I - Q)</tex> — невырожденная.

}}
== Применение ==
Фундаментальная матрица задает средние времена, которые марковский процесс проводит в непоглощающих состояниях.

Так же фундаментальная матрица используется при [[Расчет вероятности поглощения в состоянии|расчете вероятности поглощения в состоянии]]

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex>, где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position[n]}</tex> — массив нумерации состояний относительно существенной/ несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица перехода из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix()
count_q = 0
count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См.также ==
* [[Марковская цепь]]
* [[Расчет вероятности поглощения в состоянии]]

== Источники информации ==
* ''Дж. Кемени, Дж. Снелл'' — "Конечные цепи Маркова", издание "Наука", 1970г., стр. 66
* [https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Fundamental_matrix Wikipedia — Absorbing Markov Chain, Fundamental matrix]

[[Категория:Дискретная математика и алгоритмы]]

[[Категория: Марковские цепи ]]

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

2019-06-26T01:56:31Z

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

{{Определение
|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>
}}

==Абсолютная оценка==
{{Теорема
| id = thChernov
| about = Граница Чернова (аддитивная форма)
| statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>,

<tex>m = {E} \sum\limits_{i=1}^{n} X_i</tex>,

Тогда:

<tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
| proof = Так как <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 = q}</tex>

<tex>{E} X_i = p</tex>

Пусть <tex>\bar{X_i} = X_i - p</tex>, тогда <tex>{E}\bar{X_i} = 0</tex>

Преобразуем выражение <tex>{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta)</tex>. (<tex>t</tex> {{---}} любое положительное число):

<tex>{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})</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}}) = </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 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>t = 4\delta</tex>:
<tex>\mathbb {P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant e^{-2 \delta^2 n}</tex>

Аналогично доказывается, что: <tex>{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \leqslant -\delta) \leqslant e^{-2 \delta^2 n}</tex>

Таким образом: <tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>
}}

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

{{Теорема
| id = thChernov
| about = Граница Чернова (мультипликативная форма)
| 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 = \sum\limits_{i=1}^{n} X_i</tex>

<tex>m = {E}X = np</tex>

Тогда:

<tex>{P} (X \geqslant (1 + \delta)m) \leqslant e^{- \frac{\delta^2}{2 + \delta}m }</tex>, для <tex>\delta > 0</tex>
<tex>{P} (X \leqslant (1 - \delta)m) \leqslant e^{- \frac{\delta^2}{2}m }</tex>, для <tex>0 < \delta < 1</tex>
| proof =
По [[Неравенство Маркова| неравенству Маркова]]:
<tex>{P}(x \geqslant a) =</tex> <tex>{P}(e^x \geqslant e^a) \leqslant </tex> <tex>\dfrac{{E}(e^{tX})}{e^a}</tex>

Воспользуемся [[#lemma1|леммой о производящей функции моментов суммы случайных величин ]] и [[#lemma2|леммой об ограниченности производящей функции моментов]]:

<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\limits_{i = 1}^{n} p = m</tex>, кроме того <tex>a = (1 + \delta)m</tex> (по замене).

<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>x > 0</tex>): <tex>\ln(1 + x) \geqslant \dfrac{x}{1 + x^2}</tex>, для оценки выражения <tex>m(\delta - (1 + \delta)\ln(1 + \delta))</tex>:

<tex>m(\delta - (1 + \delta)\ln(1 + \delta)) \leqslant</tex> <tex>- \dfrac{\delta^2}{2 + \delta}m</tex>

Отсюда:

<tex>{P} (X \geqslant (1 + \delta)m) \leqslant e^{- \frac{\delta^2}{2 + \delta}m }</tex>, для <tex>\delta > 0</tex>

Второе неравенство доказывается аналогично.
}}

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

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

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

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

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

==Применение==
Оценка границей Чернова используется в решении проблем уравновешивания множеств <ref>[https://en.wikipedia.org/wiki/Set_balancing Wikipedia {{---}} Set balancing]</ref> и маршрутизации пакетов в разреженных сетях.

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

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

== См. также ==
* [[Неравенство Маркова]]
* [[Математическое ожидание случайной величины]]

== Примечания ==
<references/>

== Источники информации ==
* [https://www.lektorium.tv/lecture/12871 Лекториум CS-центра {{---}} Лекция Дмитрия Ицыксона]
* [https://en.wikipedia.org/wiki/Chernoff_bound 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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]

Викиконспекты - Вклад участника [ru]

Фундаментальная матрица

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