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

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

Определение

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

$\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)$

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

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

$\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)$

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

Виды схем

Каноническая схема размещения

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

$\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)$

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

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

Классическая схема размещения

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

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

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

Применение

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

См. также

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