Участник:Mk17.ru — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «__TOC__ == Определение == {{Определение |definition = '''Случайное блуждание''' (англ. ''Random walk'') {{---}} ма…»)
 
 
(не показаны 53 промежуточные версии 9 участников)
Строка 3: Строка 3:
  
 
{{Определение
 
{{Определение
|definition = '''Случайное блуждание''' (англ. ''Random walk'') {{---}} математическая модель процесса случайных изменений — шагов в дискретные моменты времени. При этом предполагается, что изменение на каждом шаге не зависит от предыдущих и от времени. В силу простоты анализа эта модель часто используется в разных сферах в математике, экономике, физике, но, как правило, такая модель является существенным упрощением реального процесса.
+
|definition = '''Случайное блуждание''' (англ. ''Random walk'') {{---}} математическая модель процесса случайных изменений — шагов в дискретные моменты времени, предполагается, что изменение на каждом шаге не зависит от предыдущих и от времени. В силу простоты анализа эта модель часто используется в разных сферах в математике, экономике, физике, но, как правило, такая модель является существенным упрощением реального процесса.  
 
}}
 
}}
  
== Двумерный случай случайных блужданий ==
+
== Случайные блуждания по прямой ==
  
''''''
+
Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки
 +
в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку <tex>k + 1</tex> и с положительной вероятностью <tex>q = 1 − p</tex>
 +
перемещается в точку <tex>k − 1</tex>.
 +
Физической системе соответствует [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%86%D0%B5%D0%BF%D1%8C цепь Маркова]:
  
*<tex>\xi_n = \xi_{n-1} + \eta_n = \xi_0 + S_n, \eta_n = </tex> определена и непрерывна для всех таких наборов <tex>p_i\in[0,\;1]</tex>, что <tex> \sum\limits_{i = 1}^{n} p_i  = 1</tex>  
+
*<tex>\xi_n = \xi_{n-1} + \eta_n = \xi_0 + S_n, \eta_n = \begin{cases} 1 &\text{с вероятностью p}\\-1 &\text{с вероятностью 1 - p}
 +
\end{cases}</tex>  
 +
Заметим, что вернуться в какую-либо точку можно только за четное число шагов.
  
* <tex dpi ="130">H(\underbrace{\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}}_\text{n}) < H(\underbrace{\dfrac{1}{n+1}, \dfrac{1}{n+1}, \dots, \dfrac{1}{n+1}}_\text{n+1})</tex>
+
==Вероятность смещения на d единиц вправо (влево)==
  
* <tex dpi ="130"> H(p_{1}q_{11}, p_{1}q_{12}, \dots, p_{n}q_{nk_n}) = H(p_1, p_2, \dots, p_n) + \sum\limits_{i=1}^{n} p_iH(q_{i1}, \dots, q_{ik_i})</tex>
+
Будем считать, что <tex>P(\xi_0 = m) = 1</tex>. Это соответствует тому, что в начальный момент времени частица находилась в точке
<tex>\rhd</tex>
+
<tex>x = m</tex> (здесь <tex>m</tex> — фиксированное число) и затем начала случайно блуждать в соответствии с описанными выше правилами. Пусть <tex>d</tex> — смещение частицы за <tex>n</tex> шагов.
 +
Найдём <tex>P(\xi_n = m + d)</tex> для каждого <tex>d ∈ Z</tex>.
  
Рассмотрим схему <tex>\mathcal{P}_m</tex> c <tex>m</tex> исходами и вероятностями <tex>\{p_1, p_2, \dots, p_m\}</tex> и схему <tex>\mathcal{R}_k</tex> с <tex>k</tex> исходами и вероятностями <tex>\{q_1, q_2, \dots, q_k\}</tex>.
+
Справедливо равенство: 
 +
*<tex>P(\xi_n = m + d) = P(\xi_n = m + d | \xi_0 = m)</tex>, если <tex>P(\xi_0 = m) = 1.</tex>
  
Образуем комбинированную схему c <tex>m + k - 1</tex> исходами следующим образом:
+
Представление через условную вероятность удобно, если нам необходимо явно указать, где находилась частица в начальный момент времени.
  
Выбирается случайным образом один из исходов схемы <tex>\mathcal{P}_m</tex>, и если произошел <tex>m</tex>-й исход, выбирается случайно один из исходов схемы <tex>\mathcal{R}_k</tex>, а остальные <tex>m - 1</tex> исходов схемы <tex>\mathcal{P}_m</tex> считаются окончательными.
+
Наша физическая модель с математической точки зрения в точности отвечает
 +
