Обобщённая схема размещения

Обобщённая схема размещения^[1][2][3] частиц по ячейкам определяется следующим образом.

Пусть неотрицательные целочисленные случайные величины (с.в.) ${\displaystyle \eta _{1},\dots ,\eta _{N}}$, сумма которых равна ${\displaystyle n}$, связаны с неотрицательными целочисленными независимыми с.в. ${\displaystyle \xi _{1},\dots ,\xi _{N}}$ следующим соотношением:

${\displaystyle \mathbb {P} \{\eta _{1}=k_{1},\dots ,\eta _{N}=k_{N}\}=\mathbb {P} \{\xi _{1}=k_{1},\dots ,\xi _{N}=k_{N}\;|\;\xi _{1}+\dots +\xi _{N}=n\}\qquad (1)}$

для всех целых неотрицательных ${\displaystyle k_{1},\dots ,k_{N}}$, сумма которых равна ${\displaystyle n}$. Тогда говорят, что с.в. ${\displaystyle \eta _{1},\dots ,\eta _{N},\xi _{1},\dots ,\xi _{N}}$ образуют обобщённую схему размещения (ОСР).

Если ОСР симметрична, то есть все с.в. ${\displaystyle \xi _{k}}$ имеют одинаковое распределение, то вероятность, стоящую справа в (1), можно записать в виде:

${\displaystyle \mathbb {P} \{\eta _{1}=k_{1},\dots ,\eta _{N}=k_{N}\}={\frac {p_{k_{1}}\dots p_{k_{N}}}{\sum \limits _{j_{1}+\dots +j_{N}=n}p_{j_{1}}\dots p_{j_{N}}}},\qquad (2)}$

где ${\displaystyle p_{k}=\mathbb {P} \{\xi _{1}=k\},\quad k=0,1,2\dots }$

Наиболее распространенным случаем ОСР является каноническая схема размещения,^[4] для которой

${\displaystyle \mathbb {P} \{\eta _{1}=k_{1},\dots ,\eta _{N}=k_{N}\}={\frac {b_{k_{1}}\dots b_{k_{N}}}{\sum \limits _{j_{1}+\dots +j_{N}=n}b_{j_{1}}\dots b_{j_{N}}}},\qquad (3)}$

где ${\displaystyle b_{0},b_{1},\dots }$ — последовательность неотрицательных чисел такая, что ${\displaystyle b_{0}>0}$, радиус сходимости ряда ${\displaystyle B(x)=\sum \limits _{k=0}^{\infty }b_{k}x^{k}}$ равен 1, максимальный шаг носителя последовательности ${\displaystyle b_{0},b_{1},\dots }$ равен 1.

К канонической схеме путём линейного преобразования с.в. ${\displaystyle \eta _{1},\dots ,\eta _{N}}$ сводятся все схемы вида (3) без указанных выше ограничений на последовательность ${\displaystyle \{b_{k}\}}$ с одним только условием — конечного и ненулевого радиуса сходимости ${\displaystyle B(x)}$. Схема (3), очевидно, является частным случаем (2) и, следовательно, (1).

Классическая схема размещения (схема равновероятного размещения частиц по ячейкам),^[2] в которой

${\displaystyle \mathbb {P} \{\eta _{1}=k_{1},\dots ,\eta _{N}=k_{N}\}={\frac {n!}{k_{1}!\dots \;k_{N}!N^{n}}},}$

не сводится к канонической, так как радиус сходимости ${\displaystyle B(x)=e^{x}}$ равен бесконечности. Но она является частным случаем (2) (и, следовательно, (1)).

Схемы размещения вида (1), (2) и (3) является удобным средством изучения таких случайных объектов, как леса Гальтона-Ватсона^[англ.],^[5] случайные подстановки,^[3] рекурсивные леса^[6] и т. д.

• Гигантская компонента