Вероятность

Прошлая глава закончилась прохожим, который на каждом перекрёстке бесконечного клетчатого города выбирает дорогу наугад. Вернётся ли он домой? Джордж Пойа ответил на этот вопрос в 1921 году, и ответ звучит странно: на плоскости прохожий вернётся «с вероятностью единица», хотя легко нарисовать путь, который уводит его всё дальше и дальше. Чтобы понять, что значат такие слова, нужно сначала договориться, что такое вероятность, и научиться не верить интуиции на слово.

Интуиция о шансах подводила всех: азартных игроков, врачей, судей и профессоров математики. Поэтому эта глава устроена как суд, а подсудимая в нём — интуиция. В каждом деле она выдвигает рассуждение, которое кажется очевидным. Мы выслушаем его, проверим расчётом и опытом и вынесем приговор. Дела идут от игорного стола к телестудии, кабинету врача и залу суда, где цена ошибки — годы чужой жизни. Последним рассмотрим дело прохожего.

Дело первое: недоигранная партия

Летом 1654 года Блез Паскаль и Пьер Ферма обменялись несколькими письмами об азартных играх. Вопросы Паскалю задал его знакомый, литератор и игрок Антуан Гомбо, известный как шевалье де Мере. Один из них был старше самого Паскаля. Двое играют до трёх побед, шансы в каждой партии равны, на кону $64$ пистоли. При счёте $2 : 1$ игру пришлось прервать. Как честно поделить ставку?

Показания интуиции записал ещё в 1494 году Лука Пачоли: делить пропорционально выигранным партиям, $2 : 1$, то есть примерно $42{,}7$ и $21{,}3$ пистоли. В середине XVI века Никколо Тарталья заметил, что правило абсурдно. Если игру до ста побед прервать при счёте $1 : 0$, по Пачоли вся ставка достаётся лидеру, хотя до победы ему как до Луны.

Паскаль и Ферма посмотрели не в прошлое, а в будущее. Лидеру не хватает одной победы, отстающему двух. Значит, не больше чем через две партии матч решится. Ферма предложил сыграть мысленно обе партии, даже если первая уже всё решит. Исходов четыре, и все равновозможны: лидер выигрывает обе, первую, вторую или ни одной. Отстающему нужны две победы подряд, это один исход из четырёх. Лидер берёт матч в трёх случаях из четырёх, и справедливо отдать ему $\frac34$ ставки: $48$ пистолей против $16$. Паскаль, считавший по-другому, получил то же самое.

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

Число исходов, при которых событие $A$ наступает. Их называют благоприятными, даже если событие печальное. Число всех исходов опыта. Формула работает, только если все они равновозможны. Пример: $P(\text{лидер выиграл матч}) = \frac34$. Если бы мы считали исходами «лидер выиграл» и «лидер проиграл», то получили бы $\frac12$ — и ошиблись бы: эти два исхода неравновозможны. Ровно ту же ошибку делали игроки, считавшие разложения сумм на трёх костях.

Игра до трёх побед, шансы в каждой партии равны, счёт $2 : 0$. Какую долю ставки справедливо отдать лидеру?

Лидеру не хватает одной победы, отстающему трёх. Матч решится не позже чем через три партии. Сыграем мысленно все три: исходов $2^3 = 8$, и отстающий выигрывает матч только в одном из них, когда побеждает трижды подряд. Лидеру положено $\frac78$ ставки.

Кодекс

Классическое определение хорошо, пока исходы равновозможны. Но монета может быть погнутой, а исходов может быть бесконечно много, как у прохожего, который гуляет без конца. Андрей Колмогоров в 1933 году оставил от вероятности только три правила, которым подчиняются все разумные способы считать шансы. Вся теория выводится из них.

Классическое определение этим правилам подчиняется: доля не бывает отрицательной, доля всех исходов равна единице, а доли непересекающихся групп складываются. Здесь $A \cup B$ означает «наступило $A$ или $B$», $A \cap B$ — «наступили оба», а $\bar A$ — «$A$ не наступило». Запись $A \subset B$ значит, что каждый исход события $A$ входит и в $B$ (в некоторых книгах пишут $A \subseteq B$).

