§5. Шарики в ящиках: раскидай и посчитай пустые

В задаче 3 встретится частный случай так называемого полиномиального распределения, возникающего при случайном размещении шаров по ящикам. Разберёмся с этой моделью подробно — она неожиданно доводит до статистической физики.

Полиномиальное распределение

Шарики, занумерованные числами от 1 до $n$, раскладываются по $N$ ящикам. Произвольное размещение описывается набором $\omega = (j_1, j_2, \dots, j_n)$, где $j_i$ — номер ящика (от 1 до $N$), куда попал $i$-й шарик. Всего существует $N^n$ различных наборов. Говоря о «случайном» распределении шаров по ящикам, мы имеем в виду, что все размещения имеют одинаковые вероятности $N^{-n}$.

Пусть $l_j$ — неотрицательные целые числа, $l_1 + \dots + l_N = n$, а $\nu_j$ — количество шариков в $j$-м ящике. Какова вероятность события $A = \{\nu_1 = l_1, \dots, \nu_N = l_N\}$?

Событие $\{\nu_1 = l_1\}$ происходит, когда среди номеров $j_i$ оказывается ровно $l_1$ единиц. Расставить $l_1$ единиц по $n$ местам можно $C_n^{l_1}$ способами. На оставшихся $n - l_1$ местах надо разместить $l_2$ двоек — $C_{n-l_1}^{l_2}$ способами, и так далее. Перемножая и сокращая факториалы:

Включение-исключение

Подсчитаем теперь вероятность того, что ровно $k$ ящиков из $N$ окажутся пустыми. Для этого потребуется общая теорема.

Теорема 4. Вероятность события $B_k$, состоящего в том, что произойдёт ровно $k$ событий из $A_1, A_2, \dots, A_N$, вычисляется по формуле

$$\mathbf{P}(B_k) = \sum_{l=k}^N (-1)^{l-k}\,C_l^k\,S_l, \qquad S_l = \sum_{1 \le j_1 < j_2 < \dots < j_l \le N}\mathbf{P}(A_{j_1}A_{j_2}\cdots A_{j_l}), \quad S_0 = 1.$$

Доказательство. Проверим, что индикатор $I_{B_k}$ представляется в виде двойной суммы:

Пусть элементарное событие $\omega$ принадлежит ровно $m$ множествам из $A_1, \dots, A_N$.

• Если $m < k$, то $I_{B_k} = 0$, и все члены правой части (4) равны 0: никакие $l \ge k$ событий одновременно не произошли.
• Если $m = k$, то $I_{B_k} = 1$. В правой части член в квадратных скобках равен 1, когда $l = k$, и 0 иначе. Правая часть тоже 1.
• Пусть $m > k$. Тогда $I_{B_k} = 0$. Сумма в квадратных скобках при $l > m$ равна 0, а при $l \le m$ равна $C_m^l$ — числу наборов по $l$ событий из $m$, содержащих $\omega$. Вся правая часть превращается в

(Использовали тождество $C_l^k C_m^l = C_m^k C_{m-k}^{l-k}$ и бином Ньютона.) Доказательство завершается взятием матожиданий от обеих частей тождества (4). $\blacksquare$

Следствие теоремы 4 — принцип включения-исключения: вероятность того, что произойдёт хотя бы одно из событий $A_1, \dots, A_N$, равна

Смысл по-пацански: посчитал всех, кто был хоть в одной бригаде, — но кто был в двух, посчитан дважды. Вычти их. Но тех, кто был в трёх, ты вычел лишний раз — прибавь обратно. И так до конца.

Задача о совпадениях

Пример 4. Вычислим вероятность наблюдать ровно $k$ совпадений при случайном сопоставлении двух одинаковых колод из $N$ различных карт (или при случайной раскладке $N$ писем по конвертам). Множество элементарных событий — перестановки $\omega = (i_1, \dots, i_N)$ первых $N$ натуральных чисел, каждой приписана вероятность $1/N!$. Пусть $A_m$ — множество перестановок, оставляющих $m$ на своём месте: $i_m = m$. Тогда $\mathbf{P}(A_{j_1}\cdots A_{j_l}) = (N - l)!/N!$, и $S_l = C_N^l(N - l)!/N! = 1/l!$. По теореме 4

