В последнее время я решил заняться задачами по теории вероятностей, потому что мне кажется, получение знаний в этой сфере принесёт большую пользу. Я нашёл ключ, часто использующийся для решения многих из них: накладываем условие на промежуточное состояние, а затем отдельно вычисляем значение этого промежуточного состояния. Это превращает очень сложные задачи в такие, где решение практически очевидно. [Однако в таком случае мы иногда обмениваем эффективность на простоту.]

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

Получить все четыре игрушки

Франшиза, продающая фаст-фуд, добавляет в детские наборы игрушку. Есть четыре разных игрушки. Каждый набор стоит $8. Сколько вы ожидаете заплатить для получения всех четырёх игрушек?

Как всегда бывает с подобными задачами, начнём с интуитивного понимания и выработаем грубую аппроксимацию. (Минимальное количество наборов будет равно четырём, и я бы очень удивился, если бы кому-то понадобилось купить для получения всех четырёх игрушек больше 25 наборов, поэтому, вероятно, логичной прикидкой будут ожидаемые затраты в интервале $50–120? Это очень грубая прикидка, но лучше, чем ничего!) Иногда необходимо быстро дать решение задачи, пока вы работаете над более точным, поэтому полезно выработать такое интуитивное чувство.

Анализ

Затраты — это просто функция от количества купленных наборов, так что давайте сосредоточимся на количестве наборов. Существует множество способов вычислить это ожидание, однако я предпочитаю способы, основанные на фундаментальных знаниях. (Причина этого заключается в том, что у меня ужасная память, зато ум довольно неплох, поэтому сосредоточившись на основах, я смогу запоминать меньше, но применять эти знания более широко. Другая причина работы с фундаментальными знаниями заключается в том, что они устойчивы к вариациям в описании задачи. В этом примере у всех игрушек одинаковая вероятность нахождения. Если это не так, то некоторые виды анализа окажутся неприменимыми. А моё решение будет относительно легко адаптировать с учётом этого.) С точки зрения основ, ожидаемое количество купленных наборов — это функция вероятности нахождения четвёртой игрушки в любом конкретном наборе. Чтобы упростить решение (сделать больше шагов, но каждый из них будет проще), мы начнём с изучения вероятности наличия четырёх игрушек (не нахождения четвёртой игрушки) после покупки любого количества наборов.

Мы начнём с записи вероятности получения игрушек после покупки наборов в виде . Некоторые примеры тривиальны:

• , потому что после первого набора мы гарантировано получим одну игрушку.
• , потому что после первого набора мы гарантировано не получим четыре игрушки.
• Аналогично, , потому что после второго набора у нас в лучшем случае будет две игрушки, а не три.
• Вероятно, мы также можем предположить, что очень мала, поскольку после покупки 99 наборов нужно быть невероятно неудачливым, чтобы по-прежнему иметь только одну разновидность игрушки.
• Аналогично, мы можем предположить, что очень близко к 1, потому что после покупки 99 наборов мы можем быть вполне уверены, что найдём все четыре игрушки.

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

• у нас было три игрушки и после пятого набора, и мы не нашли четвёртую игрушку в этом
• у нас было всего две игрушки после пятого набора, и в этом наборе мы нашли третью.

В обобщённом математическом виде это можно записать так:

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

то есть вероятность того, что событий и равна вероятности события , когда событие уже произошло, умноженное на вероятность события . Применив этот принцип к нашему примеру, получим

Первый из этих множителей, — вероятность ненахождения следующей игрушки в наборе . Он зависит от количества игрушек: если у нас одна игрушка, то вероятность получения той же самой игрушки составляет 1/4. Если у нас три игрушки, то вероятность повторного получения любой из них равна 3/4.

Второй множитель, , можно вычислить рекурсивно.

Подобные рассуждения применимы и к другом случаю, когда мы находим игрушку в наборе . В конечном итоге. вероятность получения игрушек после покупки наборов равна

Если вы прочитаете это внимательно, то сможете определить интуитивное значение каждого множителя. Учитывая то, что мы знаем об условных вероятностях, можно ещё немного упростить вычисления. (На случай, если вас сбивает с толку числитель 5-k: учитывая, что у нас есть игрушек после набора , вероятность нахождения игрушки в этом наборе зависит только от того, сколько игрушек нам не хватает. Если мы ищем последнюю игрушку, то вероятность найти её равна 1/4. Запутаться легко в том, что если мы ищем игрушку , то нам не хватает не просто 4-k игрушек, а 4-(k-1) = 5-k игрушек.)

Черновик в электронной таблице

В принципе, мы можем вычислить это в электронной таблице. Для первого набора мы вручную зададим значения (1,0,0,0), потому что найдём в этом первом наборе первую игрушку, и это даёт нашей рекурсии базовый случай. Аналогично, вероятность получения 0 игрушек после каждого набора равна 0, и это тоже базовый случай для нашей рекурсии. Тогда для каждой ячейки мы задаём, что она в k/4 меньше ячейки слева и в (5-k)/4 раз меньше ячейки выше и левее. (Меня удивило то, что после покупки четырёх наборов вероятность получения всех четырёх игрушек больше (9%), чем вероятность наличия всего одной (2%). Интуитивно мне казалось, что оба эти случая были равно маловероятны — или мы получаем одинаковую игрушку в каждом наборе, или по разной в каждом наборе. Причина того, что четыре игрушки вероятнее, в том, что они дают больший выбор в том, как будут получены вторая, третья и четвёртая игрушки.)

