Случайное блуждание и диффузионный масштаб

Случайное блуждание непредсказуемо в деталях и удивительно строго в масштабе. После тысячи шагов мы не знаем, где окажется частица, но знаем, почему типичное расстояние будет порядка $\sqrt{1000}$, а не $1000$. Из этого одного соображения вырастают и разорение игрока, и броуновское движение, и честная проверка фразы «ряд похож на случайный».

Монета прокладывает маршрут

Пусть $X_1,X_2,\ldots$ независимы и принимают значения $-1$ и $+1$ с равными вероятностями. После $n$ бросков положение частицы

$$S_n=X_1+\cdots+X_n,\qquad S_0=0.$$

Среднее каждого шага равно нулю, поэтому

$$\mathbb E S_n=\sum_{k=1}^n\mathbb E X_k=0.$$

Это не означает, что частица обычно находится в нуле. Ноль — центр симметрии ансамбля, а не адрес типичной траектории. Разброс задаётся дисперсией, и вот здесь начинается вся содержательная часть урока:

$$\operatorname{Var}(S_n)=\sum_{k=1}^n\operatorname{Var}(X_k)=n, \qquad \sigma(S_n)=\sqrt n .$$

Дисперсия растёт линейно, стандартное отклонение — как корень. Через $10\,000$ шагов типичный масштаб положения около $100$, а не $10\,000$. Пройти расстояние $10\,000$ можно, лишь если все шаги смотрят в одну сторону; вероятность такого события равна $2^{-10000}$ на каждое из двух направлений.

Это первая встреча с диффузионным масштабированием. В центральной предельной теореме сумма после деления на $\sqrt n$ приближалась к нормальному закону; там нормировка выглядела технической. Здесь она получает геометрический смысл: $\sqrt n$ — это размер облака, в котором живут траектории.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Почему складываются дисперсии, а не отклонения

Ключевой шаг — равенство $\operatorname{Var}(S_n)=n$. Оно опирается не на нормальность, а только на независимость и на то, что дисперсия каждого шага равна единице:

$$\operatorname{Var}(X+Y)=\operatorname{Var}X+\operatorname{Var}Y+2\operatorname{Cov}(X,Y),$$

и при независимости ковариация исчезает. Складываются квадраты масштабов, а корни складываются только тогда, когда шаги идеально согласованы. Именно поэтому десять независимых ошибок дают разброс $\sqrt{10}\approx3{,}16$, а не $10$.

Полезно записать это как теорему Пифагора: независимые случайные величины с нулевым средним — ортогональные векторы в пространстве со скалярным произведением $\langle X,Y\rangle=\mathbb E XY$. Тогда

$$\|S_n\|^2=\sum_{k=1}^n\|X_k\|^2,\qquad \|X\|=\sqrt{\mathbb E X^2},$$

и корень возникает просто как длина гипотенузы. Та же ортогональность работала в методе наименьших квадратов, только там проецировали данные, а здесь — случайность.

Точные вероятности и чётность

Чтобы после $n$ шагов оказаться в точке $m$, нужно сделать $(n+m)/2$ шагов вправо. Поэтому $n$ и $m$ обязаны иметь одинаковую чётность, а

$$\Pr(S_n=m)=2^{-n}\binom{n}{(n+m)/2}.$$

Вернуться в ноль за нечётное число шагов невозможно — не «маловероятно», а именно невозможно. При $n=8$ полная таблица занимает девять строк: $\Pr(S_8=0)=70/256=0{,}2734$, $\Pr(S_8=2)=56/256=0{,}2188$, $\Pr(S_8=4)=28/256=0{,}1094$, а вероятность больших отклонений $\Pr(|S_8|\ge6)=18/256=0{,}0703$.

При $n=100$ вероятность возврата равна

$$\Pr(S_{100}=0)=2^{-100}\binom{100}{50}\approx0{,}0796 .$$

Она вовсе не экспоненциально мала: центральный биномиальный коэффициент почти компенсирует $2^{100}$. Формула Стирлинга объясняет, насколько именно:

$$\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi n}}, \qquad\text{откуда}\qquad \Pr(S_{2n}=0)\sim\frac1{\sqrt{\pi n}} .$$

При $n=50$ приближение даёт $0{,}0798$ против точного $0{,}0796$ — расхождение $0{,}25\%$. Асимптотика здесь не «когда-нибудь потом», а уже на сотне шагов.

Верхняя граница блуждания: закон Хинчина

Полоса $\pm\sqrt n$ описывает типичное положение, но не отвечает на вопрос о рекордах: как далеко траектория заходит хоть когда-нибудь? Ответ дал Александр Яковлевич Хинчин в 1924 году — это закон повторного логарифма:

$$\limsup_{n\to\infty}\frac{S_n}{\sqrt{2n\ln\ln n}}=1 \quad\text{почти наверное.}$$

Огибающая $\sqrt{2n\ln\ln n}$ растёт лишь чуть быстрее $\sqrt n$: при $n=300\,000$ множитель $\sqrt{2\ln\ln n}$ равен $2{,}25$. Траектория бесконечно много раз подходит к этой границе и лишь конечное число раз выходит за любую чуть большую. В модельном опыте с seed 6606 максимум отношения $|S_n|/\sqrt{2n\ln\ln n}$ на отрезке от тысячи до трёхсот тысяч шагов составил $1{,}18$: закон говорит о пределе, а не запрещает локально превысить единицу.

Дрейф меняет всё

Пусть шаг вправо происходит с вероятностью $p$, влево — с $1-p$. Тогда

$$\mathbb E X_k=2p-1,\qquad \operatorname{Var}(X_k)=1-(2p-1)^2=4p(1-p),$$

и, по аддитивности,

$$\mathbb E S_n=n(2p-1),\qquad \sigma(S_n)=2\sqrt{np(1-p)} .$$

Центр движется линейно, шум вокруг него растёт как корень. Гонка $n$ против $\sqrt n$ имеет единственный исход: снос побеждает, вопрос только в том, когда. Для $p=0{,}51$ и $n=10^6$ средний сдвиг равен $20\,000$ при стандартном отклонении $999{,}8$ — отношение сигнала к шуму ровно $20{,}0$. Условие «снос не меньше двух сигм» выполняется начиная с

$$n\ \ge\ \left(\frac{4\sqrt{p(1-p)}}{2p-1}\right)^{2}=9996 .$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Та же арифметика лежит под стохастическим градиентным спуском из урока 24: каждый мини-батч даёт шумную оценку направления, полезная составляющая накапливается линейно по числу шагов, а шум — как корень. Она же объясняет, почему для оценки слабого преимущества нужно много раундов, а не одна яркая серия.

Граница, которая прекращает опыт

Часто важно не положение в фиксированный момент, а первое достижение границы. Игрок начинает с капиталом $i$, каждый раунд выигрывает или проигрывает единицу, игра кончается при $0$ или $N$. Вероятность $u_i$ дойти до $N$ раньше нуля в честной игре удовлетворяет разностному уравнению

$$u_i=\tfrac12u_{i-1}+\tfrac12u_{i+1}, \qquad u_0=0,\quad u_N=1 .$$

Перепишем его как $u_{i+1}-2u_i+u_{i-1}=0$: вторая конечная разность равна нулю, значит $u_i$ линейна по $i$, и с учётом краёв

$$u_i=\frac iN .$$

При $i=10$ и $N=100$ шанс дойти до сотни раньше нуля равен $0{,}1$, хотя игра абсолютно честная. Симметрия шагов не делает симметричными расстояния до границ: разоряет не нечестность, а асимметрия капиталов.

Достаточно чуть-чуть испортить монету, чтобы картина стала жёстче. При $p=0{,}49$ и тех же $i=10$, $N=100$ формула

$$u_i=\frac{1-r^{\,i}}{1-r^{\,N}},\qquad r=\frac{1-p}{p},$$

даёт $u_{10}=0{,}00917$: шанс упал в $10{,}9$ раза от честных $0{,}1$. Небольшое преимущество заведения при длинной игре превращается в почти достоверный исход.

Сколько длится игра

Среднее время до остановки $\mathbb E_i\tau$ решает уже неоднородное уравнение

$$\mathbb E_i\tau=1+\tfrac12\mathbb E_{i-1}\tau+\tfrac12\mathbb E_{i+1}\tau, \qquad \mathbb E_0\tau=\mathbb E_N\tau=0,$$

и ответ проверяется подстановкой:

$$\mathbb E_i\tau=i(N-i).$$

Вероятность $u_i$ можно получить и вовсе без разностных уравнений. В честной игре $S_n$ — мартингал, его среднее не меняется со временем, поэтому в момент остановки

$$i=\mathbb E_i S_\tau=(1-u_i)\cdot 0+u_i\cdot N \quad\Longrightarrow\quad u_i=\frac iN .$$

Такой вывод короче, но требует аккуратности: равенство $\mathbb E S_\tau=S_0$ верно не для любого момента остановки, а лишь при подходящих условиях (здесь их обеспечивает ограниченность капитала).

При $N=100$ старт с десяти жетонов даёт $900$ раундов, старт с девяноста — те же $900$, а старт с середины — $2500$. Вероятность успеха и длительность опыта отвечают на разные вопросы: у бедного игрока мало шансов, но и мучиться ему недолго.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