Следовательно, $\mathbf{P}(B_k) \to e^{-1}/k!$ при $N \to \infty$: предельный закон для числа совпадений — Пуассон с $\lambda = 1$ (глава 5). В частности, вероятность хотя бы одного совпадения стремится к $1 - e^{-1} \approx 0{,}632$. Точность приближения при небольших $N$ видна из таблицы:

Смысл по-пацански: раскидал письма по конвертам наугад. Сколько бы ни было писем — 6 или миллион — шанс, что хотя бы одно попало куда надо, почти одинаковый: около 63 %.

Пустые ящики: различимые шарики

Вернёмся к вероятности $p_k$ того, что при случайном размещении $n$ шариков по $N$ ящикам окажется ровно $k$ пустых ящиков. Обозначим через $A_j$ событие «$j$-й ящик пуст». Чтобы для заданных $l$ номеров $j_1 < \dots < j_l$ произошло $A_{j_1}\cdots A_{j_l}$, все шарики должны попасть в оставшиеся $N - l$ ящиков. Вероятность этого $(N - l)^nN^{-n} = (1 - l/N)^n$. Отсюда $S_l = C_N^l(1 - l/N)^n$, и по теореме 4

Изучим поведение $p_k$, когда $N$ и $n$ растут так, что $Ne^{-n/N} \to \lambda > 0$. Нетрудно проверить, что это условие равносильно

Теорема 5. Для $k = 0, 1, \dots$ при выполнении условия (6) вероятность $p_k \to \lambda^k e^{-\lambda}/k!$, то есть предельным законом для числа пустых ящиков служит распределение Пуассона с параметром $\lambda$.

Идея доказательства. Правая часть (5) элементарными выкладками приводится к $\frac{1}{k!}\sum_{l=k}^N\frac{(-1)^{l-k}}{(l-k)!}\bigl[(1 - l/N)^nN^l(1 - \frac{l-1}{N})\cdots\bigr]$. Так как $1 - x \le e^{-x}$, член в скобках не больше $(Ne^{-n/N})^l$, что позволяет перейти к пределу под знаком суммы. А сам член стремится к $\lambda^l$, потому что $(1 - l/N)^nN^l = \bigl[(1 - l/N)^Ne^l\bigr]^{n/N}e^{(\ln N - n/N)l}$, и при условии (6) $\ln N - n/N \to \ln\lambda$. Замена индекса $j = l - k$ даёт ряд для $e^{-\lambda}$.

Чтобы пустых ящиков не осталось с вероятностью около $e^{-1}$, нужно порядка $N\ln N$ шариков — это знаменитая задача о собирателе купонов.

Неразличимые шарики

Пример 5. Рассмотрим варианты размещения $n$ неразличимых шариков по $N$ ящикам. Каждый вариант описывается вектором $\omega = (x_1, \dots, x_N)$, где $x_j$ — число шариков в $j$-м ящике. Посмотрим на него как на последовательность символов: «0» — шарик, «|» — стенка между двумя соседними ящиками:

Так как имеется $N$ ящиков, вертикальных чёрточек $N - 1$. Общее число позиций, занятых либо ноликом, либо чёрточкой, равно $n + N - 1$, причём $n$ из них заняты ноликами. Поэтому всего разных вариантов размещения $C_{n+N-1}^n$. Если считать, что все они равновероятны, каждому $\omega$ надо приписать вероятность $1/C_{n+N-1}^n$.

Например, при $n = 2$ и $N = 2$ различимых размещений 4: (①② | ), (① | ②), (② | ①), ( | ①②). А неразличимых — 3: (00|), (0|0), (|00). В первом случае «по одному в каждом ящике» имеет вероятность $\tfrac12$, во втором — $\tfrac13$.

Физика: какие частицы как размещаются

Эта модель неожиданно применяется в статистической физике. Перескажем рассуждение Феллера. Механическую систему из $n$ неразличимых частиц описывают так: фазовое пространство разбивают на большое число $N$ малых ячеек, и состояние системы — это случайное размещение $n$ частиц по $N$ ячейкам.