схеме [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D0%91%D0%B5%D1%80%D0%BD%D1%83%D0%BB%D0%BB%D0%B8#:~:text=%D0%A1%D1%85%D0%B5%D0%BC%D0%BE%D0%B9%20%D0%91%D0%B5%D1%80%D0%BD%D1%83%D0%BB%D0%BB%D0%B8%20(%D0%B0%D0%BD%D0%B3%D0%BB.,%2C%20%D0%B0%20%D0%BD%D0%B5%D1%83%D0%B4%D0%B0%D1%87%D0%B0%20%E2%80%94%20%D1%81%20%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E%20 независимых испытаний Бернулли] с двумя исходами —- движением вправо, который мы будем называть успехом, и движением вправо (неудачей). Пусть частица сделала <tex>n</tex> прыжков. Вероятность того, что среди
 +
этих прыжков будет ровно <tex>k</tex> прыжков вправо (или, что то же самое, <tex>n−k</tex> прыжков
 +
влево) задаётся формулой:
  
В этой комбинированной схеме <tex>\mathcal{PR}</tex> мы получаем исходы <tex>1, 2, \dots, m - 1, (m, 1), (m, 2), \dots, (m, k)</tex> с вероятностями <tex>p_1, p_2, \dots, p_{m-1}, p_mq_1, p_mq_2, \dots, p_mq_k</tex>
+
*<tex>P = {C_{n}^k} p^k q^{n−k}, \quad k = 0, 1, . . . , n </tex>  
  
Легко видеть, что <tex>H(\mathcal{PR}) = H(\mathcal{P}_m) + p_mH(\mathcal{R}_k)</tex>.
+
Смещение частицы и число прыжков влево и вправо связаны уравнением
 +
*<tex>d = 1 · k + (−1) · (n − k) = 2k − n \quad</tex>
 +
 
 +
откуда <tex>k = \frac{(n + d)}{2}</tex>. Понятно, что, поскольку частица сделала ровно <tex>n</tex> прыжков,
 +
число прыжков вправо должно быть целым числом в интервале <tex>[0, n]</tex>, другими словами, <tex>P(\xi_n = m + d) = 0,</tex> если <tex>k = \frac{(n + d)}{2}, k \notin \{0, 1, . . . , n\}</tex>. Если же указанное
 +
ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли <tex>P = {C_{n}^k} p^k q^{n−k}</tex>:
 +
 
 +
*<tex> P(\xi_n = m + d) = {C_{n}^k} p^k q^{n−k}, \quad k = \frac{(n + d)}{2} </tex>, при обязательном условии <tex>k ∈ {0, 1, . . . , n}.</tex>
 +
 
 +
 
 +
'''Замечания'''.
 
   
 
   
Потребуем выполнения этого свойства для любой меры неопределенности.
+
<tex>1)</tex> Ограничение <tex>0 \leq k \leq n </tex> по формуле <tex>d = 1 · k + (−1) · (n − k) = 2k − n</tex> влечёт <tex>|d| \leq n</tex>. Это можно понять и без расчётов: если <tex>|d| > n</tex>, то частица не успевает дойти из начальной в конечную точку за <tex>n</tex> шагов.
<tex>\lhd</tex>
+
 
 +
<tex>2)</tex> При своём движении частица случайным образом выбирает одну из возможных траекторий. Для перехода из точки
 +
<tex>m</tex> в точку <tex>m</tex> за <tex>n</tex> шагов возможными являются все те и только те траектории длины
 +
<tex>n</tex>, в которых ровно <tex>k</tex> смещений вправо и <tex>n − k</tex> смещений влево, где <tex>k = \frac{(n +
 +
d)}{2}</tex>. Равенство <tex>P = {C_{n}^k} p^k q^{n−k}</tex> при этом можно интерпретировать так: вероятность того, что частица пройдет по одной из
 +
возможных траекторий, равна  <tex>p^k q^{n−k}</tex>, и всего существуют <tex>{C_{n}^k}</tex> таких траекторий, таким
 +
образом,
 +
*<tex>P = p^k \cdot q^{n−k}+...+p^k \cdot q^{n−k}={C_{n}^k} p^k q^{n−k}.</tex>
 +
 
 +
== Случайные блуждания по прямой ==
 +
 
 +
Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки
 +
в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку <tex>k + 1</tex> и с положительной вероятностью <tex>q = 1 − p</tex>
 +
перемещается в точку <tex>k − 1</tex>.
 +
Физической системе соответствует [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%86%D0%B5%D0%BF%D1%8C цепь Маркова]:
 +
 
 +
*<tex>\xi_n = \xi_{n-1} + \eta_n = \xi_0 + S_n, \eta_n = \begin{cases} 1 &\text{с вероятностью p}\\-1 &\text{с вероятностью 1 - p}
 +
