Лучшее пари для простаков

4

ЛУЧШЕЕ ПАРИ
ДЛЯ ПРОСТАКОВ

Кандидат физико-математических наук
П. А. ПЕВЗНЕР

— Почему ты никогда не играешь? — Спросил Мальыш у Смока, когда они как-то раз сделали в «Оленем роze». Нeyжели тебя не тайет к цорному столу?
— Тайет, — ответил Смок.— Но я знаю статистику производства, а мне нужна верная приблибь.

Джек Лондон, Смок Беллю

Вы наверняка знаете игру орел-решка: игрок А выбирает какую-нибудь сторону монеты (например, О — орел), сообщает об этом В; В берет другую сторону; после этого подбрасывает монета … Ни у кого не возникает сомнений в том, что игрок орел-решка — честный способ решения спорных вопросов.

В 1974 году Мартин Гарднер в статье «Парадокс, возникающий из-за неразнзитивных отношений» позnakомил читатель журнала Scientific American с «такой же чистой» игрой, которое он назвал лучшим парил проставков. Эта игра сходна с игрок орел-решка, только игроки задумывали слова не из одной буквы, как в игре орел-решка, а из нескольких букв. Мартин, игрок А задумывает слова ОРО и сообщает об этом В; В в свою очередь задумывает какое-нибудь слово такой же длины, например, OOP. Разумеется, выбранные слова не должны совпадать, поэтому А и сообщает о своей выборе В. После этого игроки начинают подбрасывать монету, записывая результат каждого бросания. Мартин, после 6 бросаний с исходами: решка, орел, решка, решка, орел, решка, будет записана последовательность POPPOP. Игра прекращается в тот момент, когда в записываемой последовательности букв на конце возникнет слово, выбранное А или В; в первом случае победа присуждается А, во втором — В. Таким образом, победает тот, чье слово появится раньше. Мартин, если на следующем монеты выпадет О, то победит А, так как будет написано POPPOP (курсивными буквами выделено возникшее в последовательности слова, выбранное игром A); Если на следующем броске выпадет P, то игру следует продолжить (так как в POPPOP не содержится ни ОРО, ни OOP); при этом в случае, когда на 8-м, 9-м и 10-м бросах выпадут О, О, Р, победит В — ведь будет написано POPPOPООР.

Если вы играете в игру орел-решка, то выбор орла или решки — дело вкуса, так как слова О и Р равноправны. На первый взгляд кажется, что и в «лучшем пари для простаков» все слова равноправны. В 1969 году создатель этой игры Вальтер Пенней обнаружил неравноправность слов. Большинство математиков, узналих правил игры, в первый момент отказываются в это поверить. Тем не менее это так — для многих пар слов выбор одного из них (самого «сильного») обеспечивает премиущество игру, осуществившего это выбор: этот игрок выгрывает чашце, чем его противник, игра оказывается нечестной. Более того, существует формула, позволяющая количественно выразить это премиущество.

С этой формулировке связана почти детективная история. Гарднер привел ее в своей статье, сославшись на известного английского математика Джона Конвея, сообщившего о ней в письме (без доказательства). Гарднер признался, что у него нет идеи о том, как ее доказывать и «предположил», что она получена с помощью матини, как и многое другое результаты Конвея.

Сообщения Конвея об этой задаче до сих пор не напечатаны, но в конце 70-х, начале 80-х годов его формула была неависимо и разными способами доказана сразу несколько математиками. Однако все эти работы использовали довольно серверный математический аппарат, и формула появлялась в них, как фокус: после деления одних трехтажных выражений на другие. Оказывается, существ-

5

вует элементарное доказательство формулы Конвеля, эскиз которого приводится в заключение этой статьи. Более того, сейчас имеется и простой алгоритм для нахождения лучшего ответа для второго игрок, хотя первоначальный заменатель алгоритм (для слов из трех букв), предложенный в статье Гарднера и принадлежший его коллеге В. Волку, по туманности и запутанности не уступает алхимическим решетам получения философского камня.

Но мы отвлеклись. Осталось невязываенным, почему слова в нашей игре могут быть неравноправными.

Какое слово сильнее?

