Оптимальная стратегия вероятностной игры

08.09.2021

Вы играете в игру, в которой вероятность выигрыша составляет 0,45, а вероятность проигрыша - 0,55. Вы начинаете с 2000 фишек, и условие выигрыша состоит в том, что если вы поставите в общей сложности 10000 фишек, вы выиграете. В противном случае, если у вас закончатся фишки, вы проиграете.

Например, если вы поставите 20 фишек, независимо от результата, вы получите 20 фишек в общей сумме. И у вас останутся текущие чипы 1980 или 2020 годов.

Минимальный размер ставки составляет 1 доллар, а максимальный - столько, сколько у вас сейчас. Какая стратегия лучше всего увеличивает вероятность выигрыша?

Я сказал, что вам следует использовать стратегию, подобную ставке как можно больше в каждом раунде. В противном случае вы проигрываете в LLN, и простое продление с небольшими ставками приведет к тому, что вы потеряете больше в долгосрочной перспективе. Я сказал, что вы, возможно, сможете рассчитать точную стратегию, используя динамическое программирование, где f (s, t) представляет то, что вы должны делать ставки на каждую комбинацию (текущие деньги, общая сумма на данный момент). Однако я не знаю, правильно ли это, и у меня не было времени, чтобы полностью решить эту проблему.

3 ответа 3

Ваша оптимальная стратегия минимизации риска - ставить одну фишку каждый раунд.

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

OP полагает, что закон больших чисел свидетельствует в пользу того, чтобы делать большие ставки в надежде очень быстро достичь общей суммы фишек в размере 10 000 долларов:

Я сказал, что вам следует использовать стратегию, подобную ставке как можно больше в каждом раунде. В противном случае вы проигрываете в LLN, и простое продление с небольшими ставками приведет к тому, что вы потеряете больше в долгосрочной перспективе.Я сказал, что вы, возможно, сможете рассчитать точную стратегию, используя динамическое программирование, где f (s, t) представляет то, что вы должны делать ставки на каждую комбинацию (текущие деньги, общая сумма на данный момент). Однако я не знаю, правильно ли это, и у меня не было времени, чтобы полностью решить эту проблему.

Но все наоборот.

Предположим, что в каждом раунде $ k \ geq 1 $ я ставлю $ C_k $ фишек, где $ C_k $ - целое положительное число.

Так как я выиграю с вероятностью 0,45 доллара, но проиграю с вероятностью 0,55 доллара, мое ожидаемое изменение богатства на раунде $ k $ составит 0,45 доллара C_k - 0,55 C_k = -0,1 C_k, $$ с дисперсией 1,1 ^ 2 C_k ^ 2. (0,45) + 0,9 ^ 2 C_k ^ 2 (0,55) = 0,99 C_k ^ 2. $$ Это означает, что чем больше я ставлю на раунд $ k $, тем больше я ожидаю проиграть и тем выше предполагаемая волатильность / риск. . Моя стратегия минимизации потерь и волатильности для каждого отдельного раунда состоит в том, чтобы каждый раз ставить $ C_k = 1 $, так что я теряю в среднем 0,1 $ фишки за раунд. Поскольку дисперсия независимых переменных является аддитивной, дисперсия за раунд составляет около 0,99 доллара за «квадрат фишек».

В долгосрочной перспективе это может показаться неутешительным, поскольку ожидается, что мое состояние $ W_k $ в начале раунда $ k $ будет неумолимо снижаться: $$ \ Bbb [W_k] = W_0 - 0,1 k, $$ где $ W_0 $ - мой начальный банкролл.

Но помните - мы играем не для того, чтобы накопить фишки , мы играем, чтобы оставаться в игре как можно дольше . А любая ставка $ C_k>1 $ фактически уменьшает $ \ Bbb. [W_ ] $ относительно однокристальной стратегии. Не существует стратегии ставок для $ C_k $, которая могла бы улучшить ожидание одной фишки $ \ Bbb. [W_ ] = W_0 - 0,1 (k + 1) $.

