М17. Среднее число индикаторов, необходимое для построения полных цепочек

Эта задача представляет собой частный случай (для N=26) более общей задачи, которая, выступая под разными названиями (например, "задача о собирателе купонов" или "задача о сигаретных пачках")^*), в течение многих лет являлась предметом повышенного интереса:

"В множестве содержатся элементы N различных типов, причем самих элементов имеется очень много. Коллекционер каждый раз случайно выбирает по одному элементу из множества. Сколько элементов (в среднем) ему придется выбрать, прежде чем у него будут элементы всех типов?"

(Для тех, кто знаком с терминологией теории вероятностей скажем, что этот случай называется "выборка с возвращением").

Можно показать (см., например, [8.1], стр. 225), что ожидаемое число равно

.

Его можно оценить, заменив сумму в скобках на соответствующий интеграл

,

где ln(N) - это натуральный логарифм числа N. Если быть более точным, то

при N,

где число , называемое константой Эйлера, равно 0.577... . Подставляя N=26, получаем оценку

26(ln(26)+0.577)99.7

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