• На первый взгляд кажется, что все $N^n$ размещений равновероятны. Это статистика Максвелла — Больцмана. Делались многочисленные попытки доказать, что частицы ведут себя именно так. Но современная теория показала, что эта статистика не применима ни к каким известным частицам.
• В статистике Бозе — Эйнштейна каждому размещению приписывается вероятность $1/C_{n+N-1}^n$ — ровно модель неразличимых шариков. Так ведут себя фотоны, атомные ядра и атомы с чётным числом элементарных частиц.
• Статистика Ферми — Дирака добавляет запрет: в одной ячейке не может быть двух частиц. Тогда размещение задаётся выбором $n$ занятых ячеек из $N$, и каждое из $C_N^n$ размещений равновероятно. Так ведут себя электроны, нейтроны и протоны.

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

Различимые против неразличимых

Размещения неразличимых частиц имеют ряд существенных отличий от размещений различимых.

Сколько шариков в фиксированном ящике. Пусть $r_k$ — вероятность того, что, скажем, первый ящик содержит ровно $k$ различимых шариков. Остальные $n - k$ шариков надо разместить по $N - 1$ ящикам:

— биномиальное распределение с $p = 1/N$. При $N, n \to \infty$ так, что среднее число шариков на ящик $n/N \to \lambda$, оно сходится к закону Пуассона с параметром $\lambda$. Наиболее вероятное число шариков — около $\lambda$.

Для неразличимых шариков вероятность $\tilde r_k$ того, что фиксированный ящик содержит ровно $k$ шариков, — это доля размещений оставшихся $n - k$ шариков по $N - 1$ ящикам: $\tilde r_k = C_{n-k+N-2}^{n-k}/C_{n+N-1}^n$. При том же предельном переходе

— геометрическое распределение с $p = (\lambda + 1)^{-1}$. Отношение соседних вероятностей $\tilde r_{k+1}/\tilde r_k = \dfrac{n - k}{n - k + N - 2}$ при $N > 2$ меньше 1, так что вероятности $\tilde r_k$ монотонно убывают по $k$. Наиболее вероятно, что фиксированный ящик пуст! (У Лагутина это отношение записано как $1 - (N-2)/(n-k)$; мы проверили на малых $n$ и $N$ — верна формула выше, вывод о монотонности тот же.)

Пустые ящики. Для неразличимых шариков относительное преобладание размещений с большим числом пустых ящиков ещё заметнее. Пусть $\tilde p_k$ — вероятность обнаружить ровно $k$ пустых ящиков. Число размещений, где заданные $l$ ящиков пусты, равно числу способов разложить $n$ шариков по оставшимся $N - l$ ящикам. По теореме 4

Эту сумму можно свернуть в одно слагаемое: выбираем, какие $k$ ящиков пусты, и раскладываем $n$ шариков по остальным $N - k$ так, чтобы каждый был непуст: $\tilde p_k = C_N^k\,C_{n-1}^{N-k-1}/C_{n+N-1}^n$.

Теорема 6. Распределение вероятностей $\tilde p_k$, заданное формулой (8), сходится к закону Пуассона, если $n, N \to \infty$ так, что $N^2/n \to \lambda > 0$.

В частности, чтобы при $\lambda = 1$ для достаточно большого $N$ с вероятностью $\tilde p_0 \approx 1/e \approx 0{,}368$ не осталось ни одного пустого ящика, потребуется случайно бросить $N^2$ неразличимых шариков. Это отличается по порядку от величины $N\ln N$, которая (согласно теореме 5) понадобится в случае различимых шариков.

Смысл по-пацански: различимые пацаны рассаживаются по лавкам «каждый сам по себе» — и лавки быстро заполняются. Неразличимые пацаны в среднем кучкуются — равновероятны все «картины рассадки», а среди них куда больше таких, где кто-то сидит толпой, а лавки пустуют.

Пощупай руками

Режим «Пустые ящики»: столбики — точные вероятности и опыт, линия — пуассоновский предел. Поставь $N = 10$ и $n = 23 \approx N\ln N$: у различимых шансы «ни одного пустого» около 0,35, у неразличимых — меньше 0,02. Подними $n$ до 100 ($= N^2$): у неразличимых — около 0,41, у различимых — почти 1.

Режим «Совпадения»: число совпадений при случайной тасовке колоды против Пуассона с $\lambda = 1$.

Посчитаем «ни одного пустого ящика» по точным формулам:

Проверь себя