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

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

ОпределениеПравить

Пусть неотрицательные целочисленные случайные величины (с.в.) ${\mathrm{\eta <!--\; \eta \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\eta <!--\; \eta \; -->}}_N$$\eta_1,\dots,\eta_N$ , сумма которых равна $n$$n$ , связаны с неотрицательными целочисленными независимыми с.в. ${\mathrm{\xi <!--\; \xi \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\xi <!--\; \xi \; -->}}_N$$\xi_1,\dots,\xi_N$  следующим соотношением:

$\mathbb{P}\{{\mathrm{\eta <!--\; \eta \; -->}}_1=k_1,\dots <!--\; \dots \; -->,{\mathrm{\eta <!--\; \eta \; -->}}_N=k_N\}=\mathbb{P}\{{\mathrm{\xi <!--\; \xi \; -->}}_1=k_1,\dots <!--\; \dots \; -->,{\mathrm{\xi <!--\; \xi \; -->}}_N=k_N|{\mathrm{\xi <!--\; \xi \; -->}}_1+\cdots <!--\; \cdots \; -->+{\mathrm{\xi <!--\; \xi \; -->}}_N=n\}(1)$$\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 <!--\; \dots \; -->,k_N$$k_1,\dots,k_N$ , сумма которых равна $n$$n$ . Тогда говорят, что с.в. ${\mathrm{\eta <!--\; \eta \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\eta <!--\; \eta \; -->}}_N,{\mathrm{\xi <!--\; \xi \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\xi <!--\; \xi \; -->}}_N$$\eta_1,\dots,\eta_N,\xi_1,\dots,\xi_N$  образуют обобщённую схему размещения (ОСР).

Если ОСР симметрична, то есть все с.в. ${\mathrm{\xi <!--\; \xi \; -->}}_k$$\xi_k$  имеют одинаковое распределение, то вероятность, стоящую справа в (1), можно записать в виде:

$\mathbb{P}\{{\mathrm{\eta <!--\; \eta \; -->}}_1=k_1,\dots <!--\; \dots \; -->,{\mathrm{\eta <!--\; \eta \; -->}}_N=k_N\}=\frac{p_{k_1}\dots <!--\; \dots \; -->p_{k_N}}{\underset{j_1+\cdots <!--\; \cdots \; -->+j_N=n}{\sum <!--\; \sum \; -->}{p}_{j_1}\dots <!--\; \dots \; -->p_{j_N}},(2)$$\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}\{{\mathrm{\xi <!--\; \xi \; -->}}_1=k\},k=0,1,2\dots <!--\; \dots \; -->$$p_k=\mathbb{P}\{\xi_1=k\},\quad k=0,1,2\dots$ 

Виды схемПравить

Каноническая схема размещенияПравить

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

$\mathbb{P}\{{\mathrm{\eta <!--\; \eta \; -->}}_1=k_1,\dots <!--\; \dots \; -->,{\mathrm{\eta <!--\; \eta \; -->}}_N=k_N\}=\frac{b_{k_1}\dots <!--\; \dots \; -->b_{k_N}}{\underset{j_1+\cdots <!--\; \cdots \; -->+j_N=n}{\sum <!--\; \sum \; -->}{b}_{j_1}\dots <!--\; \dots \; -->b_{j_N}},(3)$$\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 <!--\; \dots \; -->$$b_0,b_1,\dots$  — последовательность неотрицательных чисел такая, что $b_0>0$$b_0>0$ , радиус сходимости ряда $B(x)=\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{b}_k{x}^k$$B(x)=\sum\limits_{k=0}^\infty b_kx^k$  равен 1, максимальный шаг носителя последовательности $b_0,b_1,\dots <!--\; \dots \; -->$$b_0,b_1,\dots$  равен 1.

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

Классическая схема размещенияПравить

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

$\mathbb{P}\{{\mathrm{\eta <!--\; \eta \; -->}}_1=k_1,\dots <!--\; \dots \; -->,{\mathrm{\eta <!--\; \eta \; -->}}_N=k_N\}=\frac{n!}{k_1!\dots <!--\; \dots \; -->k_N!N^n},$$\mathbb{P}\{\eta_1=k_1,\dots,\eta_N=k_N\}=\frac{n!}{k_1!\dots\;k_N!N^n},$ 

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

ПрименениеПравить

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

См. такжеПравить

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