Кроме того, стратегия с одной фишкой также обеспечивает минимально возможную волатильность:любая ставка $ C_k>1 $ увеличивает $ \ operatorname (W_ ) $, относительно стратегии с одной фишкой, которая имеет следующую дисперсию и стандартное отклонение банкролла: \ begin \ OperatorName (W_k) & = 0.99 k \\ \ sigma_ = \ sqrt (W_k)>& = \ sqrt , \ \ end где $ \ sigma_ $ - стандартное отклонение моего банкролла $ W_k $ в начале раунда $ k $.

Таким образом, если мы будем ставить только одну фишку в каждом раунде, наш начальный банкролл в размере $ W_0 = 2 000 $ дает нам отличную возможность разместить ставки на сумму $ 10 000 фишек до того, как мы разоримся,хотя и медленными темпами.

Если мы ставим одну фишку на раунд, нам потребуется k $ = 10 000 $ раундов, чтобы достичь заявленного условия выигрыша. Но так как мы начали с фишек $ 2,000 $, у нас есть $$ \ Bbb [W_ ] = W_0 - 0,1 (10,000) = 2,000 - 1,000 = 1,000. $$ То есть мы ожидаем округлить до 10,000 $ и выиграть, имея очень удобный запас фишек в размере 1,000 $!

Более того, мы отклоняемся от этой суммы в среднем всего на $$ \ sigma_ >= \ sqrt = 99.5 \ text $$ Обратите внимание, насколько это ничтожно мало по сравнению с нашим ожидаемым банкроллом? Это означает, что у нас есть большие шансы на успех - на самом деле, очень высокие шансы на успех.

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

Мой фактический банкролл в $ W_ $ после раундов $ 10,000 $ при использовании стратегии с одной фишкой равен $$ W_ = 2,000 + \ sum_ ^ X_i, $$, где $ X_i $ - iid $. \ $ -значные случайные величины с $ \ Bbb

(X_i = +1) = 0,45 $ для всех $ i = 1, 2,. 10,000. $

10,000 $ настолько велико, что, согласно центральной предельной теореме, $ W_ $ по сути является нормальной случайной величиной со средним значением $ \ mu_ = 1,000 $, дисперсией $ \ sigma ^ 2_ = 10,000 (0,99) = 9,900, $ и стандартное отклонение $ \ sigma_ = \ sqrt \ приблизительно 99,5 $ фишек.

Закончились фишки после ставок в размере 10 000 долларов США, т.е. $ W_ = 0 долларов США, соответствовало бы z-баллу $$ z = \ frac = -10, $$, что имеет абсурдно малую вероятность порядка $ e ^ \ приблизительно 10 ^ $, или около одного секстиллиона.

Вероятность того, что я буду банкротом в более раннем раунде, чем 10 000 $ -й раунд, даже ниже, чем вероятность того, что я буду банкротом в раунде 10 000 $. Фактически, у меня даже не будет возможности разориться, пока не будет около 2000 долларов. Таким образом, мы можем ограничить мою вероятность проигрыша примерно на $ 8000 \ умножить на 10 ^ \ приблизительно 10 ^ $, или примерно на один квинтиллион.

Для сравнения: если бы я играл в эту игру раз в секунду, мне потребовалось бы как минимум $ 10 ^ $ секунд $ \ приблизительно 32 $ миллиарда лет, чтобы увидеть свой первый проигрыш!

Это объясняет приведенный выше комментарий Ионцы Иеггиеры:

К сожалению, для $ T = 10 000 $ скрипт завершится ошибкой из-за превышения ограничений по времени и памяти онлайн-калькулятора Magma.

Даже если Magma смогла бы смоделировать эту игру миллиард раз в секунду, Magma потребовались бы десятилетия или десятилетия, чтобы зарегистрировать что-либо, кроме победы!

Ускорение моих ставок непропорционально увеличивает мой риск разорения

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