Рассмотрим конкретный пример. Представим себе, что в игре с двумбукувенными словами игрок А поставил на комбинацию «решка-решка», а В — на комбинацию «орел-решка». Тогда А выиграет, только если при первых двух бросаниях выпадет PP: если выпадет ОР, сразу же выиграет В, если выпадет PO или OO, то В тоже выиграет, хотя и не сразу; именно, в последних двух случаях В выиграет, как только при очередном бросании выпадет P (а это когда-нибудь и произойдет — при чистом бросании монета не может всегда выпадать орлом). Таким образом, из четырех равновозможных слушав (PP, ОР, PO, OO) игрок А выиграет в одном (PP), т. е. шансы на выиграшу y А в три раза хуже, чем y B.

По поводу игры с двумбукувенными словами стоит заметить, что умный игрок А не будет выиграть слово PP (равно как и слово OO). Он выберет слово ОР (или PO), а тогда его шансы на выиграшии и проигрыш одинаковы, если, конечно, В не выберет одно из «слабых» слов OO или PP (проверьте!).

Рис. 1.

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

— Как же так,— спросит читатель,—почему бы игрок А не выбрать «самое сильное» слова, ведь он выбирает первым? А дело как раз в том, что нет самого сильного слова. Ситуация наглядно появляется рисунок 1. На нем выписаны все трехбукувенные слова составленные из букв O, P, а красные стрелки между двумя словами указывают, какое из этих двух слов сильнее (т. е. дает больше шанс на выиграшии).

Посмотрите на рисунок 1: из каждого слова выходит хотя бы одна стрелка; значит, для любого слова есть более сильное, т. е. нет самого сильного слова. Обратите внимание на цикл из слов PPO, OPP, OOP и PPO. Мы видим: из того, что слова X сильнее Y, а Y сильнее Z, вовсе не следует, что X будет сильнее Z (ситуация, которая часто возникнет в спортивных современных). Математики говорят, что отношение «быть сильнее» нетраизитивно (отсюда и название упомянутой статьи Гарднера). Имея в своей распоряжении рисунок 1, игрок B, руководствуясь стрелками, всегда может в ответ на выбор А выиграть для себя более сильное слово. И тогда он будет чаще выиграть, чем его противник.

Но насоколько чаше? И откуда следует, что рисунок 1 правильно отражает реальную ситуацию? На эти вопросы нам предстоит ответить.

Оценим шансы на выиграшии

Вернемся к двумбукувенной игре. Будем, как и раньше, предполагать, что наивный игрок А выбрал слово A=11, а его хитрый противник B поставил на слово B=01 (вместо букв O, P мы теперь пишем цифры 0,1, а игрок и выбранное им слова обозначаем одной буквой). Последовательности бросаний монеты, на которых выиграет А, будем называть A-сериями (анаалогично определяется B-серии). Например, 11 — A-серия, а 01, 001, 0001, 101, 1001, 10001 — B-серии.

6

Таблица 1.

Очевидно, что 11 — единственная А-серия (т. е. А выигрывает в том и только в том случае, когда первые два броска монеты дают 1). Далее, не менее оченьindo, что B-серия имеет вид 0…1, либо 10…1 (на месте многооточная может стать любое число нуля).

Итак, 11 — единственная А-серия. Давайте попытемся определить вероятность*) выигрыша A, т. е. должно слияев, в которых после двух бросаний появляется последовательность 11.

В результате одного бросания возможны два исхода (0 и 1) — вероятность каждого исхода равна 1/2. В результате двух бросаний возможны четыре исхода, вероятность каждого равна 1/4, следовательно вероятность выигрыша A равна 1/4 (т. е. А выигрыает в 1/4 всех слияев):

$$P(A, B) = P(11) = 1/4$$

(через $P(A, B)$ обозначена вероятность выигрыша A у В, через $P(11)$ — вероятность серии 11).

В результате $n$ бросаний могут получить $2^n$ (равновозможных) исходов; следовательно, вероятность каждого серии длины $n$ равна $1/2^n$. Для того, чтобы посчитать вероятность $P(B, A; n)$ выигрыша В за $n$ шагов или менее, необходимо найти вероятность каждого $B$-серии длины $\leq n$ и просуммировать эти вероятности. Получим

$$P(B, A; n) = P(01) + P(001) + \dots$$

$$\dots + P(0...01) + P(101) + P(1001) + \dots$$