\end{cases}</tex>
 +
Заметим, что вернуться в какую-либо точку можно только за четное число шагов.
 +
 
 +
== Задача о разорении игрока ==
 +
Пусть начальный капитал <tex>\xi_0</tex> первого
 +
игрока составляет <tex>k</tex> рублей, а капитал второго игрока <tex> – (n − k)</tex> рублей. Первый игрок выигрывает
 +
или проигрывает рубль с вероятностями <tex>p</tex> и <tex>q</tex> соответственно. Игра продолжается до тех пор, пока
 +
капитал первого игрока не уменьшится до нуля, либо не возрастет до <tex>n</tex>. Поглощение точки в правом
 +
конце отрезка <tex>[0, n]</tex> соответствует выигрышу первого игрока.
 +
 
 +
Рассмотрим конечную цепь Маркова:
 +
 
 +
<tex>\quad\xi_{t+1} = \xi_t + \eta_t,\quad P\{\eta_t = 1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = p,\quad P\{\eta_t = −1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = q</tex> и
 +
 
 +
<tex>\quad P\{\eta = 0|\xi_t = 0 ∨ \xi_t = n\} = 1. </tex> <tex>(2.1)</tex>
 +
 
 +
Вероятность выигрыша для первого игрока в момент времени <tex>t</tex> есть <tex>p_{kn}(t) = P\{\eta_t = n|\eta_0 = k\}</tex>
 +
 
 +
По формуле полной вероятности:
 +
 
 +
*<tex> \quad P\{\xi_{t+1} = n\} = P\{\xi_1 = k + 1|\xi_0 = k\}P\{\xi_{t+1} = n|\xi_{1} = k + 1\}
 +
+ P\{\xi_{1} = k − 1|\xi_0 = k\}P\{\xi_{t+1} = n|\xi_{1} = k - 1\} </tex>
  
==Вычисление энтропии==
+
или
  
Для доказательства формулы вычисления энтропии сначала докажем лемму.
+
*<tex> \quad p_{kn}(t + 1) = p \cdot p_{k+1,n}(t) + q \cdot p_{k−1,n}(t), \quad k = 1, 2, . . . , n 1.</tex>
{{Лемма
 
|statement = <tex dpi="140">g(n) = H(\dfrac{1}{n}, \dfrac{1}{n}, \dots, \dfrac{1}{n}) = -k \log_2 \dfrac{1}{n} = k \log_2n</tex>
 
|proof =
 
Будем рассматривать для <tex>k=1</tex> (бит).
 
  
Рассмотрим функцию <tex>g(mn)</tex>:
+
Теорему о предельных вероятностях применить не можем, но заметим, что:
: <tex>g(mn)=g(m)+ \sum\limits_{i=1}^{m} \dfrac{1}{m} g(n) = g(m)+g(n)</tex>
 
  
Пусть: <tex>g(2)=1 \quad</tex>, тогда <tex>g(2^t)=t</tex> и <tex> \quad g(n^t)=t \cdot g(n)</tex>
+
<tex> \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 = n\} ⊂ · · · ⊂ \{\xi_t = n\} ⊂ . . . </tex>  
  
Рассмотрим такое <tex> i </tex>, что <tex>2^i \leqslant  n^t < 2^{i+1}</tex>
+
Положим <tex>A =\cup_{t=1}^∞\{\xi_t = n\}</tex>. Тогда
  
Можно заметить, что если <tex> i=[ \log_2 n^t ] </tex>, то неравенство останется верным.
+
<tex> \quad \quad p_{kn} = P(A) = \lim_{t\to\infty}P\{\xi_t = n|\xi_0 = k\} = \lim_{t\to\infty}p_{kn}(t).</tex>
  
По предыдущим рассуждениям получаем, что:
+
Переходя к пределу в <tex>(2.1)</tex> при <tex>t → ∞</tex>, получим
:<tex>g(2^i) \leqslant g(n^t) < g(2^{i+1})</tex>
 
  
: <tex> i \leqslant t \cdot g(n) <i+1 \quad \quad </tex>
+
<tex>\quad \quad p_{kn} = p \cdot p_{k+1,n} + q \cdot p_{k−1,n}</tex>
  
Делим неравенство на <tex>t</tex>:
+
Так как <tex>p_{kn}</tex> вероятность выигрыша для первого игрока, то <tex>p_{0n} = 0, p_{nn} = 1</tex>. Рассматриваемая как функция от <tex>k</tex>, вероятность <tex>p_{kn}</tex> является решением уравнения в конечных разностях
: <tex dpi="140">\dfrac{i}{t} \leqslant g(n) < \dfrac{i+1}{t}</tex>, то есть <tex dpi="140">\dfrac{[ \log_2 n^t ]}{t} \leqslant g(n) < \dfrac{[ \log_2 n^t ]+1}{t}</tex>
 
  
Отсюда ясно, что если <tex> t\rightarrow \infty</tex>, то получаем <tex>g(n) = \log_2n</tex>
+
*<tex> \quad \quad p \cdot f_{k+1} − f_{k} + q \cdot f_{k−1} = 0 </tex> <tex>(2.2)</tex>
}}
+
 
 +
удовлетворяющим граничным условиям <tex>f_0 = 0 \quad f_n = 1</tex>. Теория решения таких уравнений аналогична
 +
теории линейных уравнений с постоянными коэффициентами.
 +
 
 +
Пусть сначала <tex>p ≠ q</tex>. Решение будем искать в виде <tex>f_k = \lambda^k</tex>, где <tex>\lambda</tex> является корнем характеристического уравнения <tex>p\lambda^2 − \lambda + q = 0</tex>. Корнями такого уравнения являются <tex>\lambda_1 = 1, \lambda_2 = \frac{q}{p}</tex>.
  
{{Теорема
+
Значит, функции <tex>\lambda_1^k</tex> и <tex>\lambda_2^k</tex> удовлетворяют уравнению <tex>(2.2)</tex>. Линейная комбинация
|statement= <tex dpi="140">H(p_1, p_2, \dots, p_n) = -k \sum\limits_{i=1}^{n} p_i\log_2p_i = k \sum\limits_{i=1}^{n} p_i\log_2\dfrac{1}{p_i}</tex>
 
|proof =
 
  
 +
*<tex>\quad f_k = C_1λ^k_1 + C_2λ^k_2</tex>
  
Теперь рассмотрим функцию <tex dpi="140">H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n})</tex>
+
при любых <tex>C_1</tex> и <tex>C_2</tex> также является решением. Подставляя граничные условия в <tex> f_k = C_1λ^k_1 + C_2λ^k_2</tex>, при <tex>k = 0</tex> и <tex>k = n</tex> получим
  
Приведем дроби внутри функции к одному знаменателю, получаем: <tex dpi="140"> H(\dfrac{a_1}{b_1}, \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n}) = H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b})</tex>
+
<tex>\quad C_1 + C_2 = 0, \quad C_1 + (\frac{q}{p})^nC_2 = 1.</tex>
  
