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

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

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

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

S_n=X_1+\cdots+X_n.

Среднее каждого шага равно нулю, поэтому $\mathbb E S_n=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$ можно только если почти все шаги направлены одинаково; вероятность такого события ничтожна.

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

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

Траектории случайного блуждания для 100, 1000 и 10000 шагов с корневыми полосами — Рис. 66.1. Три масштаба одной случайной прогулки
На трёх панелях изображены траектории $S_k$ при возрастающем $n$ . Голубые границы равны $\pm\sqrt{k}$ , светлые — $\pm2\sqrt{k}$ . Оси обеих координат меняют масштаб, но после нормировки $S_k/\sqrt n$ облака выглядят сравнимо.

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

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

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

Например, вернуться в ноль через нечётное число шагов невозможно. При $n=100$ вероятность возврата равна

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

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

\Pr(S_{2n}=0)\sim\frac1{\sqrt{\pi n}}.

Вероятность быть в нуле в конкретный поздний момент убывает, но сумма этих вероятностей расходится. Отсюда вырастает глубокий факт: одномерное симметричное блуждание почти наверное когда-нибудь вернётся в начало.

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

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

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

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

Теперь центр движется линейно, а шум вокруг него растёт как $\sqrt n$ . Даже крошечный перекос $p=0{,}51$ через миллион шагов даёт средний сдвиг $20\,000$ , намного больше стандартного отклонения около $1\,000$ . Слабый постоянный сигнал обнаруживается накоплением.

Эта идея вернётся в обучении с подкреплением: небольшое преимущество действия со временем доминирует, но его ещё нужно отличить от случайного разброса.

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

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

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

Вторая конечная разность равна нулю, значит $u_i$ линейна:

u_i=\frac{i}{N}.

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

Среднее время до остановки равно $i(N-i)$ . Оно максимально в середине и растёт квадратично с размером интервала. Вероятность успеха и длительность эксперимента отвечают на разные вопросы.

Графики вероятности достижения верхней границы и среднего времени остановки — Рис. 66.2. Разорение игрока: вероятность и время
По горизонтали начальный капитал $i$ при $N=100$ . Синяя прямая показывает $u_i=i/N$ , красная парабола — $\mathbb E\tau=i(N-i)$ по правой оси. Отмечены точки $i=10,50,90$ : одинаковый шаговый закон даёт им разные риск и длительность.

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

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

W_n(t)=\frac{S_{\lfloor nt\rfloor}}{\sqrt n}

на отрезке $0\le t\le1$ приближается к винеровскому процессу $W(t)$ . Его приращение на интервале длины $\Delta t$ нормально распределено с дисперсией $\Delta t$ , а непересекающиеся приращения независимы.

Траектория $W(t)$ непрерывна, но почти наверное нигде не имеет обычной производной. Если пытаться вычислять скорость по всё меньшим интервалам, отношение $\Delta W/\Delta t$ имеет масштаб $1/\sqrt{\Delta t}$ и разлетается. Это не дефект графика, а математическое свойство.

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

Лаборатория множества траекторий

Сначала поставьте $p=0{,}5$ и сравните облака конечных положений для $n=100$ , $400$ и $1600$ . Если закон корня верен, стандартные отклонения должны относиться как $1\:2\:4$ , хотя число шагов относится как $1\:4\:16$ . Затем включите небольшой дрейф и найдите момент, после которого средний сдвиг становится больше двух стандартных отклонений.

Отдельно следите за максимумом $M_n=\max_{k\le n}S_k$ и временем первого пересечения уровня. Их распределения нельзя восстановить только из $S_n$ : порядок шагов имеет значение.

Данные: дрейфующие океанские буи

Программа NOAA Global Drifter Program публикует координаты дрейфующих буёв с временными метками. Траектория определяется течением, ветром, волнами и ошибками позиционирования, поэтому простое независимое блуждание — лишь baseline.

Чтобы сравнить модель с данными, переведите широту и долготу в локальные координаты, выберите постоянный временной шаг и рассмотрите приращения

\Delta r_t=r_{t+\Delta t}-r_t.

