![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Pour la science (№ 381) — вовремя останавливаться
Замечательный класс игр, в которых нужно уметь вовремя остановиться.
Простейший пример: кидаем кубик. Максимум 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) — парадокс с двумя конвертами. Авторы повторили понравившееся мне объяснение парадокса (загадываем число, если в конверте больше — оставляем, меньше — меняем), только вместо знаний о бюджете устроителей лотереи они зачем-то приплели распределение Гаусса.
Совсем сложная (нет решения до сих пор) задача — подбрасывание монетки. Точно так же, как и раньше нужно сказать «стоп», задача — оптимизировать процент выпавших орлов.