Далее по свойству энтропии и доказанной лемме:
+
Отсюда и из <tex>f_k = C_1λ^k_1 + C_2λ^k_2</tex> находим
: <tex dpi="140">g(b)= H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) + \sum\limits_{i=1}^{n} \dfrac{x_i}{b} g(x_i)</tex>
 
  
: <tex dpi="140">H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b}) = \log_2b - \sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2x_i = -\sum\limits_{i=1}^{n} \dfrac{x_i}{b} \log_2 \dfrac{x_i}{b}</tex>
+
*<tex>\quad p_{kn} = \frac{(1 − q/p)^k}{(1 − (q/p)^n)}.</tex>
При <tex dpi="140"> p_i = \dfrac{x_i}{b} </tex> получаем, что <tex dpi="140">H(p_1, p_2, \dots, p_n) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = \sum\limits_{i=1}^{n} p_i \log_2 \dfrac{1}{p_i}</tex>  
 
}}
 
  
== Примеры ==
+
Вероятности выигрыша первым игроком <tex>p_{k0}</tex> тоже удовлетворяют уравнению <tex>(2.2)</tex>. Но граничными
=== Энтропия честной монеты ===
+
условиями станут <tex>f_0 = 1, f_n = 0.</tex> Определяя из этих условий <tex>C_1</tex> и <tex>C_2</tex>, получим
Рассмотрим [[Вероятностное пространство, элементарный исход, событие|вероятностное пространство]] {{---}} честная монета.
 
Найдем для нее энтропию:
 
:<tex dpi="140">H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot \log_2 \dfrac{1}{2}} = -\sum\limits_{i=1}^{2} {\dfrac{1}{2} \cdot (-1)} = 1</tex>
 
Это означает что после броска честной монеты мы получим информацию в размере <tex>1</tex> бит, уменьшив степень неопределенности вдвое.
 
  
=== Энтропия нечестной монеты ===
+
<tex>\quad p_{k0} = \frac{((q/p)^k − (q/p)^n)}{(1 − (q/p)^n)}.</tex>
Найдем энтропию для [[Вероятностное пространство, элементарный исход, событие|вероятностного пространства]] нечестная монета с [[Схема Бернулли| распределением Бернулли]] <tex>\{0,2; 0,8\}</tex>:
 
