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

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

Определение

Пусть неотрицательные целочисленные случайные величины (с.в.) ${\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\}(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 _{j_1+\dots +j_N=n}{p}_{j_1}\dots p_{j_N}},(2)$

где $p_k=\mathbb{P}\{{\xi }_1=k\},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 _{j_1+\dots +j_N=n}{b}_{j_1}\dots b_{j_N}},(3)$

где $b_0,b_1,\dots$ — последовательность неотрицательных чисел такая, что $b_0>0$, радиус сходимости ряда $B(x)=\sum _{k=0}^{\mathrm{\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) является удобным средством изучения таких случайных объектов, как Шаблон:Нп3, случайные подстановки, рекурсивные леса и т. д.

См. также

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