Возможно, вы слышали о финансовой стратегии ставок по методу Келли. Это система, позволяющая оборачивать себе на пользу известную информацию в азартной игре или связанные с ней предубеждения. Эта стратегия также называется максимально агрессивной или стратегией высокой дисперсии. Дело в том, что если сделать ставку выше, чем позволяет предел Келли, то последствия могут быть катастрофическими.
Недавно мне попалась странная карточная игра, в которой стратегия Келли абсолютно не подразумевала риска, поскольку в игре действует Нулевая дисперсия. В своей знаменитой книге «Математические головоломки» Питер Уинклер называет её «Next Card Bet» («Следующая карточная ставка»). Саму задачу и её решение, по-видимому, сформулировал Томас Кавер. Мне понравилась как сама эта игра в ставки, так и её анализ, поэтому я поделюсь ими с вами здесь.

Игра

Играют так: берётся стандартная колода из 52 карт, в которой 26 карт относятся к красным мастям, и 26 — к чёрным. Карты перетасовываются, и игра начинается со ставки в $1. Карты раскрываются по одной, и их последовательность в колоде не меняется. Игроку разрешено поставить любую долю имеющихся у него средств на то, какой окажется следующая карта — чёрной или красной. При выигрыше он получает столько же, сколько поставил, один к одному.
Разумеется, выигрышные стратегии в этой игре связаны с подсчётом уже увиденных чёрных и красных карт. В таком случае можно вывести, сколько красных и чёрных карт остаётся в той части колоды, которая пока не вскрыта. Например, не составляет труда удвоить капитал, не ставя ни на одну карту кроме последней. Внимательный игрок вполне может быть уверен, масть какого цвета окажется последней, спокойно поставить на неё весь свой ресурс и удвоить его.

Стратегия Келли

Стратегия Келли заключается в выборе ставки, сводящей к максимуму ожидаемый логарифм ресурса. Можно вывести формулу таким образом.
Пусть r — количество оставшихся в колоде карт красной масти, а b — количество оставшихся карт чёрной масти.  Без потери общности можно предположить, что r > b. Далее мы хотим свести к максимуму P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction) как функцию bet_fraction. Это выражение сводится к максимуму, когда производная равна нулю. Вероятность вытащить карту красной масти на следующем ходу равна r/(r + b). Поэтому мы должны решить уравнение (r/(r + b)) / (1 + bet_fraction) - (b/(r + b)) / (1 - bet_fraction) = 0. Нехитрая алгебра даёт нам bet_fraction = (r - b) / (r + b).

В таком случае, вся стратегия Келли по ставкам сводится к алгоритму:

• Если r = b, то ставки не делаем

• Если r > b, то ставим долю |r - b| / (r + b) от имеющихся у нас средств на «красное»

• Если b > r то ставим долю  |r - b| / (r + b) от имеющихся у нас средств на «чёрное»

Опробуем стратегию

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

Ввод [1]:

# импортируем инструменты
import numpy as np

Ввод[2]:

# устанавливаем генератор псевдослучайных чисел, который будет «тасовать колоду» 
rng = np.random.default_rng(2024)

Ввод[3]:

# определяем инструмент для перетасовки колоды
def k_array_with_t_true(k: int, t: int):
    """Создаём булев массив длиной k, в котором t значений равно  true"""
    is_true = np.array([False] * k, dtype=bool)
    is_true[rng.choice(k, size=t, replace=False)] = True
    return is_true

Ввод[4]:

# Реализуем стратегию ставок
def run_bets(is_red) -> float:
    """Запускаем стратегию Келли"""
    stake = 1.0
    n_red_remaining = int(np.sum(is_red))
    n_black_remaining = len(is_red) - n_red_remaining
    for i in range(len(is_red)):
        # формируем ставку
        bet_red = 0
        bet_black = 0
        fraction = np.abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining)
        if n_red_remaining > n_black_remaining:
            bet_red = stake * fraction
        elif n_black_remaining > n_red_remaining:
            bet_black = stake * fraction
        # выводим результат
        stake = stake - (bet_red + bet_black)
        if is_red[i]:
            stake = stake + 2 * bet_red
            n_red_remaining = n_red_remaining - 1
        else:
            stake = stake + 2 * bet_black
            n_black_remaining = n_black_remaining - 1
    return stake

Ввод[5]:

# играем 10000 партий
payoffs = [
    run_bets(k_array_with_t_true(52, 26)) for _ in range(10000)
]
assert np.max(payoffs) - 1e-8 < np.min(payoffs) 

(np.min(payoffs), np.max(payoffs))

Вывод [5]:

(9.081329549427776, 9.081329549427803)