:<tex dpi="140">H(X) = -\sum\limits_{i=1}^{n} p_i \log_2p_i = -0.2\log_2(0.2)-0.8\log_2(0.8) \approx 0.722 < 1 </tex>
 
  
== Ограниченность энтропии ==
+
Так как <tex>p_{k0} + p_{kn} = 1</tex>, то с вероятностью <tex>1</tex> один из игроков выиграет.
{{Теорема
 
|statement= <tex>0 \leqslant  H(p_1, p_2, \dots, p_n) \leqslant  \log_2n </tex>
 
|proof =
 
1) Докажем первую часть неравенства:
 
  
Так как <tex> p_i\in[0,\;1]</tex>, тогда <tex dpi="140">\log_2\dfrac{1}{p_i} \geqslant 0 </tex>. Таким образом <tex dpi="140"> H(p_1, p_2, \dots, p_n) = \sum\limits_{i=1}^{n} p_i\log_2 \dfrac{1}{p_i} \geqslant 0 </tex>
+
Пусть теперь <tex>p = q = 0.5</tex>. В этом случае <tex>\lambda_1 = \lambda_2 = 1</tex> и решение уравнения <tex>(2.2)</tex> нужно искать в виде <tex>f_k = C_1 + kC_2 .</tex>
  
2) Докажем вторую часть неравенства:
+
С помощью граничных условий находим
  
<tex dpi="140"> f(x)=\log_2x </tex> {{---}} выпуклая вверх функция, <tex> p_1,p_2,\ldots,p_n>0</tex> и <tex> \sum \limits_{i=1}^{n} p_i = 1 </tex>, тогда для нее выполняется неравенство Йенсена:
+
<tex>\quad p_{kn} = \frac{k}{n}, \quad p_{k0} = 1 \frac{k}{n}.</tex>
<tex dpi="140"> \sum\limits_{i=1}^{n} p_i f(\dfrac{1}{p_i}) \leqslant  f(\sum\limits_{i=1}^{n} (p_i \cdot\dfrac{1}{p_i})) </tex>
 
Таким образом получаем, что <tex> H(p_1, p_2, \dots, p_n) \leqslant  \log_2n </tex>
 
}}
 
Тогда из теоремы и доказанной выше леммы следует, что для n исходов энтропия максимальна, если они все равновероятны.
 
== Условная и взаимная энтропия ==
 
{{Определение
 
|definition = '''Условная энтропия''' (англ. ''conditional entropy'') {{---}} определяет количество остающейся энтропии (то есть, остающейся неопределенности) события <tex>A</tex> после того, как становится известным результат события <tex>B</tex>. Она называется ''энтропия <tex>A</tex> при условии <tex>B</tex>'', и обозначается <tex>H(A|B)</tex>
 
}}
 
<tex>H(A|B)= - \sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex>
 
{{Определение
 
|definition = '''Взаимная энтропия''' (англ. ''joint entropy'') {{---}} энтропия объединения двух событий <tex>A</tex> и <tex>B</tex>.
 
}}
 
<tex> H(A \cap B) = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) </tex>
 
{{Утверждение
 
|statement= <tex> H(A \cap B) = H(A|B)+H(B)=H(B|A)+H(A) </tex>
 
|proof= По формуле условной вероятности <tex dpi="130"> p(a_j|b_i)=\dfrac{p(a_j \cap b_i)}{p(b_i)} </tex>
 
  
<tex dpi="140"> H(A|B)=-\sum\limits_{i=1}^{m}p(b_i)\sum\limits_{j=1}^{n} p(a_j|b_i)\log_2p(a_j|b_i) </tex> <tex dpi="140">= - \sum\limits_{i=1}^{m}p(b_i) \sum\limits_{j=1}^{n} \dfrac{p(a_j \cap b_i)}{p(b_i)}\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2 \dfrac {p(a_j \cap b_i)}{p(b_i)} = </tex>
+
В схеме блуждания по целым точкам с поглощением только в нуле вероятность события
<tex dpi="140"> = -\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(a_j \cap b_i) + \sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) </tex><tex dpi="140">= H(A \cap B) +\sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} p(a_j \cap b_i)\log_2p(b_i) = </tex>
 
  
<tex dpi="140"> = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)\sum\limits_{j=1}^{n} p(a_j \cap b_i) = H(A \cap B) +\sum\limits_{i=1}^{m} \log_2p(b_i)p(b_i) = </tex><tex dpi="140">H(A \cap B) - H(B) </tex>
+
<tex>\quad A_n = \{\exists t : \quad \xi_t = </tex>, <tex>\quad \forall t: \quad \xi_t ∈ [0, n)\}</tex> равна
  
