2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 04:02 
Аватара пользователя


26/02/12
133
Задачка о ста заключенных наверно всем известна, но на всякий случай приведу условие.
В тюрьме содержатся сто заключённых, у каждого номер от 1 до 100. Начальник тюрьмы помещает в шкаф со ста ящиками листочки с числами от одного до ста в случайном порядке и обещает отпустить всех при условии что каждый из заключённых найдет свой номер не больше чем за 50 попыток и разумеется с условием запрета обмениваться информацией.Решением задачи как известно является стратегия с вероятностью успеха 31%.
Задача стоит расчитать эффект более сложной стратегии основанной на допущении что остальные узники могут видеть как быстро выйдет первый заключенный и сколько времени займет у него поиск ящика с его номером. Допустим, договорятся что первый зашедший открывает один ящик за пять секунд и на основании этого делают оценку в короткий или длинный цикл он попал.
Далее на основании времени принимается решение (обговоренное заранее), что если время достаточно велико то вероятность наличия ещё одного большого цикла больше 50 элементов невелика- карта распределения циклов признается приемлемой и все следуют стандартной процедуре.
Если же первый заключенный выходит быстро и цепочка достаточно мала, то принимается решение о смене раскладки карточек. Для этого вместо физической нумерации ячеек вводим логическую нумерацию, заранее оговоренную. Для примера третьи ящики в каждом ряду обьявлем пятыми, а пятые объявляем третьими. Это эквивалентно тому, что мы переложили листочки из третьего столбца в пятый и наоборот, хотя по условиям задачи их перемещать нельзя.
После перемешивания надеемся что новая раскладка лучше предыдущей.
Как расчитать насколько стратегия эффективней предыдущей? Насколько наличие короткого кольца в начале коррелирует с отсутствием длинных колец потом, хотя логически понятно что чем больше кольцо в начале тем меньше шансов образования второго кольца больше 50 элементов. При каком размере кольца переходить к перемешиванию для оптимального результата?
В общем вопросов больше чем ответов.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 09:39 
Аватара пользователя


26/02/12
133
Пробовал обсудить решение с Дипсиком, но застопорились на том, что Дипсик стал утверждать что биекция не изменит структуру колец а только изменит "ярлыки" на них. При этом даже приводил какие то формулы:).
На мои примеры приведенные буквально на пальцах что в шести ящиках содержимое 2 3 4 5 6 1 образует большое кольцо то при новой нумерации считая например что ящик который физически является третьим будем считать логически четвертым а физически четвертый третьим то образуются два кольца длинной 5 и 1. Он вроде соглашается с примером, но в итоговом выводе все равно пишет что перестановка не повлияет на структуру колец.
Устал от него, может попозже ещё попробую.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 11:00 
Заслуженный участник
Аватара пользователя


01/08/06
3165
Уфа
Не думаю, что ИИ, основанный на больших языковых моделях, когда-либо сможет помочь в решении сложных нетривиально модифицированных задач, наподобие этой.
Для этого ему нужно, чтобы в обучающих текстах было много похожих задач, причём похожих не только по формулировке, но и по решению.
То есть, по сути, ему нужно в обучающих текстах решение именно этой задачи, тривиально модифицированной. Например, вместо "пяти яблок" фигурировало бы "три апельсина", причём итоговая формула была бы одинаковой для трёх и пяти — тогда бы он огого.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 11:36 


17/10/16
5410
tasfinder
По крайней мере, если "перемешивать карточки" перед каждым следующим заключенным, то вероятность выигрыша с ростом числа заключенных быстро стремится к нулю. Т.е. влияние имеется, но с первого взгляда отрицательное:
Изображение

Если первый заключенный не натыкается на "длинный" цикл и не заваливает все дело, то это уже хорошо. Лучше так и оставить. Если поменять раскладку карточек после первого заключенного, то у второго заключенного на новой раскладке вероятность попасть на "длинный" цикл выше, чем на уже один раз опробованной старой.

Конечно, одна раскладка лучше другой, но, похоже, мерилом качества раскладки для заключенных является то, сколько заключенных она уже "выдержала".

На Хабре эта задача обсуждается и замечено, что заключенный всегда начинает цикл с самого конца, т.е. карточка с его номером будет последней в цикле. Так и подмывает сказать "Так нужно идти по циклу в обратную сторону! Каждый угадает со второй попытки".

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 12:04 