Проверьте средний дрейф, зависимость $\mathbb E\|r_{t+\tau}-r_t\|^2$ от лага $\tau$ и корреляцию соседних приращений. Для идеальной двумерной диффузии средний квадрат смещения линейно растёт со временем:

\mathbb E\|r(t+\tau)-r(t)\|^2\approx4D\tau.

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

Карта траектории океанского буя и график среднего квадрата смещения от временного лага — Рис. 66.3. От маршрута буя к коэффициенту диффузии
Слева показана траектория в локальных километрах, цвет кодирует время. Справа по логарифмическим осям отложено среднее $\|\Delta r(\tau)\|^2$ ; пунктир имеет наклон 1 и соответствует диффузии. Серой полосой отмечен диапазон лагов, использованный для оценки $D$ .

Мини-исследование: отличить диффузию от направленного движения

Пусть дана двумерная траектория длины 20 000 шагов. Одного рисунка маршрута недостаточно: медленный дрейф на фоне шума и коррелированное движение могут выглядеть одинаково. Разбейте последовательность на непересекающиеся блоки длины $m$ и вычислите block displacements

\Delta_m^{(j)}=r_{(j+1)m}-r_{jm}.

Для $m=1,4,16,64$ сравните средний вектор, covariance ellipse и распределение норм. У независимого блуждания средний после удаления дрейфа остаётся около нуля, а размер эллипса растёт как $\sqrt m$ . При инерции соседние шаги согласованы, поэтому на малых $m$ рост быстрее.

Затем перемешайте приращения по времени. Их одномерное распределение сохранится, но автокорреляция исчезнет. Если mean squared displacement после перемешивания заметно изменился, порядок содержал информацию. Это контрольный опыт в духе перестановочных тестов: разрушаем конкретную структуру, сохраняя остальные свойства.

Для доверительного интервала не считайте перекрывающиеся блоки независимыми. Можно использовать block bootstrap, пересэмплируя длинные куски траектории. Обязательно укажите длину блока и покажите, как вывод меняется при её удвоении. Такой анализ превращает фразу «маршрут похож на случайный» в набор опровержимых признаков: нулевой drift, корневой масштаб и слабая память приращений.

Ещё один контроль строится без симуляции. Для каждого $n$ разделите конечные положения на $\sqrt n$ и наложите empirical CDF. Если кривые разных $n$ сходятся, нормировка выбрана разумно. Затем разделите на $n$ : распределения сожмутся к нулю. Эта пара графиков буквально показывает, почему характерный масштаб не линейный.

Проверяйте хвосты отдельно. Среднее и дисперсия могут совпасть у процессов с редкими большими скачками, но вероятность выйти за $4\sqrt n$ будет иной. Для океанского буя такой хвост может означать шторм, сбой GPS или смену течения; каждую гипотезу проверяют по метаданным.

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

В одной и двух размерностях симметричное блуждание возвращается в начало с вероятностью $1$ . В трёх измерениях вероятность возврата уже меньше единицы. Дополнительное направление даёт больше путей «убежать». Это пример фазового изменения, вызванного не параметром, а размерностью пространства.

Главные идеи урока складываются в короткую систему. Сумма независимых шумов имеет разброс $\sqrt n$ ; постоянный дрейф накапливается как $n$ ; границы превращают траекторию в задачу первого достижения; непрерывный предел даёт броуновское движение. Эти результаты нужны не для красивой монеты, а чтобы отделять сигнал от флуктуаций в реальных временных данных.

Задачи

3баллов

Пусть $S_0=0$ , $S_n=\sum_{k=1}^nX_k$ , а независимые шаги удовлетворяют $\Pr(X_k=1)=\Pr(X_k=-1)=1/2$ . Для $n=8$ перечислите все возможные значения $S_8$ и найдите $\Pr(S_8=0)$ , $\Pr(S_8=4)$ и $\Pr(|S_8|\ge6)$ . Случайности в вычислении нет. Ответ принимается, если каждая вероятность записана через биномиальный коэффициент, сокращённой дробью и десятичным числом с четырьмя знаками.

4баллов