Таким образом получаем, что: <tex> H(A \cap B)= H(A|B)+H(B) </tex>
+
<tex> \quad p_{k0} = \begin{cases} \frac{((q/p)^k − (q/p)^n)}{(1 − (q/p)^n)},  &\text{если p≠q}\\1 − k/n, &\text{если p=0.5}
 +
\end{cases}</tex>
  
Аналогично: <tex>H(B \cap A)= H(B|A)+H(A) </tex>
+
События <tex>A_n</tex> вложены последовательно друг в друга
 +
*<tex>\quad A_1 ⊂ A_2 ⊂ · · · ⊂ A_n ⊂ . . . ,</tex>
  
Из двух полученных равенств следует, что <tex> H(A|B)+H(B)=H(B|A)+H(A) </tex>
+
поэтому вероятность поглощения в нуле равна
}}
 
  
== См. также ==
+
*<tex>p_k = \lim_{n\to\infty}P(A) = \lim_{n\to\infty}p_{k0}=\begin{cases} (\frac{q}{p})^k, &\text{если q меньше p}\\1, &\text{если q≥p}
*[[Вероятностное пространство, элементарный исход, событие|Вероятностное пространство, элементарный исход, событие]]
+
\end{cases}</tex>
*[[Условная вероятность|Условная вероятность]]
 
  
 
== Источники информации ==
 
