Цепи Маркова в задаче из первой части ЕГЭ

Бактерия каждый час либо делится на две точно такие же бактерии с вероятностью 5/7, либо погибает с вероятностью 2/7. В начале в пробирке была одна бактерия.
Какова вероятность того, что через некоторое время в пробирке не останется ни одной бактерии?

На вид это обычная задача на вероятность. Но в ней есть неприятная для школьного экзамена особенность: процесс может продолжаться сколь угодно долго. Нельзя просто нарисовать дерево на два-три шага и честно перебрать все варианты.
Попробуем всё-таки решить.
Пусть P — вероятность того, что потомство одной бактерии в конце концов исчезнет.
После первого часа есть два варианта.
Первый: бактерия погибла. Вероятность этого равна q=2/7. Тогда всё уже закончилось.
Второй: бактерия разделилась на две. Вероятность этого равна p=5/7. Теперь нужно, чтобы исчезло потомство обеих бактерий. А каждая из них начинает такую же историю, как исходная бактерия. Поэтому вероятность исчезновения двух независимых «семейств» равна P².
Получаем уравнение
P=q+pP².
Отсюда
pP²−P+q=0.
Так как p+q=1, это уравнение можно записать так:
(P−1)(P−q/p)=0.
Значит,
P=1 или P=q/p.
В нашей задаче
q/p=(2/7)/(5/7)=2/5.
Ответ: 2/5.
 
Почему не 1? Формально корень P=1 тоже появился в уравнении. Но он соответствует другой ситуации: когда размножение не сильнее гибели, популяция почти наверняка когда-нибудь вымрет. Если же p>q, то у процесса есть шанс «убежать в бесконечность»: бактерий становится всё больше, и полное вымирание уже не гарантировано.
У нас p = 5/7 > 2/7 = q, поэтому вероятность вымирания равна не 1, а q/p=2/5.
 
Та же самая задача известна в более наглядной формулировке.
Пьяница стоит в одном шаге от края обрыва. Каждый раз он делает случайный шаг: к обрыву с вероятностью q или от обрыва с вероятностью p=1−q. Какова вероятность того, что он когда-нибудь упадёт?
Если он сразу делает шаг к обрыву, то падает. Это даёт вероятность q.
Если он делает шаг от обрыва, то оказывается уже в двух шагах от края. Чтобы упасть, ему сначала нужно когда-нибудь вернуться в один шаг от края, а затем уже из этого положения упасть. Получается та же структура, что и в задаче про бактерии:
P=q+pP².
Можно посмотреть и иначе: считать вероятности падения ровно на 1-м, 3-м, 5-м, 7-м шаге и так далее.
На первом шаге вероятность равна q.
На третьем шаге путь только один:
1 → 2 → 1 → 0,
поэтому вероятность равна q²p.
На пятом шаге возможны уже два пути:
1 → 2 → 3 → 2 → 1 → 0,
1 → 2 → 1 → 2 → 1 → 0.
Поэтому вероятность равна 2q³p².
Дальше появляются коэффициенты
1, 1, 2, 5, 14, 42, ...
Это числа Каталана. Они считают пути, которые не пересекли границу раньше времени. То есть пьяница должен впервые упасть в обрыв именно на последнем шаге, а не раньше.
Так в задаче из первой части ЕГЭ неожиданно появляются сразу несколько больших тем: случайные блуждания, пути Дика, числа Каталана, цепи Маркова.
 
Цепь Маркова — это случайный процесс, в котором будущее зависит от настоящего состояния, но не зависит от всей предыдущей истории.
Не важно, как именно пьяница оказался в одном шаге от края. Важно только то, что он сейчас находится в одном шаге. Дальше процесс начинается как бы заново.
То же самое с бактерией. Если после деления появились две бактерии, то каждая из них начинает такую же независимую историю, как исходная.
Именно это «забывание прошлого» позволяет написать короткое уравнение вместо бесконечного дерева вариантов.
 
На уровне ЕГЭ эта задача, конечно, выглядит странно. Для первой части она слишком нетипична: ответ простой, но честное обоснование уводит далеко за пределы стандартных школьных приёмов.
Но как математический сюжет она замечательна.
Один случайный шаг сам по себе почти ничего не значит. Но если шаги повторяются снова и снова, возникает целая траектория. И тогда нас интересует уже не только то, что случится на следующем шаге, а судьба всего процесса: вымрет популяция или нет (упадёт ли пьяница, достигнет ли случайное движение границы).

Почему исчезают фамилии
 
