Náhodný rekurzivní strom - Random recursive tree

v teorie pravděpodobnosti, a náhodný rekurzivní strom je zakořeněný strom zvolen rovnoměrně náhodně z rekurzivní stromy s daným počtem vrcholů.

Definice a generace

V rekurzivním stromu s ${ displaystyle n}$ vrcholy, vrcholy jsou označeny čísly od ${ displaystyle 1}$ na ${ displaystyle n}$a štítky se musí zmenšovat podél jakékoli cesty ke kořenu stromu. Tyto stromy jsou neuspořádané, v tom smyslu, že neexistuje žádné rozlišené řazení dětí každého vrcholu. V náhodném rekurzivním stromu jsou všechny takové stromy stejně pravděpodobné.

Alternativně lze náhodný rekurzivní strom generovat spuštěním z jediného vrcholu označeného kořenem stromu ${ displaystyle 1}$a poté pro každý následující štítek z ${ displaystyle 2}$ na ${ displaystyle n}$ výběr náhodného vrcholu s menším štítkem, aby byl jeho rodičem. Pokud je každá z možností jednotná a nezávislá na ostatních možnostech, výsledný strom bude náhodný rekurzivní strom.

Vlastnosti

S největší pravděpodobností je nejdelší cesta od kořene k listu an ${ displaystyle n}$-vertexový náhodný rekurzivní strom má délku ${ displaystyle e log n}$.^[1]Maximální počet dětí kteréhokoli vrcholu, tj. Stupně, ve stromu je s vysokou pravděpodobností ${ displaystyle (1 pm o (1)) log _ {2} n}$.^[2]The očekávaný vzdálenost ${ displaystyle k}$th vrchol od kořene je ${ displaystyle k}$th harmonické číslo, z čehož vyplývá linearita očekávání že součet všech délek cesty od kořene k vrcholu je s vysokou pravděpodobností, ${ displaystyle (1 pm o (1)) n log n}$.^[3]Očekávaný počet listů stromu je ${ displaystyle n / 2}$ s rozptyl ${ displaystyle n / 12}$, takže s velkou pravděpodobností je počet listů ${ displaystyle (1 pm o (1)) n / 2}$.^[4]

Aplikace

Zhang (2015) uvádí několik aplikací náhodných rekurzivních stromů při modelování jevů včetně šíření nemocí, pyramidové hry, vývoj jazyků a růst počítačových sítí.^[4]

Reference