Узагальнена схема розміщення

Узагальнена схема розміщення [1] [2] [3] частинок по комірках визначається наступним чином.


1. Визначення

Нехай невід'ємні цілочисельні випадкові величини (с.в.) \ Eta_1, \ dots, \ eta_N , Сума яких дорівнює n , Пов'язані з невід'ємними цілочисельними незалежними с.в. \ Xi_1, \ dots, \ xi_N наступним співвідношенням:

для всіх цілих невід'ємних 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


2. Види схем

2.1. Канонічна схема розміщення

Найбільш поширеним випадком ОСР є канонічна схема розміщення, [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.2. Класична схема розміщення

Класична схема розміщення (схема рівноймовірно розміщення частинок по комірках), [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)).

3. Застосування

Схеми розміщення виду (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.