Comments 56
Я пропустил или не понял, но хотел бы понять: почему мы в задаче о лампочках уверены, что оптимальная стратегия обязательно заключается в одной из An?
Среди An, безусловно, есть какая-то лучшая, но почему она обязательно лучше любой возможной стратегии вообще?
Добрый вечер! Это доказывается в разделе 1. В нем мы рассматриваем оптимальную стратегию и выводим, что у нее есть момент остановки t - точка, сразу после пересечения 
и
В разделе 1 написано:
Оптимальная стратегия устроена просто: у Бориса есть список номеров, и если лампочка моргнула зеленым на одном из них — он останавливается, а в остальных случаях — продолжает игру.
без каких-либо доказательств этого утверждения.
Почему, например, оптимальная стратегия не может зависеть от предыстории? Мне кажется, тут должны быть какие-то непростые рассуждения с условными вероятностями. Ведь, например, из прошлых наблюдений, если их достаточно много, Борис может делать какие-то выводы о распределении вероятностей у Ани.
Предположим, А и Б договорились кидать кубик миллион раз. А выкинула кубик 300 тысяч раз, и ни разу он не упал шестёркой. Не зная априорно функции вероятности кубика, не будет ли логично Борису заключить, что он несимметричный, и при выпадении шестёрки на 300001 раз выбрать его, не дожидаясь 370000 бросков? Это просто пример. Я не вижу очевидных оснований отбрасывать такую стратегию без рассмотрения.
без каких-либо доказательств этого утверждения.
Это следует из предыдущего абзаца
Пусть Борис действует оптимально. Как он принимает решение после зеленой вспышки? Предположим, что осталось
ходов до конца игры. Рассмотрим две вероятности:
: за оставшиеся
ходов зеленых вспышек больше не будет
: Борис выиграет, если продолжит игру и будет действовать оптимально
Тогда, если
— выгоднее сказать «стоп», если
— продолжать игру
Вы согласны с тем, что написано в цитате? Если нет, я могу объяснить поподробнее
Если согласны, то получается, что Борис принимает решение сравнивая числа 
, которые зависят только от номера хода — и никак не зависят от прошлого
И спасибо за содержательные вопросы. Очень хотелось написать компактно, но понятно что есть тонкие места. В целом этот раздел самый содержательный, остальное это вычисления
Борис может делать какие-то выводы о распределении вероятностей у Ани
В условии задачи предполагается, что никаких данных о распределении нет. Аня пишет числа заново в начале каждой игры и перемешивает колоду. Мы говорим что стратегия наиболее успешна если для доля раскладов (тасовок колоды), на которых она выигрывает наиболее большая. То есть вы прогоняется через нее все наборы из 10! перестановок заранее неизвестных чисел и смотрите, на скольки из них она будет побеждать
Априорно у Бориса никаких данных о распределении нет. Однако апостериорная оценка распределения по выборке, составляющей 36% генеральной совокупности, ведь уже вполне репрезентативна? В каком бы порядке ни была перемешана генеральная совокупность.
Мне вот этот момент, что Борис в своей стратегии игнорирует предысторию, кажется очень контринтуитивным, пусть даже выборка и случайная.
Или тут нужны какие-то ограничения на характер распределения. Потому что видя треть случайно перемешанной генеральной совокупности, обычно мы можем очень неплохо предсказать остальные две трети. В частности, весьма точно посчитать дисперсию, что может пригодиться Борису в его труде.
, 
, 
,
С тем, что написано в цитате, я согласен.
Однако Борис ведь не знает чисел Sn и Cn. Он может оперировать только какими-то своими оценками этих чисел Sn* и Cn*. И эти оценки теоретически могут зависеть от предыстории.
Понял в чем ваш вопрос. Нет, речь идет не об оценках, а о настоящих вероятностях. Например чтобы вычислить
- : за оставшиеся ходов зеленых вспышек больше не будет
можно смоделировать очень много игр и посмотреть на долю тех, в которых зеленых не будет. Ну или посчитать напрямую, это совсем не сложно. Посчитать 
сложнее, но тоже можно — там под спойлером реккурентная формула
Но нам не важно, откуда Борис знает эти вероятности и как он их нашел — утверждается только, что если он поступил не так, как велит это неравенство, то он ведет себя не оптимально. А мы же предположили, что он играет по оптимальной стратегии!
В этом и трюк — мы пока не можем посчитать 
, а значит не знаем, как именно устроена оптимальная стратегия. Но мы знаем, что действуя оптимально Борис должен ходить так как предсказывает неравенство (даже если он не умеет считать эти числа) — а из этого следует что есть момент остановки
Я понял. Я был введён в заблуждение терминологией. То, что названо в статье стратегией Бориса, я бы не назвал стратегией, так как ей невозможно руководствоваться. Это просто теоретически оптимальная последовательность шагов, которые мог бы сделать Борис.
Но для сути обсуждаемого вопроса, конечно, разницы нет.
Спасибо!
Согласен! Я просто большую часть обозначений и терминологии придумываю на ходу, в оригинальном тексте все гораздо короче и без деталей, так что есть куда улучшать. Мне нравится как вы сформулировали, я бы добавил что-то такое
Кстати, если подумать, то мы доказали только то, что нашли идеальный момент для выбора на 37%. А вот каким именно должен быть этот выбор (действительно ли max37+1) – вроде ниоткуда не следует.
Поправьте меня, где я неправ в следующем рассуждении.
Итак, наша невеста отсмотрела 37% женихов. Допустим, что общее число женихов достаточно большое. В силу центральной предельной теоремы мы можем предполагать, что достоинства женихов в общем случае имеют нормальное распределение. Но это даже и не важно. ДОПУСТИМ, что невеста, проанализировав свою 37% выборку, установила, что распределение в ней нормально. Тогда невесте следует после 37% шагов ожидать первого жениха с ценностью примерно равной матожиданию плюс три сигмы (где матожидание и сигма посчитаны по 37% выборке), даже если максимум в выборке был меньше этой величины. Условно говоря, найденный среди женихов фантастический ублюдок даёт невесте основания мечтать о появлении столь же невероятного героя.
Это рассуждение базируется на том, что в большой нормально распределённой случайной выборке очень велика вероятность, что после обработки выборки 37% в оставшейся части генеральной совокупности будет много чисел, превосходящих максимум от выборки. И вероятность победы невесты при увеличении количества женихов стремится к нулю. Но тем не менее её можно пытаться максимизировать.
Предположим, А и Б договорились кидать кубик миллион раз. А выкинула кубик 300 тысяч раз, и ни разу он не упал шестёркой. Не зная априорно функции вероятности кубика, не будет ли логично Борису заключить, что он несимметричный, и при выпадении шестёрки на 300001 раз выбрать его, не дожидаясь 370000 бросков? Это просто пример. Я не вижу очевидных оснований отбрасывать такую стратегию без рассмотрения
По правилам игры Борису заранее известны вероятности. Например, в задаче о шестерке предполагается, что кубик честный, и все вероятности равны 
. Для нечестного кубика рассуждение тоже работает, если мы заранее знаем вероятность выпадения шестерки (это то, что обозначается за 
), просто стратегия будет другой
Если вероятности неизвестны — это уже другая задача
Почему-то вспомнил анекдот:
Шерлок Холмс и доктор Ватсон летят на воздушном шаре. Попадают в густой туман и теряют ориентацию. Тут небольшой просвет – и они видят на земле человека.
– Уважаемый не подскажете ли где мы находимся?
– В корзине воздушного шара, сэр.
Тут их относит дальше и они опять ничего не видят.
– Это был математик, – говорит Холмс.
– Но почему?
– Ну во-первых, он очень долго думал над простым вопросом, во-вторых, он ответил АБСОЛЮТНО правильно, и в-третьих, его ответ АБСОЛЮТНО бесполезен.
Тут бы оффер получить , а уж какой выбрать обычно не возникает трудностей
Ключевой момент - у вас есть набор из N элементов, и в процессе их перебора вы применяете ту или иную тактику. В реальной жизни обычно такое бывает либо с возможностью сравнения всех вариантов и выбора наилучшего, либо наоборот бывает что ты заранее не знаешь весь пул. Упустишь первый вариант - второго может увы уже и не быть
В этой задаче я знаю количество кандидатов. Но есть ее модификация (для которой стратегия и доказательство работают точно так же) где надо знать время, в течении которого я хочу сделать выбор. Например, я еду на машине по оживленному шоссе и хочу в заправиться в течении полу часа по самой низкой цене. Надо проехать 
времени и выбрать первую заправку, которая дешевле всех остальных
разница между теоретической задачей и реальной жизнью в этом примере весьма наглядна: у Вас нет гарантии, что за эти полчаса езды вы вообще встретите хоть одну заправку в принципе.
Гарантии нет и в реальной жизни, и в математической задаче.
В версии задачи с известным временем я предполагаю, что количество кандидатов распределено по Пуассона — и да, есть вероятность, что ни одного кандидата не будет.
Да и в задаче о лампочках, которая разобрана в статье, есть вероятность, что все вспышки будут красными. Точно так же как в жизни.
В этой ситуации как не играй — проиграешь. Но мы и не гарантируем победу
Гарантировать Борису победу невозможно
Наша цель — придумать стратегию, которая выигрывает с наибольшей вероятностью. В примере с заправками смысл в том, что если вы будете действовать как я сказал каждый день, то будете попадать на самую дешевую заправку гораздо чаще, чем если например будете останавливаться на первой попавшейся
Что делать, если в следующих 63% элементов (невест, квартир, оферов 🙂) не оказалось элемента лучше, чем в первых 37%?
Если ни чего не изменится, вам повезёт в следующих жизнях, в среднем. Статистические методы обладают предсказательной силой на выборках из большого количества экспериментов, проводимых в идентичных условиях. Но в каждом отдельном случае никто ни чего не гарантирует.
Ничего не поделаешь, в этой ситуации вы проиграли( Как и в задаче о лампочках — есть вероятность того, что ни одного зеленого сигнала не будет. Но вероятность этого мала — попробуйте посчитать, чему она равна
Да, для не слишком маленьких N 🙂
Кажется так. Среди последний 63% нет лидеров в точности тогда, когда лучший жених среди 37%. Вероятность этого 37% вне зависимости от их числа.
То есть с вероятностью 37% у нас не будет ни одного лидера в хвосте и мы автоматически проиграем, с вероятностью 37% в хвосте будет один лидер и мы победили, с вероятностью 26% в хвосте хотя бы два лидера и мы опять проиграли
В оригинальной задаче о разборчивой невесте если она никто не выбрала, автоматом выходит за последнего жениха
Сегодня, прямо, високосная комплексная среда, какая-то.
И уфологию, с матплотлибом и формулами, мы почитали, в плане оценок того, как быстро нам пора валить в "голактеку", и про нетворкинги с линкединами восхитились, теперь, вот, про несуществующие офферы, которые есть в заглавии, но не в содержательной части.
Я счастлив.
Осталось научиться правильно высчитывать эти "реальные тридцать семь процентов", когда в природе есть один единственный оффер, и тот мнимый. Очень похоже на то, как, лет пятнадцать назад мне пообещали зарплату "сто тыщ", а когда приехал оформляться, по документам, даже пресловутых "тридцати семи" не оказалось, ибо мелкий оклад и бесконечный премиальный ряд, состоящий из разнообразных дробных частей, сходящийся где-то около нуля, на который ещё и прогрессивная штрафная система накладывается, в рамках коллективной ответственности, да такая, что, поработав месяц, становишься должником, под проценты, года на два (всё, правда, закончилось хорошо - я хлопнул, погромче, дверью, и, в следующем месяце, уже работал в другом месте, а у них, через год-два, лицензию отозвали).
Правило 3... Хм! Гусары - молчать!
Это знаменитое правило 37%
Вот только чисто статистический метод даст вероятно лучший вариант из худших женихов - кто понаглее. Но кому такой исход интересен, кроме теоретиков?
Невесты разбираются в женихах гораздо лучше математиков. Если верить классике, то для долгого и счастливого брака работает совсем другая стратегия. Принцессе надо отказать всем этим женихам, заточиться в башню и выйти замуж за первого встречного, кто пройдёт три испытания - в которых вероятность успеха должна быть крайне мала.
Задача-то не о женихах, а о теории вероятностей - женихи так, для кое-какой, весьма и весьма условной ассоциации с реальностью, чтобы у читателя взгляд остекленел не с первых предложений, а только где-то после 37% прочитанного. А так-то женихов будет выбирать папа-король, ибо что эта овца может понимать в династических браках, потом посольства с предложениями, и т. д., принцесса, дай боже, впервые увидит суженого на церемонии бракосочетания, кому там она сможет отказать, за какого там первого встречного.
Существует какая-то инверсия "правила 37%", типа там конкурс кандидатов на одну и ту же роль, проектов на одно и то же задание, и т. п., и каждому желательно исхитриться не попасть в первые 37%, а попасть... куда?
Не критика, но пытаюсь вспомнить что когда то давно изучал.
Давненько я не был в школе, но когда изучали статистику, я запомнил что это наука о "больших числах" и требует достаточно большой выборки, чтобы анализ работал - грубо, примерно от 10 тыс замеров. Иначе это гадание на картах Таро. И второе что я запомнил - в конкретном случае, вашем личном, распределение не работает - оно имеет смысл только в приложении к большому количеству опытов. Даже если вероятность умереть на операционном столе 0.000001, именно с вами это может произойти. Как и выигрыш в лотерею. Для популяции правило будет работать статистически и она, эта популяция ничего не заметит, а вам может быть очень хорошо или очень плохо.
Подобные стратегии полезны для больших масс людей и большого количества "офферов", например когда вы непрерывно бегаете по собеседованием (так сейчас принято, насколько я понял - прыгать с работы на работу - начал работу и сразу ищешь следующую). Подобная тактика,кстати была нормальна и в 2000м, но у нее есть свои минусы тоже.
Если офферов немного, то может оказаться что горб распределения проедет раньше и останется "хвост" - ведь мы заранее не знаем что офферов будет 10, что сезон не закончится (всплеск активности потому что где то кто то пустил волну с набором на рынке) и тд, те модель может быть совсем не такой как мы думаем и меняться динамически, грубо говоря заложили белый шум в модели а приехал в реале дробовой. Ждали 5й оффер а пришла пауза в найме на полгода. В реале когда приходит "горячий" оффер мы часто не готовы психологически его принять так как возможны неожиданные условия - к примеру, я начал искать работу, еще не разослал резюме толком, а знакомый пробросил мне оффер "через три дня быть в Бостоне, контракт бессрочный, горящий и итд, по деньгам в 2 раза больше ожидания, агент в курсе, мы вместе работали все ОК" - мне ждать следующего или бросая тапки лететь на границу, по быстрому, оформлять рабочую визу? (дело было в Канаде).
Давно не учился, подзабыл все. В общем, совет для массы разработчиков правильный и нужный, но для каждого карася лучше думать самостоятельно - изучать рынок заранее, правильно оценивать себя (не завышая и не занижая) и понимать диапазон стоимости своих услуг. Мне в свое время, в начале карьеры, помогло чтение книг по HR больше чем по специальности, пройти первый фильтр "с крупной сеткой". И социализация, о чем никогда не нужно забывать - участие в сообществах, проектах, и тд, чтобы расширить круг знакомств в профессиональной среде, 70% "надежного" найма в реале происходит по рекомендациям.
Задача о женихах - отличный пример того, как математика подменяет KPI на заведомо дебильный, чтобы создать себе красивую задачу.
По сути, вознаграждение формулируется, как выбрать лучшего жениха = 1. Упустить/не дождаться лучшего = 0. И это бред. В реальной жизни это будет что-то типа
Выбрать лучшего +1
Выбрать второго лучшего +0.95
Выбрать третьего лучшего +0.9
...
Выбрать наихудшего +0.01
Уйти в монастырь -1000
И при таких условиях стратегия становится куда сложнее. Просто, мастерам мела и доски неинтересной, ибо, подозреваю, что переходит ту тонкую грань между очевидным и невозможным (где фармятся все физмат достижения), и уходит в зашквар с монте-карло и численными методами.
Ваша формулировка задачи о невесте хорошо известна маиематикам и давно решена. Можно посмотреть в Википедии. Как вы правильно заметили, мы обсуждаем частный случай этой ситуации. Я могу разобрать и общий, но чтобы было понятно надо действовать постепенно
При всей моей любви к математике, научпопу по математике и тп, правда. К жизни "математическая задача оптимальной остановки" не имеет никакого отношения.
Хотя эта задача имеет элегантное математическое решение, её прямое применение в жизни часто неудачно по нескольким причинам:
1. Упрощённые допущения
- В модели предполагается, что кандидаты оцениваются **линейно** (можно чётко ранжировать от лучшего к худшему).
- В реальности люди оцениваются по множеству критериев, и сравнение не всегда объективно.
2. Невозможность возврата к прошлым вариантам
- В задаче считается, что если вы пропустили кандидата, то не можете к нему вернуться. В жизни иногда можно возобновить общение с прошлыми партнёрами.
3. Фиксированное число кандидатов
- В математической версии известно (или оценивается) общее количество претендентов. В реальности вы не знаете, сколько ещё людей встретите.
4. Игнорирование эмоций и случайностей
- Люди не действуют как рациональные алгоритмы: чувства, химия, обстоятельства играют огромную роль.
- В задаче важно выбрать **максимум**, а в жизни часто достаточно "достаточно хорошего" партнёра.
5. Оптимальная стратегия требует "холодного расчёта"
- Решение предлагает отказывать первым 37% кандидатов, а потом выбрать первого, кто лучше всех предыдущих.
- Но если применять это буквально, можно упустить хорошие отношения из-за излишней формализации.
К жизни не имеет отношения никакая ее упрощенная модель, то есть вся математика. Как тут не вспомнить Талеба, который в "Черном лебеде" критиковал любое применение теорвера и статистики в жизни, за исключением случая казино.
Лично я данную задачу вспоминаю когда соглашаюсь на очередное собеседование: хоть и модель, но многие допущения вполне жизненны. По крайней мере делает процесс собеседования полезным независимо от исхода.
Было бы неплохо в данном контексте упомянуть парадокс двух конвертов, ибо он полностью разбивает всю интуицию, на которой строится задача о разборчивой невесте.
Согласен! Про парадокс конвертов я писал в другой статье https://habr.com/ru/articles/912270/
В задаче есть ряд семантических подвохов из-за чего может сложиться ощущение, что она переносится на реальную жизнь. И введение цифр на карточках помогает обмануть читателя.
Когда в реальной жизни мы имеем дело с выбором и числовыми оценками - всегда есть распределение, по которому задана вероятность чисел.
Задача хоть сама по себе и корректна, к этому не имеет никакого отношения, для тервера она вообще была бы некорректной.
Пример: первые два жениха - бомжи-наркоманы, а третим оказался Английский принц. Искать дальше? Всегда есть распределение и всегда есть необходимость его как-то оценить до появления данных, всегда есть для него какие-то границы. А значит всегда выбор оптимальной стратегии будет зависеть от этой оценки.
Необходимость то есть, возможности, к сожалению нету. Ну принц третий, и что ? Четвертый может сам г.Бог. Вы же лучшего выбираете, а не хоть какого-то лучше определенного уровня.
Если по условию задачи, данные по принцам - это iid, то есть независимые, одинаково распределённые случайные переменные, то возникает проблема.
Не существует произвольно случайного распределения. Это какое-то конкретное распределение. По условию задачи, мы не знаем какое. Но оно не может быть неограниченно любым: у pdf есть ограничения в определении. Результирует это в то, что нужно заранее определиться какие распределегия мы рассматриваем. А от этого будет зависеть оптимальная стратегия.
Например, в реальной жизни, лучше принца может быть десяток человек на Земле, и учитывая мат ожидание в два бомжа + принц, поделить на 3 - шанс в них попасть ничтожный.
Если вы хотите взять Бога, и инопланетян и прочее и прочее - по сути, взять неограниченное число кандидатов - вам придётся определить pdf таким образом, чтобы её интеграл сходился. Вот когда каким-то конкретным образом это сделаете, тогда будет еще одна другая, но конкретная задача.
Полностью согласен с вами, и упомянутый мной ранее парадокс двух конвертов как раз об этом. Но побуду адвокатом задачи: где сказано, что величины независимые и одинаково случайно распределенные? Я могу перефразировать задачу так, что это становится ненужным. Например так: первым делом я задаю порядок женихов. Далее первому жениху присваивается условная единица. Каждый следующий "учится" на предыдущих: принимает рациональное число в соответствии с собственной позицией относительно предыдущих, и происходит это в момент перед свиданием. Все это никак не выдаст раньше времени числа последующих, и нет речи о случайном распределении чисел, только о случайном распределении порядка женихов, имеющих некую линейную упорядоченность их качества.
Ну вот у Вас корректно поставленная задача на комбинаторику.
У меня вышло, что вероятность выбрать топового жениха равна
,
где к - это точка после которой берём жениха.
Дальше считать было лень (хотя, признаюсь, не очень внимательно считал, мог ошибиться). Но это в вашей трактовке. А если её привязывать к той, что в посте, в месте, где женихи произвольно выбирают себе число из R - это всё же какая-то магия. И именно она даёт налёт неопределённости, спорности и разных трактовок задаче.
@d1-d5 Оличная статья и подробные объяснения, спасибо!
Не уловил одного момента насчет:
примем что
: (вероятность того, что) за оставшиеся
другим словами, это вероятность того, что все оставшиеся вспышки - красные.
убывает: чем больше времени — тем меньше шанс, что все сигналы будут красным
Пусть
— вероятность зелёного сигнала,
— красного. Вероятность
Все
сигналов будут красными с вероятностью
Не уловил доказательство того, чтоубывает. Например, почему
Можете, пожалуйста, подробнее пояснить откуда берется эта рекуррентная формула?
Другими словами, почему вероятность того, что оставшиеся n+1 сигналы красные (вероятность на предыдущем ходе, когда n+1 сигналов осталось) зависит от вероятности текущего хода (n сигналов осталось).
Далее, если это по какой-то причине верно. Если S от n+1 меньше S от n, то последовательность не убывает, а возрастает. Ведь из определения выше n это количество оставшихся ходов. А n изменяется от 10 до 0.
Добрый вечер!
это вероятность события X = "n+1 последних вспышек красные". X это объединение событий Y = "следующая вспышка красная" и Z = "n последних вспышек красных". Они независимы, так чтоэто произведение
. Первый множитель равен 
, второй
Как выбрать оффер? Задача о разборчивой невесте и правило 37%