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

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

Определение

Пусть неотрицательные целочисленные случайные величины (с.в.) $\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$

Виды схем

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

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

$\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_kx^k$ равен 1, максимальный шаг носителя последовательности $b_0,b_1,\dots$ равен 1.

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

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

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

$\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) является удобным средством изучения таких случайных объектов, как леса Гальтона-Ватсона,^[5] случайные подстановки,^[3] рекурсивные леса^[6] и т. д.

См. также

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

Литература

1. ↑ Колчин В. Ф. Случайные отображения. — М.: Наука, 1984.
2. ↑ ^{1 2} Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. — М.: Наука, 1976.
3. ↑ ^{1 2} Колчин В. Ф. Случайные графы. — М.: Физматлит, 2000.
4. ↑ Казимиров Н. И. Леса Гальтона-Ватсона и случайные подстановки. — Дис. на соискание уч. степ. канд. ф.-м.н. — Петрозаводск, 2003. — 127 с.
5. ↑ Pavlov Yu. L. Random Forests. — Utrecht, VSP. — 2000.
6. ↑ Павлов Ю. Л., Лосева Е. А. Предельные распределения максимального объема дерева в случайном рекурсивном лесе // Дискретная математика. — 2002. — Т. 14. — № 1. — С. 60-74.