Длина строки, что бы встретились все символы. Тервер

[UserCan]

Добрый день.
Существует такая задача: Есть строка и некоторый алфавит длиной $N$ ($N$ в общем случае большое и можно апроксимировать). В каждый момент времени в строке появляется один символ из алфавита. Появление символов равновероятное и независимое от предшествующих. То есть строка - это бернуллиевская последовательность. Необходимо найти длину строки, при которой в ней с вероятностью $p=0.5$ появится все символы из алфавита (хотя бы один раз). Для длины достаточна оценка снизу, главное, что бы обосновано и естественно больше чем длина алфавита.
Нигде не смог найти решение данной задачи.
Данная постановка задачи описывается полиномиальным распределением, но проблема в том что что при больших размерах алфавита не понятно как найти все выборки в которых может присутствовать ноль напротив одного из символов,
а затем просуммировать их вероятности. В принципе все такие события описываются полиномиальным распределением
для $N-1$ символов. А преобразовать в соответствующую вероятность для $N$ символов (в дальнейшем использую устояшевшиеся обозначения $k = N$ - длина алфавита, $n$ - длина строки) $\frac{(k-1 )^n}{k^n}$, что выводится просто из сравнения формул вероятности для $k-1$ и $k$ при $n$ опытах. Но при этом возникают дополнительные тонкие места связанные с выборкой $n-1$ символов из алфавита $n$, что тоже легко рассчитывается. Но просто умножить их нельзя, так как в каждом из выделенных алфавитов могут быть порождены одинаковые строки, а как их учесть не понятно.
Пробовал использовать распределение Пуассона, но как работать с ним в отношении полиномиального распределения не знаю (источников пока не нашёл). А из того что получилось своими силами не понятно как привязать к данной задачи.
Смотрел обратное полиномиальное распределение. Но как его прикрутить к этой задачи не понятно, так как в ней количество опытов останавливается, когда одно из событий превысило определённый порог, а в данном случае должны превысить все события минимальный порог. Думал рассмотреть задачу как зависят вектора от максимального количества определённого события, но как к этому подойти не понятно.
В итоге я решил задачу приблизительно, но как её обосновать вопрос и рассчитать вероятность данного события при найденной длине для проверки. Для этого рассмотрел следующую схему взятия шаров из вазы с возвращением. В вазе присутствует $k$ белых шаров. Когда мы из вазы достаём белый шар мы считаем это успешным событием, после чего его красим в чёрный цвет и кладём обратно в вазу. Теперь для каждого количества белых шаров в вазе, кроме того случая когда там уже все чёрные, мы рассчитываем количество опытов $n_\text{текущее}$ при котором с вероятность $0.5$ будет успешное событие - а именно достанем белый шар. После этого суммируем количество всех опытов и получаем примерную длину строки в которой с вероятностью $0.5$ будут встречены все символы из алфавита.
$1 + \sum\limits_{i=1}^k \lceil\log_{(1-i/k)}(0.5)\rceil$

[--mS--]

В.Ф.Колчин, Б.А.Севастьянов, В.П.Чистяков "Случайные размещения", М.:Наука, 1976.
Эксперимент очевидно можно мыслить как случайное размещение частиц по $N$ ячейкам. Для числа пустых ячеек результатов много.
Например, вероятность не иметь пустых ячеек после размещения $n$ частиц (аккурат вероятность встретить все символы алфавита из $N$ символов в строке длиной $n$) равна

$$\mathsf P(\mu_0(n, N) = 0)=\sum_{k=0}^N C_N^k (-1)^k \left(1-\frac{k}{N}\right)^n.$$

Формула включения-исключения.

Оценок там, правда, нет, но есть всякие-разные асимптотики. Например, теорема 4 на стр.20, если её использовать для минимального числа $\nu_N$ частиц, которые нужно бросить для заполнения всех $N$ ящиков, даст:

$$\lim\limits_{N\to\infty} \mathsf P(\nu_N < N\ln N- N\ln\ln 2)=\frac12. $$

[UserCan]

Наверно оно. Буду читать.
Большое спасибо.