Наивный код на Python

Если нам надоест автоматическое заполнение ячеек в электронной таблице, мы можем написать рекурсию на чём-то типа Python, и спросить вероятность того, что мы, например, получим четыре игрушки после покупки пяти наборов. Согласно нашему черновику в электронной таблице, она должна быть равна 23%.

import functools

@functools.cache
def P(i, k):
    if i == 1:
        return 1 if k == 1 else 0

    p_found = (5-k)/4 * P(i-1, k-1)
    p_notfound = k/4 * P(i-1, k)

    return p_found + p_notfound

print(P(i=5, k=4))

Результат:

0.234375

Вот и всё!

Динамическое программирование

Однако если мы попробуем использовать этот код для нахождения вероятности получения четырёх игрушек после каждого набора, то столкнёмся с проблемой неэффективности рекурсии. Так как каждый набор зависит только от предыдущего набора, а количество игрушек, которые мы не можем найти, снижается, вместо рекурсии можно использовать динамическое программирование.

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

from itertools import islice

def P_k4():
    # Базовый случай первого набора для рекурсии.
    p_n = [0, 1, 0, 0, 0]
    while True:
        yield p_n[4]
        # Выполняем обновление "в обратном порядке" из-за зависимостей данных.
        for n in (4, 3, 2, 1):
            # Сюда встраивается другой базовый случай.
            p_found = 0 if n == 1 else (5-n)/4 * p_n[n-1]
            p_notfound = n/4 * p_n[n]
            p_n[n] = p_found + p_notfound

print(list(islice(P_k4(), 5)))

Результат:

[0, 0.0, 0.0, 0.09375, 0.234375]

Так и есть!

Ожидаемое количество наборов

Теперь у нас есть способ определения вероятности получения четырёх игрушек после покупки указанного количества наборов, а изначально мы хотели ответить на вопрос о вероятности нахождения четвёртой игрушки. Однако если мы возьмём вероятность получения четвёртой игрушки после набора 9 и вычтем вероятность получения четвёртой игрушки после набора 8, то получим вероятность нахождения четвёртой игрушки в наборе 9.

Мы создадим новый генератор на основании имеющегося, он будет вычислять эти последовательные разности.

def P_finding4():
    # Первый набор имеет вероятность 0 получения четвёртой игрушки.
    yield 0
    # Создаём два генератора, выполняем смещение одного из них.
    distr, offset = P_k4(), P_k4()
    next(offset)
    # Вычисляем последовательные разности.
    for a, b in zip(distr, offset):
        yield b - a

Теперь можно использовать этот код для вычисления ожидаемого количества наборов, которые нужно купить, умножив вероятность нахождения четвёртой игрушки в каждом наборе на номер этого набора. Так как существует бесконечное количество таких вероятностей, мы должны ограничить эти вычисления, допустим, первыми 150, которые, скорее всего, содержат основную часть информации всей последовательности. (Как я пришёл к значению 150? Просто попробовал множество разных чисел, пока результат не стабилизировался.)

find_probabilities = islice(P_finding4(), 150)
expectation = sum(
    p*(i+1) for i, p in enumerate(find_probabilities)
)
print(expectation)

Результат:

8.33333333333334

И это ожидаемое количество купленных наборов! При $8 за штуку мы ожидаем потратить примерно $67. Учитывая качество игрушек и их коллекционную стоимость, это может быть небольшим перебором.

Проверка

Нам нужно проверить свои вычисления. К счастью, сценарий достаточно мал, чтобы его можно было просто симулировать. Мы напишем одну функцию, которая симулирует покупку наборов, пока не получит все четыре игрушки. (А что насчёт ограничений итераций? Для симуляции они неважны, потому что на практике она всегда найдёт все четыре игрушки задолго до того, как купит тысячу наборов. Просто наличие в продакшен-коде того, что потенциально может превратиться в бесконечный цикл — плохая идея, поэтому я всегда имею привычку устанавливать для таких вещей пределы итераций, если не могу доказать, что они не могут закончиться сами по себе.) Вторая функция будет выполнять эту симуляцию большое количество раз, чтобы получить среднее количество купленных наборов.

import random

def buy_meals_until_all_toys(iterlimit=1000):
    owned_toys = [False] * 4

    for i in range(iterlimit):
        owned_toys[random.randrange(0, 4)] = True
        if all(owned_toys):
            return i+1

    raise Exception(f'Expected simulation to finish in {iterlimit} iterations.')

def estimate_expectation(n=5000):
    total = 0
    for i in range(n):
        total += buy_meals_until_all_toys()
    return total/n

