Losowe drzewo rekurencyjne

W teorii prawdopodobieństwa losowe drzewo rekurencyjne to drzewo ukorzenione wybrane równomiernie losowo z drzew rekurencyjnych o danej liczbie wierzchołków.

Definicja i generacja

W drzewie rekurencyjnym z wierzchołkami $wierzchołki$ oznaczone liczbami od do $drzewa$$a$ etykiety muszą zmniejszać się wzdłuż dowolnej ścieżki do korzenia Drzewa te są nieuporządkowane w tym sensie, że nie ma wyróżnionej kolejności dzieci każdego wierzchołka. W losowym drzewie rekurencyjnym wszystkie takie drzewa są jednakowo prawdopodobne.

Alternatywnie, losowe drzewo rekurencyjne można wygenerować, zaczynając od pojedynczego wierzchołka, korzenia drzewa, oznaczonego , a następnie dla każdej kolejnej etykiety od $displaystyle$$2}$ do ${\ displaystyle n$ wybranie losowego wierzchołka z mniejszą etykietą jako jego rodzica. Jeśli każdy z wyborów jest jednolity i niezależny od pozostałych wyborów, otrzymane drzewo będzie losowym drzewem rekurencyjnym.

Nieruchomości

Z dużym prawdopodobieństwem najdłuższa ścieżka od korzenia do liścia - wierzchołka $drzewa$ rekurencyjnego ma długość ${\ displaystyle e \ log n}$ . Maksymalna liczba dzieci dowolnego wierzchołka, tj. Stopień, w drzewie jest z dużym prawdopodobieństwem ${\ Displaystyle (1 \ pm o (1)} \ log _ { 2}n}$ . Oczekiwana odległość k $displaystyle k}$ \ $wierzchołek$ od korzenia to th liczba harmoniczna , z której wynika liniowość oczekiwań , suma wszystkich długości ścieżek od korzenia do wierzchołka wynosi z dużym prawdopodobieństwem ${\ Displaystyle (1 \ pm o (1)) n \ log n}$ . Oczekiwana liczba liści drzewa to ${\ displaystyle n/2}$ z wariancją ${\ Displaystyle n/12}$ , więc z dużym prawdopodobieństwem liczba liści wynosi ${\ Displaystyle (1 \ pm o (1)) n/2}$ .

Aplikacje

Zhang (2015) wymienia kilka zastosowań losowych drzew rekurencyjnych w modelowaniu zjawisk, w tym rozprzestrzeniania się chorób, schematów piramidowych , ewolucji języków i rozwoju sieci komputerowych.