Вероятность первого события. Вероятность второго. Вероятность, что наступили оба. В сумме первых двух слагаемых эти исходы посчитаны дважды, как в формуле включений и исключений. Для несовместных событий она равна нулю, и остаётся третья аксиома. Пример: бросаем кость, $A$ — «выпало чётное», $B$ — «выпало не меньше четырёх». $P(A \cup B) = \frac36 + \frac36 - \frac26 = \frac46 = \frac23$; действительно, подходят грани $2, 4, 5, 6$.

Хитрость в том, чтобы резать события на несовместные куски: для таких кусков третья аксиома разрешает складывать вероятности.

Прямоугольник — всё пространство исходов $\Omega$, круги — события $A$ и $B$. Событие $A$ и его дополнение $\bar A$ (всё, что вне круга $A$) несовместны и вместе составляют $\Omega$. По аксиомам 3 и 2 $P(A) + P(\bar A) = P(\Omega) = 1$, откуда $P(\bar A) = 1 - P(A)$. Разрежем $B$ на два несовместных куска: $A \cap B$ (общая часть кругов) и $B \setminus A$ (часть $B$ вне $A$). По аксиоме 3 $P(B) = P(A \cap B) + P(B \setminus A)$. Если $A \subset B$, то $A \cap B = A$, и $P(B) = P(A) + P(B \setminus A) \ge P(A)$, потому что $P(B \setminus A) \ge 0$ по аксиоме 1. При $B = \Omega$ получаем $P(A) \le 1$. Теперь $A \cup B$: это $A$ и приставленный к нему кусок $B \setminus A$. Они несовместны, поэтому $P(A \cup B) = P(A) + P(B \setminus A)$. Из второго шага $P(B \setminus A) = P(B) - P(A \cap B)$. Подставляем в третий: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$.

Первое следствие выглядит скромно, но работает чаще всех. Посчитать вероятность «хотя бы одного» трудно: вариантов много. Зато «ни одного» обычно считается сразу. Паскаль пересказывает Ферма жалобу шевалье де Мере. Тот знал, что выбросить хотя бы одну шестёрку за $4$ броска кости выгодно, а хотя бы одну пару шестёрок за $24$ броска двух костей уже нет. Между тем по старому правилу игроков шансы должны быть одинаковы: $4 : 6 = 24 : 36$. Де Мере заключил, что арифметика противоречит сама себе.

Дело второе: три двери

В 1990 году читатель американского журнала Parade прислал в колонку Мэрилин вос Савант задачу, похожую на телеигру «Давайте заключим сделку» с ведущим Монти Холлом. Перед вами три закрытые двери. За одной автомобиль, за двумя другими козы. Вы выбираете дверь. Ведущий, который знает, где что стоит, открывает одну из двух других дверей, и за ней коза. Он всегда открывает дверь с козой и всегда предлагает поменять выбор. Менять?

Показания интуиции: закрытых дверей осталось две, машина за одной из них, шансы пятьдесят на пятьдесят, менять незачем. Вос Савант ответила: менять, это удваивает шансы. Журнал получил около десяти тысяч писем, среди них почти тысячу от людей с учёной степенью, и большинство авторов утверждали, что она ошиблась. По воспоминаниям коллеги Пала Эрдёша, великий комбинатор тоже не поверил, пока не увидел компьютерную симуляцию.

Приговор: менять выгодно, при смене машина достаётся в двух играх из трёх. Проще всего увидеть это так. Тот, кто меняет выбор, проигрывает, только если сразу угадал машину, а это случается в одной игре из трёх. Во всех остальных ведущий, убрав единственную оставшуюся козу, сам показывает, где машина. Со ста дверями это видно без расчётов: вы наугад ткнули в одну дверь, ведущий открыл девяносто восемь пустых и оставил закрытой ровно одну из остальных. Держаться за свой первый выбор — значит верить, что угадали с шансом один из ста.

