Лето 1654 года: Паскаль, Ферма и задача о разделе ставки

Вопрос светского игрока

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

Задача о разделе ставки (problème des partis). Двое играют в серию партий, каждую выигрывают с вероятностью $1/2$; банк достаётся тому, кто первым наберёт условленное число очков. Игру прерывают до конца. Как честно поделить банк?

Задача была не новой: её обсуждали ПачолиЛука Пачолиитальянский францисканец, математик и счетовод · 1447–1517Собрал в одну книгу всю математику Возрождения, описал двойную бухгалтерию и дружил с Леонардо да Винчи — а заодно поставил задачу, ответ на которую нашли только через сто шестьдесят лет. (1494), ТартальяНикколо Тартальяитальянский математик и инженер · 1500–1557Заика с рассечённым лицом, самоучка из Брешии: выиграл главный математический поединок эпохи и проиграл спор о том, кому принадлежит формула., КарданоДжероламо Карданоитальянский врач, математик и астролог · 1501–1576Напечатал чужое решение кубического уравнения и получил за это славу и вечные упрёки; первым в истории посчитал шансы в игре — и эту книгу не напечатал вовсе., Форестани — и все давали разные и неправильные ответы. Пачоли предлагал делить пропорционально уже набранным очкам. Тарталья честно писал, что задача, по его мнению, вообще не имеет математического решения, «а есть предмет судейского усмотрения».

Ответ: смотреть вперёд, а не назад

Идея Паскаля и Ферма проста и радикальна: уже сыгранное неважно; важно только то, что осталось доиграть. Доля игрока равна вероятности того, что он победил бы, если бы игру продолжили.

Разберём канонический пример. Игра до $5$ побед. Счёт $4:3$ в пользу $A$. Игру прерывают. Как делить?

$A$ не хватает $1$ победы, $B$ не хватает $2$. Значит, всё решится максимум за $1 + 2 - 1 = 2$ партии. Выпишем все $2^2 = 4$ равновероятных продолжения:

Итог: $A$ побеждает в $3$ случаях из $4$. Банк делится $3:1$.

Тонкость, на которой спотыкались до Паскаля: во второй строке партия уже не игралась бы — $A$ выиграл раньше. Ферма настаивает, что это неважно: доигрывать «вхолостую» до фиксированной длины $a+b-1$ законно, потому что это не меняет победителя, зато делает все исходы равновероятными. Паскаль сначала возражал против этого приёма, потом признал его корректность. Спор двух методов — по сути первый в истории спор о том, как правильно строить вероятностную модель.

Общая формула

Пусть $A$ не хватает $a$ побед, $B$ не хватает $b$, каждая партия выигрывается независимо с вероятностью $1/2$. Всё решается не более чем за $n = a+b-1$ партий. $A$ побеждает тогда и только тогда, когда в этих $n$ партиях у него хотя бы $a$ побед, то есть у $B$ не больше $b-1$:

$$P(A) = \frac{1}{2^{\,a+b-1}} \sum_{k=0}^{b-1} C_{a+b-1}^k.$$

Проверим на примере $a=1$, $b=2$: $n=2$, $P(A) = \frac{1}{4}\left[C_2^0 + C_2^1\right] = \frac{1+2}{4} = \frac34$. Совпало.

Метод Паскаля — рекуррентный. Обозначим $e(a,b)$ долю игрока, которому осталось $a$ побед, если сопернику осталось $b$. Тогда

$$e(a,b) = \tfrac12\, e(a-1,\,b) + \tfrac12\, e(a,\,b-1), \qquad e(0,b) = 1,\quad e(a,0) = 0 .$$

Это в точности рекуррентность треугольника Паскаля. Метод работает «с конца» и вычислительно эффективнее перебора Ферма. Метод Ферма зато без изменений переносится на несимметричный случай (вероятность партии $p \ne 1/2$) — достаточно взвесить исходы:

$$P(A) = \sum_{k=0}^{b-1} C_{a+b-1}^k p^{\,a+b-1-k} (1-p)^{k}.$$

Треугольник и его шесть веков предыстории

Тем же летом 1654 года Паскаль пишет «Трактат об арифметическом треугольнике» (опубликован посмертно, в 1665-м). Треугольник, носящий его имя, был известен задолго до него:

• Пингала, Индия, ок. II в. до н. э. — комбинаторика стихотворных размеров; таблица «меру-прастара» описана комментатором Халаюдхой в X в.
• Аль-Караджи, Багдад, ок. 1000 г. — биномиальные коэффициенты и правило их построения.
• Цзя Сянь, Кайфын, ок. 1050 г. — тот же треугольник; в Китае он и сегодня называется треугольником Ян Хуэя (XIII в.).
• Омар ХайямОмар Хайямперсидский математик, астроном и поэт · 1048–1131В Европе его знают как автора четверостиший о вине и бренности; на востоке он был прежде всего математиком, решившим кубические уравнения за пятьсот лет до итальянцев., ок. 1100 г.; Тарталья, Италия, 1556 г. (в Италии — «треугольник Тартальи»).

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

$$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k.$$

Комбинаторика и вероятность с этого момента растут сросшимися.

Вторая задача де Мере

Второй «парадокс» шевалье касался игры в кости. Опытом было установлено, что выгодно ставить на выпадение хотя бы одной шестёрки за $4$ броска одной кости. По аналогии де Мере рассуждал: одна кость — $6$ исходов, две кости — $36$, значит, шансы должны быть те же, если бросить пару костей $4 \cdot 6 = 24$ раза и ждать двойную шестёрку. Опыт показывал обратное.

Считаем:

$$P_1 = 1 - \left(\frac{5}{6}\right)^{4} = 1 - \frac{625}{1296} = \frac{671}{1296} \approx 0{,}5177 > \tfrac12 ,$$

$$P_2 = 1 - \left(\frac{35}{36}\right)^{24} \approx 1 - 0{,}5086 = 0{,}4914 < \tfrac12 .$$

Разница между $0{,}5177$ и $0{,}4914$ — меньше трёх процентных пунктов. Чтобы уверенно почувствовать её за игровым столом, нужны тысячи партий. Де Мере их сыграл. Как заметил потом ПуассонСимеон Дени Пуассонфранцузский математик, механик и физик · 1781–1840Его именем названы уравнение, скобка, формула суммирования и распределение — причём распределение он считал у себя второстепенной технической деталью. Известен и тем, что отверг рукопись Галуа., «задача, предложенная светским человеком строгому янсенисту, стала началом исчисления вероятностей».

Причина расхождения — в том, что $(5/6)^4$ и $(35/36)^{24}$ близки, но не равны. Обе величины стремятся к $e^{-2/3} \approx 0{,}5134$ при переходе к пределу «много бросков с малой вероятностью»; де Мере, по существу, наткнулся на разницу между дискретной моделью и её пуассоновским пределом (см. точку о Лапласе).

Что было дальше

Три года спустя Христиан ГюйгенсХристиан Гюйгенснидерландский математик, физик и астроном · 1629–1695Написал первый печатный учебник теории вероятностей, изобрёл маятниковые часы, открыл кольца Сатурна и объяснил свет волнами., узнав о переписке во время поездки в Париж (самих писем он не видел), напишет первый в истории печатный трактат по теории вероятностей — «De ratiociniis in ludo aleae» («О расчётах в азартной игре», 1657). В нём впервые вводится математическое ожидание как центральное понятие. Первое предложение трактата, по сути, определение:

$$E = \frac{p\,a + q\,b}{p+q},$$

где $p$ — число шансов получить сумму $a$, $q$ — число шансов получить $b$. Гюйгенс выводит это не как определение, а как теорему — из принципа справедливого обмена: ожидание есть та сумма, за которую участник согласился бы продать своё место в игре. Через полвека трактат Гюйгенса войдёт первой частью в «Ars Conjectandi» Якоба БернуллиБернуллишвейцарская династия математиков · XVII–XVIII векаВосемь математиков в трёх поколениях одной базельской семьи — и почти столько же ссор между ними; на их фамилию приходится закон больших чисел, вариационное исчисление и уравнение гидродинамики. с подробными комментариями.

Задача. Игра до $6$ побед, счёт $3:1$. Как делить банк?
(Ответ: $a=3$, $b=5$, $n=7$, $P(A) = 2^{-7}\sum_{k=0}^{4}C_7^k = \frac{1+7+21+35+35}{128} = \frac{99}{128} \approx 0{,}77$.)