Словник / Випадкове блукання
Чоловік виходить з бару й на кожному перехресті звертає куди заманеться. Математика гарантує: рано чи пізно він стоятиме біля своїх дверей. А птах, який так само навмання летить уперед, убік, угору чи вниз, може не повернутися ніколи. Різниця лише в одному вимірі. Це довів Дьордь Пойа 1921 року, а математик Сідзуо Какутані підсумував так: п'яний чоловік рано чи пізно знайде дорогу додому, а п'яний птах може загубитися назавжди.
Шар «На пальцях» приховано на всіх задачах.
Кожен блукач починає вдома, у центрі, і щокроку переходить у сусідню клітинку навмання: на прямій ліворуч чи праворуч, на площині в один з чотирьох боків, у просторі ще й угору чи вниз. Хто ступив на дім, той повернувся. Випустіть по 100 блукачів у кожен світ і дайте їм по 10 000 кроків.
На прямій дітися нікуди: блукач тупцює біля дому й рано чи пізно на нього наступає. На площині місця більше, і повернення затягується, але воно все одно неминуче, просто довше чекати. У просторі напрямків так багато, що блукач, відійшовши, здебільшого потрапляє в нові місця, а не в ті, де вже був. Тому третина повертається швидко, а решта, найімовірніше, ніколи.
Пойа зацікавився цим на прогулянках лісом під Цюрихом. Він знову й знову натрапляв на того самого студента з нареченою, ніяковів, що це схоже на стеження, і замислився: чи часто зустрічаються ті, хто блукає навмання?
Шар «Строго» приховано на всіх задачах.
Випадкове блукання на прямій: стартуємо з нуля, і кожен крок дорівнює +1 або −1 з імовірністю 1/2, незалежно від попередніх. Позиція після n кроків — просто сума цих кроків. Наприклад, два кроки дають чотири однаково ймовірні варіанти:
У середньому блукач стоїть на місці: середнє позиції 0. Але квадрат відстані в середньому (4 + 0 + 0 + 4) / 4 = 2, рівно стільки, скільки кроків. Це не збіг, і з цього випливає все інше.
Здається, що вдвічі більше кроків заведуть удвічі далі. Ні: кроки здебільшого гасять один одного. Типова відстань від старту після n кроків — близько √n. Після 100 кроків це приблизно 10, після 10 000 кроків лише приблизно 100. Нижче 200 блукачів на прямій: час іде вправо, позиція вгору або вниз.
Типова відстань тут — корінь із середнього квадрата відстані всіх 200 блукачів. Пунктир — ±√n.
Олена й Богдан кидають монетку 1000 разів: орел — очко Олені, решка — Богданові. Рахунок між ними — те саме випадкове блукання. Здається, що лідерство має раз у раз переходити з рук у руки, і кожен буде попереду десь половину гри. Насправді рівний поділ найменш імовірний, а найчастіше хтось один веде майже весь час.
Гістограма: частка кидків, протягом яких попереду Олена, за всіма зіграними іграми. Кидок, на якому рахунок стає рівним або перестає бути рівним, зараховуємо тому, хто веде на іншому його кінці.
Шар «Глибше» приховано на всіх задачах.
Sn = X₁ + X₂ + … + Xn, E[Sn²] = Σ E[Xi²] + Σi≠j E[XiXj] = n · 1 + 0 = n
Кожен крок у квадраті дорівнює 1, тож перша сума дає n. Перехресні добутки XiXj однаково часто дорівнюють +1 і −1, бо кроки незалежні, і в середньому зникають. Тому дисперсія позиції дорівнює n, а типова відстань √n. Середня відстань без квадрата трохи менша: E|Sn| ≈ √(2n/π) ≈ 0,8 √n.
Зробіть кілька кроків у симуляції з 200 блукачами, і тут з'являться їхні числа.
P(попереду 2k кидків з 2n) = C(2k, k) · C(2n − 2k, n − k) / 2²ⁿ
P(частка часу попереду ≤ x) → (2/π) · arcsin √x
Перша формула точна для гри з 2n кидків. Найбільші ймовірності в крайніх значень k = 0 і k = n, найменша посередині. Друга формула — її межа для довгих ігор, звідки й назва. Імовірність, що хтось веде щонайменше 90% часу, у межі дорівнює 2 · (1 − (2/π) · arcsin √0,9) ≈ 0,410, а точно для 1000 кидків 0,413. Рівний поділ від 40 до 60% трапляється лише з імовірністю ≈ 0,129.
Зіграйте ігри в симуляції вище, і тут з'являться ваші частки.
Імовірність колись повернутися додому: пряма 1, площина 1, простір ≈ 0,3405
Нехай p — імовірність колись повернутися. Після кожного повернення блукання починається наче заново, тож середня кількість відвідин дому, разом зі стартом, дорівнює 1/(1 − p). З іншого боку, це сума ймовірностей бути вдома на кожному кроці. Після 2n кроків ця ймовірність приблизно така:
пряма 1/√(πn) · площина 1/(πn) · простір 2 · (3/(4πn))3/2
Перші дві суми нескінченні, тож 1/(1 − p) нескінченне і p = 1. Друга росте лише як логарифм, тому площина повертає блукачів так повільно: за 10 000 кроків тільки близько 74%. Третя сума скінченна, вона дорівнює 1,516…, і p = 1 − 1/1,516 ≈ 0,3405. За 10 000 кроків у просторі повертається близько 33,7%, тобто майже всі, хто взагалі колись повернеться. У чотирьох і більше вимірах блукачі повертаються ще рідше.
Випустіть блукачів у першій симуляції, і тут з'являться ваші підсумки.
Зростання, за якого величина щоразу множиться на те саме число, тож подвоюється через рівні проміжки часу.
Одне зернятко на першій клітинці шахівниці й подвоєння на кожній наступній: на останній клітинці стільки рису, скільки світ вирощує понад 300 років.
Скільки разів треба помножити основу саму на себе, щоб отримати число: log₂ 8 = 3, бо 2 · 2 · 2 = 8.
Аркуш паперу, складений навпіл 42 рази, був би товщим за відстань до Місяця.
Сума 1 + ½ + ⅓ + ¼ + …: вона росте без меж, але неймовірно повільно.
Однакові книжки можна скласти так, що верхня нависатиме над краєм столу як завгодно далеко.
Потік незалежних випадкових подій зі сталою середньою частотою: дзвінки, клацання лічильника, краплі дощу.
У 1944 році лондонцям здавалося, що німецькі літаючі бомби влучають прицільно, а це була звичайна випадкова купчастість.