Но виджет показывает и другое: когда ведущий забывчивый и открыл козу случайно, менять уже бесполезно, шансы действительно пятьдесят на пятьдесят. Двери те же, козы те же, а ответ другой. Значит, важно не только то, что мы увидели, но и то, как эти сведения к нам попали. Чтобы разобраться в этом, нужна вероятность, пересчитанная с учётом новых сведений.

Вероятность, что наступили оба события: исходы из $B$, в которых наступило и $A$. Вероятность условия: новый «весь мир», в котором мы теперь живём. Делим на неё, чтобы вероятности внутри $B$ снова складывались в единицу. При $P(B) = 0$ формула не работает. Пример: бросили кость, и нам сказали, что выпало чётное. Вероятность, что это шестёрка, равна $P(\text{шесть} \mid \text{чётное}) = \frac{1/6}{1/2} = \frac13$: из трёх чётных граней подходит одна. Умножив обе части на $P(B)$, получаем правило умножения $P(A \cap B) = P(B) \cdot P(A \mid B)$.

Хитрость в том, чтобы нарисовать вероятности площадями: весь квадрат имеет площадь $1$, а условная вероятность — доля одной площади внутри другой.

Машина за дверью $1$, $2$ или $3$ с вероятностью $\frac13$ каждая: делим квадрат на три равные полосы. Добавим выбор ведущего. Если машина за вашей дверью $1$, он открывает $2$ или $3$ наугад, и полоса делится пополам: по $\frac16$ на каждый вариант. Если машина за дверью $2$, ему остаётся открыть только дверь $3$; если за дверью $3$ — только дверь $2$. Ведущий открыл дверь $3$. Всё остальное не случилось, и остаются два куска: нижняя половина первой полосы и вся вторая полоса. Их площадь $P(\text{открыл }3) = \frac16 + \frac13 = \frac12$. Машина за дверью $2$ — это вся вторая полоса, по правилу умножения $P(\text{машина за }2 \cap \text{открыл }3) = \frac13 \cdot 1 = \frac13$. Делим: $P(\text{машина за }2 \mid \text{открыл }3) = \frac{1/3}{1/2} = \frac23$, а на свою дверь остаётся $\frac{1/6}{1/2} = \frac13$.

Забывчивый ведущий рисуется так же, только в каждой полосе он открывает дверь $3$ с вероятностью $\frac12$, и во второй полосе тоже. Кусок «открыл $3$, а там машина» мы выбрасываем: по условию за дверью оказалась коза. Остаются два куска по $\frac16$, и шансы выравниваются. Знающий ведущий передаёт вам сведения своим выбором, забывчивый — нет.

Дверей четыре, машина за одной. Вы выбрали дверь, знающий ведущий открыл одну из трёх других, пустую, и предлагает перейти на любую из двух оставшихся закрытых. Вы переходите на одну из них наугад. Какова вероятность выиграть машину?

С вероятностью $\frac14$ машина за вашей первой дверью, и при смене вы проигрываете. С вероятностью $\frac34$ она за одной из трёх других дверей; ведущий открыл пустую, так что машина за одной из двух оставшихся закрытых, и вы выбираете верную с вероятностью $\frac12$. По правилу умножения $\frac34 \cdot \frac12 = \frac38$. Это больше, чем $\frac14$ без смены.

Дело третье: положительный анализ

Следующее дело слушается в кабинете врача. Психолог Герд Гигеренцер давал эту задачу врачам на курсах повышения квалификации. Женщина в возрасте около пятидесяти проходит плановое обследование на рак груди. Известно: рак есть примерно у $1\,\%$ женщин её возраста; если рак есть, маммография обнаруживает его в $90\,\%$ случаев; если рака нет, снимок всё равно даёт ложную тревогу в $9\,\%$ случаев. Снимок у неё положительный. Что ей сказать?

Какова вероятность, что у женщины с положительным снимком действительно рак?