От ломаной к броуновскому движению

Увеличим число шагов и одновременно уменьшим их длину. Процесс

$$W_n(t)=\frac{S_{\lfloor nt\rfloor}}{\sqrt n},\qquad 0\le t\le1,$$

сходится — как случайная функция целиком, а не только в фиксированной точке — к винеровскому процессу $W(t)$. Его свойства коротки: $W(0)=0$, приращение на интервале длины $\Delta t$ распределено нормально,

$$W(t+\Delta t)-W(t)\sim\mathcal N(0,\Delta t),$$

непересекающиеся приращения независимы, а траектория непрерывна.

Нормировка $\sqrt n$ здесь единственно возможная. Разделим на $n$ — получим тождественный ноль (закон больших чисел). Разделим на $n^{1/4}$ — разброс уйдёт в бесконечность. Только корень оставляет живой предел.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Траектория $W(t)$ непрерывна, но почти наверное нигде не дифференцируема. Причина видна из масштабов: приращение имеет размер $\sqrt{\Delta t}$, поэтому

$$\frac{\Delta W}{\Delta t}\sim\frac{1}{\sqrt{\Delta t}}\xrightarrow[\Delta t\to0]{}\infty .$$

Это не дефект рисунка и не следствие конечного разрешения экрана, а математическое свойство: мгновенной скорости у броуновской частицы нет.

Броуновское движение — модель теплового движения, шума датчиков и случайных возмущений. Оно же стоит под стохастическими дифференциальными уравнениями и под непрерывным взглядом на диффузионные генеративные модели, где картинку получают, аккуратно разворачивая добавление шума назад во времени.

Чего не видно по одному значению $S_n$

Распределение конечной точки — далеко не вся информация о траектории. Два процесса могут иметь одинаковое $\Pr(S_n=\cdot)$ и совершенно разные свойства пути. Классический пример — доля времени, проведённая выше нуля. Интуиция подсказывает, что честная монета должна держать нас примерно поровну по обе стороны. Правда обратная: закон арксинуса утверждает, что типичны как раз крайние доли,