Скажем, я хочу идти в 10 \ раз быстрее, поэтому я ставлю $ C_k = 10 $ фишек каждый раунд, и мне потребовалось бы раундов по 1000 $, чтобы достичь цели в 10 000 $. Я ожидаю, что при этой стратегии я потеряю около 0,1 доллара C_k = 1 фишку за раунд, поэтому после раундов по 1000 долларов я ожидаю, что у меня будет $$ \ Bbb [W_ ] = 2 000–1 000 (1) = 1 000 $$ фишек осталось.

( Обратите внимание, что, используя стратегию с одной фишкой, мы ожидаем, что на этом этапе игры у нас останется намного больше нашего начального банкролла: $ \ Bbb [W_ ] = 2,000 - 1,000 (0,1) = 1,900 $ осталось фишек. Но со стратегией с одной фишкой у нас все еще есть ставки на 9000 долларов, тогда как со стратегией с десятью фишками мы уже заканчиваем раунд на 1000 долларов, если мы дойдем до этого. )

Результирующий анализ очень похож: мой фактический банкролл в $ W_ $ после раундов $ 10,000 $ при использовании стратегии с десятью фишками равен $ W_ = 2,000 + 10 \ sum_ ^ X_i $, где $ X_i $ - это iid $ \ $ -значные случайные величины с $ \ Bbb

(X_i = +1) = 0,45 $ для всех $ i = 1, 2,. 1,000. $

W_ $ снова в основном нормальное значение для CLT, в среднем $ \ mu_ = 1,000 $.

Однако на этот раз, поскольку мы делаем ставку в 10 раз больше за раунд, наша дисперсия в 100 раз больше, что соответствует стандартному отклонению в 10 раз больше. Ожидаемая стоимость одиночной ставки составляет $ -1 $ фишек, поэтому дисперсия одиночной ставки составляет $$ (10 - (-1)) ^ 2 (0,45) + (-10 - (-1)) ^ 2 ( 0,55) = 99 \ text $$, а дисперсия наших ставок в размере 1000 $ составляет $ \ sigma ^ 2_ = 1000 \ times 99 = 99000 $. Это дает нам стандартное отклонение $ \ sigma_ = \ sqrt \ приблизительно 314,6 $ фишек. Таким образом, вероятность разорения вround $ W_ $ соответствует вероятности получения $ z $ -оценки $$ z = \ frac = -3,178, $$, что все еще является довольно низкой вероятностью (около 0,007–0,008 долларов США). $), но теперь твердо в пределах возможного. И это просто вероятность разорения при ставке в 1000 долларов - моя вероятность разориться на уровне или раньше.ставка 1000 $ на самом деле немного выше. Итак, мое нетерпение увеличило мою вероятность проигрыша в тысячу миллионов миллионов раз и сильно повлияло на мою погрешность. В тот момент, когда вы все еще играете в эту игру за 1000 долларов подряд, компромисс, похоже, не стоит того. Ставки на фишки по 2 или 5 долларов за раунд, сохраняя при этом практически гарантированную вероятность выигрыша, предлагают еще более скромное ускорение. И, конечно же, ни стратегия с пятью фишками, ни стратегия с двумя фишками не предлагают более высокую вероятность выигрыша, чем стратегия с одной фишкой.

Вы совершенно правы, что оптимальную стратегию можно рассчитать с помощью динамического программирования. Как и в вашем вопросе, пусть $ \ s \ $ будет вашим текущим банком, $ \ t \ $ - общей суммой, которую вы сделали на данный момент, и $ \ f (s, t) \ $ - оптимальной ставкой в ​​этой ситуации. Пусть $ \ p ^ * (s, t) \ $ будет вероятностью того, что вы в конечном итоге добьетесь успеха, если с этого момента вы будете играть оптимально. Пусть $ \ S_0 \ $ будет вашим начальным банком $ (\ S_0 = \ $ 2,000 \ $ в заданном вопросе $) $, а $ \ T \ $ будет целевым значением для $ \ t \ $ ($ T = \ $ 10,000 \ $ в вопросе).