около $90\,\%$ около $81\,\%$ около $10\,\%$ около $1\,\%$

Из $1000$ женщин $10$ больны, и у $9$ из них снимок положительный. Из $990$ здоровых ложную тревогу получат около $89$. Положительных снимков $9 + 89 = 98$, и лишь $9$ из них у больных: примерно каждый одиннадцатый.

По словам Гигеренцера, верный ответ выбирала примерно пятая часть врачей, а многие называли $80$–$90\,\%$. Ошибка у них та же, что у присяжных в последнем деле. Вероятность положительного снимка при болезни — одно, вероятность болезни при положительном снимке — совсем другое, и они различаются в десять раз.

Решает дело число, о котором обычно забывают: доля больных до обследования. Здоровых в сто раз больше, и даже редкие ошибки на них складываются в толпу ложных тревог. Гигеренцер советует считать не процентами, а натуральными частотами: «из тысячи женщин…». Так задача решается на пальцах.

Хитрость та же, что с дверями: вероятности — площади в квадрате площади $1$. Правило умножения превращает каждую площадь в произведение ширины на высоту.

Разрежем квадрат на две полосы: $H$ (болен) шириной $P(H)$ и $\bar H$ (здоров) шириной $P(\bar H) = 1 - P(H)$. В полосе $H$ отложим снизу высоту ${P(E \mid H)}$: там лежат больные с положительным тестом. Площадь прямоугольника равна ${P(H) \cdot P(E \mid H)}$, а по правилу умножения это $P(H \cap E)$. В полосе $\bar H$ отложим высоту ${P(E \mid \bar H)}$: здоровые с положительным тестом, ложные тревоги. Площадь $P(\bar H) \cdot P(E \mid \bar H) = P(\bar H \cap E)$. Событие $E$ целиком состоит из двух закрашенных прямоугольников: положительный тест бывает у больных и у здоровых, и одновременно то и другое невозможно. Прямоугольники несовместны, по аксиоме 3 их площади складываются: $P(E) = P(H)\,P(E \mid H) + P(\bar H)\,P(E \mid \bar H)$. Это формула полной вероятности. По определению $P(H \mid E) = \frac{P(H \cap E)}{P(E)}$ — доля первого прямоугольника во всей закрашенной площади. Подставив $P(H \cap E) = P(H)\,P(E \mid H)$, получаем формулу Байеса.

Первый прямоугольник: априорная вероятность гипотезы (до улики), умноженная на то, насколько улика ожидаема, если гипотеза верна. У нас это доля больных $0{,}01$, умноженная на чувствительность $0{,}9$. Второй прямоугольник: то же для противоположной гипотезы, $0{,}99 \cdot 0{,}09$. Малая вероятность ложной тревоги, умноженная на огромную долю здоровых, может перевесить всё. Вместе прямоугольники дают $P(E)$. Пример: $P(\text{рак} \mid +) = \frac{0{,}01 \cdot 0{,}9}{0{,}01 \cdot 0{,}9 + 0{,}99 \cdot 0{,}09} = \frac{0{,}009}{0{,}0981} \approx 0{,}092$. Слева в формуле апостериорная вероятность — после улики.

Повторный анализ меняет картину. После первого положительного снимка вероятность рака уже не $1\,\%$, а $9\,\%$, и она становится априорной для второго теста. Если второй снимок тоже положительный, а ошибки двух снимков независимы, формула Байеса даёт около $50\,\%$. Поэтому положительный результат скрининга — повод для точного обследования, а не диагноз. Оговорка про независимость ошибок серьёзная: если тревогу вызывает особенность строения ткани, повторный снимок её повторит.

Болезнью страдает $2\,\%$ людей. Тест находит болезнь у $95\,\%$ больных и ошибочно даёт положительный результат у $5\,\%$ здоровых. Тест оказался положительным. Какова вероятность, что человек болен? Ответ дайте дробью или десятичной дробью с точностью до сотых.