Пусть $S_0=0$ , $S_n=\sum_{k=1}^nX_k$ , шаги независимы, $\Pr(X_k=1)=0{,}55$ и $\Pr(X_k=-1)=0{,}45$ . По формулам $\mathbb E S_n=n\mathbb E X_1$ и $\operatorname{Var}(S_n)=n\operatorname{Var}(X_1)$ вычислите среднее и стандартное отклонение для $n\in\{100,1000,10\,000\}$ . Найдите наименьшее целое $n$ , при котором $\mathbb E S_n\ge3\sqrt{\operatorname{Var}(S_n)}$ . Случайности и единиц измерения нет; зачёт требует точное неравенство для $n$ , численный порог и объяснение обнаружения слабого дрейфа.

5баллов

Капитал $S_n$ измеряется в жетонах и до поглощения меняется на $+1$ или $-1$ с вероятностями $1/2$ . Границы равны 0 и 25, а $T=\min\{n\:S_n\in\{0,25\}\}$ . Для стартов $S_0=7$ и $S_0=18$ найдите $\Pr(S_T=25\mid S_0=i)=i/25$ и $\mathbb E_iT=i(25-i)$ . В частности, проверьте равенство $\mathbb E_7T=\mathbb E_{18}T=126$ и объясните симметрию заменой $S_n\mapsto25-S_n$ ; вероятности успеха при этом должны сложиться в единицу. Случайности в решении нет, нужны точные дроби и времена в раундах.

6баллов

Смоделируйте процесс $S_0=0$ , $S_k=S_{k-1}+X_k$ , где независимые шаги имеют распределение $\Pr(X_k=1)=\Pr(X_k=-1)=1/2$ . Генератор PCG64 инициализируйте seed 6604; для каждого $n\in\{100,400,1600,6400\}$ создайте отдельные 20 000 траекторий и вычислите выборочное стандартное отклонение $S_n$ , медиану и 95-й процентиль $M_n=\max_{0\le k\le n}|S_k|$ . Оцените для каждой метрики наклон МНК-модели $y=b\sqrt n$ без свободного члена. Единица обеих величин равна одному шагу; зачёт требует таблицу, график, наклоны и относительную ошибку стандартного отклонения от $\sqrt n$ не более 3% во всех четырёх строках.

7баллов

Загрузите NOAA Global Drifter Program Hourly QC v2.01.1, DOI 10.25921/x46c-3620, через ERDDAP-набор drifter_hourly_qc. Оставьте буй ID=116351 и часы UTC от 2015-05-09T00\:00\:00Z включительно до 2015-07-08T00\:00\:00Z включительно; строки без широты или долготы удалите, дубликаты часа оставьте последними, разрывы не интерполируйте. Долготу сначала разверните без скачков на $360^\circ$ . Если первая точка в радианах равна $(\varphi_0,\lambda_0)$ , переведите каждую точку в локальные километры по формулам $x=R\cos\varphi_0(\lambda-\lambda_0)$ , $y=R(\varphi-\varphi_0)$ при фиксированном $R=6371{,}0088$ км. Вычтите отдельные линейные тренды $x(t)$ и $y(t)$ , оценённые МНК на первых 48 сутках. На последних 12 сутках для каждого $\tau\in\{6,12,\ldots,240\}$ используйте только пары наблюдений, чьи UTC-времена различаются ровно на $\tau$ часов, и усредните квадраты двумерных смещений. Подберите без свободного члена $\operatorname{MSD}(\tau)=4D\tau$ ровно на лагах 6, 12, ..., 48 часов. Для каждого лага отдельно постройте все перекрывающиеся блоки из 24 displacement-пар с последовательными часовыми стартами. В каждой из 2 000 bootstrap-реплик независимо для каждого лага выбирайте такие блоки с возвращением до исходного числа пар и обрезайте последний блок; из полного bootstrap-вектора MSD по лагам 6–48 часов заново оценивайте $D$ . Используйте PCG64 seed 6605, проходя лаги по возрастанию. Зачёт требует $D$ в км²/ч, percentile 95%-интервал, число пар на каждом лаге и два количественно отмеченных отклонения от линейной модели.