§6. Принцип отражения: зеркало для случайного блуждания

Материал этого параграфа в основном взят из главы III замечательной книги У. Феллера «Введение в теорию вероятностей и её приложения», которую Лагутин настоятельно рекомендует прочитать. В конце параграфа результаты применяются к двум задачам проверки однородности.

Пути

Рассмотрим случайное блуждание $S_n = \xi_1 + \dots + \xi_n$, где независимые «шаги» $\xi_i$ принимают значения $+1$ и $-1$ с вероятностью $1/2$. Траекторией (путём) блуждания длины $n$ назовём ломаную через точки $(i, S_i)$, $i = 1, \dots, n$. Каждый из $2^n$ путей имеет вероятность $2^{-n}$.

Обозначим через $N_{n,m}$ количество путей из $(0, 0)$ в $(n, m)$. Если у пути $k$ шагов вверх и $l$ вниз, то $k + l = n$, $k - l = m$, откуда $k = (n + m)/2$. Расставить $k$ «плюс единиц» по $n$ местам можно $C^k_n$ способами:

где биномиальный коэффициент считается равным 0, если $(n + m)/2$ — не целое число между 0 и $n$.

Пусть $a$ и $b$ — положительные целые. Перенесём начало блуждания из 0 в $a$ и потребуем, чтобы в момент $n$ траектория пришла в точку $(n, b)$. Таких путей $N_{n,b-a}$. Сколько из них положительных, то есть лежат целиком над осью абсцисс?

Принцип отражения. Число путей из $(0, a)$ в $(n, b)$, касающихся или пересекающих ось абсцисс, совпадает с числом путей из $(0, a)$ в $(n, -b)$, которое равно $N_{n,a+b}$.

Доказательство. Пусть $\tau$ — момент первого касания осью. Отразим относительно оси участок пути от $(\tau, 0)$ до $(n, b)$ и присоединим к начальному участку от $(0, a)$ до $(\tau, 0)$. Получим путь из $(0, a)$ в $(n, -b)$. По построенному пути исходный восстанавливается однозначно — достаточно отразить его после первого касания оси. $\blacksquare$

(В виджете ниже отражается начальный участок — до $\tau$. Это равносильно: путь из $(0, -a)$ в $(n, b)$ тоже обязан пересечь ось, и таких путей тоже $N_{n,a+b}$.)

Следствие. Количество положительных траекторий из $(0, a)$ в $(n, b)$ равно $N_{n,b-a} - N_{n,a+b}$.

Геометрическая задача. По всей ширине дороги рассыпано зерно. Слева от дороги на заборе высоты $a$ сидит ворона. Она хочет поклевать зёрна, а затем перелететь на забор высоты $b$ ($b > a$) справа от дороги. В каком месте ей приземлиться, чтобы общая длина двух перелётов была минимальной? (Вопрос 6.)

Задача о баллотировке

Частный случай следствия — результат У. Уитворта (1878), заново полученный Ж. Бертраном в 1887 году.

Задача о баллотировке. На выборах первый кандидат набрал $k$ голосов, второй — $l$, причём $k > l$. Вероятность того, что при последовательном подсчёте голосов первый всё время был впереди второго, равна $(k - l)/(k + l)$.

Доказательство. Нужная траектория обязательно проходит через точку $(1, 1)$. По следствию и формуле (12) число положительных путей из $(1, 1)$ в $(k + l, k - l)$ (здесь $n = k + l - 1$, $a = 1$, $b = k - l$) равно

Простыми преобразованиями правая часть приводится к $N_{k+l,k-l}\,(k - l)/(k + l)$. $\blacksquare$

Смысл по-пацански: победил 6:4 — шанс, что ты лидировал с первого же бюллетеня до последнего, всего $2/10$. Даже убедительная победа обычно идёт с качелями.

Возвращения в ноль

Среди путей длины $2n$ выделим приходящие в $(2n, 0)$:

Формула Стирлинга ($n! \sim \sqrt{2\pi n}\,n^ne^{-n}$) даёт асимптотику

Доля траекторий, приходящих в $(2n, 0)$, стремится к нулю со скоростью порядка $1/\sqrt n$ (решение задачи 5 главы 12). Оказывается, неотрицательных путей за время $2n$ ровно столько же, сколько путей, приходящих в $(2n, 0)$.

Теорема 1. При всех $n$ справедливо равенство $\mathbf P(S_1 \ge 0, \dots, S_{2n} \ge 0) = u_{2n}$.