Возьмём $10\,000$ человек. Больных $200$, у $190$ из них тест положительный. Здоровых $9800$, ложных тревог $5\,\%$ от них, то есть $490$. Положительных $190 + 490 = 680$, больных среди них $190$: $\frac{190}{680} = \frac{19}{68} \approx 0{,}28$.

Дело четвёртое: общий день рождения

В главе о комбинаторике принцип Дирихле гарантировал совпадение дней рождения только в компании из $367$ человек. А там же было обещано, что уже среди $23$ человек совпадение случается чаще, чем в половине случаев. Интуиция возражает: дней в году $365$, людей всего $23$, откуда взяться совпадению?

Будем считать, что каждый рождается в любой из $365$ дней с равными шансами и независимо от других; 29 февраля забудем. Совпадение — это «хотя бы одна пара», а мы уже знаем, что «хотя бы» удобнее считать через дополнение.

Посчитаем вероятность того, что все дни рождения разные, по классическому определению, а совпадение — её дополнение.

Выпишем дни рождения $n$ человек по порядку. Получится набор из $n$ дат; по правилу произведения таких наборов $365^n$, и все они равновозможны. Посчитаем наборы, где все даты разные. Первый человек может родиться в любой из $365$ дней. Второй — в любой день, кроме занятого первым: $364$ варианта, какой бы день ни занял первый. Третий — в любой из $363$ оставшихся, и так далее: у $k$-го человека свободно $365 - k + 1$ дней. По правилу произведения наборов с разными датами $365 \cdot 364 \cdots (365 - n + 1)$. Это число размещений $A_{365}^n$, и вероятность, что все даты разные, равна $\frac{A_{365}^n}{365^n}$. «Хотя бы двое совпали» — дополнение к событию «все даты разные», поэтому его вероятность равна $1 - \frac{365 \cdot 364 \cdots (365 - n + 1)}{365^n}$. Произведение всех чисел от $1$ до $365$. После деления на $(365 - n)!$ от факториала остаются только $n$ старших множителей $365 \cdot 364 \cdots (365 - n + 1)$, по одному на человека: столько наборов с разными датами. Все наборы дней рождения $n$ человек. Пример: $P_{23} \approx 0{,}507$, $P_{30} \approx 0{,}706$, $P_{50} \approx 0{,}970$, а при $57$ людях вероятность совпадения превышает $0{,}99$. Формула верна при $n \le 365$; при $n > 365$ совпадение гарантировано.

Почему интуиция ошибается? Она примеряет задачу на себя: найдётся ли кто-то, кто родился со мной в один день? Среди $22$ других людей это случается с вероятностью $1 - \left(\frac{364}{365}\right)^{22} \approx 0{,}06$. Но совпасть может любая пара, а пар среди $23$ человек $\binom{23}{2} = 253$. Каждая пара совпадает с вероятностью $\frac1{365}$, и хотя пары не вполне независимы, $\left(1 - \frac1{365}\right)^{253} \approx 0{,}50$ хорошо приближает шанс, что не совпала ни одна. Любопытно, что те же $253$ появляются и в «эгоистичном» вопросе: чтобы кто-то родился с вами в один день с вероятностью больше половины, нужно $253$ других человека.

Какова вероятность, что у пяти случайных людей дни рождения приходятся на пять разных месяцев? Считайте, что все месяцы равновероятны. Ответ дайте дробью или с точностью до сотых.

Та же схема, что в задаче о днях рождения, только «дней» двенадцать: $\frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{12^5} = \frac{95\,040}{248\,832} = \frac{55}{144} \approx 0{,}38$. Значит, с вероятностью около $0{,}62$ двое из пяти родились в одном месяце.

Дело пятое: чёрное двадцать шесть раз

По известному рассказу, 18 августа 1913 года в казино Монте-Карло шарик рулетки упал на чёрное двадцать шесть раз подряд. Где-то после пятнадцатого раза игроки кинулись ставить на красное: после такой серии красное «обязано» выпасть. Они повышали ставки с каждым новым чёрным и проиграли, по преданию, миллионы франков.