print(estimate_expectation())

Результат:

8.3564

Это и в самом деле близко к теоретическому значению 8.33, которое мы нашли ранее. Хорошо!

Игра в остановленный кубик

Мастер игры один раз бросает кубик. Вы выигрываете сумму в долларах, равное количеству точек на верхней грани, но можете обменять свой выигрыш (каким бы он ни был) на новый бросок. Вы можете сделать это дважды, иными словами, на третьем броске вам придётся принять любой полученный выигрыш. Участие в игре стоит $4. Сыграете?

Вопрос в том, будет ли ожидаемое значение ev первого броска превышать стоимость входа в игру ($4). Кажется, это сложная задача. Однако мы можем быстро определить ev третьего броска: $3.5. (Это среднее количество точек, которые выпадут на кубике.) Отсюда мы можем двинуться назад. Если предположить, что мы выбрали сделать второй бросок, то нужно будет выбирать между сохранением текущего выигрыша (известного числа в интервале 1–6) или риском последнего броска со значением ev 3.5.

Очевидно, что если при втором броске выпало 1–3, то стоит рискнуть и сделать третий. Если при втором броске выпало 4–6, то в среднем мы выиграем, забрав этот выигрыш и больше не бросая. Тогда каково значение ev второго броска? Есть две возможности:

• Выпадет 1–3, в таком случае будет браться ev третьего броска, который мы совершим: 3.5; или
• Выпадет 4–6, мы оставим выпавшее, в таком случае ev будет равно среднему этих чисел: 5.

Оба этих результата равновероятны, то есть ev равно (3.5+5)/2 = 4.25.

Мы используем те же рассуждения, возвращаясь к первому броску. Учитывая ev второго броска, мы можем оставить свой выигрыш на первом броске, только если он равен 5 или 6. Это значит, что первый бросок имеет ev 2/6 × 5.5 + 4/6 × 4.25 = 4.67.

Если устроитель игры берёт с нас за неё всего по $4, то мы должны играть максимальное количество раз, ведь средняя прибыль составит по $0.67 за игру! Но вычислить мы это смогли потому, что смогли обусловить результат предыдущего броска и мы знаем вероятности этого.

Воссоздание ставки

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

Вы говорите другу, что станете контрагентом в его ставке и в случае победы Альфы выплатите вдвое от того, что заплатил он, в противном случае ничего. Делаете ли вы ошибку?

Если считать, что вы не хотите рисковать с этой ставкой, на самом деле вопрос формулируется так: за каждый $1, отданный вам другом, сможете ли вы ставить его на отдельные игры у букмекеров так, что в конце получите $2, если Альфа выиграет серию, а в противном случае ничего?

Структуру серии можно изобразить так:


(Белые узлы обозначают игры, а числа в узле — это количество побед каждой команды до начала игры. Чёрные узлы обозначают, что победитель определён и больше игр не будет, а в узле указан результат серии.)

В результатах, показанных в верхних двух чёрных узлах, нам нужно иметь $2, а в нижних двух узлах ничего. Для понятности добавим эту информацию в граф.


Это накладывает ограничение на игру 1–1: нам нужно сделать ставку так, что если Альфа победит, мы получим $2, а если Альфа проиграет, мы не получим ничего. Поразмыслив, мы придём к ответу: перед игрой мы должны обладать $1, и поставить его на победу Альфы в игре. Это мы тоже добавим в граф.


Теперь процесс повторяется. Это наложило ограничение на игру 1–0. Мы должны обладать деньгами и поставить их так, чтобы если Альфа выиграет, у нас было $2, а если Альфа проиграет, то у нас всё равно останется $1. Это может произойти, только если у нас $1.5, а ставка равна $0.5. Это продолжается до самой первой игры:


Иными словами, если вероятности для всех игр установлены заранее, мы можем воссоздать ставку на серию 2:1, умным образом делая ставки на отдельные игры. Мы разобрались, как это делать, наложив условия на результаты предыдущих игр.

Черновик в электронной таблице

При таком малом количестве игр вычисления можно выполнить вручную. Если команды проводят больше игр, то нам может понадобиться электронная таблица. Наклонив голову вбок, мы увидим, что узлы графа образуют своего рода систему координат, где по каждой оси указано количество побед соответствующей команды.

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


Теперь для каждой игры у нас есть следующие уравнения:

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

или что количество наших денег в каждой ячейке просто будет средним от победы и проигрыша по этой ставке. (Из-за коэффициента 2:1.)

Подставим эту формулу и выполним автоматическое заполнение с правой нижней ячейки до левой верхней.


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

Если коэффициент отличается от 2:1, например, 1.63, то в результате у нас получатся чуть более сложные уравнения:

это даст нам вероятность . Если мы подставим эту формулу в электронную таблицу, то увидим, что чтобы остаться с $1 в случае победы A, нам нужно начать с $0.71.


Из этого мы узнали, что подходящие коэффициенты на всю серию, исходя из коэффициентов на отдельные игры, составляют 0.71:1, или 1.41 в десятичном виде.