У задачи про бактерию есть близкий исторический родственник — задача о вымирании фамилий.
Пусть фамилия передаётся только по мужской линии: от отца к сыну. Тогда судьба фамилии зависит не от общего числа детей в семье, а от числа сыновей, которые доживут до взрослого возраста и смогут передать фамилию дальше.
Если у мужчины нет таких сыновей, эта ветвь фамилии обрывается.
Если один сын — линия продолжается одной ветвью.
Если два или больше — фамилия разветвляется.
Получается ветвящийся процесс: каждый человек в текущем поколении даёт случайное число продолжателей в следующем.
В задаче про бактерию была совсем простая схема:
0 потомков или 2 потомка.
Для фамилий такая схема слишком груба. У мужчины может быть 0, 1, 2, 3, ... сыновей. Поэтому вместо двух вероятностей нужно задать целое распределение.
Уотсон и Гальтон в статье о вымирании фамилий рассматривали, например, такую модель: число взрослых сыновей распределено как Bin(5, ¼).
То есть как будто у каждого мужчины есть 5 независимых «попыток» получить сына-продолжателя, и каждая попытка успешна с вероятностью ¼. Число ¼ здесь — параметр модельного примера. Это не точная статистика по конкретной стране, а удобная модель. Но она хорошо показывает сам эффект.
По биномиальной формуле получаются вероятности:
0 сыновей: (¾)⁵ ≈ 0,237;
1 сын: 5·¼·(¾)⁴ ≈ 0,396;
2 сына: 10·(¼)²·(¾)³ ≈ 0,264;
3 сына: 10·(¼)³·(¾)² ≈ 0,088;
4 сына: 5·(¼)⁴· ¾  ≈0,015;
5 сыновей: (¼)⁵ ≈ 0,001.
Среднее число сыновей, продолжающих фамилию, равно 5·¼=1,25.
То есть в среднем на одного мужчину приходится больше одного продолжателя фамилии.
Кажется, что при таком среднем фамилия должна уверенно сохраняться. Но это не так.
Пусть P — вероятность того, что фамилия когда-нибудь исчезнет.
Если у первого мужчины 0 сыновей, фамилия исчезает сразу. Это даёт 0,237.
Если у него 1 сын, должна исчезнуть одна ветвь. Вероятность этого P.
Если 2 сына, должны исчезнуть обе независимые ветви. Вероятность P².
Если 3 сына — P³.
И так далее.
Поэтому P должно удовлетворять уравнению
P=0,237+0,396P+0,264P²+0,088P³+0,015P⁴+0,001P⁵.
Это тот же ход, что в задаче про бактерию, только вместо короткого уравнения P=q+pP² получается более длинное.
У этого уравнения всегда есть корень P=1: полное вымирание формально возможно.
Но когда среднее число продолжателей больше 1, появляется ещё один корень между 0 и 1. Именно он и даёт настоящую вероятность вымирания.
В этой модели меньший корень примерно равен P ≈ 0,55.
То есть даже при среднем числе сыновей 1,25 вероятность окончательного исчезновения фамилии — около 55%.
Это главный эффект ветвящихся процессов.
Среднее больше 1 означает не гарантию выживания, а только положительный шанс выжить.
Одна неудача в раннем поколении может оборвать всё дерево. Если в какой-то момент продолжателей стало 0, процесс попал в ноль, а из нуля уже нельзя выйти.
Поэтому в большой популяции могут одновременно происходить две вещи:
население по мужским линиям в среднем растёт,
а большинство отдельных фамилий всё равно исчезает.
Выжившие фамилии потом могут стать очень многочисленными. Но это не обязательно значит, что они были «сильнее». Часто это значит, что их ветви просто не оборвались в первых поколениях.
В обычных задачах на среднее мы смотрим на массу.
В ветвящемся процессе важен другой вопрос: что станет с одной конкретной линией?
Среднее говорит: процесс в целом способен расти.
Вероятность вымирания говорит: отдельная линия всё равно может исчезнуть навсегда.
Так что задача про бактерию из ЕГЭ не такая искусственная, как кажется. Она является маленькой моделью фамилий, родов, популяций, цепных реакций, эпидемий — всего, что не просто продолжается, а ветвится.

Среднее растёт, медиана равна нулю
 
В модели Уотсона–Гальтона из прошлой заметки среднее число сыновей-продолжателей равно 1,25.
Значит, через 10 поколений среднее число носителей фамилии от одного исходного мужчины равно 1,25¹⁰ ≈ 9,3.
Но вероятность исчезнуть к десятому поколению в той же модели составляет примерно 0,53.
То есть к этому моменту больше половины фамилий уже имеют 0 носителей.
Поэтому медиана равна 0, хотя среднее равно 9,3.
Противоречия здесь нет. Среднее считается по всем исходным фамилиям: и по исчезнувшим, и по выжившим.
Если 53% фамилий исчезли, то среднее 9,3 создаётся оставшимися 47%.
Среди выживших фамилий среднее число носителей к десятому поколению будет примерно
9,3/(1−0,53) ≈ 20.
То есть картина не такая: каждая фамилия понемногу растёт.
А такая: больше половины фамилий исчезли;
среди выживших среднее число носителей около 20.
Это типичная особенность ветвящихся процессов. Математическое ожидание может расти, хотя наиболее вероятный или медианный исход равен нулю.
Причина в нуле как поглощающем состоянии. Если фамилия исчезла, дальше она уже не восстановится. А выжившие линии продолжают ветвиться и дают вклад в среднее.
Та же разница между средним и типичным исходом появляется в других моделях с ветвлением: ранние цепочки заражений, полезные мутации, цепные реакции.
Пока ветвей мало, распределение очень несимметрично: много нулей и длинный правый хвост.
Поэтому вопрос «сколько будет в среднем?» и вопрос «что обычно случится с одной линией?» в таких задачах дают разные ответы.

