Pour la science (№ 381) — вовремя останавливаться

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

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

Comments

[birdwatcher.livejournal.com]

О, в процессе найма на работу я эту задачу много раз видел.

[green-fr.livejournal.com]

Там было обобщение, когда мы не знаем, сколько карт в колоде — сколько из приславших CV человек реально придёт на собеседование :-)
И вариант для экономии времени, когда нужно выбрать не самого-самого, а хотя бы из первой десятки.

Но в любом случае, первым пришедшим на собеседование везёт как в том анекдоте, когда работодатель берёт половину пучки присланных ему CV и выкидывает в корзину со словами «лузеры нам не нужны».

[birdwatcher.livejournal.com]

я имею в виду, ее всё время задают на собеседовании

[green-fr.livejournal.com]

Блин, и где люди находят такие работы, когда на собеседовании задают вменяемые вопросы? А не «Чем вам понравилась наша фирма?» и «Какие у вас есть недостатки?»

[birdwatcher.livejournal.com]

Меня в этой части один раз спросили "если мы скажем, что мы тебя не взяли, то как ты думаешь, почему это будет?" Я ответил откровенно - "это будет потому, что вы, суки, никого и не собираетесь сейчас брать, а желаете разнообразить свой день общением". Так и вышло!!! Мне мужик потом даже написал прочувствованный е-мейл, мол, ты молодец, очень хорошо выступил, я бы хотел с тобой работать, вот, даже на этот вопрос правильно ответил.

[green-fr.livejournal.com]

Зашибись :-)

[dmpogo.livejournal.com]

Последние вопросы мне кажутся более вменяемыми при найме на серьезную позицию :)

[green-fr.livejournal.com]

Очень может быть. Но пока что я сталкивался только с молодыми людьми, явно прочитавшими подобные вопросы в книжке «Отдел кадров за 24 часа», и у меня были очень сильные сомнения в их способностях сделать какие-то выводы из моих ответов.
Последний раз вообще смешно было, когда я из отдела в отдел переходил, все уже давно обо всём договорились, но протокол требует разговора с отделом кадров. И вот мы полтора часа занимались подобными вопросами, было нестерпимо скучно и мне, и интервьюировавшей меня девушке. Смысл процедуры я не понял до сих пор…

[andreylv.livejournal.com]

да, мне эту задачу задали, когда я первый раз в жизни пошел на интервью :-) меня собеседовали тоже бывшие мехматовцы, примерно лет на 10 старше меня (т.е. они еще не успели забыть, чему их учили). больше такого в моей жизни не случалось :-)

[andreylv.livejournal.com]

кстати, в русскоязычной литературе эта задача называется "задача про разборчивую невесту".

[green-fr.livejournal.com]

О, спасибо, по-французски она тоже с невестой, но я как-то не решился дословно переводить.
Википедия по твоему названию, правда, только Березовского (http://ru.wikipedia.org/wiki/%D0%91%D0%B5%D1%80%D0%B5%D0%B7%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9,_%D0%91%D0%BE%D1%80%D0%B8%D1%81_%D0%90%D0%B1%D1%80%D0%B0%D0%BC%D0%BE%D0%B2%D0%B8%D1%87) находит :-Р

[oldjackaroo.livejournal.com]

Зато гугл находит вот это:
http://www.hse.ru/data/562/291/1235/gt_pset.pdf
Задача 9.16

[green-fr.livejournal.com]

И снова Березовский :-)))

[oldjackaroo.livejournal.com]

По-моему, я встречал ее под названием "задача о найме секретарши".
Кстати, с таким названием ее тоже невозможно нагуглить :)

[insead-hec.livejournal.com]

Мне непонятно с последней задачей - а никто не пытался доказать, что оптимального решения не существует? Я так понимаю, что общее количество подбрасываний либо бесконечно, либо случайно.

[birdwatcher.livejournal.com]

Я попытался и не понял, в чем сложность. На каждом шаге у нас известно, что выпало k орлов из n попыток. Значит, на следующем будет либо k из n+1, либо k+1 из n+1 с вероятностями 1/2. Стало быть, останавливаемся, если k/(n+1) + (k+1)/(n+1) < 2(k/n).

[green-fr.livejournal.com]

Возможно, не корректно ограничиваться только следующим шагом. С кубиками, например, это точно неправильно было — иначе ответ был бы «как только увидел больше 3,5 — останавливайся».
Они говорят, что до какого-то момента, очевидно, нужно останавливаться, как только выпало больше орлов, чем решек. но с какого-то момента нужно иметь минимум на два орла больше, потом на три и т.д. Вопрос в нахождении закона этих критических чисел.

[insead-hec.livejournal.com]

В кубике ведь целевая функция другая. Там нужно максимизирвать одну реализацию, а не средний результат.

А можно ссылку? Мне все-таки непонятно, почему 50% через какое-то время перестает быть stopping rule.

