Недавно, при просмотре неофициального онлайн-турнира по одной соревновательной игре, я ознакомился со следующим утверждением: для двух команд, равных по силе, т.е. когда исход матча моделируется броском симметричной бернуллиевской монетки, при игре в формате "до двух побед" вероятность счёта "в одни ворота", т.е. 2-0/0-2, равна вероятности счёта не "в одни ворота", т.е. 2-1/1-2. Это утверждение заставило меня вытащить из глубин памяти знания школьной комбинаторики и теорвера. Приведу небольшие заметки по данному вопросу.

Сценарий

Две команды — команда 0 и команда 1 — играют серию матчей. Результаты разных матчей серии являются независимыми случайными величинами со следующим распределением. Вероятность победы команды 0 в матче есть p, вероятность победы команды 1 есть q. Считаем что p+q=1, т.е. ничьей быть не может.

Серия матчей играется в формате "first to N", т.е. до тех пор, пока некая команда не одержит N > 0 побед в серии матчей. Формат "first to N" (FT N) эквивалентен формату "best of 2N-1" (BO 2N-1), где победитель определяется на основании серии матчей длины 2N-1 — если некая команда уже одержала N побед, то её оппонент не может одержать более N-1 победы, т.е. не может выиграть.

Завершившуюся серию матчей можно представить в виде последовательности нулей и единиц, где 0 на позиции i означает, что матч под номером i выиграла команда 0, а 1 на позиции i означает, что матч выиграла команда 1. Пример такой последовательности:

0 \, 0 \, 1 \, 0 \, 1 \, 0

В данном примере команда 0 выиграла со счётом 4-2 в FT4/BO7. В дальнейшем для обозначения счёта будем также использовать запись следующего вида: (x_0, x_1), где x_0 есть число побед команды 0, а x_1 есть число побед команды 1. Т.е. счёт выше можно записать в виде (4, 2). Любой счёт завершившейся серии матчей может быть представлен в виде (N, x) в случае победы команды 0, и (x, N) в случае победы команды 1, где 0 \le x < N. Заметим также что команда, победившая в серии матчей, обязана победить в последней игре серии, т.е. в случае победы команды 0 последовательность должна заканчиваться на 0, в случае победы команды 1 — на 1. Число нулей в последовательности есть число побед команды 0, число единиц в последовательности есть число побед команды 1.

Вероятность определённого счёта в серии матчей

Серия матчей между двумя командами, где в каждом матче результат (победа команды 0 или команды 1) является случайной величиной с указанными выше вероятностями, может быть моделирована как последовательность случайных величин, подчиняющихся распределению Бернулли. Если результаты отдельных матчей независимы, то вероятность выпадения последовательности есть произведение вероятностей отдельных элементов. К примеру, для рассмотренной выше последовательности 0 \, 0 \, 1 \, 0 \, 1 \, 0 вероятность именно такой серии матчей есть p \cdot p \cdot q \cdot p \cdot q \cdot p =p^4 q^2. Однако, одному и тому же счёту могут соответствовать разные серии матчей. К примеру, счёт (4, 2) может получиться из следующих серий:

1 \, 1 \, 0 \, 0 \, 0 \, 0, 1 \, 0 \, 1 \, 0 \, 0 \, 0, 1 \, 0 \, 0 \, 1 \, 0 \, 0, 1 \, 0 \, 0 \, 0 \, 1 \, 0, 0 \, 1 \, 1 \, 0 \, 0 \, 0,0 \, 1 \, 0 \, 1 \, 0 \, 0, 0 \, 1 \, 0 \, 0 \, 1 \, 0, 0 \, 0 \, 1 \, 1 \, 0 \, 0, 0 \, 0 \, 1 \, 0 \, 1 \, 0, 0 \, 0 \, 0 \, 1 \, 1 \, 0.

Необходимо подсчитать общее число возможных серий для произвольного счёта.

В серии матчей для счёта вида (N, x) (т.е. с победой команды 0) будет содержаться ровно N нулей. Расставим x единиц в последовательность из N нулей. Для первой единицы есть ровно N мест, в которые единицу можно поставить (так как последовательность должна заканчиваться нулём, а серия матчей — победой команды 0). Следующую единицу вставляем в последовательность из N+1 элементов, т.е. возможных мест для её постановки будет N+1. Считая, что все вставляемые единицы уникальны, получаем

