Словник / Випадкове блукання
Чоловік виходить з бару й на кожному перехресті звертає куди заманеться. Математика гарантує: рано чи пізно він стоятиме біля своїх дверей. А птах, який так само навмання летить уперед, убік, угору чи вниз, може не повернутися ніколи. Різниця лише в одному вимірі. Це довів Дьордь Пойа 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%, тобто майже всі, хто взагалі колись повернеться. У чотирьох і більше вимірах блукачі повертаються ще рідше.
Випустіть блукачів у першій симуляції, і тут з'являться ваші підсумки.
Число посередині: якщо всіх вишикувати за зростанням, половина буде нижче, половина вище.
До бару заходить мільйонер, і середній дохід відвідувачів злітає, а медіана ледь ворухнеться.
Сума всіх значень, поділена на їхню кількість: скільки дісталося б кожному, якби поділити порівну.
Майже кожна людина має більше ніг, ніж у середньому: середнє трохи менше за дві.
Середній результат, якого можна чекати, якщо повторювати те саме дуже багато разів.
У грального кубика сподівання 3,5, хоча такої грані немає.
Число від −1 до +1, що показує, наскільки дві величини рухаються разом.
Улітку ростуть і продаж морозива, і кількість утоплень. Морозиво тут ні до чого: обох розганяє спека.
Міра розкиду: наскільки значення в середньому відходять від середнього. Стандартне відхилення — корінь з дисперсії, у тих самих одиницях.
Два міста з однаковою середньою температурою: в одному весь рік близько +15, в іншому то −20, то +50.
Розподіл у формі дзвона: більшість значень біля середнього, а що далі від нього, то рідше.
Кожна кулька на дошці Гальтона падає навмання, а тисячі кульок щоразу складаються в той самий дзвін.
Що більше повторень, то ближче частка результату до його справжньої ймовірності.
Частка орлів підповзає до 50%, а різниця між орлами й решками в штуках зазвичай росте.
Шанс події за умови, що вже відомо щось інше.
Майже всі баскетболісти НБА високі, але майже всі високі люди не баскетболісти.
Події незалежні, якщо знання про одну не змінює шансів іншої.
Після п'яти орлів поспіль решка не стає ймовірнішою: монета нічого не пам'ятає.
Скільки разів треба помножити основу саму на себе, щоб отримати число: log₂ 8 = 3, бо 2 · 2 · 2 = 8.
Аркуш паперу, складений навпіл 42 рази, був би товщим за відстань до Місяця.
Вибірка, у яку одні потрапляють частіше за інших, тож вона погано описує всіх.
1936 року журнал опитав мільйони американців і все одно помилився з переможцем виборів.
Як часто сам лише випадок дав би розрив щонайменше такий, як у вас, якби різниці насправді не було.
Коли ефекту немає зовсім, p < 0,05 випадає так само часто, як p між 0,50 і 0,55.
Діапазон навколо виміряного числа, побудований методом, що накриває справжнє значення в обраній частці вибірок, наприклад у 95%.
Із двадцяти чесних 95% інтервалів у середньому один промахується, і жоден не знає, чи це він.
Імовірність, що тест помітить справжній ефект заданого розміру. Потужність 80% означає: один робочий ефект із п'яти тест пропустить.
Слабкий A/B-тест, який таки знайшов ефект, майже завжди його перебільшує: справжні +10% на дашборді стають +24%.
Наскільки зазвичай промахується середнє чи частка, пораховані з вибірки: σ, поділене на корінь з розміру вибірки.
Щоб удвічі зменшити похибку, треба вчетверо більше даних.
Наука про те, скількома способами можна впорядкувати або вибрати речі: перестановки n!, сполучення C(n, k).
Добре перетасована колода майже напевно лежить у порядку, якого ще не бачив ніхто й ніколи.
Сума 1 + ½ + ⅓ + ¼ + …: вона росте без меж, але неймовірно повільно.
Однакові книжки можна скласти так, що верхня нависатиме над краєм столу як завгодно далеко.
Правило, як змінювати впевненість, коли з'являються нові докази: апріорні шанси × сила доказу.
Два слабкі докази разом бувають сильними, а один яскравий нічого не важить, якщо твердження було малоймовірним.
Зростання, за якого величина щоразу множиться на те саме число, тож подвоюється через рівні проміжки часу.
Одне зернятко на першій клітинці шахівниці й подвоєння на кожній наступній: на останній клітинці стільки рису, скільки світ вирощує понад 300 років.
Потік незалежних випадкових подій зі сталою середньою частотою: дзвінки, клацання лічильника, краплі дощу.
У 1944 році лондонцям здавалося, що німецькі літаючі бомби влучають прицільно, а це була звичайна випадкова купчастість.