Показания интуиции: закон больших чисел обещает, что красного и чёрного выпадает поровну, значит, после длинной чёрной серии рулетка должна «отыграться» красным. Приговор: у рулетки нет памяти. Каждый запуск шарика физически не связан с прошлыми, и на колесе с одним зеро красное выпадает с вероятностью $\frac{18}{37}$ всегда, после любой серии. Эту ошибку так и называют: ошибка игрока.

Вероятность первого события. Вероятность второго. Для независимых событий вероятность «оба» — просто произведение, для зависимых нужна условная: $P(A \cap B) = P(B) \cdot P(A \mid B)$. Пример: на двух костях $P(\text{шесть и шесть}) = \frac16 \cdot \frac16 = \frac1{36}$. Двадцать шесть чёрных подряд на рулетке: $\left(\frac{18}{37}\right)^{26} \approx 7 \cdot 10^{-9}$, примерно один шанс на $137$ миллионов. Но после двадцати пяти чёрных двадцать шестое чёрное имеет вероятность $\frac{18}{37}$, как любое другое.

Как же тогда частоты выравниваются? Не компенсацией, а разбавлением. Если после двадцати лишних чёрных сыграть ещё миллион раз, эти двадцать никуда не денутся, но на фоне миллиона станут незаметны: доля чёрного подойдёт к $\frac{18}{37}$, хотя разница в штуках может даже вырасти. Что именно обещает закон больших чисел, мы точно сформулируем и докажем в следующей главе.

Честную монету бросили пять раз, и пять раз выпал орёл. Какова вероятность, что шестой бросок тоже даст орла?

$\frac12$ $\frac1{64}$ меньше $\frac12$: пора решке больше $\frac12$: орлу везёт

Броски честной монеты независимы, и вероятность орла на каждом равна $\frac12$ при любой истории.

Независимость не бывает «очевидной»: её либо обеспечивает устройство опыта (монета, рулетка, кость), либо надо проверять. Если из колоды вынули туза и не вернули его, второй туз вынуть уже труднее: события зависимы. Если в семье есть наследственная болезнь, то болезни двух братьев тоже зависимы. Вот где ошибку независимости однажды допустили в зале суда.

Свою задачу — на кости, урны, анализы или серию испытаний — можно разобрать по шагам в решателе: он нарисует дерево исходов и объяснит, какую формулу и почему он выбрал.

Дело шестое: Салли Кларк

Это дело не учебное. В декабре 1996 года у английского юриста Салли Кларк внезапно умер одиннадцатинедельный сын Кристофер. В январе 1998 года так же умер восьминедельный сын Гарри. Салли Кларк обвинили в убийстве обоих детей. В 1999 году суд присяжных признал её виновной, и её приговорили к пожизненному заключению.

Одним из доводов обвинения было число. Педиатр профессор Рой Мидоу сообщил суду, что внезапная необъяснимая смерть младенца (синдром внезапной детской смерти, СВДС) в благополучной некурящей семье вроде семьи Кларк случается примерно в одном случае из $8543$. А две такие смерти в одной семье — в одном случае из $8543 \cdot 8543$, то есть примерно из $73$ миллионов. Число прозвучало как приговор: такого не бывает, значит, это убийство.

В этом рассуждении две ошибки, и обе мы уже разобрали.

Первая: мнимая независимость. Возводить вероятность в квадрат можно, только если две смерти независимы. Но у братьев общие гены, общий дом и общие условия, и если в семье уже случилась одна такая смерть, риск второй заметно выше, чем в среднем. Число $73$ миллиона занижено, и во много раз.

Вторая, главная: перевёрнутая условная вероятность. Даже будь число верным, это $P(\text{две смерти} \mid \text{невиновна})$ — вероятность улики при невиновности. А присяжным нужна $P(\text{невиновна} \mid \text{две смерти})$. Это разные числа, как в деле о маммографии. Двойное убийство младенцев матерью — тоже исключительно редкое событие. Когда случилось что-то очень редкое, сравнивать надо не шансы одного объяснения с единицей, а шансы двух объяснений друг с другом. Это прямо следует из формулы Байеса: отношение апостериорных вероятностей двух гипотез равно отношению их априорных вероятностей, умноженному на отношение вероятностей улики при каждой из них.