Почти всегда конечно, но среднее бесконечно

Вернёмся к критической модели бактерии:
с вероятностью ½ бактерия погибает,
с вероятностью ½ делится на две.
Среднее число потомков равно
0·½ + 2·½ = 1.
Такой процесс почти наверняка вымирает. Но можно спросить не только о вымирании, а об общем числе бактерий, которые успеют появиться за всё время.
Если произошло m делений, то дерево потомства имеет m внутренних вершин и m+1 листьев. Всего бактерий: 2m+1.
Значит, возможны только нечётные значения:
1, 3, 5, 7, ...
Сколько есть разных деревьев с m делениями?
Число Каталана:
Cₘ = 1/(m+1)·C₂ₘᵐ.
Каждое такое дерево имеет m делений и m+1 смертей, всего 2m+1 случайных исходов. Поэтому вероятность одного конкретного дерева равна   (½)²ᵐ⁺¹.
Отсюда
P(T=2m+1) = Cₘ/2²ᵐ⁺¹.
Например:
P(T=1) = 1/2;
P(T=3) =1/8;
P(T=5) = 1/16;
P(T=7) = 5/128.
Теперь важна асимптотика чисел Каталана:
Cₘ ~ 4ᵐ/(√π·m³ᐟ²).
Тогда
P(T=2m+1) ~ 1/(2√π·m³ᐟ²).
Вероятность больших деревьев убывает как m⁻³ᐟ².
Это достаточно быстро, чтобы сумма вероятностей сходилась.
Но недостаточно быстро, чтобы сходилось среднее:
E(T) = Σ(2m+1) · P(T=2m+1).
Слагаемое ведёт себя как константа, умноженная на m⁻¹ᐟ², а ряд  Σm⁻¹ᐟ²  расходится.
Значит, E(T) = ∞.
Получается внешне противоречивая картина:
процесс почти наверняка когда-нибудь закончится;
но среднее общее число бактерий за всё время бесконечно.
Почти все деревья конечны. Просто распределение имеет тяжёлый хвост: редкие очень большие деревья дают бесконечный вклад в математическое ожидание.
Похожий эффект возникает в обычном случайном блуждании.
Если точка стартует из 0 и каждый раз с равными вероятностями идёт на 1 вправо или на 1 влево, то она почти наверняка когда-нибудь вернётся в 0.
Но среднее время первого возвращения бесконечно.
Причина та же: вероятность очень долгого ожидания убывает медленно, примерно как n⁻³ᐟ². Этого хватает, чтобы возвращение произошло почти наверняка, но не хватает, чтобы среднее время ожидания было конечным.
Похожий эффект встречался нам в Санкт-Петербургском парадоксе и горне Гавриила. Там тоже конечность одного параметра не гарантирует конечности другого: игра почти наверняка заканчивается, но ожидаемый выигрыш бесконечен; объём горна конечен, но площадь поверхности бесконечна. Здесь аналогично: дерево почти наверняка конечно, но его средний размер бесконечен.

Законы арксинуса

Кажется естественным, что в длинной честной игре сумма должна примерно половину времени быть положительной.
Но это неверно.
Если игра очень длинная, а шаги сделать маленькими, получится броуновское движение — непрерывный предел случайного блуждания.
Для него Поль Леви доказал три закона арксинуса.
Первый закон отвечает именно на вопрос из опроса.
Пусть A — доля времени на отрезке [0; 1], в течение которого броуновская траектория была выше нуля.
Тогда
P(A≤x) = 2/π · arcsin√x.
Это не нормальное распределение и не распределение, сосредоточенное около 1/2.
Его плотность равна 1/(π√(x(1−x))).
Она растёт у краёв 0 и 1. Поэтому крайние случаи встречаются часто.
Например,
P(A<0,1) = 2/π · arcsin√0,1 ≈ 0,205.
Столько же:
P(A>0,9) ≈ 0,205.
Значит,
P(A<0,1 или A>0,9) ≈ 0,41.
А вероятность провести в плюсе от 40% до 60% времени равна
2/π · (arcsin√0,6 − arcsin√0,4) ≈ 0,13.
То есть для длинной честной игры гораздо вероятнее провести почти всё время по одну сторону от нуля, чем выглядеть «примерно поровну».
У Леви есть ещё два закона арксинуса.
Та же самая формула описывает:
момент последнего возвращения траектории в ноль;
момент, когда траектория достигает своего максимума на отрезке [0; 1].
Во всех трёх случаях распределение одно и то же:
2/π · arcsin√x.
Это неожиданно, потому что вопросы разные.
Сколько времени траектория была выше нуля?
Когда она в последний раз была в нуле?
Когда она достигла максимума?
Но ответ задаётся одной и той же функцией арксинуса.
Так что «честная игра» означает только отсутствие сдвига в среднем.
Она не обязана выглядеть симметричной на каждом длинном промежутке наблюдения.
График честной игры часто долго держится по одну сторону от нуля. Поэтому визуально он может казаться «нечестным», хотя математически никакого преимущества у плюса или минуса нет.