N \cdot (N+1) \cdot (N+2) \cdot \dots \cdot (N+x-1)=\frac{(N+x-1)!}{(N-1)!}

вариантов для вставки x единиц в оригинальную последовательность из N нулей. Вспомним теперь, что любая перестановка единиц не меняет получившуюся последовательность. Это значит, что результат необходимо поделить на число перестановок x единиц, равное x!. Итого получаем:

\frac{(N+x-1)!}{x! (N-1)!}=\binom{N+x-1}{x}=\binom{N+x-1}{N-1}.

Итоговая вероятность счёта (N, x) есть \binom{N+x-1}{N-1} p^N q^x.

Для счёта (x, N), аналогичным образом, вероятность есть \binom{N+x-1}{N-1} p^x q^N.

Проверку условия нормировки

\sum_{x=0}^{N-1} \left[\binom{N+x-1}{N-1} p^N q^x + \binom{N+x-1}{N-1} p^x q^N \right] = 1

оставим читателю.

Результаты

Первым делом посмотрим просто на распределение с произвольно выбранными параметрами:

График получился асимметричным в силу того, что p \neq q, максимум вероятности достигается для счёта 3-10, что вполне соответствует заданным вероятностям. Как кривые меняются при изменении вероятностей победы в матче?

Кажется, что вероятность некоторых счётов одинакова — к примеру, при p=0.1, q=0.9 вероятность для 0-10 и 1-10 не поменялась. Обратимся к выведенным ранее формулам. Вероятность счёта (0, N) есть q^N. Вероятность счёта (1, N) есть N p q^N. Т.е. вероятности оказываются одинаковыми при Np=1 \Leftrightarrow p=\frac{1}{N}. Несмотря на то, что вероятность более длинной серии матчей для счёта (1, N) меньше вероятности короткой серии матчей для счёта (0, N), за счёт увеличения числа серий матчей, при которых достигается счёт (1, N) вероятность счёта (1, N) равна вероятности счёта (0, N).

Для N=5 подобный эффект наблюдается уже при p=0.2, q=0.8 и p=0.8, q=0.2 соответственно, тогда как для p=0.1, q=0.9 и p=0.9, q=0.1 вероятность есть монотонная функция от счёта. Рассмотрение утверждения о том, что вероятность является монотонной функцией от счёта для любых случаев, когда p<\frac{1}{N} либо q < \frac{1}{N}, оставим читателю.

Также, при p=q=\frac{1}{2} наблюдается равенство вероятностей для счётов 10-8, 10-9, 9-10, 8-10, и для счётов 3-5, 4-5, 5-4, 5-3. Покажем, что для любого N \ge 2 при p=q=\frac{1}{2} вероятность счёта (N, N-2) равна вероятности счёта (N, N-1).

Вероятность счёта (N, N-2) в данном случае есть \binom{2N-3}{N-2} \frac{1}{2^{2N - 2}}, а вероятность счёта (N, N-1) есть \binom{2N-2}{N-1} \frac{1}{2^{2N - 1}}.

Заметим, что \binom{2N-2}{N-1}=\binom{2N-3}{N-2} \frac{2N-2}{N-1}=2\binom{2N-3}{N-2}.

Получаем, что \binom{2N-2}{N-1} \frac{1}{2^{2N - 1}} = 2\binom{2N-3}{N-2}\frac{1}{2^{2N - 1}}=\binom{2N-3}{N-2}\frac{1}{2^{2N - 2}}.

Полученный результат легко объясняется с точки зрения модели: и для счёта (N, N-2) и для счёта (N, N-1) в серии матчей должен возникнуть счёт (N-1, N-2) после какого-то матча. Из этого счёта может с вероятностью \frac{1}{2} получиться счёт (N, N-2), либо с вероятностью \frac{1}{2} может получиться счёт (N-1, N-1). Из последнего счёта возможен только счёт (N, N-1) или (N-1, N) с равными вероятностями.

