Вариаций много, встречается часто с равномерным отрезком [0;1] или с перебросом шестигранного кубика.
🤓 Условие задачи
У вас честный шестигранный кубик.
Вы делаете первый бросок и видите результат X. Затем вы можете:
1. оставить этот результат
2. сделать второй бросок (перебросить) и тогда итогом станет результат второго броска Y.
Вопрос: какую стратегию нужно использовать, чтобы максимизировать математическое ожидание итогового результата, и чему равно это математическое ожидание выигрышной стратегии?
Решение под спойлером
1. Матожидание кубика = (1+2+3+4+5+6) / 6 = 3.5
Ключевая идея: в среднем мы будем стремиться к 3.5 при бесконечном количестве бросков. Мы хотим максимизировать выигрыш. Для этого мы должны сравнить теоретическое значение с фактическим.
а) Если x > 3.5, выгоднее оставить, так как в среднем мы получаем меньше, чем видим сейчас
б) Если x < 3.5, лучше перебросить, в среднем мы получаем больше, чем видим сейчас
в) Если x = 3.5, ничего. Но фактически мы не можем получить 3.5, поэтому разбивается на два сценария (только а и б).
Имеем исходы с перебросом: {1; 2; 3} и исходы без переброса: {4; 5; 6}
2. Теперь к выигрышной стратегии
Пусть W выигрышная стратегия а E(Y) — матожидание кубика, будем смотреть на вариации первого броска и дальше считать матожидание стратегии
При X <= 3
E(W|X=1) = E(W|X=2)=E(W|X=3) = E(Y) = 3.5
💡 Когда нам выпало 1, 2 или 3, мы отказываемся от этого значения и фактически играем заново с чистого листа, а значит в среднем получаем матожидание одного честного броска — 3.5. Второй бросок — обычный честный кубик 🎲
При X > 3
E(W|X=4) = 4
E(W|X=5) = 5
E(W|X=6) = 6
Тогда E(X| X > 3) = (4+5+6) / 3 = 5
При выпадении 4, 5 или 6 текущее значение уже больше математического ожидания нового броска (3.5), поэтому перебрасывать невыгодно. Поэтому условные матожидания будут фактическими значениями на кубике.
Тогда получаем матожидание выигрышной стратегии
E(W)= P(X<3) * E(Y) + P(X>=4)*E(X|X>=4) = 3/6 *3.5 + 3/6 * 5🥳🥳🥳
Еще есть интересный вопрос на понимание: А что будет, если перебрасывать мы будем не один раз, а два, три и так далее? Меня это кстати спрашивали на собеседовании в одной компании. Нужно включить голову 🤔
Спойлер для двух перебросов (максимум 3 броска):
Так как при одном перебросе (двух бросках) матожидание оптимальной стратегии равно 4.25, то при двух перебросах оптимально оставлять 5 и 6.
E(W) = 4.25 * 4/6 + (5 + 6) * 2/6 = 14/3 = 4.666...
И дополнительно вопрос, а куда будет стремиться матожидание при бесконечном количестве подбрасываний, если нам разрешат забирать выигрыш на тех подбрасываниях, которые нас устроили?
Мы используем оптимальное правило остановки: перебрасываем, пока не выпадет 6. Вероятность того, что 6 рано или поздно выпадет, равна 1, поэтому матожидание стратегии стремится к 6.
🐍 Python можно задать вот так
def expected_value(rerolls, sides=6):
"""
Возвращает максимальное матожидание,
если осталось несколько перебросов
"""
V = (sides + 1) / 2
for _ in range(rerolls):
total = 0
for x in range(1, sides + 1):
total += max(x, V)
V = total / sides
return V
for k in range(5):
print(f"{k} перебросов. Матожидание = {expected_value(k)}")
Ставьте 🐳, если понравился разбор и нужен разбор еще задач!
Делитесь в комментариях, попадалась ли вам подобная или похожая задача? Можно разобрать!
👌 Если у вас есть Premium, вы можете бустануть канал — это бесплатно и занимает 3 секунды. Нам совсем чуть-чуть осталось до 10 уровня, хочу поставить обои!
@zasql_python