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 fortune danseuse», 1922. Пишут, что это, возможно, портрет Айседоры Дункан, которую…

  • Баранов-Россине в Центре Помпиду

    В прошлый поход в Помпиду наткнулся на целый зал, посвящённый человеку, о котором я до сих пор ничего не слышал — Владимир Давидович…

  • Centre Pompidou после большого перерыва

    С Помпиду вышла смешная история. В начале 2020 мы поехали в Италию, и я перед отъездом традиционно облегчил свой кошелёк, выложив все ненужные…

  • 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 fortune danseuse», 1922. Пишут, что это, возможно, портрет Айседоры Дункан, которую…

  • Баранов-Россине в Центре Помпиду

    В прошлый поход в Помпиду наткнулся на целый зал, посвящённый человеку, о котором я до сих пор ничего не слышал — Владимир Давидович…

  • Centre Pompidou после большого перерыва

    С Помпиду вышла смешная история. В начале 2020 мы поехали в Италию, и я перед отъездом традиционно облегчил свой кошелёк, выложив все ненужные…