Куда ушла энергия

В посте про честную игру возникала неожиданная формула:
P(A≤x) = 2/π · arcsin√x.
Там A обозначала долю времени, в течение которого накопленный выигрыш был положительным.
Оказалось, что эта доля совсем не обязана быть близкой к 1/2. Значения около 0 и 1 встречаются очень часто.
Но та же формула появляется и в гораздо более простой геометрической ситуации.
Пусть частица движется с постоянной скоростью v, но направление движения выбирается случайно.
Обозначим через φ острый угол между направлением движения и горизонталью.
Горизонтальная составляющая скорости равна
vₓ = v cosφ.
Полная кинетическая энергия пропорциональна v².
А часть кинетической энергии, связанная с горизонтальным движением, пропорциональна
vₓ² = v²cos²φ.
Значит, горизонтальная доля энергии равна
A = vₓ²/v² = cos²φ.
Если направление выбрано случайно, то из-за симметрии можно считать, что φ равномерно распределён на отрезке от 0 до π/2.
Найдём распределение величины A.
Условие A ≤ x означает cos²φ ≤ x.
Так как 0≤φ≤π/2, это равносильно условию cosφ ≤ √x.
Косинус на этом отрезке убывает, поэтому φ ≥ arccos√x.
Значит, подходящие углы занимают промежуток от arccos√x до π/2.
Его длина равна
π/2 − arccos√x = arcsin√x.
А весь промежуток возможных значений φ имеет длину π/2.
Поэтому
P(A≤x) = arcsin√x /(π/2) = 2/π · arcsin√x.
Получилась та же арксинусная формула.
Теперь посчитаем конкретные вероятности.
Вероятность, что горизонтальная доля энергии меньше 10%, равна
P(A<0,1) = 2/π · arcsin√0,1 ≈ 0,205.
Столько же вероятность, что горизонтальная доля энергии больше 90%.
Значит, P(A<0,1 или A>0,9) ≈ 0,41.
А вероятность попасть в середину, от 40% до 60%, равна
P(0,4<A<0,6) = 2/π · (arcsin√0,6 − arcsin√0,4) ≈ 0,13.
То есть случайное направление гораздо чаще даёт почти горизонтальное или почти вертикальное распределение энергии, чем аккуратное «примерно пополам».
При этом среднее значение A всё равно равно 1/2:
E(A) = E(cos²φ) = 1/2.
В среднем половина энергии приходится на горизонтальную составляющую.
Но это среднее не означает, что случайная доля обычно близка к половине.
В длинной честной игре арксинус появлялся как закон времени, проведённого выше нуля.
Здесь он появляется как закон квадрата проекции случайного направления.
В обоих случаях симметрия есть, но она не заставляет отдельный случай выглядеть как равное деление.

Вернётся ли пьяница?