$$\Pr\!\left(\frac{\#\{k\le n\:S_k>0\}}{n}\le x\right)\longrightarrow \frac2\pi\arcsin\sqrt x .$$

В модельном опыте (20 000 траекторий по 2000 шагов, seed 6607) доля времени оказалась ближе к краям, чем к середине: в $40{,}9\%$ случаев она была меньше $0{,}1$ или больше $0{,}9$ (теория даёт $0{,}410$), и лишь в $12{,}9\%$ случаев попала в интервал от $0{,}4$ до $0{,}6$.

Максимум $M_n=\max_{k\le n}S_k$ тоже не восстанавливается из $S_n$: по принципу отражения

$$\Pr(M_n\ge a)=2\Pr(S_n>a)+\Pr(S_n=a),$$

то есть распределение рекорда вдвое тяжелее распределения конца пути. Порядок шагов содержит информацию, которую итог не хранит.

Лаборатория: триста траекторий сразу

Начните с $p=0{,}5$ и сравните $n=100$, $400$, $1600$: в режиме «как есть» облако растёт, но выборочная $\sigma$ каждый раз близка к $\sqrt n$, а отношение $\sigma/\sqrt n$ держится около единицы. Переключите нормировку на «делить на $\sqrt n$» — картинка перестанет зависеть от $n$: это и есть содержание корневого закона. Затем «делить на $n$» — облако схлопнется в линию, и вы увидите закон больших чисел.

Дальше включите перекос. При $p=0{,}52$ найдите $n$, при котором прямая сноса выходит из коридора $\pm2\sigma$ вокруг нуля, и сравните с формулой $n^*=\bigl(4\sqrt{p(1-p)}/(2p-1)\bigr)^2$. Полезно отдельно последить за долей траекторий вне коридора: при любом $n$ она колеблется около теоретических $4{,}55\%$ (нормальный хвост за двумя сигмами), потому что коридор построен вокруг правильного центра, а не вокруг нуля.

Реальные данные: метро вместо монеты

Проверим модель там, где её любят применять не глядя. Возьмём ежедневную посещаемость метро Нью-Йорка (открытые данные MTA): $1105$ суток с $2022\text{-}01\text{-}01$ по $2025\text{-}01\text{-}09$. Работать будем с логарифмом числа поездок $y_t=\ln R_t$; тогда шаги $d_t=y_{t+1}-y_t$ — это относительные суточные изменения, и модель «случайное блуждание» звучит так: $y_t$ есть сумма независимых одинаково распределённых шагов.

Стандартное отклонение шага равно $0{,}302$ — типичное суточное изменение в десятки процентов, что уже подозрительно много. Корреляция соседних шагов почти нулевая, $0{,}04$, и на этом многие останавливаются: «шаги независимы, значит блуждание». Но корреляция шагов на лаге семь равна $0{,}81$. Память есть, просто она недельная.

Главный инструмент — средний квадрат смещения (mean squared displacement):

$$\operatorname{MSD}(\tau)=\frac1{n-\tau}\sum_{t}\bigl(y_{t+\tau}-y_t\bigr)^2 .$$

Универсальная форма записи — степенной закон

$$\operatorname{MSD}(\tau)\propto\tau^{\alpha}, \qquad \alpha=\frac{d\log\operatorname{MSD}}{d\log\tau},$$

где $\alpha=1$ отвечает диффузии, $\alpha=2$ — равномерному движению, а $\alpha\approx0$ — процессу, привязанному к уровню. Для свободного блуждания $\operatorname{MSD}(\tau)=\sigma^2\tau$: в логарифмических осях это прямая с наклоном ровно $1$. Для наших данных на кратных неделе лагах наклон равен $0{,}09$. Между лагом $7$ и лагом $56$ MSD вырос с $0{,}0279$ до $0{,}0355$ — в $1{,}27$ раза вместо восьмикратного роста, предсказанного диффузией. Ряд не блуждает: он привязан к своему уровню.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Перемешивание как контрольный опыт

Как отличить «нет диффузии» от «мы плохо оценили»? Проведём контрольный опыт: перемешаем те же приращения случайным образом (40 перестановок, seed 6605) и соберём ряд заново,

$$\tilde y_t=y_0+\sum_{s\le t}d_{\pi(s)} .$$

Перестановка сохраняет всё, что не зависит от порядка: множество шагов, их среднее, дисперсию $0{,}0914$, гистограмму, экстремумы. Она разрушает ровно одно — временную структуру. Результат однозначен: MSD перемешанного ряда идёт с наклоном $0{,}99$ и растёт от лага $7$ к лагу $56$ в $7{,}83$ раза, почти точно в восемь. На восьминедельном горизонте свободное блуждание из тех же шагов уходит от старта в $138{,}2$ раза дальше по квадрату смещения — это в $11{,}8$ раза дальше по расстоянию, чем реальный ряд.

Возврат, размерность и здравый смысл

Симметричное блуждание в одном и двух измерениях возвращается в начало с вероятностью $1$; в трёх — уже нет. Это теорема Пойа 1921 года, и её обычно формулируют так: пьяница вернётся домой, пьяная птица — не обязательно. Вероятность возврата в трёхмерной решётке равна $0{,}3405$.

В модельном опыте (3000 блужданий по 20 000 шагов на каждую размерность, seed 6603) доля вернувшихся составила $0{,}992$ при $d=1$, $0{,}757$ при $d=2$ и $0{,}344$ при $d=3$. Первое число близко к единице, третье — к константе Пойа. Второе кажется далёким от единицы, и это поучительно: в двумерном случае возврат достоверен, но время ожидания огромно, поэтому конечный горизонт систематически занижает долю. Симуляция подтверждает теорему только вместе с пониманием скорости сходимости.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Практический вывод из размерности — не про пьяниц. Случайный поиск в пространстве параметров тем хуже накрывает окрестность старта, чем выше размерность; та же причина стоит за неэффективностью наивного случайного блуждания в алгоритмах MCMC, где приходится специально придумывать предложения, чтобы цепь не тонула в объёме пространства.

Что уносим

Урок держится на четырёх утверждениях, и каждое мы посчитали. Дисперсии независимых шагов складываются, поэтому масштаб суммы равен $\sqrt n$, а не $n$. Постоянный снос накапливается линейно и потому рано или поздно побеждает шум — при $p=0{,}51$ это происходит после $9996$ шагов. Границы превращают блуждание в задачу первого достижения с ответами $i/N$ и $i(N-i)$. Непрерывный предел даёт винеровский процесс — непрерывный, но недифференцируемый.

И пятое, методическое: гипотезу «это случайное блуждание» нужно проверять, а не объявлять. У ряда метро суточные шаги выглядят некоррелированными на лаге 1, но MSD с наклоном $0{,}09$ и корреляция $0{,}81$ на лаге 7 закрывают вопрос. Инструменты такой проверки — лог-лог наклон MSD, автокорреляция на нескольких лагах и перестановочный контроль. Всё это опирается на то же определение дисперсии, с которого начинался модуль вероятности.

Задачи