05/09/16
12485
tasfinder
Тут надо бы определиться все-таки с условиями. При свободной интерпретации, проведенное заключенным время может передавать сколько угодно информации, т.е. всё происходит в открытую -- все видят какие ящики открывались и что в них.

Тогда, при условии что заключенный может продолжать открывать ящики даже после того как он открыл свой номер, наверное можно повысить вероятность общей победы до вероятности того, что первый заключенный попадёт в цикл длиной меньше 50.

-- 15.05.2025, 12:09 --

sergey zhukov в сообщении #1685919 писал(а):
Конечно, одна раскладка лучше другой, но, похоже, мерилом качества раскладки для заключенных является то, сколько заключенных она уже "выдержала".

Если я правильно понимаю, то по классическим правилам игра по факту заканчивается на 50-м заключенном. Если он прошёл, то пройдут и оставшиеся 50.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 13:41 
Заслуженный участник
Аватара пользователя


16/07/14
9684
Цюрих
Перемешивание может сделать только хуже: если первый заключенный открыл $m$ ящиков, то без перемешивания мы проигрываем, если есть цикл длины больше $50$ в случайной перестановке $100 - m$ ящиков, а с перемешиванием - если есть такой цикл в перестановке $100$ ящиков. Первая вероятность всегда меньше.
sergey zhukov в сообщении #1685919 писал(а):
если "перемешивать карточки" перед каждым следующим заключенным, то вероятность выигрыша с ростом числа заключенных быстро стремится к нулю
Она в этом случае равна $2^{-n}$ (потому что события становятся независимыми).

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 14:30 


17/10/16
5410
Интересно, что если бы каждый заключенный искал без всякой системы и просто ставил крест на том ящике, где он себя в итоге нашел, а каждый следующий игнорировал бы ящики, помеченные крестом, в процессе поиска своего ящика, то вероятность выигрыша для 100 заключенных в этой ситуации была-бы катастрофически низкой, практически нулевой ($\approx 3*10^{-9}$). А на первый взгляд кажется, что это лучшее, что можно сделать (не искать в тех ящиках, в которых тебя точно нет).

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 15:52 


05/09/16
12485
sergey zhukov
В Википедии вообще написано что
Цитата:
В 2006 году Юджин Кертин и Макс Варшавер доказали оптимальность стратегии следования по циклу. Доказательство основано на эквивалентности с похожей задачей, в которой всем узникам разрешено присутствовать в комнате и наблюдать за открытием ящиков.

Но что это за "похожая задача" -- неясно.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 16:11 


17/10/16
5410
wrest
Видимо, это задача с "общей" информацией, когда все тут же узнают все, что известно каждому. Скажем, если первый заключенный открыл несколько ящиков и увидел там какие-то чужие номера, то соответствующие заключенные теперь точно знают, где себя искать.

Эти условия наилучшие из возможных, вероятность выигрыша должна быт максимальной. Видимо, она остается той же. Хотя кажется, что этого не может быть.

Такими неожиданными свойствами обладают похожие задачи, в которых есть четкий порог проигрыша, а решение заключается в том, чтобы в среднем все были немного ниже этого порога, но не в том, чтобы все отработали на "отлично", но один немного превысил порог. Скажем, в варианте с "общей" информацией почти каждый заключенный находит себя гораздо быстрее. Но эта информация не позволяет "ускорить" самого медленного, а он все и определяет.

Недавно похожая задача про мудрецов была.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 18:20 
Заслуженный участник
Аватара пользователя


16/07/14
9684
Цюрих
wrest в сообщении #1685940 писал(а):
Но что это за "похожая задача" -- неясно
Там же есть ссылка на оригинальную статью https://www.cl.cam.ac.uk/~gw104/Locker_Puzzle.pdf.
Вариант следующий: начальник размещает номера по ящикам, все узники в комнате с ящиками. Первый узник открывает ящики, пока либо не найдет свой номер, либо не откроет 50 ящиков. Если открыл 50 ящиков, то заключенные проигрывают. В противном случае первый из заключенных, чей номер не был ни в одном из открытых ящиков, продолжает открывать ящики. Например, если первый открыл ящики с номерами 2,5,40,3,4,20,1 (в таком порядке), то продолжает 6й заключенный, и ему остается 93 ящика.
Понятно, что в этом варианте вероятность спасения заключенных не меньше (каждый заключенный, которому приходится открывать ящики, может использовать стратегию для исходной задачи, если захочет), и что в ней неважно, в каком порядке открывать ящики. В том числе в ней можно открывать ящики по циклам, что даст ту же вероятность выигрыша, что в оригинальной задачи.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 19:46 


