![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frЗамечательный класс игр, в которых нужно уметь вовремя остановиться.
Простейший пример: кидаем кубик. Максимум N=6 раз. В любой момент можно остановиться — последнее выпавшее число будет нашим результатом. Возвращаться к когда-то выпавшим числам нельзя. Вопрос: когда выгодно останавливаться, а когда — продолжать кидать кубик? В этом случае ответ простой — просчитывается по индукции с конца:
1. N=1. Очевидно, от нас вообще ничего не зависит. Ожидание результата = 3,5.
2. N=2. Если выпадет меньше 3,5 — выгодно кинуть ещё раз (см. результат п.1), иначе (выпало 4, 5 или 6) выгодно оставить (среднее значение 5). Ожидание результата = 1/2 * 5 + 1/2 * 3,5 = 4,25.
И так далее.
Задача чуть посложнее — колода из N=100 карточек, на каждой написано какое-то число. Перед вами открывают карточки одна за одной. В любой момент можно остановиться, задача — остановиться в тот момент, когда вам показывают самое большое в колоде число.
Впервые эту задачку решил некто John Elton (с таким именем нагуглить человека невозможно). Служа в армии во время войны во Вьетнаме, он спорил с товарищами, что угадает самое большое из сотни чисел. Найденный им алгоритм позволялобирать боевых товарищей указывать максимальное число примерно в трети случаев.
Сначала простой вариант, дающий правильный ответ в четверти случаев:
— смотрим первую половину колоды, запоминаем самое большое встреченное число;
— смотрим вторую половину колоды, говорим «стоп», как только видим число больше запомненного;
Очевидно, что алгоритм даёт правильный ответ как минимум в четверти случаев — когда самое большое число находится во второй половине колоды (1/2), а следующее за ним — в первой (ещё 1/2).
Оптимальный алгоритм состоит лишь в замене половины колоды на 1/e.
Задача не такая уж и теоретическая — при условии наличия объективного сравнения, её можно увидеть в процессе найма на работу (с обеих сторон), поиске квартиры и т.п.
Частный случай (N=2) — парадокс с двумя конвертами. Авторы повторили понравившееся мне объяснение парадокса (загадываем число, если в конверте больше — оставляем, меньше — меняем), только вместо знаний о бюджете устроителей лотереи они зачем-то приплели распределение Гаусса.
Совсем сложная (нет решения до сих пор) задача — подбрасывание монетки. Точно так же, как и раньше нужно сказать «стоп», задача — оптимизировать процент выпавших орлов.
Простейший пример: кидаем кубик. Максимум N=6 раз. В любой момент можно остановиться — последнее выпавшее число будет нашим результатом. Возвращаться к когда-то выпавшим числам нельзя. Вопрос: когда выгодно останавливаться, а когда — продолжать кидать кубик? В этом случае ответ простой — просчитывается по индукции с конца:
1. N=1. Очевидно, от нас вообще ничего не зависит. Ожидание результата = 3,5.
2. N=2. Если выпадет меньше 3,5 — выгодно кинуть ещё раз (см. результат п.1), иначе (выпало 4, 5 или 6) выгодно оставить (среднее значение 5). Ожидание результата = 1/2 * 5 + 1/2 * 3,5 = 4,25.
И так далее.
Задача чуть посложнее — колода из N=100 карточек, на каждой написано какое-то число. Перед вами открывают карточки одна за одной. В любой момент можно остановиться, задача — остановиться в тот момент, когда вам показывают самое большое в колоде число.
Впервые эту задачку решил некто John Elton (с таким именем нагуглить человека невозможно). Служа в армии во время войны во Вьетнаме, он спорил с товарищами, что угадает самое большое из сотни чисел. Найденный им алгоритм позволял
Сначала простой вариант, дающий правильный ответ в четверти случаев:
— смотрим первую половину колоды, запоминаем самое большое встреченное число;
— смотрим вторую половину колоды, говорим «стоп», как только видим число больше запомненного;
Очевидно, что алгоритм даёт правильный ответ как минимум в четверти случаев — когда самое большое число находится во второй половине колоды (1/2), а следующее за ним — в первой (ещё 1/2).
Оптимальный алгоритм состоит лишь в замене половины колоды на 1/e.
Задача не такая уж и теоретическая — при условии наличия объективного сравнения, её можно увидеть в процессе найма на работу (с обеих сторон), поиске квартиры и т.п.
Частный случай (N=2) — парадокс с двумя конвертами. Авторы повторили понравившееся мне объяснение парадокса (загадываем число, если в конверте больше — оставляем, меньше — меняем), только вместо знаний о бюджете устроителей лотереи они зачем-то приплели распределение Гаусса.
Совсем сложная (нет решения до сих пор) задача — подбрасывание монетки. Точно так же, как и раньше нужно сказать «стоп», задача — оптимизировать процент выпавших орлов.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-08-04 04:28 pm (UTC)А можно ссылку? Мне все-таки непонятно, почему 50% через какое-то время перестает быть stopping rule.
no subject
Date: 2009-08-05 07:53 am (UTC)Я предполагаю, что это как-то связано с постепенным снижением стоимости каждого броска. n-й бросок влияет на результат в пределах 1/n.
С другой стороны, учитывая независимость бросков, я вообще не понимаю, откуда может взяться пороговое значение.
Авторы, впрочем, так и говорят, что задача - гроб :-)
no subject
Date: 2009-08-05 07:17 pm (UTC)Понял в чем моя ошибка. Я предполагал, что при достижении 0.5 нужно останавливаться (поскольку 0.5 - мат ожидание бесконечного продолжения игры), а это не так.
no subject
Date: 2009-08-05 10:03 pm (UTC)no subject
Date: 2009-08-05 10:35 pm (UTC)Кажется уже даже доказано, что вероятность окончания игры равна 1 (не уверен). И поэтому, в любой момент математическое ожидание выигрыша строго больше чем 0.5 (разве что в случае глобального невезения оно возможно асимптотически приблизится к 0.5). Например, перед первым ходом мат ожидание выигрыша строго больше 0.75 (если орел, то игра прекращается, если решка, то продолжаем с мат ожиданием выигрыша больше 0.5)
no subject
Date: 2009-08-06 06:52 am (UTC)