но с какого-то момента нужно иметь минимум на два орла больше, потом на три и т.д.

[green-fr.livejournal.com]

Вот ссылка (http://www.pourlascience.fr/ewb_pages/f/fiche-article-savoir-quand-s-arreter-22670.php?chap=8) (судя по нику, ты по-французски читаешь :-)), там не объясняется, просто констатируется факт.

Я предполагаю, что это как-то связано с постепенным снижением стоимости каждого броска. n-й бросок влияет на результат в пределах 1/n.

С другой стороны, учитывая независимость бросков, я вообще не понимаю, откуда может взяться пороговое значение.

Авторы, впрочем, так и говорят, что задача - гроб :-)

[insead-hec.livejournal.com]

Спасибо за ссылку.

Понял в чем моя ошибка. Я предполагал, что при достижении 0.5 нужно останавливаться (поскольку 0.5 - мат ожидание бесконечного продолжения игры), а это не так.

[green-fr.livejournal.com]

А почему 0,5 - не мат. ожидание бесконечного продолжения игры? Чтобы и я понял :-)

[insead-hec.livejournal.com]

0.5 как раз-таки мат. ожидание бесконечного продолжения игры, но мы не ожидаем, что игра продолжится бесконечно.

Кажется уже даже доказано, что вероятность окончания игры равна 1 (не уверен). И поэтому, в любой момент математическое ожидание выигрыша строго больше чем 0.5 (разве что в случае глобального невезения оно возможно асимптотически приблизится к 0.5). Например, перед первым ходом мат ожидание выигрыша строго больше 0.75 (если орел, то игра прекращается, если решка, то продолжаем с мат ожиданием выигрыша больше 0.5)

[green-fr.livejournal.com]

Да, красиво, спасибо.

[birdwatcher.livejournal.com]

мне интуитивно кажется, что без автокорреляции не стоит расчитывать на то, что сделаем сначала хуже, потому что потом станет лучше

[kalvado.livejournal.com]

(2k+1)/(n+1)-2k/n=(n-2k)/[n(n+1)] - т.е. если у нас меньше половины орлов, то продолжаем кидать; ожидаемое число - где-то 1/2+1/(2n) вроде.
Ну как бы не особо выгода по сравнению с "кину ковырнадцать раз, и будь что будет"

[green-fr.livejournal.com]

Майк, как ты пришёл в половине орлов? Почему это же рассуждение не применимо к трети или двум третям?

[kalvado.livejournal.com]

Ну это как бы ответ кому-то, алгоритм - кидаем пока матожидание "после следуюшего броска" ниже чем текушее.
Аккуратно считаю, и получаю условие 2к-н<0..
Поскольку коэффициент 2, а не 1/3 и не 3/2...

[green-fr.livejournal.com]

Оптимальное решение — это набор чисел t(n): если после броска номер n мы получаем значение большее, чем t(n), то останавливаемся, иначе — движемся дальше. И это t(n) просчитано достаточно глубоко. Проблема в том, что не видна общая формула.

[insead-hec.livejournal.com]

Очень напоминает последовательный анализ Вальда. Непонятно, почему тогда t(n) не равно математическому ожиданием при условии продолжения.

[roving-mind.livejournal.com]

"Какая игра сложнее: очко или преферанс? - Конечно, очко! В очко - думать надо, шанс прикидывать. А в преферансе карты раздадут, побормочут чего-то и и сразу карты открывают." :)

Задачки интересные - ничего не понял.
Спасибо за ссылки :)

[green-fr.livejournal.com]

Я кажется понимаю, почему на такие посты меньше комментариев, чем я думал. Надо объяснять внятнее :-)
Скажи, где именно ты застрял? С кубиком всё понятно?

[roving-mind.livejournal.com]

С условными вероятностями беда - ничего не помню. Надо читать мат. часть.
Хороший повод пропылесосить за шкафом :)

На работе условные вероятности - вообще враг.
вызываем API, проверяем возвращаемое значение, ловим эксепшен.
проверяем условия и никаких вероятностей!
все время ДОЛЖНЫ (MUST) знать куда и при каких условиях нам идти и кому об этом сообщить. и так до тех пор пока не откажет железо. что тоже вполне нормальное условие - ни о чем думать больше не надо...

[roving-mind.livejournal.com]

Парадокс Монти Холла понравился. действительно первое впечатление - осталось 2 - поэтому вероятность по 1/2.

А решение на пальцах может выглядить так:
вероятность успеха в первом выборе - 1/3. Соответственно вероятность того что выигрыш оставшихся вариантах("в другой части") - 2/3.
Ведущий своим действием сокращает кол-во варантов "в другой части", но суммарная вероятность найти там приз остается (потому что она определена на шаге 1 - до действий ведущего).
Т.к. теперь "другая часть" это одна штука - следует немедленно выбрать ее :)

[green-fr.livejournal.com]

Именно :-)