Изменения

|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 dpi ="130">H=Вероятность смещения на d единиц вправо (\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>==

* Будем считать, что <tex dpi ="130"> HP(p_{\xi_0 = m) = 1}q_{11}</tex>. Это соответствует тому, p_{1}q_{12}, \dots, p_{n}q_{nk_n}) что в начальный момент времени частица находилась в точке<tex>x = Hm</tex> (p_1, p_2, \dots, p_nздесь <tex>m</tex> — фиксированное число) + \sum\limits_{i=1}^{и затем начала случайно блуждать в соответствии с описанными выше правилами. Пусть <tex>d</tex> — смещение частицы за <tex>n} p_iH</tex> шагов.Найдём <tex>P(q_{i1}, \dots, q_{ik_i}xi_n = m + d)</tex>для каждого <tex>\rhdd ∈ Z</tex>.

Рассмотрим схему Справедливо равенство: *<tex>P(\mathcal{xi_n = m + d) = P}_m</tex> c <tex>(\xi_n = m + d | \xi_0 = m)</tex> исходами и вероятностями <tex>\{p_1, p_2, \dots, p_m\}</tex> и схему если <tex>P(\mathcal{R}_k</tex> с <tex>k</tex> исходами и вероятностями <tex>\{q_1, q_2, \dots, q_k\}xi_0 = m) = 1.</tex>.

Выбирается случайным образом один из исходов схемы <tex>\mathcal{P}_m<Наша физическая модель с математической точки зрения в точности отвечаетсхеме [https://neerc.ifmo.ru/wiki/tex>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>mn</tex>-й исходпрыжков. Вероятность того, выбирается случайно один из исходов схемы что средиэтих прыжков будет ровно <tex>\mathcal{R}_kk</tex>прыжков вправо (или, что то же самое, а остальные <tex>m - 1</tex> исходов схемы <tex>\mathcal{P}_mn−k</tex> считаются окончательными.прыжковвлево) задаётся формулой:

В этой комбинированной схеме *<tex>\mathcalP = {C_{n}^k} p^k q^{PRn−k}</tex> мы получаем исходы <tex>1, 2, \dots, m - 1, (m, 1), (m, 2), \dots, (m, quad k)</tex> с вероятностями <tex>p_1, p_2, \dots= 0, p_{m-1}, p_mq_1, p_mq_2, \dots. . . , p_mq_kn </tex>

Легко видетьСмещение частицы и число прыжков влево и вправо связаны уравнением*<tex>d = 1 · k + (−1) · (n − k) = 2k − n \quad</tex>  откуда <tex>k = \frac{(n + d)}{2}</tex>. Понятно, что , поскольку частица сделала ровно <tex>Hn</tex> прыжков,число прыжков вправо должно быть целым числом в интервале <tex>[0, n]</tex>, другими словами, <tex>P(\mathcal{PR}xi_n = m + d) = H0,</tex> если <tex>k = \frac{(n + d)}{2}, k \notin \mathcal{0, 1, . . . , n\}</tex>. Если же указанноеограничение выполнено, то в рамках нашей модели блужданий мы можем воспользоваться распределением Бернулли <tex>P= {C_{n}^k} p^k q^{n−k}_m) + p_mH</tex>: *<tex> P(\mathcalxi_n = m + d) = {C_{Rn}^k}_kp^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>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> == Задача о разорении игрока ==Пусть начальный капитал <tex>\lhdxi_0</tex> первогоигрока составляет <tex>k</tex> рублей, а капитал второго игрока <tex> – (n − k)</tex> рублей. Первый игрок выигрываетили проигрывает рубль с вероятностями <tex>p</tex> и <tex>q</tex>соответственно. Игра продолжается до тех пор, покакапитал первого игрока не уменьшится до нуля, либо не возрастет до <tex>n</tex>. Поглощение точки в правомконце отрезка <tex>[0, n]</tex> соответствует выигрышу первого игрока.