Сначала заметьте, что если $ \ s + t \ ge T \ $ (и $ \ t

Затем, если $ \ s + t \ $, потому что этого достаточно, чтобы гарантировать победу в следующем раунде, если вы выиграете этот, и если вы сделаете больше, у вас будет меньше средств в следующем раунде, если вы проиграете этот.

Если вы поставите $ \ b \ $ и проиграете, то новые значения $ \ s \ $ и $ \ t \ $ будут $ \ sb \ $ и $ \ t + b \ $ соответственно. Таким образом, если $ \ p \ $ - это вероятность выигрыша в одном раунде ($ p = 0.45 \ $ в заданном вопросе), а $ \ q = 1-p \ $ вероятность проиграть, то \ begin p ^ * (s, t) & = \ max_ \ right)>\ big (p \, p ^ * (s + b, t + b) + q \, p ^ * (sb, t + b) \ big) \\ f (s, t) & = \ underset \ right)>\ big (p \, p ^ * (s + b, t + b) + q \, p ^ * (sb, t + b) \ big) \. \конец Работая в обратном направлении от $ \ t = T-2 \ $, вы можете использовать приведенные выше уравнения для последовательного вычисления $ \ p ^ * (s, t) \ $ и $ \ f (s, t) \ $ для $ \ s \ в \ big \ \ $ и $ \ t = T-2, T-3, \ dots, 1,0 \ $.

Я написал следующий сценарий Magma для выполнения этих расчетов для $ \ T = 1000 \ $.

Скрипт можно запустить, скопировав и вставив его в онлайн-калькулятор Magma здесь. К сожалению, для $ \ T = 10000 \ $ скрипт завершится ошибкой из-за превышения ограничений по времени и памяти онлайн-калькулятора Magma. Однако для $ \ T = 1000 \ $ выходные данные говорят нам, что для начального банка в $ \ $ 64 $ или меньше оптимальной первой ставкой является весь банк, а для начального банка в размере от $ \ $ 117 $ до $ \ $ 200 $ включительно, оптимальная первая ставка - $ \ $ 1 $. При оптимальной игре шанс на окончательный успех выше, чем $ \ 99 \% \ $ для любого начального банка в $ \ $ 175 $ или больше. При оптимальной игре вероятность успеха для $ \ S_0 = 200 \ $ оказывается $$ 0.99913348949325492439801621030571175189427531 \ dots \. $$ Результаты этих расчетов показывают, что ставки в размере $ \ $ 1 $ являются оптимальными, если только ваш банк не является довольно маленьким по сравнению с текущей целью.

Вышеупомянутый сценарий можно легко изменить для расчета вероятности успеха для стратегии B, описанной в ответе user2661923 (с поправками, внесенными в соответствии с исправлением, предложенным в моем третьем комментарии к ответу). Если $ \ p_1 (s, t) \ $ - это вероятность успеха при розыгрыше этой стратегии из позиции, в которой текущий банк равен $ \ s \ $, а общая ставка на данный момент составляет $ \ t \ $, то $ \ p_1 \ $ удовлетворяет рекурсии $$ p_1 (s, t) = p \, p_1 (s + 1, t + 1) + q \, p_1 (s-1, t + 1) \. $$ Приведенный выше сценарий можно изменить, чтобы табулировать значения $ \ p_1 \ $ для $ \ 1 \ le s \ le 1000 \ $ и $ \ 0 \ le t \ le 1000 \ $, заменив код

с единственной инструкцией

Для $ \ T = 1000 \ $ и $ \ S_0 = 200 \ $ модифицированный скрипт дает вероятность окончательного успеха при использовании этой стратегии $$ 0.999051356533203111486952131756939063716486183 \ dots $$. Хотя эта вероятность меньше, чем гарантированная оптимальной стратегией, что показывает, что эта стратегия не совсем оптимальна, разница настолько мала ($ \ \ приблизительно0.000082 \ $), что ею можно пренебречь.

Для меньших значений $ \ S_0 \ $ стратегия использования ставок $ \ $ 1 $ может быть очень далека от оптимальной. Например, для $ \ S_0 = 50 \ $ и $ \ T = 1000 \ $ оптимальная стратегия дает вероятность окончательного успеха $ 0,30041494580652103310049100479730984926032991 \ dots $$, тогда как стратегия ставок всего $ \ $ 1 $ все time имеет вероятность успеха всего 0,03353384615182354449189130202943683024299148 \ dots \. $$