Рассмотрим случайное блуждание по решётке.
На прямой точка каждый раз идёт на 1 влево или на 1 вправо.
На плоскости — на одну клетку в одном из четырёх направлений.
В трёхмерном пространстве — в одном из шести направлений.
Вопрос: вернётся ли точка когда-нибудь в исходное положение?
Ответ зависит от размерности.
На прямой — вернётся почти наверняка.
На плоскости — тоже почти наверняка.
В трёхмерном пространстве вероятность возвращения уже меньше 1.
Это теорема Пойи.
Посмотрим, откуда возникает граница между размерностями 2 и 3.
Начнём с прямой. Каждый шаг равен +1 или −1 с вероятностями ½  и ½ .
После n шагов положение равно
Sₙ = X₁+X₂+...+Xₙ,
где каждое Xᵢ равно +1 или −1.
Среднее одного шага равно E(Xᵢ) = 0.
Средний квадрат равен E(Xᵢ²) = 1.
Значит, дисперсия одного шага равна 1, а дисперсия суммы равна
D(Sₙ) = D(X₁)+...+D(Xₙ) = n.
Стандартное отклонение равно √n.
Это естественный масштаб случайного блуждания после n шагов. Обычно положение не имеет порядок n: шаги частично компенсируют друг друга, поэтому типичное отклонение от начала имеет порядок √n.
На прямой существенная часть вероятности распределена на отрезке длины порядка √n.
Поэтому вероятность оказаться в одной конкретной точке, например в начале, имеет порядок 1/√n=n⁻¹ᐟ².
На плоскости за n шагов каждая координата тоже имеет разброс порядка √n. Поэтому существенная часть вероятности распределена в области размера примерно √n×√n.
Её площадь имеет порядок n. Значит, вероятность попасть в одну фиксированную точку имеет порядок 1/n=n⁻¹.
В d-мерном случае типичный разброс по каждой координате имеет порядок √n. Значит, существенная часть вероятности распределена не по всему пространству, а по области с линейным размером порядка √n в каждом из d направлений.
Число точек в такой области имеет порядок (√n)ᵈ = nᵈᐟ².
Если вероятность распределена примерно по nᵈᐟ² точкам, то вероятность оказаться в одной фиксированной точке, например в начале, имеет порядок 1/nᵈᐟ²=n⁻ᵈᐟ².
Теперь важно, что мы складываем эти вероятности по всем моментам времени n.
Для прямой d=1, поэтому вероятность возврата в начало в момент n имеет порядок Σn⁻¹ᐟ². Возникает ряд порядка Σn⁻¹ᐟ². Он расходится.
Для плоскости d=2, поэтому вероятность возврата в момент n имеет порядок n⁻¹. Возникает ряд порядка Σn⁻¹. Он тоже расходится.
Для трёхмерного пространства d=3, поэтому вероятность возврата в момент n имеет порядок n⁻³ᐟ². Возникает ряд порядка Σn⁻³ᐟ². Он сходится.
Вот почему двумерный и трёхмерный случаи различаются.
В обоих случаях типичное расстояние от начала после n шагов имеет порядок √n.
Но число возможных точек в типичной области разное:
на плоскости — порядка (√n)²=n;
в пространстве — порядка (√n)³=n³ᐟ².
Поэтому в трёхмерном случае вероятность оказаться ровно в начале убывает быстрее: не как 1/n, а как 1/n³ᐟ².
Именно переход от ряда Σ1/n к ряду Σ1/n³ᐟ² и даёт границу между размерностями 2 и 3.
Остаётся связать это с вероятностью возвращения.
Пусть r — вероятность когда-нибудь вернуться в начало после ухода из него.
После каждого возвращения процесс начинается заново: снова та же вероятность r вернуться ещё раз.
Поэтому ожидаемое число посещений начальной точки имеет вид
1 + r + r² + r³ + ...
Если r<1, эта сумма конечна: 1/(1−r).
Если ожидаемое число посещений бесконечно, значит, r=1.
В размерностях 1 и 2 сумма вероятностей возврата по всем моментам времени расходится, поэтому ожидаемое число посещений начальной точки бесконечно. Значит, r=1.
В размерности 3 сумма вероятностей конечна, значит, ожидаемое число посещений конечно. Поэтому r<1: есть положительная вероятность больше никогда не вернуться.

Почему электричество знает, вернётся ли пьяница

В теореме Пойи случайное блуждание ведёт себя по-разному в разных размерностях.
На прямой и на плоскости точка почти наверняка когда-нибудь вернётся в начало.
В трёхмерном пространстве вероятность возвращения уже меньше 1.
Ту же границу можно увидеть без вероятностей — через электрическую сеть.
Заменим каждое ребро решётки резистором сопротивления 1 Ом.
Теперь спросим: каково сопротивление от начальной точки до бесконечности?
Оказывается, здесь работает правило:
если сопротивление до бесконечности бесконечно, случайное блуждание возвратно;
если сопротивление конечно, есть положительная вероятность уйти и не вернуться.
На прямой всё очевидно. Чтобы уйти к бесконечности, ток должен пройти через бесконечную цепочку резисторов, соединённых последовательно:
1 + 1 + 1 + ... = ∞.
Сопротивление бесконечно. Поэтому одномерное блуждание возвращается.
На плоскости ситуация не такая очевидная.
Ток может растекаться во все стороны. Но посмотрим на квадратные «слои» вокруг начала.
На расстоянии порядка r от начала слой имеет длину порядка r. Значит, через этот слой есть порядка r параллельных путей.
Если r одинаковых резисторов соединены параллельно, их общее сопротивление имеет порядок 1/r.
Чтобы уйти на бесконечность, нужно пройти все слои:
1 + 1/2 + 1/3 + 1/4 + ....
Это гармонический ряд, он расходится.
Значит, сопротивление плоской решётки до бесконечности тоже бесконечно.
Поэтому случайное блуждание на плоскости возвращается почти наверняка.
Но это уже пограничный случай: сопротивление растёт очень медленно, как гармонический ряд.
В трёхмерном пространстве слой радиуса r имеет уже не длину, а площадь порядка r².
Значит, параллельных проходов через слой порядка r², а сопротивление слоя имеет порядок 1/r².
Общее сопротивление до бесконечности ведёт себя как
1 + 1/2² + 1/3² + 1/4² + ....
Этот ряд сходится; более того, его сумма равна π²/6. Точное сопротивление решётки не равно этой сумме, но для вопроса о возвратности важен сам факт сходимости.
Поэтому в трёхмерной решётке случайное блуждание уже невозвратно: есть положительная вероятность уйти навсегда.
В размерности d та же оценка даёт слой размера порядка rᵈ⁻¹.
Сопротивление слоя имеет порядок 1/rᵈ⁻¹.
Поэтому нужно смотреть на ряд Σ1/rᵈ⁻¹.
При d = 1 он расходится.
При d =2 получается гармонический ряд, он тоже расходится.
При d ≥ 3 ряд сходится.
Так электрическая сеть даёт ту же границу, что и теорема Пойи:
d =1, 2 — возвращение почти наверняка;
d ≥ 3 — есть шанс уйти навсегда.
Почему здесь вообще появляется электричество?
Потому что напряжение в электрической сети и вероятность попадания в точку подчиняются одному и тому же локальному правилу.
Если в вершине нет источника тока, то её напряжение равно среднему значению напряжений в соседних вершинах. Это закон Кирхгофа.
Если случайное блуждание находится в вершине, то вероятность будущего события тоже равна среднему значению таких вероятностей по соседним вершинам: следующий шаг выбирается равновероятно.
В обоих случаях возникает одна и та же дискретная гармоническая функция на графе. Поэтому вопрос о возвращении случайного блуждания можно перевести на язык токов, напряжений и сопротивлений.
Электрическая формулировка показывает, что в размерности 2 путей наружу становится больше, но ещё недостаточно: сопротивления слоёв дают гармонический ряд. В размерности 3 площадь слоёв растёт как r², параллельных путей становится достаточно много, и суммарное сопротивление до бесконечности оказывается конечным.