Математик Рэй Хилл в 2004 году оценил обе вероятности по данным о семьях Англии и Уэльса. По его подсчёту, до знакомства с остальными уликами две внезапные смерти в одной семье были в несколько раз, примерно в $4{,}5$–$9$ раз, вероятнее двух убийств. Число, которое прозвучало в суде, указывало в противоположную сторону от того, что следовало из данных.

В 2000 году первая апелляция Кларк была отклонена. В 2001 году Королевское статистическое общество выступило с заявлением: число «один на $73$ миллиона» получено неверно, а подано так, что подталкивает к ошибке прокурора. В январе 2003 года апелляционный суд отменил приговор. Главным основанием стало то, что обвинение не раскрыло защите результаты анализов, указывавшие на бактериальную инфекцию у Гарри. Но суд отметил и то, что яркая статистика могла сильно повлиять на присяжных. Салли Кларк провела в заключении больше трёх лет. Она так и не оправилась от пережитого и умерла в 2007 году. После её дела в Англии пересмотрели и другие приговоры матерям, построенные на похожих доводах.

На месте преступления найдена ДНК. Случайное совпадение профиля с ней бывает у одного человека из миллиона. Подозреваемого нашли, проверив базу данных, и его профиль совпал; других улик нет. В городе пять миллионов жителей. Какова вероятность, что он невиновен?

одна миллионная около $\frac56$ около $\frac12$ почти ноль

Натуральные частоты: среди пяти миллионов невиновных профиль совпадёт в среднем примерно у пяти человек, плюс сам преступник. Тот, кого нашли по одному лишь совпадению, с равными шансами может оказаться любым из этих шести, и вероятность его невиновности около $\frac56$. Другие улики, конечно, могут всё изменить.

Дело седьмое: прохожий

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

Путей, которые уводят прохожего навсегда, сколько угодно: например, всё время вправо. Поэтому вопрос не в том, может ли он не вернуться, а в том, какова вероятность. Путей длины $2n$ всего $2^{2n}$, и все они равновероятны. Прохожий не вернулся за первые $2n$ шагов, если его путь ни разу не коснулся нуля после старта. Сколько таких путей?

Хитрость — принцип отражения, с которым мы уже считали правильные скобочные слова: плохой путь, отражённый до первого касания оси, превращается в путь, который легко посчитать.

Нарисуем путь ломаной: по горизонтали время, по вертикали положение. Путь не возвращается, если после старта он всё время выше оси или всё время ниже. Отражение относительно оси превращает верхние пути в нижние и обратно, поэтому невозвращающихся путей вдвое больше, чем верхних. Обозначим число верхних путей $N_+$. Верхний путь первым шагом поднимается в точку $1$ и дальше $2n - 1$ шагов не касается оси. Значит, $N_+$ — число путей длины $2n - 1$ из точки $1$, которые ни разу не касаются нуля. Пусть такой путь кончается в точке $h$; после нечётного числа шагов из нечётной точки $h$ чётно, $h = 2, 4, \ldots, 2n$. Возьмём плохой путь из $1$ в $h$, то есть касающийся оси. Отразим его кусок до первого касания относительно оси: получится путь из $-1$ в $h$. Обратно, любой путь из $-1$ в $h > 0$ обязан пересечь ось, и то же отражение вернёт плохой путь. Это соответствие один к одному, поэтому плохих путей из $1$ в $h$ столько же, сколько всех путей из $-1$ в $h$. Обозначим через $N(a \to b)$ число путей длины $2n - 1$ из $a$ в $b$. Хороших путей в $h$: $N(1 \to h) - N(-1 \to h)$. Число путей зависит только от разности концов, поэтому $N(-1 \to h) = N(1 \to h + 2)$. Сложим по всем $h = 2, 4, \ldots$: сумма $\bigl(N(1 \to 2) - N(1 \to 4)\bigr) + \bigl(N(1 \to 4) - N(1 \to 6)\bigr) + \ldots$ сокращается, и остаётся $N_+ = N(1 \to 2)$. Путь из $1$ в $2$ за $2n - 1$ шагов делает $n$ шагов вверх и $n - 1$ вниз, поэтому $N_+ = \binom{2n - 1}{n}$. Так как $\binom{2n - 1}{n} = \frac12\binom{2n}{n}$, невозвращающихся путей $2N_+ = \binom{2n}{n}$, и их доля среди всех $2^{2n}$ путей равна $\frac{1}{2^{2n}}\binom{2n}{n}$. Это же число — доля путей, которые приходят в $0$ ровно на шаге $2n$: они делают $n$ шагов вправо и $n$ влево.

