Термист Термомеханическое упрочнение арматурного проката технология, средства, разработка

Выбор наибольшего случайного числа

Постановка задачи

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

Какой должна быть стратегия мудреца?

Решение задачи

Довольно понятно, что надо выбрать первое же число, если оно достаточно велико, например, равно 0.999, потому что вероятность получить не меньшее же число позднее, равна только
1 - (0.999)99 ≈ 0.1.

Как и в предыдущей задаче, мы должны выбирать между очередным максимальным появившимся номером и шансом на то, что одно из последующих чисел будет больше этого номера, причем мы его выберем. Рассмотрим процедуру решения с конца. Если мы не сделали выбор до последнего шага, то останавливаемся на последнем числе и выигрываем или проигрываем. Если выбор не произведен до предпоследнего вытягивания, и появилось максимальное число (самое большое до сих пор), мы выбираем его, если оно больше 1/2, отказываемся от него, если оно меньше 1/2, и поступаем произвольным образом в случае 1/2. Если это число меньше 1/2, то шанс на выигрыш больше при продолжении испытаний.

Если третье с конца число x максимально, то вероятности появления 0, 1 или 2 больших чисел после этого равны x², 2x∙(1 - x) и (1 - x)² соответственно. Если мы пропустим x и выберем следующее большее, чем x, число, то вероятность выигрыша окажется равной
2x∙(1 - x) + 1/2∙(1 - x)²,
так как если дальше будет 0 больших чисел, мы не выиграем, если 1, то выиграем наверняка, и если два числа, больших x, то мы выберем наибольшее с вероятностью 1/2. Если мы пропускаем какое-то число при определенном вытаскивании, то при последующих вытягиваниях это положение может измениться, так как нам, возможно, придется остановиться на этом числе, ввиду уменьшения шансов на появление большего. Следовательно, если имеются два числа, больших «порогового» уровня x в нашей последовательности, то мы заведомо выберем первое. Оно лишь с вероятностью 1/2 наибольшее из этих двух чисел. Таким образом, если на некотором шагу мы отказались от «порогового» числа, то можно быть уверенным в том, что оптимальная стратегия выбирает первое число, значение которого превосходит данный «пороговый» уровень.

Определим это «пороговое» значение x для третьего с конца шага. Это число удовлетворяет уравнению
x² = 2x∙(1 - x) + 1/2∙(1 - x)².

Здесь x² есть вероятность того, что мы выиграем, остановившись на числе x, а правая часть есть вероятность выиграть, если мы отказались от x. «Пороговый» уровень, как нетрудно проверить, равен

Таким образом, мы выбираем максимальное число третье с конца, если его значение превосходит 0.6899.

Вообще, если остается r билетов и появилось максимальное число, то мы выберем его, если оно превосходит «пороговое» значение x, вычисляемое из уравнения
          (1)

Для нахождения x при небольших значениях r это уравнение можно решать численно, используя, например, таблицы вероятностей биномиального закона. В нижеследующей таблице «пороговых» уровней приведены некоторые из них.

Таблица 1

Таблица «пороговых» уровней и их приближений

Число оставшихся испытаний	Решение уравнения (1)		Число оставшихся испытаний	Решение уравнения (1)
1	0.5000	0.5542	9	0.9160	0.9180
2	0.6899	0.7132	10	0.9240	0.9256
3	0.7758	0.7886	11	0.9305	0.9319
4	0.8246	0.8326	12	0.9361	0.9372
5	0.9856	0.8614	13	0.9408	0.9417
6	0.8778	0.8818	14	0.9448	0.9457
7	0.8939	0.8969	15	0.9484	0.9491
8	0.9063	0.9086

Чтобы найти приближенное решение, заметим, что 1 - x уменьшается по мере возрастания r, и главный вклад в правую часть уравнения (1) дается первым членом. Таким образом,
x^r ≈ r∙x^{r - 1}∙(1 - x),   или   x ≈ r/(r + 1).

С другой стороны, деля обе части уравнения (1) на x^r и полагая z = (1 - x)/x, получаем
          (2)
откуда определяется z.

Наконец, так как приближенно z = 1/r, положим

где α(r) - функция, близкая к постоянной. Так,
α(1) = 1
α(2) = 0.8990,
α(3) = 0.8668,
α(4) = 0.8509,
α(5) = 0.8415.

Полагая в (2) z = α(r)/r и устремляя r к бесконечности, получаем
          (3)
α(r)
Здесь α - предельное значение α(r), α = 0.8043.Хотя существуют и лучшие приближения для α(r), заменим α(r) на α. Тогда

Эта формула для x дает результаты, приведенные в последнем столбце Таблицы 1.

Поскольку в данной игре больше информации, чем в игре из предыдущей задачи, то шансы на выигрыш также больше. Если число билетов равно 2, то игроку следует выбрать первое число, если оно больше 1/2, а в противном случае избрать второе. Вероятность правильного решения в этом случае равна 3/4. Увеличение числа билетов от 1 до 2 значительно уменьшило вероятность выигрыша. Некоторые геометрические соображения, которые мы не будем здесь приводить, показывают, что для n = 3 вероятность правильного выбора равна приблизительно 0.684. Для больших n эта вероятность равняется приближенно 0.580.

Публикуется по работе: Пятьдесят занимательных вероятностных задач с решениями. Ф.Мостеллер, перев. с англ., издание второе. М. Наука, 1975, 112 с.

К началу страницы

Web-сайт “Термист” (termist.com)
Термомеханическое упрочнение арматурного проката

Отсутствие ссылки на использованный материал является нарушением заповеди "Не укради"

Редактор сайта: Гунькин И.А. (termist.com@gmail.com)