Урна Пойи

В урне лежат 1 белый и 1 чёрный шар.
Повторяем один и тот же опыт:
достаём случайный шар;
возвращаем его обратно;
добавляем ещё один шар того же цвета.
Если достали белый, белых стало на один больше.
Если достали чёрный, чёрных стало на один больше.
На первый взгляд модель полностью симметрична. Поэтому хочется ожидать, что доля белых шаров со временем должна стремиться к 1/2.
Но это неверно.
Урна Пойи устроена иначе: ранняя случайность не сглаживается, а закрепляется.
Посмотрим на точный расчёт.
Пусть сделано n добавлений. Тогда всего в урне n+2 шара.
Пусть за это время было добавлено k белых шаров. Тогда белых шаров стало k+1, а чёрных — n−k+1.
Оказывается, для любого k = 0, 1, ..., n
P(добавлено ровно k белых)=1/(n+1).
То есть после n шагов все варианты
0, 1, 2, ..., n
для числа добавленных белых шаров равновероятны.
Это можно проверить индукцией.
После n шагов пусть каждое значение k имеет вероятность 1/(n+1).
После следующего шага получить k белых добавлений можно двумя способами:
уже было k, и достали чёрный шар;
или было k−1, и достали белый шар.
В первом случае вероятность достать чёрный равна
(n−k+1)/(n+2).
Во втором случае вероятность достать белый равна
k/(n+2).
Поэтому
Pₙ₊₁(k) = 1/(n+1)·(n−k+1)/(n+2) + 1/(n+1)·k/(n+2).
Складываем:
Pₙ₊₁(k) = 1/(n+1)·(n+1)/(n+2) = 1/(n+2).
Равномерность сохраняется.
Значит, после большого числа шагов доля белых шаров не обязана быть близка к ½ .
Более того, в пределе она стремится к случайному числу на отрезке [0; 1], и при начальной урне 1 белый, 1 чёрный этот предел распределён равномерно.
Например, вероятность того, что предельная доля белых окажется между 0,4 и 0,6, равна 0,2.
Вероятность оказаться между 0 и 0,2 тоже равна 0,2.
И вероятность оказаться между 0,8 и 1 тоже равна 0,2.
Симметрия здесь означает не сходимость к половине.
Она означает, что заранее ни один итоговый уровень не имеет преимущества.
Это модель с положительной обратной связью: чем больше белых шаров уже накопилось, тем выше шанс снова достать белый; чем больше чёрных, тем выше шанс снова достать чёрный.
Поэтому случайное раннее преимущество может закрепиться. Так появляется «случайный лидер».
Два варианта стартуют почти одинаково. Первый небольшой перевес может возникнуть случайно. Но дальше сам механизм выбора начинает этот перевес поддерживать.
Модель наглядно объясняет процессы «самоусиления», когда начальный успех увеличивает шансы на последующий успех — принцип «богатые богатеют».
Похожая логика есть в моделях популярности: статью чаще цитируют, если её уже часто цитировали; товар чаще выбирают, если его уже многие выбрали; страницу чаще открывают, если она уже поднялась выше в выдаче; участника сети чаще замечают, если у него уже много связей.
Конечно, реальные системы сложнее урны Пойи. Но основной механизм тот же:
вероятность нового выбора зависит от уже накопленного результата.
В обычном усреднении случайные колебания со временем уменьшаются. А в урне Пойи они могут стать частью будущих правил игры.