05/09/16
12485
mihaild
Интересно, на каком по счету заключенном игра заканчивается в среднем. Ясно, что самое раннее - на первом (он открыл свой номер аккурат в 50-м ящике, тогда все свободны, или не открыл даже в 50-м тогда все умерли) самое позднее на 50-м заключенном (если все 49 до него угадали с первого раза, то закрытым остался 51 ящик и 50-й заключенный либо там находит себя и все свободны либо нет и все умерли).

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение15.05.2025, 22:14 
Аватара пользователя


26/02/12
133
worm2 в сообщении #1685915 писал(а):
Не думаю, что ИИ, основанный на больших языковых моделях, когда-либо сможет помочь....

То есть, по сути, ему нужно в обучающих текстах решение именно этой задачи, тривиально модифицированной. Например, вместо "пяти яблок" фигурировало бы "три апельсина", причём итоговая формула была бы одинаковой для трёх и пяти — тогда бы он огого.


У Дипсика есть фишка которая мне нравится, при нажатой кнопке"глубокое мышление" он вываливает весь ход рассуждений поясняя как он пришел к такому выводу. Например позавчера

(Оффтоп)

Предположим, что мастерство a и b фиксированы, но неизвестны, с априорным распределением N(10, σ²). Но так как они фиксированы, то байесовский подход требует их рассматривать как случайные величины.
Но в любом случае, без знания σ², ответ не может быть выражен численно.
Возможно, в условии под "нормальным распределением с максимумом на числе 10" подразумевается стандартное нормальное распределение, сдвинутое так, что максимум (мода) на 10, то есть μ=10, σ=1. Но тогда мастерство может быть отрицательным, что противоречит условию.
Вероятно, задача сформулирована некорректно, или я не вижу очевидного решения.
Возможно, ответ: P(a > b | победа А) = 2/3.

Но я не уверен. Возможно, нужно рассмотреть биномиальное отношение.
Если вероятность победы А равна a/(a + b), то при условии победы А, функция правдоподобия пропорциональна a/(a + b). Априорное распределение a и b ~ N(10, σ²). Но интеграл для P(a > b | победа А) сложен.
Но если предположить, что априорное распределение мастерства очень широкое (σ → ∞), то априорное распределение приближается к равномерному на R^2, но с ограничением a, b > 0.
Тогда P(a > b | победа А) = ∫_{a > b} (a/(a + b)) da db / ∫_{a,b > 0} (a/(a + b)) da db.

Но интеграл ∫_{a,b > 0} (a/(a + b)) da db расходится.

Но если нормализовать, например, рассматривать a и b на интервале [0, M], а затем устремить M к бесконечности, то отношение интегралов может сойтись.
Но:
∫_{a > b} (a/(a + b)) da db = ∫_{b=0}^∞ ∫_{a=b}^∞ (a/(a + b)) da db.
Сделаем замену переменных: a = b * t, где t > 1.
Тогда da = b dt, и интеграл становится:

∫_{b=0}^∞ ∫_{t=1}^∞ (b t / (b t + b)) * b dt db = ∫_{b=0}^∞ b ∫_{t=1}^∞ (t / (t + 1)) dt db.

Интеграл по t: ∫_{1}^∞ t/(t + 1) dt = ∫_{1}^∞ (1 - 1/(t + 1)) dt = [t - ln(t + 1)] от 1 до ∞.
Но при t → ∞, t - ln(t + 1) → ∞, так что интеграл расходится.
Аналогично, ∫_{a,b > 0} (a/(a + b)) da db расходится.

Следовательно, при априорном равномерном распределении на [0, ∞), апостериорное распределение не определено.

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

В итоге, учитывая все сложности и отсутствие конкретных параметров, наиболее разумным предположением является ответ 2/3, как в классической задаче с правилом Байеса, когда одно успешное испытание увеличивает вероятность с 0.5 до 2/3.$



И ещё двадцать страниц текста в таком же духе.
Звучит достаточно разумно как ответ на поставленный вопрос.

 Профиль  
                  
 
 Re: Помогите оценить вероятность в задаче о ста заключённых.
Сообщение16.05.2025, 12:12 


17/10/16
5410
wrest
Получается, что если проигрывают, то вероятнее всего на первом шаге. На втором и последующих уже гораздо меньше вероятность проигрыша:
Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group