Для доказательства формулы вычисления энтропии сначала докажем лемму.{{Лемма|statement = <tex dpi="140">g(n) = H(\dfracquad\xi_{t+1}{n}= \xi_t + \eta_t, \dfracquad P\{\eta_t = 1}{|\xi_t ≠ 0 ∨ \xi_t ≠ n\}= p, \dots, quad P\dfrac{1}{n}) \eta_t = -k −1|\log_2 xi_t ≠ 0 ∨ \dfrac{1}{xi_t ≠ n\} = k \log_2n</tex>|proof =Будем рассматривать для <tex>k=1q</tex> (бит).и

Рассмотрим функцию <tex>g(mn)</tex>:: <tex>g(mn)\quad P\{\eta =g(m)+ 0|\sumxi_t = 0 ∨ \limits_{ixi_t =1}^{m} n\dfrac{1}{m} g(n) = g(m)+g(n)1. </tex>(2.1)

Пусть: Вероятность выигрыша для первого игрока в момент времени <tex>g(2)=1 \quadt</tex>, тогда есть <tex>gp_{kn}(2^t)=t</tex> и <tex> P\{\quad g(eta_t = n^t)|\eta_0 =t k\cdot g(n)}</tex>

Можно заметить, что если *<tex> i\quad P\{\xi_{t+1} = n\} = P\{\xi_1 = k + 1|\xi_0 =[ k\}P\{\log_2 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> i \leqslant quad p_{kn}(t + 1) = p \cdot gp_{k+1,n}(nt) <i+1 q \quad cdot p_{k−1,n}(t), \quad k = 1, 2, . . . , n − 1.</tex>

Делим неравенство на <tex>t</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> \quad \quad \{\xi_1 = n\} ⊂ \{\xi_2 = n\} ⊂ · · · ⊂ \{\xi_t = n\} ⊂ . . . </tex>  Положим <tex>A =\cup_{t=1}^∞\{\xi_t = n\}</tex>. Тогда <tex> \rightarrow 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> Переходя к пределу в (2.1) при <tex>t → ∞</tex>, получим <tex>\quad \quad p_{kn} = p \cdot p_{k+1,n} + q \cdot p_{k−1,n}</tex> Так как <tex>p_{kn}</tex> вероятность выигрыша для первого игрока, то получаем <tex>gp_{0n} = 0, p_{nn} = 1</tex>. Рассматриваемая как функция от <tex>k</tex>, вероятность <tex>p_{kn}</tex> является решением уравнения в конечных разностях *<tex> \quad \quad p \cdot f_{k+1} − f_{k} + q \cdot f_{k−1} = 0 </tex> (n2.2)  удовлетворяющим граничным условиям <tex>f_0 = 0 \log_2nquad 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>.

{{Теорема|statement= Значит, функции <tex dpi="140">H(p_1, p_2, \dots, p_n) = -lambda_1^k </tex> и <tex>\sum\limits_{i=1}lambda_2^{n} p_i\log_2p_i = k \sum\limits_{i=1}^{n} p_i\log_2\dfrac{1}{p_i}</tex>|proof =удовлетворяют уравнению (2.2). Линейная комбинация

Теперь рассмотрим функцию при любых <tex dpi="140">HC_1</tex> и <tex>C_2</tex> также является решением. Подставляя граничные условия в (\dfrac{a_1}{b_1}2.3), \dfrac{a_2}{b_2}, \dots, \dfrac{a_n}{b_n})при <tex>k = 0</tex> и <tex>k = n</tex>получим

Приведем дроби внутри функции к одному знаменателю, получаем: <tex dpi="140"> H(\dfrac{a_1}{b_1}quad C_1 + C_2 = 0, \dfrac{a_2}{b_2}, quad C_1 + (\dots, \dfracfrac{a_nq}{b_np}) ^nC_2 = H(\dfrac{x_1}{b}, \dfrac{x_2}{b}, \dots, \dfrac{x_n}{b})1.</tex>

Далее по свойству энтропии Отсюда и доказанной лемме:: <tex dpi="140">gиз (b2.3)= 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}quad p_{bkn}, \dots, \dfrac{x_n}{b}) = \log_2b - \sum\limits_frac{i=(1}− q/p)^{nk} \dfrac{x_i}{b} \log_2x_i = -\sum\limits_{i=(1}^{n} \dfrac{x_i}{b} \log_2 \dfrac{x_i}{b}<− (q/tex>При <tex dpi="140"> p_i = \dfrac{x_i}{b} </tex> получаем, что <tex dpi="140">H(p_1, p_2, \dots, p_np) = -\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 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). Но граничнымиусловиями станут <tex>f_0 =1}^{2} {\dfrac{1}{2} \cdot (-1)} , f_n = 10.</tex> Определяя из этих условий <tex>C_1</tex>Это означает что после броска честной монеты мы получим информацию в размере и <tex>1C_2</tex> бит, уменьшив степень неопределенности вдвое.получим

=== Энтропия нечестной монеты ===Найдем энтропию для [[Вероятностное пространство, элементарный исход, событие|вероятностного пространства]] нечестная монета с [[Схема Бернулли| распределением Бернулли]] <tex>\quad p_{0,2; 0,8k0} = \}<frac{((q/tex>::<tex dpi="140">Hp)^k − (Xq/p) = -\sum\limits_{i=1}^{n)} p_i \log_2p_i = -0.2\log_2{(1 − (0.2q/p)-0.8\log_2(0.8^n) \approx 0}.722 < 1 </tex>

== Ограниченность энтропии ==Так как <tex>p_{k0} + p_{Теорема|statementkn} = 1</tex>0 \leqslant H(p_1, p_2, \dots, p_n) \leqslant \log_2n то с вероятностью <tex>1</tex>|proof =1) Докажем первую часть неравенства:один из игроков выиграет.

Так как Пусть теперь <tex> p_i\in[p = q = 0,\;1].5</tex>, тогда . В этом случае <tex dpi="140">\log_2lambda_1 = \dfrac{lambda_2 = 1}{p_i} \geqslant 0 </tex>и решение уравнения (2. Таким образом 2) нужно искать в виде <tex dpi="140"> H(p_1, p_2, \dots, p_n) f_k = \sum\limits_{i=1}^{n} p_i\log_2 \dfrac{1}{p_i} \geqslant 0 C_1 + kC_2 .</tex>

<tex dpi="140"> f(x)=\log_2x </tex> {quad p_{---kn}} выпуклая вверх функция, <tex> p_1,p_2,\ldots,p_n>0</tex> и <tex> \sum \limits_{i=1}^{n} p_i = 1 </tex>, тогда для нее выполняется неравенство Йенсена:<tex dpi="140"> \sum\limits_{i=1}^{n} p_i f(\dfrac{1}{p_i}) \leqslant f(\sum\limits_frac{i=1k}^{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'') {quad p_{---}k0} определяет количество остающейся энтропии (то есть, остающейся неопределенности) события <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_frac{j=1k}^{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 \cap B) +\sum\limits_{iquad A_n =1}^{m} \log_2p(b_i)\sum\limits_{j=1}^{n} p(a_j \cap b_i) = H(A exists t : \cap B) +quad \sum\limits_{i=1}^{m} \log_2p(b_i)p(b_i) xi_t = 0 </tex>, <tex dpi="140">H(A \cap B) - H(Bquad \forall t: \quad \xi_t ∈ [0, n) \}</tex>равна

Таким образом получаем, что: <tex> H\quad p_{k0} = \begin{cases} \frac{((A \cap Bq/p)= H^k − (A|Bq/p)+H^n)}{(B1 − (q/p) ^n)}, &\text{если p≠q}\\1 − k/n, &\text{если p=0.5} \end{cases}</tex>

Аналогично: События <tex>A_n</tex> вложены последовательно друг в друга*<tex>H(B \cap A)= H(B|A)+H(A) quad A_1 ⊂ A_2 ⊂ · · · ⊂ A_n ⊂ . . . ,</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>

* [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 "Задача о разорении игрока"]

[[Категория: Теория вероятности ]]