Так, для формата FT2/BO3 получаем что действительно, если команды равны и исход матча определяется симметричной бернуллиевской монеткой, то вероятности счётов 2-0/0-2 и счётов 2-1/1-2 одинаковы и составляют \frac{1}{2} каждый. Означает ли это, однако, что итоговый счёт для формата FT2/BO3 не позволяет извлечь совершенно никакой информации о силе команд и вероятностях победы?

Заметим, что полученные нами ранее формулы для вероятностей счёта позволяют найти ML-оценки вероятностей победы p и q. Вероятность счёта (x_1, x_2) пропорциональна произведению p^{x_1} q^{x_2}. Логарифм правдоподобия, с точностью до постоянного слагаемого, есть L = x_1 \ln p + x_2 \ln q = x_1 \ln p + x_2 \ln (1-p). Дифференцируя логарифм правдоподобия по p и приравнивая производную к нулю получаем условие экстремума: \frac{x_1}{x_2} = \frac{p}{1-p}=\frac{p}{q}.

Отсюда следуют оценки на вероятности: \hat{p}=\frac{x_1}{x_1 + x_2}, \hat{q}=\frac{x_2}{x_1 + x_2}. Доказательство того, что эти оценки максимизируют логарифм правдоподобия, оставим читателю.

Таким образом, хоть формата FT2/BO3 и недостаточно для точной оценки относительной силы команд, однако некоторую информацию ML-подход всё-таки позволяет извлечь. Рассмотрим, как меняется функция правдоподобия для фиксированного счёта:

Вероятности для счётов 2-0 и 0-2 принимают максимум в точках, соответствующих однозначной победе соответствующей команды. Вероятности для счётов 2-1 и 1-2 принимают максимум в точках p=\frac{2}{3}, q=\frac{1}{3} и p=\frac{1}{3}, q=\frac{2}{3} соответственно, т.е. счёт с одной победой в серии проигравшей команды является более сильным свидетельством в пользу равенства команд, нежели счёт "в одни ворота". Как от вероятности p зависит будет ли счёт "в одни ворота" или нет в формате FT2/BO3 ?

Вероятность счёта "в одни ворота" есть сумма вероятностей для счётов 2-0 и 0-2. Эта вероятность есть:

p^2 + q^2 = p^2 + (1-p)^2=1 - 2p + 2p^2.

Вероятность счёта "не в одни ворота" есть сумма вероятностей для счётов 2-1 и 1-2. Эта вероятность есть:

2 p^2 q + 2 p q^2 = 2pq (p+q) = 2 p (1-p)=2p - 2p^2.

Можно заметить, что счёты 2-1/1-2 могут выпадать при практически любом соотношении сил команд, кроме крайних случаев p=0, q=1 или p=1, q=0. При увеличении равенства сил команд, т.е. при p \to \frac{1}{2}, вероятность счётов 2-1/1-2 увеличивается, но она всегда ниже вероятности счётов 2-0/0-2 и становится равной только в точке своего максимума (и минимума вероятности 2-0/0-2), при p=\frac{1}{2}. Т.е. проводя между фиксированными командами достаточно большое количество серий матчей в формате FT2/BO3, мы не увидим результатов 2-1/1-2 более чем в 50% серий матчей просто в силу того, что счёт "не в одни ворота" не выпадает чаще 50% независимо от силы команд. А в случае неравенства сил команд частоты счётов 2-1/1-2 будут даже меньше 50%. Факт выпадения счётов 2-1/1-2 свидетельствует в пользу равенства команд, тогда как факт выпадения счётов 2-0/0-2 говорят об обратном.

При проведении турнира у нас нет возможности посчитать частоты различных счётов, так как большинство серий матчей проводятся для каждой пары команд, т.е. для каждых вероятностей p и q, лишь один раз. Тем не менее, даже единственный сампл счёта позволяет извлечь информацию об относительной силе команд. Несмотря на то, что при равной силе команд счёты 2-0/0-2 выпадают с такой же частотой, что и счёты 2-1/1-2, это не говорит о том, что мы можем просто не учитывать факт выпадения тех или иных счётов. Чем больше счётов 2-1/1-2 мы получаем в турнире — тем больше у нас оснований полагать, что в условиях описанный выше модели силы команд, участвующих в турнире, действительно примерно равны.

Комментарии (0)