Obří součástka

Obří složka je efekt, který se vyskytuje ve schématech náhodného umístění částic do buněk s neomezeným nárůstem počtu částic. Výsledkem je, že téměř všechny částice (v procentech) jsou shromážděny v jedné buňce.

Uvažujme zobecněné rozložení n částic v N buňkách:

\eta _{1}+\tečky +\eta _{N}=n,\qquad (1)

Označme variační řadou náhodných veličin . Jedná se tedy o maximální součást obvodu (nebo maximální počet částic v jedné buňce) a je další největší složkou. ${\displaystyle \eta _{(1)}\leq \dots \leq \eta _{(N)))$ $\eta_1,\tečky,\eta_N$ ${\displaystyle \;\eta _{(N)))$ ${\displaystyle \;\eta _{(N-1)))$

Jestliže pro má náhodná veličina limitní rozdělení, které se neakumuluje na nule, ale degeneruje na nulu, pak říkáme, že se v alokačním schématu objevuje obří složka (1) . [jeden] $n\to\infty$ $\;\eta _{(N)}/n$ $\;\eta _{(N-1)}/n$

Je například známo, že v klasickém alokačním schématu není žádná obří složka, ale v logaritmickém schématu popisujícím délky cyklů při náhodné substituci se obří složka objeví, když , tedy za podmínky, že parametr roste pomaleji než . [2] $n\to\infty$ $\ln(n)/N\to \infty$ $N$ $\ln(n)$

Literatura

↑ Kolchin V.F. O existenci obří komponenty v rozložení částic // Review of Applied and Industrial Mathematics. - 2000. - T. 7 , č. 1 . - S. 112-113 .
↑ Kazimirov N. I. Galton-Watsonovy lesy a náhodné substituce . - Dis. na výuční list krok. cand. f.-m.s. - Petrozavodsk, 2003. - 127 s.