Доказательство. Э. Нельсон предложил оригинальное взаимно однозначное преобразование путей, приходящих в 0, в неотрицательные. Обозначим через $M = (k, -m)$ самую левую (если их несколько) точку глобального минимума пути, ведущего в $(2n, 0)$. Отразим участок от начала до $M$ относительно вертикальной прямой $x = k$ и перенесём его так, чтобы его начальная точка совпала с концом $(2n, 0)$. Примем $M$ за начало новой системы координат: в ней путь ведёт из начала в $(2n, 2m)$, а все его вершины лежат не ниже оси абсцисс. $\blacksquare$

Рассмотрим траектории, не возвращающиеся в 0 за время $2n$. Каждая из них либо положительная, либо отрицательная (не считая начальной точки). Из симметрии и вопроса 7

Пусть $B_{2n} = \{S_{2n} = 0\}$, а $f_{2n} = \mathbf P(A_{2n-2}B_{2n})$ — вероятность вернуться в 0 впервые в момент $2n$. Ввиду (15)

С учётом $u_0 = 1$ и $u_{2n} \to 0$ отсюда получаем, что вероятность вернуться в 0 когда-нибудь $f_2 + f_4 + \dots = 1$. Из (13) и (16) легко выводится тождество

Асимптотика (14) даёт для $f_{2n}$ порядок малости $n^{-3/2}$. Поэтому $\sum 2nf_{2n} \sim c\sum1/\sqrt n = \infty$: среднее время до первого возвращения бесконечно.

Смысл по-пацански: пацан идёт по улице и на каждом перекрёстке подбрасывает монетку: орёл — шаг вперёд, решка — назад. К своему подъезду он обязательно вернётся. Но ждать этого в среднем придётся бесконечно долго. Это не противоречие: почти всегда возвращается быстро, но изредка забредает так далеко, что среднее улетает в бесконечность.

Пусть $g_{2n-1}$ — вероятность впервые достигнуть уровня 1 на $(2n-1)$-м шаге.

Теорема 2. Имеет место равенство $g_{2n-1} = f_{2n}$.

Доказательство. Величина $K_n = 2^{2n-1}g_{2n-1}$ совпадает с числом отрицательных (кроме крайних точек) путей из $(1, -1)$ в $(2n, 0)$. Соединив точку $(1, -1)$ с началом координат, получим траекторию, впервые возвращающуюся в 0 в момент $2n$. Сопоставим исходному пути эту траекторию и симметричную ей относительно оси абсцисс. Так как исходный путь по этим траекториям определяется однозначно, $2^{2n}f_{2n} = 2K_n$. $\blacksquare$

Из теоремы 2 следует, что среднее время до первого достижения любого уровня $h > 0$ симметричным блужданием бесконечно (это использовалось в контрпримере к тождеству Вальда, §3 главы 13).

Проверим формулы (17) и теоремы 2 полным перебором путей и сравним точный хвост одностороннего Смирнова с пределом (это понадобится в конце параграфа):

Закон арксинуса

Обозначим через $\nu_{2n}$ момент последнего попадания в 0 за время $2n$. Положим $\alpha_{2i,2n} = \mathbf P(\nu_{2n} = 2i)$, $i = 0, 1, \dots, n$.

Теорема 3. Справедливо соотношение $\alpha_{2i,2n} = u_{2i}\,u_{2n-2i}$.

Доказательство. Нас интересуют пути, у которых $S_{2i} = 0$ и $S_{2i+1} \ne 0, \dots, S_{2n} \ne 0$. Первые $2i$ вершин можно выбрать $2^{2i}u_{2i}$ способами. Взяв точку $(2i, 0)$ за новое начало координат, по равенству (15) остальные $2n - 2i$ вершин можно выбрать $2^{2n-2i}u_{2n-2i}$ способами. Всего $2^{2n}u_{2i}u_{2n-2i}$ вариантов. $\blacksquare$

Из теоремы 3 и асимптотики (14) следует, что предельным законом для $\nu_{2n}/(2n)$ является распределение арксинуса с функцией распределения $F(x) = (2/\pi)\arcsin\sqrt x$ и плотностью $p(x) = 1/(\pi\sqrt{x(1 - x)})$, $0 < x < 1$ (её график — на рис. 8 главы 5):

Смысл по-пацански: два игрока бросают монетку тысячу раз. Интуиция говорит: лидер меняется постоянно, последняя ничья где-то в середине. А закон арксинуса говорит: самые вероятные моменты последней ничьей — у самого начала и у самого конца. С вероятностью около 0,4 последняя ничья случается в первые или последние 10 % игры, и дальше один и тот же игрок лидирует почти всё время.

Оказывается, время, в течение которого траектория находилась в полуплоскости $y \ge 0$, распределено так же, как $\nu_{2n}$ (§4 главы 16). Но если ограничиться путями, приходящими в момент $2n$ в 0, то условная вероятность того, что ровно $2i$ ($i = 0, 1, \dots, n$) их звеньев лежат над осью абсцисс, равна $1/(n + 1)$ — независимо от $i$. Это утверждение известно как теорема о равнораспределённости.

