Випадкові ходи: Закон √t, Повернення та Лев’євські польоти

Початок випадкового ходу

Уявіть собі точку на числовій прямій, що знаходиться в позиції 0. З кожною секудою, коли звучить годинник, киньте чесну монету: орлом - зробіть крок праворуч, монею - зробіть крок ліворуч. Це і є найпростіший можливий випадковий хід, і водночас він лежить в основі таких явищ, як підсікання пилкових часток у воді, поширення газів у кімнаті або щоденний шлях ціни акцій. Простота ходу робить його потужним - одна й та ж кількість статистичних фактів застосовується незалежно від того, що фізично представляє собою "крок".

Чому √t, а не t

Після n кроків ±1, положення є сумою з n незалежних випадкових знаків. Очікуване положення дорівнює точно нулю — позитивні та негативні кроки скасовують один одного в середньому — але дисперсія поводиться зовсім не так, як очікувалося: для незалежних випадкових змінних дисперсії просто додаються. Лише цей факт визначає всю тему.

X_n = S1 + S2 + ... + Sn // кожне Si = +1 або -1, однакова ймовірність E[X_n] = 0 // очікуване положення: повертаємося до початку Var(X_n) = n // дисперсія зростає ЛІНІЙНО з кроків sigma(X_n) = sqrt(n) // типове відхилення зростає як sqrt(n) // Після 1000000 кроків: зазвичай лише ~1000 кроків від початку Згідно з Центральною теоремою про граничне розподілу, розподіл X_n збігається до Гаусового, X_n ~ N(0, n), незважаючи на те, що кожен окремий крок є дискретним кидком монети без жодної симетричної кривої — вражаюча регулярність, яка виникає з чистого випадковості. Зменшіть розмір кроку та інтервал часу разом, зберігаючи це масштабування незмінним, і дисковий хід стає безперервно-часовим Броунівським рухом, чиє середньоквадратичне відхилення дорівнює ⟨r²⟩ = 2dDt (d = розміри, D = коефіцієнт дифузії) — результат Ейнштейна 1905 року, пізніше підтверджений експериментально Жозефом Перріном, який надав однієї з перших твердих доказів того, що атоми реальні.

X_n = S1 + S2 + ... + Sn        // each Si = +1 or -1, equal probability

E[X_n]   = 0                    // expected position: back at the origin
Var(X_n) = n                    // variance grows LINEARLY with steps
sigma(X_n) = sqrt(n)            // typical displacement grows as sqrt(n)

// After 1,000,000 steps: typically only ~1,000 steps from the start

Закон √t для случайных ходов

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

dP/dt = D * d2P/dx2 // уравнение теплопроводности (тепло) P(x, t) = 1/sqrt(4*PI*D*t) * exp(-x^2 / (4*D*t)) // решение для источника в точке // Гауссовское распределение, расширяющееся как sqrt(t) -- то же масштабирование sqrt(n), снова Соответствие работает в обоих направлениях на практике: физики численно решают уравнение теплопроводности путем моделирования роев независимых случайных шажников (метод Монте-Карло), и наоборот, вычисляют статистику ходов путем непосредственного решения дифференциального уравнения — два взгляда на один и тот же основной процесс.

dP/dt = D * d2P/dx2                          // the diffusion (heat) equation

P(x, t) = 1/sqrt(4*PI*D*t) * exp(-x^2 / (4*D*t))   // point-source solution

// A Gaussian that widens as sqrt(t)  --  the same sqrt(n) scaling, again

Рекурент у 1D та 2D, транзіентний у 3D

Один із найбільш вражаючих результатів у теорії ймовірностей, завдяки Джорджу Полі в 1921 році, полягає в тому, що лише розмірність простору визначає, чи гарантовано повернеться випадковому перебіжнику:

Ймовірність повернення до початкової точки: 1D: P = 1 // рекурентний – певно повертається 2D: P = 1 // рекурентний – "наркоману завжди знаходить дім" 3D: P ≈ 0.3405 // транзієнтний – "наркоманів птах може загубитися назавжди" 4D+: P -> 0 // майже ніколи не повертається Розріз у двох вимірах має реальні фізичні наслідки: два диффузійні дефекти, обмежені 2D поверхнею, математично гарантовано зіткнуться та можуть реагувати або анулюватися, тоді як ті самі частинки, які вільно дифундують у 3D просторі, — і часто це відбувається — можуть назавжди віддалитися один від одного, що пояснює, чому реакції, обмежені дифузією, поводяться зовсім іншим чином у мембрані, ніж у масовому рідині. Відмінний, але пов'язаний з цим варіант — це самозапобіжний перебіг, який ніколи не відвідує сайт, який вже зайнятий — стандартна модель для полімерної ланцюга в розчині, кінцева відстань якого зростає як n^ν з показником Flory ν ≈ 0.588 у 3D, а не 0.5 звичайного необмеженого перебігу.

P(eventually returns to origin):
  1D:  P = 1        // recurrent -- certain to return
  2D:  P = 1        // recurrent -- "a drunk always finds home"
  3D:  P ≈ 0.3405   // transient -- "a drunk bird may be lost forever"
  4D+: P -> 0        // almost never returns

Лейфві фліґти, ланташні та де збігається модель

Реальні "випадкові ходи" рідко мають кроки довжини з гарного обмеженого розподілу. Ланташний випадковий хід обмежує кроки дискретними сітковими напрямками — класична модель для дифундуючої молекули газу або наївного алгоритму розв’язання лабіринту. Лейфві фліґти замість цього витягують довжини кроків із розподілу з важким хвостом потужної функції: переважно короткі локальні стрибки, що іноді підсилюються дуже довгим стрибком. Ця суміш спостерігалася в траєкторіях пошуку альбатросів та акул, які полюють на рідкісні, непередбачувані розподіли здобичі, і виявляється, що вона близька до математично оптимальної стратегії пошуку, коли цілі рідкісні та випадково розкидані — справді інший режим масштабування, ніж акуратний закон √t гаусових випадкових ходів.

Фінансові ринки є найважливішим місцем, де чистого припущення про випадкову ходу не вистачає. Луї Башельєр моделював ціни акцій як броунівський рух у 1900 році, п’ять років до Ейнштейна, і геометричний броунівський рух все ще лежить в основі моделі Black-Scholes з оцінки опціонів — але реальні ринки показують товсті хвости (екстремальні рухи набагато частіше, ніж передбачає гаусів), кластеризацію волатильності та довгострокові кореляції, які не може захопити простий випадковий хід, що саме тому кількісне фінансування звертається до процесів Лейфві та часткового броунівського руху замість цього.

Поширеність випадкових ходів

Google оригінальний алгоритм PageRank моделює веб-переглядача як випадкового перехідника, що переходить за посиланнями; важливість сторінки просто йде від ймовірності того, що перехідник там знаходиться в стазі. Марковська ланцюгова Монте-Карло будує випадковий хід через простір можливих станів таким чином, щоб час, проведений у кожній стані, відповідав його цільовій ймовірності, живлячи все від баєсової статистики до симуляцій згортання білків. Бактеріальна хімотакси досягає спрямованого руху за допомогою спотвореного випадкового ходу — E. coli чергує прямі «подорожі» з випадковими «перевертаннями», просто подовжуючи свої подорожі, коли речі покращуються вздовж хімічного градієнту. І в квантовому обчисленні, квантовий хід є послідовним аналогом усього цього: оскільки амплітуди ймовірності можуть взаємодіяти замість просто додаватися, квантовий хід поширюється як t замість √t, математичний двигун за квадратичне прискорення в алгоритмі пошуку Гровера.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.