На каждом прогоне мы выигрываем в 9.08 раз от поставленных средств. Интересно, что в результатах нет никакой дисперсии или вариаций. Обратите внимание: более чем девятикратный выигрыш (9.08) гораздо больше, чем двукратный выигрыш при стратегии «дождаться последней карты».
Этот результат очень необычен для стратегии Келли. Стратегия Келли гарантирует, что вы не «прогорите» (не проиграете всех денег). При этом она позволяет максимизировать ожидаемую скорость роста логарифма от поставленных средств. Но в остальном она обычно почти ничего не гарантирует, на практике может приводить к проигрышу и отличается высокой дисперсией. Почему в таком случае стратегия Келли считается беспроигрышной?

Объяснение

Существует замечательное доказательство нулевой дисперсии у этой стратегии.
Есть (52 choose 26) = 495 918 532 948 104 возможных последовательностей красных и чёрных карт в колоде. Стандартный результат (здесь не доказывается) таков, что в хорошо перетасованной колоде любая из этих последовательностей выстраивается с равной вероятностью.
Опишем новую стратегию «формирования портфеля» следующим образом.

• Каждая из возможных (52 choose 26) последовательностей красных и чёрных карт будет считаться подстратегией в рамках нашего портфеля.

• Выделяем долю 1/(52 choose 26) от нашего исходного запаса средств на каждую подстратегию. Фонд на каждую подстратегию автономен, мы не перераспределяем деньги от одной подстратегии к другой.

• Каждой подстратегии присваивается некоторая последовательность карт красной и чёрной масти, которая действительно может сложиться в реальной колоде. Все ставки подстратегии распределены так, что какая-то часть её фонда соответствует каждой карте. Фактически, весь фонд подстратегии зависит от каждой карты — ставка делается на то, что следующая открытая карта продолжит последовательность, закреплённую за данной подстратегией.

Поэтому все подстратегии в портфеле кроме одной приводят к потере всех заложенных на них фондов — поскольку рано или поздно выпадет неподходящая карта. Единственная подстратегия, которая окажется верной, приводит к 52-разовому удваиванию средств и не даёт никаких потерь. Следовательно, умножение стартового фонда этой подстратегии составит 2^(52). Соответственно, та стратегия, по которой мы сформировали наш портфель, всегда даёт общий совокупный выигрыш $1/(52 choose 26) * 2^(52) ~ $9,08 при начальной ставке $1. Такой конечный выигрыш совершенно не зависит от порядка карт. После этого я утверждаю, что новая стратегия формирования портфеля идентична стратегии Келли, применявшейся ранее.

Посудите, что происходит с портфелем, когда вытянута красная карта. В нашей стратегии доля r / (r + b) неразорительных подстратегий предполагает, что следующая карта будет «красной» и доля b / (r + b) неразорительных подстратегий предполагает, что следующая карта будет «чёрной». Следующая вытянутая карта банкротит одну половину этих стратегий и удваивает выигрыш в другой половине (в зависимости от того, какая карта была вытянута). По-видимому, стратегия портфеля, охватывающая совокупные средства, развивается следующим образом:

• Совокупная stake идёт в stake * 2 * b / (r + b), когда вытянуто «красное»

• Совокупная stake идёт в stake * 2 * r / (r + b), когда вытянуто «чёрное»

Далее простая алгебра доказывает, что окупаемость этого портфеля в точности соответствует паттерну окупаемости для использовавшейся ранее стратегии Келли, где

|r - b| / (r + b) ставилось на тот цвет, карт которого в колоде осталось больше. Стратегия Келли и стратегия нашего портфеля идентичны по окупаемости, то есть, в принципе, это одно и то же.

Для стратегии Келли характерна нулевая дисперсия, как и для стратегии портфеля, у которой точно нулевая дисперсия.

Комментарий

Мне нравится следующий вывод из изложенного. Поскольку мы всегда ставим на преобладающий цвет, после каждой проигрышной ставки колода становится всё более разбалансированной в нашу пользу. Если сделать достаточно небольшую ставку, то затем, оседлав тенденцию, вы позже растеряете капитал. В данном случае в стратегии Келли мы платим за информацию или за уменьшение неопределённости, и стратегия совершенно правильна. Логика напоминает смену фаз «исследования и эксплуатации» при решении таких задач как A/B тестирование.

Приведённое доказательство взято из книги Уинклера (Winkler Mathematical Puzzles). Я настоятельно рекомендую данную книгу, в ней подробно разобраны и другие задачи. Само доказательство выдержано в стиле Кавера. Именно Кавер впоследствии изобрёл инвестиционную стратегию универсального портфеля.