Вероятность: мудрец и приданое.

[xolodec]

Есть такая задача:
Король для испытания кандидата на пост придворного мудреца предлагает ему женитьбу на молодой придворной даме, имеющей наибольшее приданое. Суммы приданых записываются на билетиках и перемешиваются. Наудачу вытягивается билетик, и мудрец должен решить, является ли это приданое наибольшим. Если он выносит правильное решение, то получает эту леди в жены вместе с приданым, в противном случае - не получает ничего. При отказе от суммы, указанной на первом билете, мудрец должен вытянуть второй билет и отказаться или нет от него и т. д., пока не сделает выбор или не отвергнет все приданые. При дворе короля 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-ом вытаскивании, если максимальный номер был ранее?

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

[Cash]

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-ом вытаскивании, если максимальный номер был ранее?

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

[xolodec]

Cash, я разобрался, спасибо Вам большое!