Случайный человек или случайный друг

Представим очень простую социальную сеть.
Есть один человек, который дружит со всеми остальными 100 людьми.
А каждый из этих 100 людей дружит только с ним.
Получается сеть-звезда.
У центрального человека 100 друзей.
У каждого из остальных — по 1 другу.
Сколько друзей у случайного человека в такой сети?
Среднее равно
(100+100·1)/101 ≈ 1,98.
То есть случайный человек имеет в среднем около 2 друзей.
Теперь выберем не случайного человека, а случайного друга.
Иначе говоря, выберем случайную дружескую связь и посмотрим на один из её концов.
Тогда центральный человек попадётся очень часто: к нему ведут 100 связей.
Каждый из остальных попадётся только по одной связи.
Среднее число друзей в такой выборке равно
(100²+100·1²)/(100+100)=50,5.
Получается резкий разрыв:
случайный человек имеет в среднем около 2 друзей;
случайный друг имеет в среднем 50,5 друзей.
Такой вот парадокс дружбы.
Он возникает не из-за психологии, а из-за способа выбора.
Если выбирать людей напрямую, каждый человек имеет одинаковый вес.
Если выбирать людей через дружеские связи, человек с k друзьями попадает в выборку в k раз чаще.
Поэтому более связные люди автоматически пере представлены.
В общем виде это записывается так.
Пусть D — число друзей у случайного человека.
Среднее число друзей у случайного человека равно
E(D).
А среднее число друзей у случайного друга равно
E(D²)/E(D).
Квадрат появляется потому, что человек с k друзьями имеет значение k и одновременно попадает в выборку в k раз чаще.
Так как E(D²) ≥ E(D)²,
получаем E(D²)/E(D) ≥ E(D).
Если число друзей не у всех одинаковое, неравенство строгое.
Поэтому средний друг имеет больше друзей, чем средний человек.
Популярная фраза «у большинства людей их друзья популярнее их самих» — более сильная версия этого эффекта. Она часто верна в реальных сетях, но универсальная математическая формулировка именно такая:
средний друг популярнее среднего человека.
Та же ошибка возникает в любой выборке, где мы выбираем объект не напрямую, а через его связи или появления.
Случайный ученик чаще окажется в большом классе.
Случайный пассажир чаще окажется в загруженном автобусе.
Случайная ссылка чаще приведёт на популярную страницу.
Это выборка, смещённая размером.
Чем больше у объекта связей, мест или появлений, тем чаще он попадает в наблюдение.

Встречный курс

Пусть в системе отсчёта Земли один корабль летит вправо со скоростью 0,8c, а другой — влево с такой же скоростью. За одну секунду расстояние между ними уменьшается на
0,8c + 0,8c = 1,6c.
Значит, в системе отсчёта Земли скорость их сближения равна 1,6c.
Противоречия с теорией относительности здесь нет. Число 1,6c — не скорость одного корабля в системе отсчёта другого. Это скорость, с которой уменьшается расстояние между ними по земным часам.
если источник испускает два световых луча в противоположных направлениях, то в системе отсчёта источника расстояние между фронтами лучей увеличивается со скоростью 2c. Но каждый луч по-прежнему движется со скоростью c.
В опросе спрашивалось другое: какую скорость одного корабля измерит наблюдатель на другом корабле?
Для этого обычное сложение уже не подходит. Если u и v — модули скоростей двух тел, движущихся навстречу друг другу, то скорость одного тела относительно другого равна
w = (u + v)/(1 + uv/c²).
Поэтому
w = (0,8c + 0,8c)/(1 + 0,8·0,8) = 40c/41.
Почему закон сложения скоростей устроен такой странной дробью?
Будем измерять скорости в долях скорости света. Пусть:
β₁ = v₁/c,  β₂ = v₂/c,
где v₁ и v₂ — модули скоростей двух тел. Скорость одного тела относительно другого тоже выразим в долях c и обозначим через  β₁₂. Тогда
β₁₂ = (β₁ + β₂)/(1 + β₁β₂).
Теперь введём вспомогательную величину
q = (1 + β)/(1 − β).
Для трёх скоростей получаем:
q₁ = (1 + β₁)/(1 − β₁),
q₂ = (1 + β₂)/(1 − β₂),
q₁₂ = (1 + β₁₂)/(1 − β₁₂).
Подставим формулу для β₁₂:
q₁₂ = [1 + (β₁+β₂)/(1+β₁β₂)] / [1 − (β₁+β₂)/(1+β₁β₂)].
После упрощения:
q₁₂ = (1+β₁β₂+β₁+β₂)/(1+β₁β₂−β₁−β₂).
Числитель и знаменатель раскладываются на множители:
q₁₂ = (1+β₁)(1+β₂)/((1−β₁)(1−β₂)).
Значит, q₁₂ = q₁q₂.
Итак, сами скорости складываются по дробной формуле, а соответствующие им числа q при этом просто перемножаются.
Остаётся превратить умножение в сложение. Для этого нужен логарифм. Введём величину
φ = ½ ln q = ½ ln((1 + β)/(1 − β)).
Она называется быстротой.
Поскольку q₁₂ = q₁q₂, получаем
φ₁₂ = ½ ln(q₁q₂) = ½ ln q₁ + ½ ln q₂ = φ₁ + φ₂.
Получается, что скорости складываются сложно, а быстроты — обычным образом.
Это не просто удобная замена переменной. Из определения быстроты можно выразить скорость:
β = (e^(2φ) − 1)/(e^(2φ) + 1) = th φ.
В обычной геометрии поворот сохраняет величину x² + y², а последовательным поворотам соответствует сложение углов. Преобразования Лоренца устроены похоже, только они сохраняют величину c²t² − x². Их можно рассматривать как гиперболические повороты, а быстрота φ играет роль гиперболического угла.
Поэтому быстроты складываются по той же причине, по которой складываются углы последовательных поворотов.
При этом th φ при любом конечном φ остаётся между −1 и 1. Значит, соответствующая скорость βc всегда меньше c. Скорости света отвечала бы бесконечная быстрота.