• Мы не определем здесь понятие вероятности — в нашей стране слова «вероятность» и «доля слияев» — синонимы. Читатель, желающий ознакомиться с этим понятием, мы отсылаем к книге: А. Н. Колмогоров, И. Г. Журбенко, А. В. Прокоров, Введение в теории вероятностей, М.: Наука, 1978.

Таблица 2.

$$\dots + P(10...01) = \left( \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^n} \right) +$$

$$+ \left( \frac{1}{8} + \frac{1}{16} + \dots + \frac{1}{2^n} \right) = \frac{3}{4} - \frac{1}{2^{n-1}}.$$

Следовательно, В выигрыает у А за $n$ шагов или менее с вероятностью, которая при больших $n$ оцень близка к 3/4; вероятность того, что после $n$ бросаний еще никто не выигрел, равна $1/2^{n-1}$ (т. е. ничего мало при больших $n$). Переход к предлу в равенстве $P(B, A; n) = 3/4 - 1/2^{n-1}$ при $n \to \infty$, можно считать, что мы получим вероятность $P(B, A)$ выигрыша В у А при «неограниченном продолжении» игры:

$$P(B, A) = 3/4.$$

Вероятность выигрышей для произвольных двухбуквенных слов $A$ и $B$ показана в таблице 1 (число, стоящее на пересечении строки $B$ и столбца $A$, дает вероятность выигрыша В у А). Эту таблицу несложно составить.

Оценим преимущество

По таблице 1 строится таблица 2, дающая преимущество В над $A$

$$d(B, A) = \frac{P(B, A)}{P(A, B)}.$$

В таблице 3 приводятся преимущества для всех трехбуквенных слов. Пользоваться этой таблицей мы и построили «неграничный» граф, показанный на рисунке 1.

Но как найти числа в таблице 3? К сожалению, формула (1) малопригодна для вычисления при длине слов $l \geq 3$. Уже для трехбуквенных слов $A, B$ найти $P(A, B)$ неосредственно — весма непряная задача, а для больших $l$ — безнадежная. Но тут нас выручает «магическая»

7

Формула Конвеля

Формула Конвеля позволяет найти $d(B, A)$ при произвольных $B$ и $A$, не вычисляя никаких вероятностей. Для того, чтобы объяснить эту формулу, нам нужно определить многочлен Конвеля $K_{XY}(t)$ слов $X, Y$.

На рисунке 2 слова $Y$ шесть раз записано под словом $X$, причем каждое новое слово $Y$ сдигается на одну позицию вправо по сравнению с предыдущим (для $n$-буквенных слов слова $Y$ будет записано под $X, n$ раз).

Кажdomу сдигу слова $Y$ поставим в соответствии число 1 или 0 в зависимости от того, совпадает ли все буквы, находящиеся друг под другом в общих позициях $X$ и $Y$, или нет. Полученное таким образом слова (длины $n$) из нулей и единиц называется корреляцией $X$ и $Y$ и обозначается $\langle XY \rangle$. Так, например, для 2-го сдиги $Y$ общее позиции совпадает, поэтому во второй строке на рисунке 2 записана единица — вторая буква слова $\langle XY \rangle$.

В нашем примере
$$\langle XY \rangle = 010011.$$

В общем случае, пусть $\langle XY \rangle = e_1 \dots e_n$ (где $e_i$ — нули или единицы). Тогда многочлен Конвеля слов $X, Y$ определяется так:
$$K_{XY}(t) = e_1 + e_2 t + \dots + e_n t^{n-1}.$$

В нашем случае $K_{XY}(t) = t + t^4 + t^5$. Очень странное определение! Во всяком случае совершено непонятно, как до него можно было допуться. Но оно работает — на нем основана формула Конвеля:

$$d(B, A) = \frac{K_{AA}(1/2) - K_{AB}(1/2)}{K_{BB}(1/2) - K_{BA}(1/2)}.$$

Можно понять Гарднера, когда он приписывает выбор этой необъичной формулы «потусторонним» слам: ну магия, и только!

Не остававливаясь пока на вывод формулы (*), появим, как его пользоваться. Сначала нужно найти корреляции $\langle AA \rangle, \langle AB \rangle, \langle BB \rangle, \langle BA \rangle$. Затем по ним написать четыре многочлена Конвеля, в каждой из них подставить $t = 1/2$ и, наконец, выполнить действия, указанные в пра-