green_fr (green_fr) wrote,
green_fr
green_fr

Category:

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) — парадокс с двумя конвертами. Авторы повторили понравившееся мне объяснение парадокса (загадываем число, если в конверте больше — оставляем, меньше — меняем), только вместо знаний о бюджете устроителей лотереи они зачем-то приплели распределение Гаусса.

Совсем сложная (нет решения до сих пор) задача — подбрасывание монетки. Точно так же, как и раньше нужно сказать «стоп», задача — оптимизировать процент выпавших орлов.
Tags: pour la science
Subscribe

  • La Vague и L'Odyssée des Gènes

    Практически одновременно купил два нон-фикшена. La Vague — книга французского эпидемиолога о первой волне ковида. Мы с Анютой — она тоже прочитала…

  • Разные книжки

    Был период, когда читать хотелось совсем какую-то ерунду, лишь бы попроще. Похоже, период прошёл, но за это время успел прочитать: «Nymphéas noirs»…

  • Weapons of Math Destruction

    Прочитал (спасибо wildest_honey!) книжку про риски применения математических алгоритмов в разных областях. Автор вводит вынесенный…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 34 comments

  • La Vague и L'Odyssée des Gènes

    Практически одновременно купил два нон-фикшена. La Vague — книга французского эпидемиолога о первой волне ковида. Мы с Анютой — она тоже прочитала…

  • Разные книжки

    Был период, когда читать хотелось совсем какую-то ерунду, лишь бы попроще. Похоже, период прошёл, но за это время успел прочитать: «Nymphéas noirs»…

  • Weapons of Math Destruction

    Прочитал (спасибо wildest_honey!) книжку про риски применения математических алгоритмов в разных областях. Автор вводит вынесенный…