Доказательство (набросок). Случай $i = n$: число путей в $(2n, 0)$ со всеми звеньями выше оси равно числу положительных путей из $(0, 2)$ в $(2n - 1, 1)$, то есть по следствию принципа отражения $C^n_{2n-1} - C^{n+1}_{2n-1} = \frac1{n+1}C^n_{2n}$. По симметрии то же верно при $i = 0$. При $1 \le i \le n - 1$ — индукция по $n$. Разобьём путь по моменту $2r$ первого возвращения в 0. Если начальный участок до $2r$ лежит над осью ($1 \le r \le i$), то после $2r$ должно быть ровно $2i - 2r$ звеньев над осью. По предположению индукции и формуле (17) таких путей

Если начальный участок под осью ($1 \le r \le n - i$), получаем то же выражение. Сумма по $r$ этих двух групп после замены $j = n - r + 1$ во второй сумме превращается в сумму (18) по всем $1 \le r \le n$ — она не зависит от $i$. $\blacksquare$

Применение: статистика Гальтона

Применим эти результаты к проверке гипотезы однородности $H_0$ двух независимых выборок $\mathbf X = (X_1, \dots, X_n)$ и $\mathbf Y = (Y_1, \dots, Y_n)$ одинакового размера, без совпадений (Д3 гарантирует это с вероятностью 1). Упорядочим каждую выборку: $X_{(1)} < \dots < X_{(n)}$ и $Y_{(1)} < \dots < Y_{(n)}$. Пусть $L$ — число индексов $i$, при которых $X_{(i)} < Y_{(i)}$. Близость $L$ к $n$ указывает, что альтернатива доминирования $H_2$ предпочтительнее $H_0$. Для критической границы нужен закон $L$ при $H_0$.

Переведём задачу на язык блужданий. Упорядочим все $2n$ значений обеих выборок в один ряд. Пусть $\xi_k = -1$ или $+1$ в зависимости от того, из $\mathbf X$ или из $\mathbf Y$ $k$-й член ряда, и $S_k = \xi_1 + \dots + \xi_k$. Полный путь длины $2n$ соединяет начало с точкой $(2n, 0)$.

Событие $X_{(k)} < Y_{(k)}$ происходит тогда и только тогда, когда $S_{2k-1}$ содержит не меньше $k$ «плюс единиц», то есть $S_{2k-1} > 0$. Тогда $S_{2k} \ge 0$, и $(2k-1)$-е и $2k$-е звенья лежат выше оси. Значит, $L = l$ тогда и только тогда, когда ровно $2l$ звеньев выше оси. По теореме о равнораспределённости эта вероятность равна $1/(n + 1)$ независимо от $l$.

Статистику $L$ впервые использовал Ф. Гальтон, исследуя данные, присланные ему Чарльзом Дарвином. Значения $l$ и $n$ были равны 13 и 15. Не зная реальных вероятностей, Гальтон отверг $H_0$. Однако при $H_0$ вероятность того, что $L$ примет значение 13 и более (фактический уровень значимости, §1 главы 12), равна $3/16$. Другими словами, в 3 случаях из 16 будет наблюдаться такое же или большее превосходство $\mathbf Y$ над $\mathbf X$ при полном совпадении законов. Феллер по этому поводу замечает, что численный анализ бывает полезным дополнением к интуиции, которая не всегда надёжна.

Смысл по-пацански: 13 из 15 — выглядит как разгром. А на деле при честной игре такое бывает чаще, чем раз из шести. Прежде чем кричать «доказано!», посчитай.

Предельный закон одностороннего Смирнова

В заключение получим с помощью принципа отражения предельную теорему (2) из §3 для $D^+_{n,m} = \sup_x(\hat F_n(x) - \hat G_m(x))$ при $m = n$. Заметим, что для любого $l = 1, \dots, n$

(здесь блуждание строится наоборот: $+1$ для икса, $-1$ для игрека). Путь из 0 в $(2n, 0)$, достигший уровня $l$, отражаем после первого касания этого уровня — получаем путь в $(2n, 2l)$. По (12) и (13)

Множитель $\sqrt{nm/(n+m)}$ из (2) при $m = n$ равен $\sqrt{n/2}$. Чтобы установить, что для произвольного $x \ge 0$ при $n \to \infty$

остаётся применить формулу Стирлинга и разложение $\ln(1 + t) = t - t^2/2 + o(t^2)$ (задача 6). Таблица в RunnableCode выше показывает, что уже при $n = 20$ точная вероятность отличается от предела меньше чем на 0,01.

Проверь себя