Две дороги между встречами

Если тело движется со скоростью v, то его собственное время τ связано с земным временем t соотношением
τ = t√(1 − v²/c²).
Для одного участка пути:
τ = 5√(1 − 0,6²) = 4 года.
Туда и обратно — 8 лет.
Но здесь есть более интересный способ увидеть тот же ответ.
За один участок корабль перемещается на 3 световых года за 5 земных лет. Время, прошедшее на корабле, равно
√(5² − 3²) = 4 года.
Да, получился египетский треугольник 3–4–5, только теорема Пифагора работает не как
5² = 4² + 3², а как
4² = 5² − 3².
Числа те же, но геометрия другая.
В обычной геометрии длина отрезка на плоскости равна
√(x² + y²).
В пространстве-времени собственное время между двумя событиями определяется выражением
τ = √(t² − x²/c²).
Из-за знака минус привычное неравенство треугольника как будто переворачивается.
Корабль движется от первого события — старта — ко второму, развороту, а затем к третьему — возвращению. На двух участках его собственное время равно
4 + 4 = 8 лет.
Земля между теми же событиями старта и возвращения никуда не перемещается, поэтому её собственное время равно
√(10² − 0²) = 10 лет.
Получается
4 + 4 < 10.
Ломаная мировая линия оказалась короче прямой.
Это, конечно, не особенность удачно выбранных чисел. Пусть тело движется в течение времени t₁ с координатной скоростью v₁, а затем в течение времени t₂ с координатной скоростью v₂. Скорости здесь берутся со знаками: движение в обратную сторону соответствует отрицательной скорости.
На его часах пройдёт
τ = t₁f(v₁) + t₂f(v₂),
где
f(v) = √(1 − v²/c²).
Эта функция вогнута:
f″(v) < 0.
По неравенству Йенсена
t₁f(v₁) + t₂f(v₂) ≤
(t₁ + t₂)f((t₁v₁ + t₂v₂)/(t₁ + t₂)).
Дробь в правой части — средняя скорость на всём пути. Значит, справа стоит время, которое прошло бы при равномерном прямолинейном движении между теми же двумя событиями.
Итак, между двумя фиксированными событиями в плоском пространстве-времени прямая мировая линия даёт не наименьшее, а наибольшее собственное время.
Поэтому дело не в том, что ускорение само по себе «замедляет часы». Разворот нужен, чтобы перейти с одного прямолинейного участка на другой. Меньше времени набирает именно непрямая мировая линия.
В обычной геометрии тот, кто идёт напрямик, проходит меньше.
В пространстве-времени тот, кто не сворачивает, стареет больше.

Календарь и новостная лента в эти дни довольно настойчиво предлагают одну и ту же тему. Поэтому сегодня — несколько задач про яблоки.
 
 
Задача (Я.И. Перельман)
Садовник продал первому покупателю половину всех своих яблок и ещё пол-яблока, второму — половину оставшихся и ещё пол-яблока, третьему — половину оставшихся и ещё пол-яблока и т. д. Седьмому покупателю он продал половину оставшихся яблок и ещё пол-яблока; после этого яблок у него не осталось.
Сколько яблок было у садовника?
 
Решение  по ссылке.

Задача (А.В. Шаповалов).
На столе лежат 6 яблок, не обязательно одинакового веса. Таня разложила их по 3 на две чаши весов, и весы оказались в равновесии. Саша разложил те же яблоки иначе: 2 на одну чашу и 4 на другую, и весы снова оказались в равновесии.
Докажите, что можно положить на одну чашу одно яблоко, а на другую — два так, чтобы весы опять оказались в равновесии.
 
Решение  по ссылке.