Этот конспект ещё находится в процессе редактуры: в тексте могут встречаться опечатки, неточности и локально не проработанные места. Если что-то нашли — сообщите, пожалуйста, автору (контакты на странице курса).
Предположим, что шаг случайного блуждания принимает всего 2 значения: \(1\) и \(-1\) с вероятностями \(p\) и \(1-p\):
\[
\mathbb {P}\left(\xi _1 = 1\right) = p, \qquad \mathbb {P}\left(\xi _1 = -1\right) = 1-p =: q
\]
Случайное блуждание с такими шагами
\[
S_0 = 0, \qquad S_n := \sum _{i=1}^n \xi _i, \; n \geq 1
\]
называется простейшим. Если \(p = \frac{1}{2}\), то оно называется симметричным.
В данной главе мы будем изучать только простейшее случайное блуждание. Зачастую слово «простейшее» мы будем опускать.
В общем случае начальное положение \(S_0\) – это тоже случайная величина, независимая с \(\xi_1, \xi_2, \ldots\), имеет произвольное распределение на \(\mathbb {Z}\). В этом случае \(S_n = S_0 + \sum_{i=1}^n \xi_i\) (\(n \in \mathbb {N}\)) – это случайное блуждание. Нам будет удобно в дальнейшем считать, что \(S_{0}\) имеет некоторое распределение на \(\mathbb {Z}\), такое что \(\mathbb {P}\left(S_0 = k\right) > 0\) для всех \(k \in \mathbb {Z}\), чтобы иметь возможность изучать условные вероятности
\[
\mathbb {P}\left( \cdots \; \mid S_{0} = k\right)
\]
Если мы захотим вернуться к блужданию, стартующему п.н. в \(0\), достаточно взять условную вероятность \(\mathbb {P}\left( \cdots \; \mid \; S_0 = 0\right)\).
Мы будем периодически использовать следующие обозначения:
\[
\begin{align} \mathbb {P}_{a}\left(A \right) := \mathbb {P}\left( A \mid S_{0} = a\right), \qquad \mathbb {E}_{a}\left[Y\right] := \mathbb {E}\left[Y \mid S_{0} = a\right] \end{align}
\]
где \(A\) – это некоторое событие, а \(Y\) – это некоторая случайная величина.
Траектория простейшего случайного блуждания, соответствующая некоторому элементарному исходу ω₀.
Условные вероятности и рекуррентные соотношения: задача о разорении игрока
Лемма 1 Случайное блуждание \(S_n\) обладает тремя важными свойствами.
Простое случайное блуждание является пространственно однородным, то есть
\[
\mathbb {P}_{a}\left(S_{n} = j\right) = \mathbb {P}_{a+b}\left(S_{n} = j+b\right)
\]
для любых \(a,b,j \in \mathbb {Z}\), \(n \in \mathbb {N}\).
Простое случайное блуждание является однородным во времени; то есть для любых \(m, n \in \mathbb {N}\) имеем
\[
\mathbb {P}\left(S_{n} = j \mid S_{0} = a\right) = \mathbb {P}\left(S_{m+n} = j \mid S_{m} = a\right)
\]
Простое случайное блуждание обладает свойством Маркова, то есть для любого \(j \in \mathbb {Z}\), для любых \(m, n \in \mathbb {Z}_+\) имеем
\[
\mathbb {P}\left(S_{m+n} = j \; \left| \; \begin{array}{c} S_{0} \\ S_{1} \\ \cdots \\ S_{m-1} \\ S_{m} \end{array}\right.\right) \; \stackrel{\text{п.н.}}{=} \; \mathbb {P}\left(S_{m+n} = j \mid S_{m}\right)
\]
Иначе говоря, при фиксированном настоящем (временная точка \(m\), значение \(S_m\)) будущее значение процесса (\(S_{m+n}\)) не зависит от прошлого, т.е. от значений \(S_0, S_1, \ldots , S_{m-1}\).
Игрок пришел в казино с суммой \(s_0 \in \mathbb {N}\) рублей. За \(1\) кон он может выиграть \(1\) рубль с вероятностью \(p \in (0,1)\) или проиграть \(1\) рубль с вероятностью \(1-p\). Игрок заканчивает играть в 2 вариантах:
игрок побеждает: он достигает желаемой суммы \(b \in \mathbb {N}\) (\(s_0 < b\));
игрок разоряется и проигрывает: сумма у игрока на руках опускается до некоторого уровня прожиточного минимума \(a \in \mathbb {N}\) (\(a < s_0\)), на который игрок играть не может.
Имеем \(a < s_0 < b\).
Найдите вероятность победы и вероятность проигрыша.
Примечание. \(a,b\) еще называют поглощающими барьерами для случайного блуждания.
Формализуем эксперимент. Пусть \(\left(S_{n}, n \in \mathbb {Z}_+\right)\) – простейшее случайное блуждание
\[
S_n = S_0 + \xi _1 + \ldots + \xi _n, \qquad n \geq 1
\]
с вероятностью шага вверх \(p\): \(\mathbb {P}\left(\xi_i = 1\right) = p\). В нашем случае \(S_0 = s_0\), но удобнее считать, что \(S_0\) – случайная величина, не зависящая от \(\xi_1, \xi_2, \ldots\) и имеющая некоторое (ненулевое в каждой точке) распределение на \(\left\{ a, a+1, \ldots , b-1, b\right\}\), т.к. в дальнейшем нам понадобится считать условные вероятности по событиям \(S_0 = i\), \(i = a, a+1, \ldots , b\).
Обозначим
\[
\tau _{\left\{ a,b\right\} } := \min \left\{ n \geq 0: S_{n} \in \left\{ a, b\right\} \right\}
\]
– момент выхода процесса \(S_{n}\) из полосы. Необходимо вычислить распределение \(S_{\tau_{\left\{ a,b\right\} }}\) при условии \(S_0 = s_0\). Примем без доказательства, что п.н. за конечное время игрок либо проигрывает, либо выигрывает (\(\tau_{\left\{ a,b\right\} } < \infty\) п.н., доказательство см. в следующей задаче). Тогда \(S_{\tau_{\left\{ a,b\right\} }}\) принимает п.н. 2 значения, \(a\) и \(b\). Т.е. по-сути требуется посчитать
\[
\mathbb {P}_{s_0}\left(S_{\tau _{\left\{ a,b\right\} }} = b\right)
\]
Обозначим \(\alpha_{i} = \mathbb {P}_{i}\left(S_{\tau_{\left\{ a,b\right\} }} = b\right)\) вероятность выигрыша при условии, что игрок начинает играть с суммой \(i\), где \(a \leq i \leq b\).
Граничные условия. \(\alpha_a = 0, \alpha_b = 1\).
Поиск рекуррентного соотношения. Пусть \(i \in \{ a + 1, \dots , b-1\}\). Либо блуждание двинется наверх с вероятностью \(p\), и в этом случае нужно будет выходить на верхний поглощающий барьер с уровня \(i + 1\). Либо оно двинется вниз, и тогда с уровня \(i-1\). В итоге
\[
\alpha _i = \alpha _{i+1} \cdot p + \alpha _{i-1} \cdot (1-p)
\]
Формально: рассмотрим первый шаг \(\xi_1\), его возможные значения. По формуле полной вероятности:
\[
\begin{align} \alpha _{i} \quad = \quad \quad & \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid \xi _1 = 1, \; S_0 = i\right) \\ & \quad \cdot \mathbb {P}\left( \xi _1 = 1 \mid S_0 = i\right) \; + \\ + \quad & \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid \xi _1 = -1, \; S_0 = i\right) \cdot \mathbb {P}\left(\xi _1 = -1 \mid S_0 = i\right) \end{align}
\]
Имеем 2 слагаемых
\(\xi_{1}\) не зависит от \(S_0\), значит вторые множители в этих слагаемых равны \(p\) и \(1-p\) соотв.
Первый множитель для 1-го слагаемого:
\[
\begin{align} \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid \xi _1 = 1, \; S_0 = i\right) & = \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid S_1 = i+1, \; S_0 = i\right) \\ & \overset {\text{Марковское свойство}}{=} \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid S_1 = i+1\right) \stackrel{*}{=} \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid S_0 = i+1\right) \\ & = \alpha _{i+1} \end{align}
\]
Равенство \(*\) – это однородность блуждания во времени (см. лемму выше): сдвиг времени на один шаг дает блуждание с теми же переходными вероятностями, стартующее из \(i + 1\).
Первый множитель для 2-го слагаемого: аналогично, \(\alpha_{i-1}\).
Решение рекуррентного соотношения. Характеристический многочлен:
\[
p\lambda ^2 - \lambda + q = 0 \quad \iff \quad p(\lambda - 1) \left(\lambda - \frac{q}{p}\right) = 0
\]
Случай \(p=q=\frac{1}{2}\). \(\lambda_1=\lambda_2 = 1\). Тогда решение будет задаваться уравнением
\[
\alpha _i = c_1 1^i + c_2 i 1^{i} = c_1 + c_2 i
\]
Подставляем граничные условия:
\[
\begin{cases} 0 = \alpha _a = c_1 + c_2 a \\ 1 = \alpha _b = c_1 + c_2 b \end{cases} \iff \begin{cases} -c_2a = c_1 \\ 1 = \alpha _b = c_2(b - a) \end{cases} \iff \begin{cases} c_1 = \frac{-a}{b-a} \\ c_2 = \frac{1}{b-a} \end{cases}
\]
Следовательно,
\[
\begin{align} \alpha _i & = \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid S_0 = i\right) = \frac{i - a}{b-a} = \frac{a - i}{a - b}, \\ & \quad \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = a \mid S_0 = i\right) = \frac{i - b}{a - b} \end{align}
\]
В частности, при \(i = s_0\) получаем ответ.
Случай \(p\neq q\). Тогда \(\lambda_1 = 1\), \(\lambda_2 = \frac{q}{p} \neq 1\). Тогда решение будет задаваться уравнением \(\alpha_i = c_1 + c_2 \lambda_2^{i}\).
Обозначим \(\theta := \frac{p}{q}\) шансы успеха (от англ. odds). Например, шансы \(2\) к \(1\) означают, что на \(2\) успеха приходится один провал, т.е. как раз \(p = \frac{2}{3}\), \(q = \frac{1}{3}\), \(\theta = 2\). Тогда решение уравнения:
\[
\alpha _i = c_1 + c_2 \theta ^{-i}
\]
Граничные условия:
\[
\begin{cases} 0 = \alpha _a = c_1 + c_2 \theta ^{-a} \\ 1 = \alpha _b = c_1 + c_2 \theta ^{-b} \end{cases} \iff \begin{cases} -c_2\theta ^{-a} = c_1 \\ 1 = \alpha _b = c_2(\theta ^{-b} - \theta ^{-a}) \end{cases} \iff \begin{cases} c_1 = \frac{-\theta ^{-a}}{\theta ^{-b} - \theta ^{-a}} \\ c_2 = \frac{1}{\theta ^{-b} - \theta ^{-a}} \end{cases}
\]
Вероятность выйти на верхний барьер:
\[
\begin{align} \alpha _{s_0} & = \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid S_0 = s_0\right) = \frac{\theta ^{-s_0} - \theta ^{-a}}{\theta ^{-b}-\theta ^{-a}} \\ & = \frac{\theta ^{b-s_0} - \theta ^{b-a}}{1 - \theta ^{b-a}} \\ & = \frac{\theta ^{b-a}}{1 - \theta ^{b-a}} \cdot \left(\theta ^{a - s_0} - 1\right) \end{align}
\]
Вероятность выйти на нижний барьер:
\[
\begin{align} \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = a \mid S_0 = s_0\right) & = 1 - \mathbb {P}\left(S_{\tau _{\left\{ a,b\right\} }} = b \mid S_0 = s_0\right) \\ & = \frac{1 - \theta ^{b-s_0}}{1 - \theta ^{b-a}} \end{align}
\]
График вероятности выиграть P₀(S_τ = 10) при a = -1, s₀ = 0, b = 10, θ = p/(1-p), в зависимости от p.
При \(p = q = \frac{1}{2}\) имеем \[
\mathbb {P}_{s_0}\left(S_\tau = a\right) = \frac{s_0-b}{a-b}, \qquad \mathbb {P}_{s_0}\left(S_\tau = b\right) = \frac{a - s_0}{a-b},
\] При \(p \neq \frac{1}{2}\) \[
\begin{align} \mathbb {P}_{s_0}\left(S_\tau = a\right) & = \frac{1 - \theta ^{b-s_0}}{1 - \theta ^{b-a}}, \\ & \quad \mathbb {P}_{s_0}\left(S_\tau = b\right) = \frac{\theta ^{b-a}}{1 - \theta ^{b-a}} \cdot \left(\theta ^{a - s_0} - 1\right) , \end{align}
\] где \(\theta = \frac{p}{q}\).
Предположим, что игрок в задаче о разорении может уходить в неограниченный минус. Т.е. нижнего барьера теперь нет. Верхний барьер при этом остается. С какой вероятностью игрок все таки выйдет на верхний барьер, а не уйдет в бесконечный минус?
Примечание. Предположите для простоты, что \(s_0 = 0\), \(b = 1\).
Обозначим момент выхода на уровень \(b\) как \(\tau_{b}\). Требуется посчитать \(\mathbb {P}_{s_0}\left(\tau_{b}< \infty \right)\). Заметим, что
\[
\tau _{\left\{ a,b\right\} }(\omega ) \xrightarrow [a \to -\infty ]{} \tau _{b}(\omega ) \qquad \forall \omega \in \Omega
\]
причем \(\tau_{\left\{ a,b\right\} }\) монотонно (поточечно) возрастает к \(\tau_{b}\).
\[
\left\{ \tau _{b} < \infty \right\} = \bigcup _{a = -1}^{-\infty } \left\{ \text{сл. блужд. $S$ вышло на $b$ раньше, чем на $a$}\right\} = \bigcup _{a = -1}^{-\infty } \left\{ S_{\tau _{\left\{ a,b\right\} }} = b\right\}
\]
причем события справа все время расширяются. Значит, можно пользоваться непрерывностью меры.
Далее для простоты предполагаем, что \(s_0 = 0\), \(b = 1\).
\(p = q = \frac{1}{2}\).
\[
\mathbb {P}_{0}\left(\tau _{1} < \infty \right) = \lim _{a \to -\infty }\mathbb {P}_{0}\left(S_{\tau _{\left\{ a,1\right\} }} = 1\right) = \lim _{a \to -\infty } \frac{a}{a - 1} = 1
\]
\(p \neq q\).
\[
\mathbb {P}_{0}\left(\tau _{1} < \infty \right) = \lim _{a \to -\infty }\mathbb {P}_{0}\left(S_{\tau _{\left\{ a,1\right\} }} = 1\right) = \lim _{a \to -\infty } \left( 1 - \frac{1 - \theta ^{1}}{1 - \theta ^{1 - a}}\right) = \begin{cases} 1, & \theta > 1 \\ \theta , & \theta < 1 \end{cases}
\]
Если \(p \geq \frac{1}{2}\), то с вероятностью \(1\). Если \(p < \frac{1}{2}\), то с некоторой ненулевой вероятностью игрок уйдет в бесконечный минус.
В задаче о разорении игрока Пример 1 найдите матожидание длительности игры (если оно существует) в двух случаях:
\(p = \frac{1}{2}\);
\(p \in (0,1)\), \(p \neq \frac{1}{2}\).
Пусть \(m_i = \mathbb {E}_{i}\left[\tau_{a,b}\right]\), \(i \in \left\{ a,a+1, \ldots , b\right\}\). Составьте рекуррентное соотношение для \(m_i\). Решите его.
Задача о разорении при \(a = 0\), \(b = 20\): матожидание длительности игры \(\mathbb{E}_{s_0}\left[\tau_{\left\{a,b\right\}}\right]\) как функция стартового капитала \(s_0\). При \(p = \frac{1}{2}\) это парабола \(s_0(b - s_0)\) с максимумом \(100\) конов в середине полосы; уже небольшой перекос вероятности шага резко сокращает игру – блуждание со сносом быстро доходит до “своего” барьера. Двигайте слайдер \(p\), чтобы увидеть, как форма кривой меняется, и наводите курсор на кривую, чтобы увидеть в этой точке разложение на вероятность выигрыша (дойти до \(b\) раньше, чем до \(a\)) и матожидание длительности игры.
Снова предположим, что игрок в задаче о разорении может уходить в неограниченный минус. Т.е. нижнего барьера теперь нет. Чему теперь будет равно матожидание длительности игры? А именно, покажите, что \[
\mathbb {E}_{s_0}\left[\tau _b\right] = \begin{cases} \frac{b - s_0}{p-q}, & p > \frac{1}{2}\\ +\infty , & p \leq \frac{1}{2} \end{cases}
\]
Итого, в отсутствии нижнего барьера время игры \(\tau_{b}\) ведет себя в зависимости от \(p\) так:
Игра выгодна казино: \(p < \frac{1}{2}\). С некоторой положительной вероятностью \(\tau_b = +\infty\), т.е. игра будет продолжаться бесконечно долго (игрок будет бесконечно долго уходить в минус). И, соотв., матожидание будет бесконечным: \(\mathbb {E}\left[\tau_b\right] = +\infty\).
Честная игра: \(p = \frac{1}{2}\). П.н. игра закончится за конечное время (\(\mathbb {P}\left(\tau_b < \infty \right) = 1\)), однако матожидание у нее все равно будет бесконечным: \(\mathbb {E}\left[\tau_b\right] = +\infty\).
Игра выгодна игроку: \(p > \frac{1}{2}\). В таком случае \(\mathbb {P}\left(\tau_b < \infty \right) = 1\) и \(\mathbb {E}\left[\tau_b\right] < +\infty\).
При помощи рекуррентных соотношений можно полностью найти распределение \(\tau_b\), т.е. вычислить \(\mathbb {P}_{0}\left(\tau_b = k\right)\) для всех \(k\in \mathbb {N}\). Однако проще это сделать через подсчет траекторий, см. ниже.
Докажите, что в задаче о разорении игрока (с двумя поглощающими барьерами) игра кончится за п.н. конечное время, т.е. \(\mathbb {P}\left(\tau_{\left\{ a,b\right\} } < \infty \right) = 1\);
Докажите, что у времени игры \(\tau\) существует любой момент, т.е. \(\mathbb {E}\left[\tau_{\left\{ a,b\right\} }^k\right] < \infty\), \(\forall k \in \mathbb {N}\).
Если в последовательности \(\xi_1, \xi_2, \ldots\) выпадет подряд \((b-a)\) единиц, то игра точно закончится. Т.е. чтобы она никогда не заканчивалась, необходимо, чтобы никогда \((b-a)\) единиц подряд не выпадало.
Предположим в задаче о разорении, что у игрока есть богатый дядя, который гарантирует все его потери. Тогда случайное блуждание не заканчивается, когда сумма попадает в \(a\). Вместо этого \[
\mathbb {P}\left(S_{n+1} = a \mid S_{n} = a\right) = 1-p \quad \text{ и } \quad \mathbb {P}\left(S_{n+1} = a + 1 \mid S_{n} = a\right) = p
\] \(a\) иногда называют удерживающим барьером.
Какова теперь ожидаемая продолжительность игры?
Для простоты можете считать, что \(a = 0\).
Справка: как решать некоторые рекуррентные соотношения
Напомним, как решать рекуррентные линейные отношения второго порядка:
\[
y_{t} = \alpha _1 y_{t-1} + \alpha _2 y_{t-2} + F(t), \qquad t \in \mathbb {Z}
\]
Если \(F(t) \equiv 0\), то рекуррентное соотношение называют однородным. В противном случае неоднородным.
Рассмотрим сначала однородный случай \(y_{t} = \alpha_1 y_{t-1} + \alpha_2 y_{t-2}\). Необходимо сначала выписать характеристический многочлен:
\[
p(\lambda ) = \lambda ^2 - \alpha _1\lambda - \alpha _2
\]
Пусть его корни равны \(\lambda_1, \lambda_2\).
Если \(\lambda_1 \neq \lambda_2\), то решение представляется в виде \(y_t = c_1\lambda_1^t + c_2 \lambda_2^t\);
Если \(\lambda_1 = \lambda_2\), то решение представляется в виде \(y_t = (c_1 + c_2 t) \lambda_1^t\).
Числа \(c_1, c_2 \in \mathbb {R}\) определяются начальными (граничными) условиями.
Решение неоднородного соотношения задается в виде \(y_t = y_t^h + y_t^n\), где \(y_t^h\) – решение соотв. однородного уравнения (без \(F(t)\)), а \(y_t^n\) – произвольное решение неоднородного уравнения. Мы можем найти в явном виде частное решение только в некоторых случаях. Например, если \(F(t) = P(t) \cdot \gamma^t\), где \(P(t)\) – полином степени (не выше) \(2\), \(\gamma \in \mathbb {R}\), причем \(\gamma\) явл. корнем степени \(m = 0,1,2,\ldots\) хар. многочлена однородного соотношения, то неоднородное решение будет иметь вид
\[
y_t^{n} = Q(t) \cdot t^m \cdot \gamma ^t
\]
где \(Q(t)\) – полином степени не выше степени \(P(t)\).
Подсчет траекторий
В предыдущем разделе наша основная техника заключалась в том, чтобы поставить условие на первом шаге блуждания и затем решить вытекающее разностное уравнение. Другой простой но полезной техникой является подсчет траекторий.
Пусть случайное блуждание стартует из нуля. Найдите распределение \(S_n\), т.е. найдите значение функции вероятностей \(\mathbb {P}\left(S_n = b\right) = \mathbb {P}_{0}\left(S_n = b\right)\) для произвольного \(b \in \mathbb {Z}\).
Если \(\left|b\right| > n\), то блуждание не сможет дойти из нуля за \(n\) шагов до \(b\), вероятность нуль.
Если \(\left|b\right| \leq n\), то блуждание из нуля в точку \(b\) сможет дойти, если сделает \(k\) шагов вверх и \(n-k\) шагов вниз, причем
\[
k - (n-k) = b \iff 2k = b + n
\]
т.е. вероятность ненулевая, только если \(b\) и \(n\) одинаковой четности, и в этом случае вероятность равна
\[
\mathbb {P}_{0}\left(S_n = b\right) = C_{n}^k p^k q^{n-k} = C_{n}^{(n+b)/2}p^{(n+b)/2}q^{(n-b)/2}
\]
\[
\mathbb {P}_{0}\left(S_n = b\right) = \begin{cases} 0, & b \leq -n-1 \\ C_{n}^{(n+b)/2}p^{(n+b)/2}q^{(n-b)/2}, & -n \leq b \leq n \text{ и } n \equiv _2 b \\ 0, & -n \leq b \leq n \text{ и } n \not\equiv _2 b \\ 0, & n + 1 \leq b \end{cases}
\]
В дальнейшем мы часто будем использовать \(\mathbb {P}_{0}\left(S_n = b\right)\) как константу.
Пусть \(p=\frac{1}{2}\), т.е. мы рассматриваем симметричное простейшее случайное блуждание.
- Докажите, что в таком случае матожидание модуля случайного блуждания можно вычислить так:
\[
\mathbb {E}_{0}\left[\left|S_{2m - 1}\right|\right] = \mathbb {E}_{0}\left[\left|S_{2m}\right|\right] = 2m \cdot \mathbb {P}_{0}\left(S_{2m} = 0\right) = 2mC_{2m}^m \frac{1}{2^{2m}}
\]
при \(m \geq 1\)
- Найдите асимптотику \(\mathbb {E}\left[\left|S_{n}\right|\right]\).
В пункте б) используйте следствие из формулы Стирлинга: \(C_{2m}^m \sim \frac{2^{2m}}{\sqrt{\pi m}}\) при \(m \to +\infty\).
Нас будет интересовать
когда происходит первый визит случайного блуждания в заданную точку;
какая самая удаленная вправо точка, которую посетило случайное блуждание к моменту времени \(n\).
На эти вопросы можно ответить с помощью некоторых элегантных результатов и методов подсчета траекторий. Первый из них – это принцип отражения. Предположим, мы знаем, что \(S_{0} = a\) и \(S_{n} = b\). Случайное блуждание может посетить или не посетить начало координат между моментами \(0\) и \(n\). Пусть \(N_{n}(a, b)\) — число возможных траекторий от \((0, a)\) до \((n, b)\), и пусть \(N_{n}^{0}(a, b)\) — число таких траекторий, которые содержат некоторую точку \((k, 0)\) на оси \(x\).
Теорема 1 (Принцип отражения) Если \(a, b > 0\), то \(N_{n}^{0}(a, b) = N_{n}(-a, b)\).
Докажите принцип отражения.
Принцип отражения для случайного блуждания: пунктирная линия — отражение начального отрезка [0,k] траектории, идущей из a.
Каждая траектория от \((0,-a)\) до \((n, b)\) пересекает ось \(x\) в некоторой самой ранней точке \((k, 0)\). Отразим отрезок пути с \(0 \leq x \leq k\) по оси \(x\), чтобы получить траекторию из \((0, a)\) в \((n, b)\), пересекающую ось \(x\). Эта операция устанавливает взаимно однозначное соответствие между множествами таких траекторий.
Как и прежде, мы имеем формулу для \(N_{n}(a, b)\): если \(a - n \leq b \leq a+n\) и \((b-a) \equiv_2 n\), то
\[
N_{n}(a, b) = C_{n}^{\frac{1}{2}(n+b-a)}
\]
Теорема о выборах: вероятность, что выигравший кандидат лидировал все время подсчета голосов
Знаменитая «теорема о выборах» является следствием этих элементарных результатов; впервые она была доказана У. А. Уитвортом в 1878 году, но названа в честь Ж. Бертрана, который переоткрыл ее в 1887 г.
Теорема 2 (Бертрана о выборах) В выборах участвовали два кандидата, Алиса и Боб. Пусть мы знаем, что Алиса получила на этих выборах \(a\) голосов, а Боб \(b\) голосов, где \(a>b\), т.е. Алиса победила. Предположим, что голоса считали в случайном порядке. Тогда Алиса лидировала на протяжении всего подсчета голосов с вероятностью \(\frac{a-b}{a+b}\).
Докажите, что доля путей из \((0,0)\) в \((n, b)\) (\(b > 0\)), которые не пересекают нулевой уровень, от общего числа путей из \((0,0)\) в \((n, b)\) составляет \(\frac{b}{n}\).
Докажите теорему Бертрана о выборах.
Максимум случайного блуждания: его распределение и момент его достижения
Еще одна интересная характеристика — максимальное значение, достигаемое случайным блужданием. Обозначим
\[
M_{n} = \max \left\{ S_{i}: 0 \leq i \leq n\right\}
\]
Теорема 3 (о совместном распределении случайного блуждания и его максимума) Для \(r \geq 1\) имеем \[
\begin{align} \mathbb {P}_{0}\left(M_{n} \geq r, S_{n} = b\right) & = \\ & \quad \begin{cases} \mathbb {P}_{0}\left(S_{n} = b\right) & \text{ если } b \geq r, \\ \left(\frac{q}{p}\right)^{r-b} \mathbb {P}_{0}\left(S_{n} = 2 r-b\right) & \text{ если } b < r .\end{cases} \end{align}
\]
Докажите теорему о совместном распределении случайного блуждания и его максимума.
Принцип отражения при поиске совместного распределения Sₙ и Mₙ: после первого достижения уровня r хвост траектории отражается относительно r.
Можно предположить, что \(r \geq 1\) и \(b < r\). Пусть \(N_{n}^{r}(0, b)\) — число траекторий из \((0,0)\) в \((n, b)\), включающих некоторую точку с высотой \(r\), то есть некоторую точку (\(i, r\)) при \(0 < i < n\); для такого пути \(\pi\) пусть \(\left(i_{\pi }, r\right)\) — самая ранняя такая точка. Мы можем отразить отрезок пути с \(i_{\pi } \leq x \leq n\) на прямой \(y = r\), чтобы получить траекторию \(\pi^{\prime }\), соединяющую \((0,0)\) с \((n, 2 r-b)\). Любая такая траектория \(\pi^{\prime }\) получается таким образом из единственной траектории \(\pi\), и поэтому \(N_{n}^{r}(0, b) = N_{n}(0,2 r-b)\). Отсюда следует, что
\[
\begin{aligned} \mathbb {P}_{0}\left(M_{n} \geq r, S_{n} = b\right) & = N_{n}^{r}(0, b) p^{\frac{1}{2}(n+b)} q^{\frac{1}{2}(n-b)} \\ & = (q / p)^{r-b} N_{n}(0,2 r-b) p^{\frac{1}{2}(n+2 r-b)} q^{\frac{1}{2}(n-2 r+b)} \\ & = (q / p)^{r-b} \mathbb {P}_{0}\left(S_{n} = 2 r-b\right) \end{aligned}
\]
Какова вероятность того, что блуждание достигнет нового максимума в определенный момент времени? Точнее, какова вероятность того, что блуждание, начиная с 0, достигнет точки \(b > 0\) в первый раз на \(n\)-ом шаге? Обозначим, как и прежде, момент первого пересечения случайным блужданием \(S_n\) уровня \(y=b\) (время попадания в \(b\)) как \(\tau_b\):
\[
\tau _b := \min \left\{ n \geq 0 \; : \; S_n = b\right\}
\]
Пусть \(S_0 = 0\). Найдите распределение случайной величины \(\tau_b\) для произвольного \(b \geq 1\).
Найдем функцию вероятностей. Для \(n \leq 0\) имеем \(\mathbb {P}_{0}\left(\tau_b = n\right) = 0\). Для \(n \geq 1\) имеем \[
\begin{aligned} \mathbb {P}_{0}\left(\tau _b = n\right) & = \mathbb {P}_{0}\left(M_{n-1} = S_{n-1} = b-1, \; \frac{}{} S_{n} = b\right) = \\ & = \mathbb {P}_{0}\left(M_{n-1} = S_{n-1} = b-1, \; \frac{}{} \xi _{n} = 1\right) = \\ & = \underbrace{\mathbb {P}_{0}\left(\xi _n = 1\right)}_{=p} \cdot \mathbb {P}_{0}\left(M_{n-1} = S_{n-1} = b-1\right) \\ & = p \cdot \bigg[\mathbb {P}_{0}\left(M_{n-1} \geq b-1, \; \frac{}{} S_{n-1} = b-1\right) \\ & \quad -\mathbb {P}_{0}\left(M_{n-1} \geq b, \; \frac{}{} S_{n-1} = b-1\right)\bigg] \\ & = p\cdot \bigg[\mathbb {P}_{0}\left(S_{n-1} = b-1\right) - \frac{q}{p} \cdot \mathbb {P}\left(S_{n-1} = b+1\right)\bigg] = \\ & = \frac{b}{n} \mathbb {P}_{0}\left(S_{n} = b\right) \end{aligned}
\]
Мы доказали следующую теорему.
Теорема 4 (о распределении времени попадания) Вероятность \(\mathbb {P}_{0}\left(\tau_b = n\right)\) того, что случайное блуждание \(S\) впервые попадет в точку \(b\) на \(n\)-м шаге, стартовав из \(0\), такая: \[
\mathbb {P}_{0}\left(\tau _b = n\right) = \frac{|b|}{n} \mathbb {P}_{0}\left(S_{n} = b\right)\quad \text{ для } \quad n \geq 1
\]
Функция вероятностей времени попадания \(\tau_b\) (первого достижения уровня \(b\)): \(\probval[0]{\tau_b = n} = \frac{b}{n}\probval[0]{S_n = b}\); масса сосредоточена на \(n\) той же четности, что и \(b\). Двигайте слайдеры \(b\) и \(p\): при \(p = \frac{1}{2}\) хвост тяжелый, порядка \(n^{-3/2}\) (именно поэтому \(\tau_b\) конечно п.н., но \(\mean[0]{\tau_b} = +\infty\)), а при \(p > \frac{1}{2}\) хвост убывает геометрически. Пунктиром показана асимптотика \(\frac{b}{\sqrt{2\pi}}\, n^{-3/2}\), справедливая при \(p=\frac12\) (при \(p \ne \frac12\) она перестаёт описывать истинный хвост — это видно по расхождению кривых). Внизу — бегущая сумма вероятностей: она стремится к \(1\), если \(p \ge \frac12\), и к \((p/q)^b\), если \(p < \frac12\).
Выше, при помощи условных вероятностей, мы уже находили, с какой вероятностью \(\tau_b\) конечно и в каком случае его матожидание конечно. Сейчас мы получили гораздо более общий результат: мы нашли функцию вероятностей для \(\tau_b\), а она однозначно задает распределение. Можно проверить результаты, полученные в предыдущем разделе, при помощи новых формул:
\[
\mathbb {P}_{0}\left(\tau _{b} < \infty \right) = \sum _{n=1}^{\infty } \mathbb {P}_{0}\left(\tau _{b} = n\right), \qquad \mathbb {E}_{0}\left[\tau _b\right] = \begin{cases} +\infty , & \mathbb {P}_{0}\left(\tau _{b} = +\infty \right) > 0 \\ \sum _{n=1}^{+\infty } n\mathbb {P}_{0}\left(\tau _{b} = n\right), & \mathbb {P}_{0}\left(\tau _{b} = +\infty \right) = 0 \end{cases}
\]
Если кому-то это интересно, можете самостоятельно проверить.
Итого, мы полностью охарактеризовали распределение времени \(\tau_b\).
Пусть \(p = \frac{1}{2}\), т.е. случайное блуждание симметрично. Покажите, что в таком случае функцию масс для максимума можно вычислить так: \[
\mathbb {P}_{0}\left(M_n = r\right) = \mathbb {P}_{0}\left(S_{n} = r\right) + \mathbb {P}_{0}\left(S_{n} = r+1\right)
\]
Вероятность не вернуться в начало
Мы уже вводили время достижения какого-то уровня:
\[
\tau _{i} = \min \left\{ n \geq 0 \; : \; S_{n} = i\right\}
\]
Введем время достижения после \(1\)-го шага:
\[
T_{i} := \min \left\{ n \geq 1 \; : \; S_{n} = i\right\}
\]
(это все стандартные обозначения). Эти случайные величины очень похожи: если блуждание стартует не из состояния \(i\), то они совпадают:
\[
\mathbb {P}_{j}\left(T_{i} = \tau _{i}\right) = 1, \qquad i \neq j
\]
Выше мы уже полностью изучили \(\tau_{i}\), так что и распределение \(T_{i}\) мы полностью понимаем в этом случае.
Однако если цепь стартует из состояния \(i\), то смысла в \(\tau_{i}\) особо нет, это тождественный ноль. А вот \(T_i\) будет обозначать время возврата в \(i\), это нечто осмысленное. Найдем распределение \(T_i\) в этом случае. Не огр. общности, пусть \(S_0 = i = 0\), т.е. цепь стартует из нуля. Будем искать функцию выживания \(T_{0}\):
\[
\underbrace{\mathbb {P}_{0}\left(T_{0} > n\right)}_{\text{функция выживания}} \quad = \quad 1 - \underbrace{\mathbb {P}_{0}\left(T_{0} \leq n\right)}_{\text{функция распределения}} , \qquad n \geq 1
\]
Это вероятность, с которой случайное блуждание не вернется в начальную точку за первые \(n\) шагов. Как и функция распределения, функция выживания полностью задает само распределение.
Найдите \[
\mathbb {P}_{0}\left(T_{0} > n, S_{n} = b\right)
\]
Предположим, что \(S_{0} = 0\) и \(S_{n} = b > 0\). Рассматриваемое событие происходит тогда и только тогда, когда траектория случайного блуждания не посещает ось \(x\) в интервале времени \([1, n]\). Число таких траекторий равно \((b / n) N_{n}(0, b)\), и каждая такая траектория имеет \(\frac{1}{2}(n+b)\) шагов вправо и \(\frac{1}{2}(n-b)\) шагов влево. Поэтому \[
\mathbb {P}_{0}\left(T_{0} > n, S_{n} = b\right) = \frac{b}{n} N_{n}(0, b) p^{\frac{1}{2}(n+b)} q^{\frac{1}{2}(n-b)} = \frac{b}{n} \mathbb {P}_{0}\left(S_{n} = b\right)
\] Аналогичное вычисление справедливо для \(b < 0\).
\(\mathbb {P}_{0}\left(T_{0} > n, S_{n} = b\right) = \frac{\left|b\right|}{n}\mathbb {P}_{0}\left(S_{n} = b\right)\)
Найдите функцию выживания для \(T_0\). А именно, докажите, что
\[
\mathbb {P}_{0}\left(T_{0} > n\right) = \frac{1}{n} \mathbb {E}_{0}\left[\left|S_{n}\right|\right]
\]
Найдите, с какой вероятностью случайное блуждание никогда не возвратится в стартовую точку. А именно, покажите, что
\[
\mathbb {P}_{0}\left(T_{0} = +\infty \right) = \left|2p - 1\right|
\]
Таким образом, при \(p \neq \frac{1}{2}\) случайное блуждание, выйдя из нуля, с некоторой ненулевой вероятностью никогда в него не вернется: \(\mathbb {P}_{0}\left(T_{0} = +\infty \right) > 0\). Разумеется, в этом случае \(\mathbb {E}_{0}\left[T_{0}\right] = +\infty\). Если же \(p = \frac{1}{2}\), то \(T_{0}\) п.н. конечно: \(\mathbb {P}_{0}\left(T_{0} < +\infty \right) = 1\). Но что с матожиданием?
Пусть \(p=\frac{1}{2}\), т.е. рассматриваем симметричное простейшее случайное блуждание.
- Найдите функцию вероятностей для \(T_0\) при условии \(S_0 = 0\). А именно, покажите, что распределение \(T_0\) сосредоточено в четных точках, причем
\[
\mathbb {P}_{0}\left(T_0 = 2m\right) = \frac{1}{2m - 1}\mathbb {P}_{0}\left(S_{2m} = 0\right) = \frac{1}{2m-1} C_{2m}^{m} \frac{1}{2^{2m}}, \quad m \in \mathbb {N}
\]
- Покажите, что \(\mathbb {E}_{0}\left[T_0^{\alpha }\right] < \infty\) тогда и только тогда, когда \(\alpha < \frac{1}{2}\). В частности, покажите, что \(\mathbb {E}_{0}\left[T_0\right] = +\infty\).
используйте следствие из формулы Стирлинга: \(C_{2m}^m \sim \frac{2^{2m}}{\sqrt{\pi m}}\) при \(m \to +\infty\).
(*) Симметричное простейшее случайное блуждание: законы арксинуса
В данном параграфе мы всюду предполагаем, что случайное блуждание симметрично и стартует из нуля: \(S_0 = 0\), \(p = \frac{1}{2}\). Факты, которые нам уже известны:
Матожидание модуля: \(\frac{1}{2m}\mathbb {E}_{0}\left[\left|S_{2m - 1}\right|\right] = \frac{1}{2m}\mathbb {E}_{0}\left[\left|S_{2m}\right|\right] = \mathbb {P}_{0}\left(S_{2m} = 0\right) = C_{2m}^{m}\frac{1}{2^{2m}}\) (из Задача 5);
Распределение максимума: \(\mathbb {P}_{0}\left(M_n = r\right) = \mathbb {P}_{0}\left(S_n = r\right) + \mathbb {P}_{0}\left(S_n = r+1\right)\) (из Задача 7);
Время возврата: \(\mathbb {P}_{0}\left(T_0 < \infty \right) = 1\), но \(\mathbb {E}_{0}\left[T_0\right] = +\infty\)
Последний момент обнуления
Фиксируем \(n \in \mathbb {N}\). Обозначим \(\operatorname {LZ}_{n} = \operatorname {LastZero}_{n}\) момент последнего попадания в \(0\) случайного блуждания перед моментом \(n\). Заметим, что \(\operatorname {LZ}_{2m} = \operatorname {LZ}_{2m + 1}\), поскольку на нечетном шаге нельзя попасть в ноль. Поэтому в дальнейшем мы будем изучать распределение \(\operatorname {LZ}_{n}\) при \(n = 2m\), т.е. при четных \(n\).
Найдите распределение \(\operatorname {LZ}_{2m}\), \(m \in \mathbb {N}\). А именно, покажите, что оно сосредоточено на четных числах от \(0\) до \(2m\), причем \[
\mathbb {P}_{0}\left(\operatorname {LZ}_{2m} = 2k\right) = \mathbb {P}_{0}\left(S_{2 k} = 0\right) \cdot \mathbb {P}_{0}\left(S_{2 m-2 k} = 0\right)
\] для \(k = 0,1,\ldots ,m\).
\(\operatorname {LZ}_{2m}\) – это дискретная случайная величина, которая может принимать только четные неотрицательные значения \(0,2,4,\ldots ,2m\), поскольку в ноль можно попасть только на четном шаге. Пусть \(0 \leq k \leq m\). Имеем
\[
\begin{align} \mathbb {P}\left(\operatorname {LZ}_{2m} = 2k\right) & = \mathbb {P}\left(S_{2k} = 0, \quad S_{2k + 1}, \ldots , S_{2m} \neq 0\right) = \\ & = \mathbb {P}\left(S_{2 k} = 0\right) \cdot \mathbb {P}\left(S_{2 k+1} S_{2 k+2} \cdots S_{2 m} \neq 0 \mid S_{2 k} = 0\right) \\ & = \mathbb {P}\left(S_{2 k} = 0\right) \cdot \mathbb {P}\left(S_{1} S_{2} \cdots S_{2 m-2 k} \neq 0\right) = \\ & = \mathbb {P}\left(S_{2 k} = 0\right) \cdot \mathbb {P}\left(T_{0} > 2m-2k\right) = \\ & = \mathbb {P}\left(S_{2 k} = 0\right) \cdot \frac{1}{2m-2k} \mathbb {E}\left[\left|S_{2m-2k}\right|\right] \end{align}
\]
Пока мы не пользовались тем, что случайное блуждание симметрично.
Чтобы получить ответ, нужно вспомнить (см. пример Задача 5), что для симметричного случайного блуждания
\[
\frac{1}{2m-2k} \mathbb {E}\left[\left|S_{2m-2k}\right|\right] = \mathbb {P}_{0}\left(S_{2m-2k} = 0\right)
\]
Точное распределение момента последнего нуля \(\operatorname{LZ}_{2m}\) симметричного блуждания: \(\probval[0]{\operatorname{LZ}_{2m} = 2k} = u_{2k}\, u_{2m - 2k}\), где \(u_{2j} = \probval[0]{S_{2j} = 0} = C_{2j}^{j}/2^{2j}\) (синие стемы), поверх асимптотической U-образной кривой \(\frac{1}{\pi\sqrt{k(m-k)}}\) (красная), дающей в пределе плотность арксинуса. Двигайте слайдер \(m\), чтобы увидеть, как при росте \(m\) стемы “уплотняются” к этой кривой: последний ноль чаще всего оказывается совсем рядом с началом или с концом отрезка наблюдения. Снизу — одна смоделированная траектория блуждания длины \(2m\) с отмеченным на ней последним нулём; кнопка перегенерирует траекторию.
Рассмотрим нормированную случайную величину \(\frac{1}{n}\operatorname {LZ}_{n}\). Это случайная величина со значениями в \([0,1]\), показывающая, насколько давно был последний \(0\) относительно всего прошедшего времени.
Найдите предельное распределение \(\frac{1}{n}\operatorname {LZ}_{n}\).
Будем искать предельное распределение для \(\frac{1}{2m}\operatorname {LZ}_{2m}\).
По формуле Стирлинга:
\[
\begin{align} \mathbb {P}_{0}\left(S_{2k} = 0\right) & = C_{2k}^{k}\frac{1}{2^{2k}} \sim \frac{1}{\sqrt{\pi k}} \end{align}
\]
при \(k \to +\infty\). Тогда
\[
\mathbb {P}_{0}\left(\operatorname {LZ}_{2m} = 2k\right) \sim \frac{1}{\pi \sqrt{k(m-k)}}
\]
Это справедливо для значений \(k\), которые не близки ни к \(0\), ни к \(n\). Тогда
\[
\begin{align} \mathbb {P}\left(\frac{\operatorname {LZ}_{2n}}{2n} \leq x\right) & \sim \sum _{k \leq x n} \frac{1}{\pi \sqrt{k(n-k)}} \\ & \sim \int _{u = 0}^{x n} \frac{1}{\pi \sqrt{u(n-u)}} d u \\ & = \frac{2}{\pi } \arcsin (\sqrt{x}) \end{align}
\]
Распределение на \([0,1]\) с функцией распределения \(\frac{2}{\pi }\arcsin (\sqrt{x})\) называется распределением арксинуса и обозначается \(\operatorname {Arcsine}\). Его плотность:
\[
f(x) = \frac{1}{\pi \sqrt{x(1-x)}} \cdot \; \mathbb {1}_{[0,1]}(x)
\]
Т.е. это частный случай Бета-распределения: \(\operatorname {Arcsine} = \operatorname {Beta}(\frac{1}{2}, \frac{1}{2})\).
Мы доказали
Лемма 2 (Закон арксинуса для времени последнего нуля) Пусть \(S_{n}\) – симметричное простейшее случайное блуждание, стартующее из нуля. Тогда \[
\frac{1}{n}\operatorname {LZ}_{n} \xrightarrow [n \to \infty ]{d} \operatorname {Arcsine}
\]
Распределение арксинуса: функция распределения F(x) = (2/π)·arcsin(√x) и плотность f(x) = 1/(π·√(x(1-x))), x ∈ [0,1] (график плотности обрезан по y ≤ 3 — плотность неограничена на концах отрезка).
Закон арксинуса довольно примечателен. Можно подумать, что в длинном ряду из \(2 m\) подбрасываний честной монетки периоды времени, в которые появлялось равное количество орлов и решек, должны возникать довольно часто. Однако оказывается, что с вероятностью \(\frac{1}{2}\) в последних \(m\) подбрасываниях не наступит такого периода, и, более того, с вероятностью примерно \(\frac{1}{5}\) после первых \(\frac{1}{5} m\) подбрасываний не наступит такого периода.
Можно думать, что в длинной серии из \(2m\) подбрасываний честной монетки последний момент, когда число орлов и решек было одинаковым, как правило, находится ближе к концу. Реальность сильно расходится с интуицией: распределение этого времени симметрично около середины (\(m\)).
Сколько времени блуждание проводит в плюсе
Сколько времени симметричное случайное блуждание проводит на положительной полуоси? Говорим, что случайное блуждание провело временной интервал \((k,k+1)\) в плюсе, если \(S_k > 0\) или \(S_{k+1} > 0\) (соседние значения отличаются ровно на \(1\), поэтому в этом случае отрезок траектории между ними лежит выше оси – не считая, возможно, одного из концов). Пусть \(\operatorname {SI}_{n} = \operatorname {SojournIntervals}_{n}\) – это количество таких интервалов (длины \(1\)) за время с \(0\) до \(n\):
\[
\begin{align} \operatorname {SI}_{n} & := \; \mathbb {1}_{\left\{ S_{0} >0 \text{ или } S_{1} > 0\right\} } + \; \mathbb {1}_{\left\{ S_{1} >0 \text{ или } S_{2} > 0\right\} } \\ & \quad + \ldots + \; \mathbb {1}_{\left\{ S_{n-1} >0 \text{ или } S_{n} > 0\right\} } \end{align}
\]
Обратите внимание на <<или>> в конвенции: интервал, примыкающий к нулю траектории, приписывается той стороне, на которой траектория проводит сам интервал. С конвенцией <<и>> утверждение следующей задачи было бы неверно (проверьте на \(n = 2\)!).
Мы уже находили предельное распределение для \(\frac{1}{n}\operatorname {LZ}_{n}\). Оно будет таким же и для \(\frac{1}{n}\operatorname {SI}_{n}\). Получаем
Лемма 3 (Закон арксинуса для интервалов простоя в плюсе) Пусть \(S_{n}\) – симметричное простейшее случайное блуждание, стартующее из нуля. Тогда \[
\frac{1}{n}\operatorname {SI}_{n} \xrightarrow [n \to \infty ]{d} \operatorname {Arcsine}
\]
Опять же, интуитивно можно было бы ожидать, что ответ будет около \(n\) с большой вероятностью, но на самом деле все обстоит совсем иначе. С большой вероятностью доля времени, проведенного справа (или слева) от начала координат, близка к 0 или к 1, но не близка к \(\frac{1}{2}\). Иными словами, при длинной последовательности подбрасываний честной монетки велика вероятность того, что одна из граней (либо голова, либо решка) будет опережать другую на непропорционально большое количество времени.
Момент достижения максимума
Пусть \(\operatorname {AM}_{n} = \operatorname {ArgMax}_n := \min \left(\operatorname *{arg\, max}_{k \in \left\{ 0,\ldots ,n\right\} }S_{k}\right)\) – момент, в который случайное блуждание впервые достигает своего максимума на отрезке времени \(\left\{ 0, \ldots , n\right\}\). Оказывается, при \(0 < 2k\) и \(2k + 1 < 2m\) выполнено
\[
\begin{align} \mathbb {P}_{0}\left(\operatorname {AM}_{2m} = 2k\right) = \mathbb {P}_{0}\left(\operatorname {AM}_{2m} = 2k + 1\right) = \frac{1}{2}\, \mathbb {P}_{0}\left(S_{2k} = 0 \right) \cdot \mathbb {P}_{0}\left(S_{2m-2k} = 0\right) \end{align}
\]
(ср. (Feller 1968 г., III, 7)).
Докажите формулу для распределения момента первого максимума \(\operatorname {AM}_{2m}\). Разберите заодно краевые случаи: чему равны \(\mathbb {P}_{0}\left(\operatorname {AM}_{2m} = 0\right)\) и \(\mathbb {P}_{0}\left(\operatorname {AM}_{2m} = 2m\right)\)?
Разрежьте траекторию в точке первого максимума; на левом куске обратите время. Пригодятся факты из шага 1 решения задачи о \(\operatorname {SI}_{2m}\).
Пусть \(0 \leq l \leq 2m\). Событие \(\left\{ \operatorname {AM}_{2m} = l\right\}\) – пересечение двух событий, зависящих от непересекающихся наборов шагов (и потому независимых):
\(A_l\): максимум на \(\left\{ 0, \ldots , l\right\}\) впервые достигается ровно в \(l\), т.е. \(S_i < S_l\) для всех \(0 \leq i < l\) (зависит только от \(\xi_1, \ldots , \xi_l\));
\(B_l\): после момента \(l\) траектория не поднимается выше, т.е. \(S_{l+j} - S_l \leq 0\) для всех \(1 \leq j \leq 2m-l\) (зависит только от \(\xi_{l+1}, \ldots , \xi_{2m}\)).
Вероятность \(B_l\). Процесс \((S_{l+j} - S_l)_{j \geq 0}\) – снова симметричное блуждание из нуля, поэтому, с учетом симметрии \(S \mapsto -S\),
\[
\mathbb {P}\left(B_l\right) = \mathbb {P}_{0}\left(S_1 \geq 0, \ldots , S_{2m-l} \geq 0\right)
\]
В шаге 1 решения задачи о \(\operatorname {SI}_{2m}\) мы показали, что для четных длин \(\mathbb {P}_{0}\left(S_1 \geq 0, \ldots , S_{2j} \geq 0\right) = u_{2j}\); нечетная длина \(2j-1\) дает ту же вероятность, поскольку из \(S_{2j-1} \geq 0\) по четности автоматически следует \(S_{2j} \geq 0\). Поэтому и для \(l = 2k\), и для \(l = 2k+1\)
\[
\mathbb {P}\left(B_l\right) = u_{2m - 2k}
\]
Вероятность \(A_l\). Обратим время на первых \(l\) шагах: положим \(\xi '_{j} := \xi_{l-j+1}\) – это снова независимые симметричные шаги, и для соответствующего блуждания \(S'_j := \xi '_1 + \ldots + \xi '_j = S_l - S_{l-j}\) условие \(\left\{ S_i < S_l \; \; \forall \, i < l\right\}\) превращается в \(\left\{ S'_j > 0 \; \; \forall \, 1 \leq j \leq l\right\}\). Снова по шагу 1: \(\mathbb {P}_{0}\left(S_1 > 0, \ldots , S_{2k} > 0\right) = \frac{1}{2}u_{2k}\), и нечетная длина \(2k+1\) дает ту же вероятность: \(S_{2k} > 0\) – четное число, т.е. \(S_{2k} \geq 2\), откуда \(S_{2k+1} \geq 1 > 0\) автоматически. Поэтому для \(l \in \left\{ 2k, 2k + 1\right\}\), \(l \geq 1\),
\[
\mathbb {P}\left(A_l\right) = \frac{1}{2} u_{2k}
\]
Сборка. Перемножая, для \(l = 2k \geq 2\) и для \(l = 2k + 1 \leq 2m - 1\) получаем
\[
\mathbb {P}_{0}\left(\operatorname {AM}_{2m} = l\right) = \mathbb {P}\left(A_l\right) \cdot \mathbb {P}\left(B_l\right) = \frac{1}{2}\, u_{2k}\, u_{2m-2k}
\]
Краевые случаи: при \(l = 0\) событие \(A_0\) тривиально (\(\mathbb {P}\left(A_0\right) = 1\)), поэтому \(\mathbb {P}_{0}\left(\operatorname {AM}_{2m} = 0\right) = u_{2m}\) – множитель \(\frac{1}{2}\) пропадает; при \(l = 2m\) тривиально уже \(B_{2m}\), и \(\mathbb {P}_{0}\left(\operatorname {AM}_{2m} = 2m\right) = \frac{1}{2}u_{2m}\) (это частный случай общей формулы при \(k = m\)).
Сложим вероятности в парах \(\left\{ 2k, 2k+1\right\}\): при \(1 \leq k \leq m-1\)
\[
\mathbb {P}_{0}\left(\operatorname {AM}_{2m} \in \left\{ 2k, 2k+1\right\} \right) = u_{2k} \, u_{2m-2k} = \mathbb {P}_{0}\left(\operatorname {LZ}_{2m} = 2k\right)
\]
Т.е. с точностью до краевых слагаемых (а они порядка \(u_{2m} \sim \frac{1}{\sqrt{\pi m}} \to 0\) и на предел не влияют) момент первого максимума распределен как момент последнего нуля! Предельный переход поэтому дословно тот же, что и раньше, и мы получаем третий закон арксинуса.
Лемма 4 (Закон арксинуса для момента достижения максимума) Пусть \(S_{n}\) – симметричное простейшее случайное блуждание, стартующее из нуля. Тогда \[
\frac{1}{n}\operatorname {AM}_{n} \xrightarrow [n \to \infty ]{d} \operatorname {Arcsine}
\]
Какие еще бывают законы арксинуса? Семейство подобных результатов заметно шире трех доказанных фактов.
По симметрии \(S \mapsto -S\) те же законы верны для доли времени в минусе и для момента достижения минимума; вместо первого момента максимума можно взять последний – предел не изменится.
Все три закона (П. Леви, 1939) выполнены и для броуновского движения на отрезке \([0,1]\): арксинусно распределены момент последнего нуля, доля времени выше нуля и точка максимума траектории. С последним фактом мы еще встретимся в главе про марковские моменты.
Универсальность (теорема Спарре Андерсена): предельный закон арксинуса для доли времени в плюсе верен для любого случайного блуждания с симметричным безатомным распределением шага – результат по сути комбинаторный и от конкретного распределения не зависит.
Обобщенные законы арксинуса (Спицер, Ламперти): если \(\mathbb {P}\left(S_n > 0\right) \xrightarrow [n \to \infty ]{} \rho \in (0, 1)\), то доля времени в плюсе сходится по распределению к \(\operatorname {Beta}(\rho , 1 - \rho )\); при \(\rho = \frac{1}{2}\) это в точности распределение арксинуса.
использованная литература
Feller, William. 1968 г. An Introduction to Probability Theory and Its Applications, Vol. 1. 3-я изд. Wiley.