2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Вероятность: мудрец и приданое.
Сообщение28.03.2015, 09:22 


29/04/14
139
Есть такая задача:
Король для испытания кандидата на пост придворного мудреца предлагает ему женитьбу на молодой придворной даме, имеющей наибольшее приданое. Суммы приданых записываются на билетиках и перемешиваются. Наудачу вытягивается билетик, и мудрец должен решить, является ли это приданое наибольшим. Если он выносит правильное решение, то получает эту леди в жены вместе с приданым, в противном случае - не получает ничего. При отказе от суммы, указанной на первом билете, мудрец должен вытянуть второй билет и отказаться или нет от него и т. д., пока не сделает выбор или не отвергнет все приданые. При дворе короля 100 привлекательных дам, все их приданые различны.

Собственно задача не нова и ее решение известно, описывается в книге Ф.Мостеллера, но в ходе доказательства у меня возникает недопонимание, котрое я уже неделю не могу сам себе объяснить.

Вот приблизительная схема доказательства:
Цитата:
Покажем теперь, что оптимальная стратегия - пропустить $ s - 1 $ билетов и выбрать первый максимальный номер после них. Мы выберем максимальное приданое на $i$-м шагу, если вероятность того, что оно наибольшее среди всех имеющихся, превосходит вероятность правильного решения при оптимальной стратегии и более позднем вытягивании. Формально: остановимся на максимальном номере при $i$-м вытягивании, если

$$ P(\text{выиграть при i-м вытягивании}) > $$ $$ P(\text{выиграть при оптимальной стратегии, начиная с i + 1 вытягивания})$$ (1)

Покажем, что вероятность в правой части (1) убывает, когда i возрастает, а вероятность в левой части (1) возрастает с возрастанием i, и потому существует выбор шага i, после которого предпочтительнее удержать максимальное приданое, нежели продолжать испытания. Вычисляя затем вероятность выигрыша для такой стратегии, найдем оптимальный выбор значения s.

После нескольких первых ходов в этой игре мы можем еще прибегнуть ко всем стратегиям, определяемым последующими вытаскиваниями, так как мы всегда можем пропустить часть билетов, пока не достигнем нужного нам числа билетов. Следовательно, вероятность в правой части неравенства (1) не возрастает с ростом $i$. При $i = 0$ это искомая оптимальная вероятность, а при $i = n - 1$ эта вероятность равна $1/n$ как вероятность выигрыша при выборе на последнем шагу.

Вероятность того, что на $i$-м шагу максимальное приданое больше всех имеющихся, равна вероятности того, что наилучший номер находится на одном из первых i билетов, а именно, равна $i/n$, что является строго возрастающей от $1/n$ до $1$ функцией от $i$. Поэтому значение $i/n$ в какой-то точке превосходит вероятность выигрыша при продолжении испытаний.


Я, собственно говоря, не могу понять, почему
$$ P(\text{выиграть при i-м вытягивании}) = \frac{i}{n} $$
Версия 1.
Вероятность выиграть при i-м вытягивании не может быть отлична от $\frac{1}{n}$, поскольку в $n$ номерах только один наибольший и он может быть вытащен на любом ходе.
Версия 2.
В задаче рассматривается вероятность, что вытащенный i-ый номер максимальный среди всех $i-1$, которые уже были вытащены. Но тогда, нет гарантии, что мы выиграем, потому что данная вероятность учитывает вероятность "локального" максимума из первых $i$ билетов, но не максимум из всех билетов вообще.
Версия 3.
Автор рассматривает потенциальную возможность выиграть на i-ом вытаскивании, безотносительно к стратегии, о которой пишет. Выиграть на первом вытаскивании можно только в том случае, если на первом месте окажется наибольший билет, т.е., действительно, $\frac{1}{n}$.
Вероятность того, что мы выиграем к i-ому вытаскиванию, равна вероятности, что мы выиграем на любом из $i$ первых вытаскиваний.
Но в этом случае неясно, почему нам стоит остановиться на i-ом вытаскивании, если максимальный номер был ранее?

Можете, пожалуйста, прояснить ситуацию ?

 Профиль  
                  
 
 Re: Вероятность: мудрец и приданое.
Сообщение28.03.2015, 11:56 
Заслуженный участник


12/09/10
1547
xolodec в сообщении #996792 писал(а):
Вероятность выиграть при i-м вытягивании не может быть отлична от $\frac{1}{n}$, поскольку в $n$ номерах только один наибольший и он может быть вытащен на любом ходе.

Вероятность того, что, если мы получили максимум на $i$-м шаге, то он окажется глобальным - равна $\frac in$.
xolodec в сообщении #996792 писал(а):
В задаче рассматривается вероятность, что вытащенный i-ый номер максимальный среди всех $i-1$, которые уже были вытащены. Но тогда, нет гарантии, что мы выиграем, потому что данная вероятность учитывает вероятность "локального" максимума из первых $i$ билетов, но не максимум из всех билетов вообще.

Как известно, полную гарантию дает лишь страховой полис. Наша задача, всего лишь, максимизировать свои шансы.
xolodec в сообщении #996792 писал(а):
Автор рассматривает потенциальную возможность выиграть на i-ом вытаскивании, безотносительно к стратегии, о которой пишет. Выиграть на первом вытаскивании можно только в том случае, если на первом месте окажется наибольший билет, т.е., действительно, $\frac{1}{n}$.
Вероятность того, что мы выиграем к i-ому вытаскиванию, равна вероятности, что мы выиграем на любом из $i$ первых вытаскиваний.
Но в этом случае неясно, почему нам стоит остановиться на i-ом вытаскивании, если максимальный номер был ранее?

Мы не останавливаемся, если не получен максимум (локальный), поэтому ваши страхи напрасны.

 Профиль  
                  
 
 Re: Вероятность: мудрец и приданое.
Сообщение28.03.2015, 18:19 


29/04/14
139
Cash, я разобрался, спасибо Вам большое!

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

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



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

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


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

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