Пятьдесят занимательных вероятностных задач с решениями

Число совпадений	0	1	2	3
Вероятность	2/6	3/6	0/6	1/6

Приведем также соответствующую таблицу для n = 4. Легко заметить, что вероятность того, что произойдет n совпадений, равна 1/n!, поскольку только одной из n! перестановок отвечает n совпадений.

Число совпадений	0	1	2	3	4
n = 1, вероятность	0	1
n = 2, вероятность	1/2	0	1/2
n = 3, вероятность	2/6	3/6	0	1/6
n = 4, вероятность	9/24	8/24	6/24	0	1/24

Отметим, что математическое ожидание каждого распределения равно 1, как указано в предыдущей задаче.

Пусть P(r/n) обозначает вероятность ровно r совпадений при распределении n объектов. Эти r совпадений могут быть получены за счет совпадения r фиксированных объектов и несовпадения остальных. Так, например, вероятность того, что совпадают именно r первых объектов, равна

Число различных выборов r объектов из n равно так что

При r = n, как мы знаем, P(n/n) = 1/n!, и мы можем положить P(0/0) = 1.

Проверим справедливость соотношения (1) при n = 4, г = 2. Согласно (1)

а из нашей таблицы видно, что

P(2/4) = 6/24,

P(0/2) = 1/2

и 6/24 = 1/4, что подтверждает (1) в этом частном случае.

Мы знаем также, что сумма вероятностей по всем возможным числам совпадений при заданном значении n равна 1, т. е.

P(0/n) + P(1/n) + ... + P(n − 1/n) + P(n/n) = 1.

Используя (1), запишем это соотношение как

Так как P(n/n) = 1/n!, то отсюда можно последовательно находить значения P(0/n).

Итак, мы можем найти в принципе значение P(0/n) при любом n, но не располагаем общей формулой для вычисления P(0/n). Как и в некоторых других задачах, здесь помогает вычисление последовательных разностей. Подсчитаем P(0/n) − P(0/n − 1) для различных значений n. Имеем

P(0/1) − P

(0/0) = 0 − 1 = −1 = −1/1!,

P(0/2) − P(0/1) = 1/2 − 0 = 1/2 = 1/2!,

P(0/3) − P(0/2) = 2/6 − 1/2 = −1/6 = −1/3!,

P(0/4) − P(0/3) = 9/24 − 2/6 = 1/24 = 1/4!.

Эти выкладки наводят на мысль о том, что искомые разности имеют вид (-l)^r/r!, т. е.

Суммируя эти разности, получаем

Записывая P(0/0) в виде 1/0!, получаем

          (3)

Осталось проверить теперь справедливость нашей догадки. Нам надо вычислить

          (4)

Не следует терять хладнокровия. при виде этого зловещего выражения. Ведь сумма в (4) образована слагаемыми вида

где индекс j отвечает множителю, стоящему перед знаком суммы, а индекс i соответствует отдельным членам этой суммы. Переставим местами слагаемые так, чтобы сумма i + j была постоянной. Так, для i + j = 3 получим

Умножая на 3!, получаем более знакомое выражение

которое с помощью биномиальных коэффициентов может быть записано в виде

Но эта сумма есть разложение (x + y)³ при х = −1, y = 1 и, значит, равна нулю, так как (-1 + 1)³ = 0³ = 0. Этот факт имеет место при каждом значении i + j = r, r = 1, 2, ...., n, так что соответствующие суммы равны нулю. Лишь при r = 0 получаем единственный член (-1)⁰/(0!·0!) = 1. Следовательно, решение (3) удовлетворяет уравнению (2).

Ясно, что других решений у (2) нет. Это может быть доказано методом индукции, так как P

(0/n) выражается через P(0/1), P(0/2), ..., P(0/n − 1).

Из (1) и (3), наконец, выводим

Если n − r велико, то выражение в скобках близко к e⁻¹ и

если только n − r достаточно велико. Итак, действительно, вероятности r совпадений в нашей задаче близки к пуассоновским со средним 1. Однако для этой близости необходимо, чтобы разность n − r была велика, а не только само n, как казалось в начале.

Вероятность того, что нет ни одного совпадения, при больших n стремится к e⁻¹ ≈ 0.368.

47. Решение задачи о выборе наибольшего приданого

Любопытно узнать — на много ли шансы мудреца на успех больше 1/100? Многие предлагают следующую стратегию: пропустить первую половину билетов и затем выбрать первую сумму, превосходящую все предыдущие, если таковая найдется. Это достаточно разумно, но такая стратегия не является оптимальной. Очень немногие представляют себе порядок величины вероятности выигрыша.

Мы начнем с рассмотрения нескольких примеров. Поскольку мы ничего не знаем о суммах, проставленных на билетах, то можем рассматривать лишь номера билетов при их упорядочении согласно величинам сумм, записанных на них. Если, например, у нас имеется три билета с номерами 1, 2, 3, то билету 3 отвечает наибольшее приданое. Для одного или двух билетов задача тривиальна: мудрец делает правильный выбор при одном билете, и его шансы на выигрыш равны 1/2 при двух билетах.

При трех билетах имеем шесть возможных способов вытаскивания:

    123 231*        

    132* 312        

    213* 321        

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

Допустим теперь, что у нас есть четыре билета. Их возможные перестановки есть

    1234 2134 3124*+ 4123    

    1243+ 2143*+ 3142*+ 4132    

    1324+ 2314+ 3214*+ 4213    

    1342+ 2341+ 3241*+ 4231    

    1423* 2413* 3412* 4312