== Источники информации ==
* И.В. Романовский "Дискретный анализ"
+
'''Все источники нужно сделать кликабельными'''
* [http://ru.wikipedia.org/wiki/Информационная_энтропия Википедия {{---}} Информационная энтропия]
+
* [https://en.wikipedia.org/wiki/Random_walk "Википедия - Random_walk"]
* [https://en.wikipedia.org/wiki/Entropy_(information_theory) Wkipedia {{---}} Entropy(information_theory)]  
+
* [https://www.youtube.com/watch?v=6wUD_gp5WeE "Лекция MIT Random Walks"]
 +
* [http://math.csu.ru/new_files/students/lectures/teor_slych_proc/solovev_teor_slych_proc.pdf Конспект лекций по теории случайных процессов А.А. Соловьев]
 +
* [https://cmp.phys.msu.ru/sites/default/files/02_RandomWalks.pdf Случайные блуждания по прямой]
 +
*[https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%B7%D0%BE%D1%80%D0%B5%D0%BD%D0%B8%D0%B8_%D0%B8%D0%B3%D1%80%D0%BE%D0%BA%D0%B0 "Задача о разорении игрока"]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
  
[[Категория: Теория вероятности ]]
+
[[Категория: Теория ]]

Текущая версия на 16:19, 2 сентября 2020

Определение

Определение:
Случайное блуждание (англ. Random walk) — математическая модель процесса случайных изменений — шагов в дискретные моменты времени, предполагается, что изменение на каждом шаге не зависит от предыдущих и от времени. В силу простоты анализа эта модель часто используется в разных сферах в математике, экономике, физике, но, как правило, такая модель является существенным упрощением реального процесса.


Случайные блуждания по прямой

Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку [math]k + 1[/math] и с положительной вероятностью [math]q = 1 − p[/math] перемещается в точку [math]k − 1[/math]. Физической системе соответствует цепь Маркова:

  • [math]\xi_n = \xi_{n-1} + \eta_n = \xi_0 + S_n, \eta_n = \begin{cases} 1 &\text{с вероятностью p}\\-1 &\text{с вероятностью 1 - p} \end{cases}[/math]

Заметим, что вернуться в какую-либо точку можно только за четное число шагов.

Вероятность смещения на d единиц вправо (влево)

Будем считать, что [math]P(\xi_0 = m) = 1[/math]. Это соответствует тому, что в начальный момент времени частица находилась в точке [math]x = m[/math] (здесь [math]m[/math] — фиксированное число) и затем начала случайно блуждать в соответствии с описанными выше правилами. Пусть [math]d[/math] — смещение частицы за [math]n[/math] шагов. Найдём [math]P(\xi_n = m + d)[/math] для каждого [math]d ∈ Z[/math].

Справедливо равенство:

  • [math]P(\xi_n = m + d) = P(\xi_n = m + d | \xi_0 = m)[/math], если [math]P(\xi_0 = m) = 1.[/math]

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

Наша физическая модель с математической точки зрения в точности отвечает схеме независимых испытаний Бернулли с двумя исходами —- движением вправо, который мы будем называть успехом, и движением вправо (неудачей). Пусть частица сделала [math]n[/math] прыжков. Вероятность того, что среди этих прыжков будет ровно [math]k[/math] прыжков вправо (или, что то же самое, [math]n−k[/math] прыжков влево) задаётся формулой:

  • [math]P = {C_{n}^k} p^k q^{n−k}, \quad k = 0, 1, . . . , n [/math]

Смещение частицы и число прыжков влево и вправо связаны уравнением

  • [math]d = 1 · k + (−1) · (n − k) = 2k − n \quad[/math]

откуда [math]k = \frac{(n + d)}{2}[/math]. Понятно, что, поскольку частица сделала ровно [math]n[/math] прыжков, число прыжков вправо должно быть целым числом в интервале [math][0, n][/math], другими словами, [math]P(\xi_n = m + d) = 0,[/math] если [math]k = \frac{(n + d)}{2}, k \notin \{0, 1, . . . , n\}[/math]. Если же указанное ограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли [math]P = {C_{n}^k} p^k q^{n−k}[/math]:

  • [math] P(\xi_n = m + d) = {C_{n}^k} p^k q^{n−k}, \quad k = \frac{(n + d)}{2} [/math], при обязательном условии [math]k ∈ {0, 1, . . . , n}.[/math]


Замечания.

[math]1)[/math] Ограничение [math]0 \leq k \leq n [/math] по формуле [math]d = 1 · k + (−1) · (n − k) = 2k − n[/math] влечёт [math]|d| \leq n[/math]. Это можно понять и без расчётов: если [math]|d| \gt n[/math], то частица не успевает дойти из начальной в конечную точку за [math]n[/math] шагов.

[math]2)[/math] При своём движении частица случайным образом выбирает одну из возможных траекторий. Для перехода из точки [math]m[/math] в точку [math]m[/math] за [math]n[/math] шагов возможными являются все те и только те траектории длины [math]n[/math], в которых ровно [math]k[/math] смещений вправо и [math]n − k[/math] смещений влево, где [math]k = \frac{(n + d)}{2}[/math]. Равенство [math]P = {C_{n}^k} p^k q^{n−k}[/math] при этом можно интерпретировать так: вероятность того, что частица пройдет по одной из возможных траекторий, равна [math]p^k q^{n−k}[/math], и всего существуют [math]{C_{n}^k}[/math] таких траекторий, таким образом,

  • [math]P = p^k \cdot q^{n−k}+...+p^k \cdot q^{n−k}={C_{n}^k} p^k q^{n−k}.[/math]

Случайные блуждания по прямой

Представим частицу, которая движется по целым точкам на прямой. Перемещение из одной точки в другую происходит через равные промежутки времени. За один шаг частица из точки k с положительной вероятностью p перемещается в точку [math]k + 1[/math] и с положительной вероятностью [math]q = 1 − p[/math] перемещается в точку [math]k − 1[/math]. Физической системе соответствует цепь Маркова:

  • [math]\xi_n = \xi_{n-1} + \eta_n = \xi_0 + S_n, \eta_n = \begin{cases} 1 &\text{с вероятностью p}\\-1 &\text{с вероятностью 1 - p} \end{cases}[/math]

Заметим, что вернуться в какую-либо точку можно только за четное число шагов.

Задача о разорении игрока

Пусть начальный капитал [math]\xi_0[/math] первого игрока составляет [math]k[/math] рублей, а капитал второго игрока [math] – (n − k)[/math] рублей. Первый игрок выигрывает или проигрывает рубль с вероятностями [math]p[/math] и [math]q[/math] соответственно. Игра продолжается до тех пор, пока капитал первого игрока не уменьшится до нуля, либо не возрастет до [math]n[/math]. Поглощение точки в правом конце отрезка [math][0, n][/math] соответствует выигрышу первого игрока.

Рассмотрим конечную цепь Маркова:

[math]\quad\xi_{t+1} = \xi_t + \eta_t,\quad P\{\eta_t = 1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = p,\quad P\{\eta_t = −1|\xi_t ≠ 0 ∨ \xi_t ≠ n\} = q[/math] и

[math]\quad P\{\eta = 0|\xi_t = 0 ∨ \xi_t = n\} = 1. [/math] [math](2.1)[/math]

Вероятность выигрыша для первого игрока в момент времени [math]t[/math] есть [math]p_{kn}(t) = P\{\eta_t = n|\eta_0 = k\}[/math]

По формуле полной вероятности:

  • [math] \quad P\{\xi_{t+1} = n\} = P\{\xi_1 = k + 1|\xi_0 = k\}P\{\xi_{t+1} = n|\xi_{1} = k + 1\} + P\{\xi_{1} = k − 1|\xi_0 = k\}P\{\xi_{t+1} = n|\xi_{1} = k - 1\} [/math]

или

  • [math] \quad p_{kn}(t + 1) = p \cdot p_{k+1,n}(t) + q \cdot p_{k−1,n}(t), \quad k = 1, 2, . . . , n − 1.[/math]

Теорему о предельных вероятностях применить не можем, но заметим, что:

[math] \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 = n\} ⊂ · · · ⊂ \{\xi_t = n\} ⊂ . . . [/math]

Положим [math]A =\cup_{t=1}^∞\{\xi_t = n\}[/math]. Тогда

[math] \quad \quad p_{kn} = P(A) = \lim_{t\to\infty}P\{\xi_t = n|\xi_0 = k\} = \lim_{t\to\infty}p_{kn}(t).[/math]

Переходя к пределу в [math](2.1)[/math] при [math]t → ∞[/math], получим

[math]\quad \quad p_{kn} = p \cdot p_{k+1,n} + q \cdot p_{k−1,n}[/math]

Так как [math]p_{kn}[/math] вероятность выигрыша для первого игрока, то [math]p_{0n} = 0, p_{nn} = 1[/math]. Рассматриваемая как функция от [math]k[/math], вероятность [math]p_{kn}[/math] является решением уравнения в конечных разностях

  • [math] \quad \quad p \cdot f_{k+1} − f_{k} + q \cdot f_{k−1} = 0 [/math] [math](2.2)[/math]

удовлетворяющим граничным условиям [math]f_0 = 0 \quad f_n = 1[/math]. Теория решения таких уравнений аналогична теории линейных уравнений с постоянными коэффициентами.

Пусть сначала [math]p ≠ q[/math]. Решение будем искать в виде [math]f_k = \lambda^k[/math], где [math]\lambda[/math] является корнем характеристического уравнения [math]p\lambda^2 − \lambda + q = 0[/math]. Корнями такого уравнения являются [math]\lambda_1 = 1, \lambda_2 = \frac{q}{p}[/math].

Значит, функции [math]\lambda_1^k[/math] и [math]\lambda_2^k[/math] удовлетворяют уравнению [math](2.2)[/math]. Линейная комбинация

  • [math]\quad f_k = C_1λ^k_1 + C_2λ^k_2[/math]

при любых [math]C_1[/math] и [math]C_2[/math] также является решением. Подставляя граничные условия в [math] f_k = C_1λ^k_1 + C_2λ^k_2[/math], при [math]k = 0[/math] и [math]k = n[/math] получим

[math]\quad C_1 + C_2 = 0, \quad C_1 + (\frac{q}{p})^nC_2 = 1.[/math]

Отсюда и из [math]f_k = C_1λ^k_1 + C_2λ^k_2[/math] находим

  • [math]\quad p_{kn} = \frac{(1 − q/p)^k}{(1 − (q/p)^n)}.[/math]

Вероятности выигрыша первым игроком [math]p_{k0}[/math] тоже удовлетворяют уравнению [math](2.2)[/math]. Но граничными условиями станут [math]f_0 = 1, f_n = 0.[/math] Определяя из этих условий [math]C_1[/math] и [math]C_2[/math], получим

[math]\quad p_{k0} = \frac{((q/p)^k − (q/p)^n)}{(1 − (q/p)^n)}.[/math]

Так как [math]p_{k0} + p_{kn} = 1[/math], то с вероятностью [math]1[/math] один из игроков выиграет.

Пусть теперь [math]p = q = 0.5[/math]. В этом случае [math]\lambda_1 = \lambda_2 = 1[/math] и решение уравнения [math](2.2)[/math] нужно искать в виде [math]f_k = C_1 + kC_2 .[/math]

С помощью граничных условий находим

[math]\quad p_{kn} = \frac{k}{n}, \quad p_{k0} = 1 − \frac{k}{n}.[/math]

В схеме блуждания по целым точкам с поглощением только в нуле вероятность события

[math]\quad A_n = \{\exists t : \quad \xi_t = 0 [/math], [math]\quad \forall t: \quad \xi_t ∈ [0, n)\}[/math] равна

[math] \quad p_{k0} = \begin{cases} \frac{((q/p)^k − (q/p)^n)}{(1 − (q/p)^n)}, &\text{если p≠q}\\1 − k/n, &\text{если p=0.5} \end{cases}[/math]

События [math]A_n[/math] вложены последовательно друг в друга

  • [math]\quad A_1 ⊂ A_2 ⊂ · · · ⊂ A_n ⊂ . . . ,[/math]

поэтому вероятность поглощения в нуле равна

  • [math]p_k = \lim_{n\to\infty}P(A) = \lim_{n\to\infty}p_{k0}=\begin{cases} (\frac{q}{p})^k, &\text{если q меньше p}\\1, &\text{если q≥p} \end{cases}[/math]

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

Все источники нужно сделать кликабельными