Следующий скрипт вычисляет вероятность окончательного успеха со стартовым банком $ \ S_0 = \ $ 2000 \ $ и нацеливается на $ \ T = \ $ 10000 \ $, когда вы всегда ставите только $ \ $ 1 $, если только $ \ T \ $ не раундов. были сыграны, или $ \ s = T \ $, и в этом случае вы делаете ставку $ \ Tt \ $. Если вы выживете в течение раундов $ \ T \ $, даже если ваш банк упадет до нуля в последнем раунде, вы выиграете, потому что общая сумма вашей ставки будет точно $ \ T \ $. С другой стороны, если $ \ s = T \ $ до того, как вы сыграли $ \ T \ $ раундов, то общая сумма $ \ t \ $, которую вы поставили до сих пор, - это просто количество раундов, которые вы сделали. сыграно, поэтому $ 0 \ le Tt \ le s \ $, и вы можете выиграть в следующем раунде, сделав ставку на $ \ Tt \ $.

Этот сценарий можно смоделировать как однородную по времени цепь Маркова с поглощающими состояниями в $ \ s = 0 \ $ и $ \ s = T \ $ и начальным состоянием $ \ s = S_0 \ $ с вероятностью $ 1 $. Если $ \ p_a (s, t) \ $ - это вероятность того, что цепь находится в состоянии $ \ s \ $ в момент $ \ t \ $, $ \ w (t) = p_a (T, t) \ $ и $ \ l (t) = p_a (0, t) \ $, тогда $ \ p_a, w \ $ и $ \ l \ $ удовлетворяют следующим уравнениям:

\начинать p_a (s, 0) & = \ case \\ l (t + 1) & = l (t) + q \, p_a (1, t) \ \ w (t + 1) & = w (t) + p \, p_a (T-1, t) \\ p_a (1, t + 1) & = q \, p_a (2, t) \\ p_a ( Т-1, t + 1) & = p \ p_a (T-2, t) \\ p_a (s, t + 1) & = q \, p_a (s + 1, t) + p \, p_a (s -1, t) \ \ \ text \ 2 \ le s \ le T-2 \. \конец Тогда вероятность окончательного успеха равна $$ \ sum_. ^ Tp_a (s, T) - p_a (0, T-1) = 1-l (T-1) \, $$, который следующий скрипт вычисляет для $ \ T = 10000 \ $ и $ \ S_0 = 2000 \ $ .

Для $ \ T = 10000 \ $ и $ \ S_0 = 2000 \ $ и стратегии повторных ставок $ \ $ 1 $ приведенный выше скрипт дает $$ 0.999999999999999999960876990789091728946 \ dots $$ как вероятность окончательного успеха. Хотя эта стратегия вряд ли будет «оптимальной» в самом строгом смысле этого слова, ее вероятность успеха настолько близка к $ 1 $, что расхождение совершенно несущественно.

Хотя эта стратегия немного отличается от стратегий A и B, описанных в ответе user2661923, все три ответа полностью эквивалентны и имеют одинаковую вероятность успеха. Это связано с тем, что $ \ s + t \ $ никогда не уменьшается, поэтому, как только $ \ s + t \ ge T \ $ (что позволяет стратегии B завершиться раньше, чем два других), даже если вы продолжаете делать ставки $ \ $ 1 $, ваш банк $ \ s \ $ не может уменьшиться до нуля до того, как $ \ t \ $ достигнет $ \ T \ $, поэтому вы все равно наверняка добьетесь успеха.

Для $ \ T = 1000 \ $ и $ \ S_0 = 200 \ $ этот сценарий дает вероятность окончательного успеха $$ 0.999051356533203111486952131756939063716486183 \ dots, $$ идентично ответу, который предыдущий модифицированный сценарий дает для стратегии B, таким образом обеспечивая некоторую подтверждение того, что алгоритмы реализованы правильно.

Еще новости