Осталось показать, что эта вероятность стремится к нулю. Обозначим $a_n = \frac{1}{2^{2n}}\binom{2n}{n}$. Её удобно переписать: в $(2n)!$ соберём отдельно нечётные множители и чётные, а произведение чётных равно $2 \cdot 4 \cdots 2n = 2^n\,n!$. После сокращения

$$a_n = \frac{(2n)!}{n!\,n!\,2^{2n}} = \frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots 2n}.$$

Теперь доказательство теоремы закончено. Событие «прохожий никогда не вернётся» входит в событие «не вернулся за первые $2n$ шагов» при любом $n$, и по второму следствию аксиом его вероятность не больше $a_n < \frac{1}{\sqrt{2n + 1}}$. Число, которое меньше любого положительного числа и не меньше нуля, равно нулю. Прохожий вернётся с вероятностью $1$. При этом возвращения приходится ждать долго: за $10\,000$ шагов не вернулся примерно каждый сто двадцать пятый ($a_{5000} \approx 0{,}008$).

Число путей длины $2n$, которые ни разу не касаются нуля после старта. Столько же путей приходят в ноль ровно на шаге $2n$. Все пути длины $2n$: на каждом шаге два варианта. Оценка Валлиса. На самом деле $a_n$ ещё меньше и близко к $\frac{1}{\sqrt{\pi n}}$, но для доказательства хватает и этой. Пример: за $10$ шагов не возвращаются $\frac{252}{1024} \approx 0{,}25$ прохожих, за $100$ шагов — около $0{,}080$, за $10\,000$ — около $0{,}008$.

Пойа доказал больше. На плоскости прохожий тоже возвращается с вероятностью $1$, только ещё медленнее: в виджете видно, что за десять тысяч шагов вернулись лишь около трёх четвертей. А в трёхмерном городе из кубиков он вернётся домой лишь с вероятностью около $0{,}34$, и почти две трети прохожих уйдут навсегда. Японскому математику Сидзуо Какутани приписывают шутку: пьяный человек найдёт дорогу домой, а пьяная птица может потеряться навсегда. Для плоскости и пространства подсчёт путей уже не помогает; понадобится новый инструмент — среднее число возвращений. Доказательство ждёт нас в следующей главе.

Куда дальше

Прохожий на прямой возвращается наверняка. А сколько его ждать? Запишем, через сколько шагов он вернулся впервые, повторим прогулку тысячу раз и усредним. Среднее не успокоится: изредка попадаются прогулки в миллионы шагов, и каждая такая прогулка тянет среднее вверх. С кубиком всё наоборот: одного броска не угадать, но средние очки за десять тысяч бросков почти наверняка окажутся между $3{,}4$ и $3{,}6$.

Какие средние успокаиваются, а какие нет? Почему сумма многих случайных чисел почти всегда складывается в один и тот же колокол, из чего бы она ни состояла? И что значит, что в комнате из $23$ человек «в среднем» набирается $0{,}69$ пары с общим днём рождения? Чтобы ответить, мы перестанем говорить о событиях и начнём говорить о случайных числах. Об этом следующая глава.