Сторінка Шарапова М.М.

Зліченна ймовірносна схема

Високий рівень

Умова

П'яниця стоїть на відстані одного кроку від прірви. Кожну секунду він робить крок з ймовірністю $q = \frac{1}{2}$ до прірви та з ймовірністю $p = \frac{1}{2}$ від неї. Знайти ймовірність того, що рано чи пізно він впаде у прірву.

Розв’язок

Послідовність кроків п’яниці задамо вектором $\left( {{a_1},{a_2},...,{a_n}} \right)$, де $n \le \propto $. Причому ${a_i} = 1$ тільки тоді, коли п'яниця і-ий крок зробив у напрямку від прірви, а ${a_i} = - 1$ тільки тоді, коли п'яниця і-ий крок зробив у напрямку до прірви. Якщо п’яниця знаходиться на відстані одного кроку від прірви та вперше впаде у прірву тільки на $n$-му кроці, то $\sum\limits_{i = 1}^t {{a_i}} > - 1,\;\forall t < n$. Простір елементарних подій описаного стохастичного експерименту задамо наступним чином: $$\Omega = \left\{ {\left. {\left( {{a_1},{a_2},...,{a_n}} \right)} \right|\;\;n \le \propto ,\;{a_i} \in \left\{ { - 1,1} \right\},\;\forall t < n:\sum\limits_{i = 1}^t {{a_i}} > - 1} \right\}.$$ Розглянемо подію $ A = $ {п’яниця впав у прірву}. Після падіння п’яниці блукання закінчуються, тому усі елементарні події, що входять в $ A $, задаються вектором скінченної довжини. Нехай п’яниця впав на $n$-ому кроці. Падіння через $n$ кроків означає виконання рівності $\sum\limits_{i = 1}^n {{a_i}} = - 1.$ Тому $$A = \left\{ {\left. {\left( {{a_1},{a_2},...,{a_n}} \right)} \right|\;\;n \in N,\;{a_i} \in \left\{ { - 1,1} \right\};\;\forall t < n:\sum\limits_{i = 1}^t {{a_i}} > - 1;\;\;\sum\limits_{i = 1}^n {{a_i}} = - 1} \right\}.$$ Розглянемо подію $\bar A $ = {п’яниця не впав у прірву}. Усі елементарні події, що входять в $\bar A $, задаються вектором нескінченої довжини, тому $$\bar A = \left\{ {\left. {\left( {{a_1},{a_2},...,{a_k},...} \right)} \right|\;{a_k} \in \left\{ { - 1,1} \right\},\forall t \in N:\sum\limits_{i = 1}^t {{a_i}} > - 1} \right\}.$$ Будемо вважати, що на початку п'яниця стоїть у точці, що має координату $x = 1,$ а початок прірви знаходиться у точці $x = 0,$ кожен крок має довжину рівну 1. Нехай ${P_m}$ – це ймовірність того, що він впаде, якщо почне з точки $x = m,$ де $m \in N.$ Розглянемо події $ H_1 $ = {перший крок п’яниця зробив у напрямку до прірви} і $ H_2 $ = {перший крок п’яниця зробив у напрямку від прірви}. Події $ H_1 $ і $ H_2 $ несумісні та їх об’єднання утворює $\Omega $, тому $ H_1 $, $ H_2 $ утворюють повну групу подій. За умовою $ P(H_1)=1-p $, $ P(H_2) = p $.

Очевидно, що $ P(A | H_1) = 1 $ (п’яниця стояв на відстані одного кроку від прірви і зробив крок у напрямку до прірви, тому він впав) та $ P(A | H_2) = P_2 $ (він змінив позицію з $x = 1$ на $x = 2$). За формулою повної ймовірності $$P_1 ~=~ P(A) ~=~ P(A|H_1)P(H_1) ~+~ P(A|H_2)P(H_2),$$ $${P_1} ~=~ 1 - p + p \cdot P_2 \tag{1} $$ Кожен шлях, що призводить до падіння і починається у точці $x = 2,$ можна розбити на дві частини: шлях з точки $x = 2$ у $x = 1,$ шлях з $x = 1$ у $x = 0.$ Ймовірність потрапити з точки $x = 2$ у $x = 1$ також дорівнює ${P_1}$, бо структура блукання ідентична, тільки початок координат переноситься у точку $x = 1.$ Тому $P{}_2 = P_1^2.$ Підставимо отриману рівність у рівність (1): $${P_1} = 1 - p + p \cdot P_1^2,$$ тобто ${P_1} = \frac{1}{2} + \frac{1}{2} \cdot P_1^2$, $P_1^2 - 2{P_1} + 1 = 0$, ${P_1} = 1.$ Тобто ми знайшли ймовірність що п’яниця впаде, якщо почне з точки, що має координату $x = 1.$

Зауваження

Доведемо, що ймовірність впасти залишається рівною одиниці, незалежно від того на якій відстані від прірви п’яниця стоїть спочатку. Тобто доведемо, що $P{}_m = 1$ для $\forall m \in N.$ Для цього скористаємось методом математичної індукції. База: ${P_1} = 1$ (доведено вище). Індукційний перехід: припустимо, що для $\forall k < m,$ $k \in N$: $P{}_k = 1.$ Доведемо, що $P_m = 1.$ Шлях від точки $x = m$ до прірви розіб’ємо на дві частини: від точки $x = m$ до точки $x = m - 1,$ від точки $x = m - 1$ до краю прірви. Ймовірність, що п’яниця дійде від точки $x = m$ до точки $x = m - 1,$ дорівнює ${P_1},$ бо структура блукання ідентична, тільки початок координат переноситься. Тому $P{}_m = P{}_1 \cdot P{}_{m - 1} = 1$, що і треба було довести.

Відповідь: 1.
Висновок:

Перевірка Для перевірки отриманого результату напишемо програму мовою Javascript.

const M = Number.MAX_SAFE_INTEGER; # 9007199254740991

n = 10000 	# кількість експериментів
m = 0 		# кількість успішних експериментів (коли п'яниця врятується)
max = 0		# максимальне віддаленя

for(let i=0; i < n; i++){
	s = 1;
	while(s > 0 && s < M){
		if(Math.random() < 0.5) s+=1; else s+= -1;
		if(s > max) max = s;
	}
	if(s == 0) m +=1; 
}
console.log("max =", max)
console.log("m/n =", m/n)

Вважаємо, що п'яниця стоїть у точці $s = 1$ і може зробити крок у прірву, роль якої виконує точка $s = 0$, або від прірви в точку $s = 2$ і так далі. Константа $M = Number.MAX\_SAFE\_INTEGER = 9007199254740991$ відіграє роль "максимального віддалення" від прірви, за якого вже вважаємо, що п'яниця не повернеться до прірви і буде врятований. Заради цікавості обчислимо максимальне віддаленя, на яке відійде п'яниця від прірви упродовж усіх проведених експериментів.

Результат роботи цієї програми:

max = 181069
m/n = 1

підтверджує правильність отриманого результату.