Jaka jest oczekiwana głębokość losowo wygenerowanego drzewa?

19

Dawno temu myślałem o tym problemie, ale nie mam o nim pojęcia.

Algorytm generujący jest następujący. Zakładamy, że istnieje dyskretnych węzłów ponumerowanych od do . Następnie dla każdego w , nadrzędny ty węzeł w drzewie będzie losowym węzłem w . Iteruj po każdym , aby wynik był losowym drzewem z węzłem głównym . (Być może nie jest to wystarczająco losowe, ale to nie ma znaczenia.)n0n1i{1,,n1}i{0,,i1}i0

Jaka jest oczekiwana głębokość tego drzewa?

zhxchen17
źródło
Zakładam, że jest rootem i chciałeś powiedzieć: „Następnie dla każdego w tworzymy element nadrzędny węzła ...”. Dobrze? v0i[1,n)i
Bez tytułu
Czego próbowałeś? Czy próbowałeś napisać relację powtarzalności, powiedzmy dla jaka jest oczekiwana głębokość węzła ? d(i)i
DW
3
Obiekty te są znane pod nazwą „losowe drzewo rekurencyjne”.
James Martin

Odpowiedzi:

15

Myślę, że istnieje wynik koncentracji o , ale nie podałem jeszcze szczegółów.elogn

Możemy uzyskać górną granicę prawdopodobieństwa, że ​​węzeł ma przodków, w tym . Dla każdego możliwego pełnego łańcucha niezerowych przodków prawdopodobieństwo tego łańcucha wynosi . Odpowiada to razy wyrażeniu gdzie warunki są uporządkowane. Zatem górną granicą tego prawdopodobieństwa jest gdzie jest pierwszą liczbą harmonicznychd 0 d ( 1 , 2 , . . . , d ) ( 1nd0d(a1,a2,...,ad) 1(1a1)(1a2)(1ad)×1n (1+11n1(1+12)+13)+1n-1)re Hn-1n-11+11n(re!)H.n-1reH.n-1n-1 Hn-1log(n-1)+γdnnd+11+12)+...+1n-1 . . Dla stałych i prawdopodobieństwo, że węzeł jest na głębokości wynosi co najwyżejH.n-1log(n-1)+γrennre+1

(logn)ren(re!)(1+o(1))

Przez przybliżenie Stirlinga możemy to oszacować jako

1n2πd(elognd)d.

W przypadku dużego , cokolwiek znacznie większego niż , podstawa wykładnicza jest mała, więc to ograniczenie jest małe, i możemy użyć powiązania unii, aby powiedzieć, że prawdopodobieństwo, że istnieje co najmniej jeden węzeł z niezerowymi przodkami jest mały.remilognre


Widzieć

Luc Devroye, Omar Fawzi, Nicolas Fraiman. „Właściwości głębokości losowych rekurencyjnych drzew skalowanych załączników”.

B. Pittel. Uwaga na wysokości losowych drzew rekurencyjnych i losowych drzew wyszukiwania m-ary. Struktury losowe i algorytmy, 5: 337–348, 1994.

Pierwsze z nich twierdzi, że drugie wykazało, że maksymalna głębokość wynosi z dużym prawdopodobieństwem, i oferuje kolejny dowód.(e+o(1))logn

Douglas Zare
źródło
2
Bardzo dobrze. W celu wyjaśnienia dla innych czytelników: ponieważ nie można powtórzyć , termin ( 1 + 1aijest tylko górną granicą. (1+12++1n1)d
Peter Shor,
3

Na to pytanie udzielono odpowiedzi kilka lat temu, ale dla zabawy, oto prosty dowód górnej granicy. Ograniczamy oczekiwania, a następnie ograniczamy ogonem.

Zdefiniuj rv jako głębokość węzła i { 0 , 1 , , n - 1 } . Zdefiniuj ϕ i = i j = 0 e d j .dii{0,1,,n1}ϕi=j=0iedj.

lemat 1. Oczekiwana maksymalna głębokość, wynosi co najwyżej eE[maxidi] .eHn1

Dowód. Maksymalna głębokość wynosi co najwyżej . Na koniec pokazujemy E [ ln ϕ n - 1 ] elnϕn1 .E[lnϕn1]eHn1

Dla dowolnego , uzależnienie od ϕ i - 1 , przez sprawdzenie ϕ i , E [ ϕ ii1ϕi1ϕi

E[ϕi|ϕi1]=ϕi1+E[edi]=ϕi1+eiϕi1=(1+ei)ϕi1.

Z indukcji wynika, że

E[ϕn1]=i=1n1(1+ei)<i=1n1exp(ei)=exp(eHn1).

Zatem przez wklęsłość logarytmu

E[lnϕn1]lnE[ϕn1]<lnexp(eHn1)=eHn1.       

Oto granica ogona:

lemat 2. Napraw dowolne . Następnie Pr [ max i d i ] ec0 wynosi co najwyżej exp ( - c ) .Pr[maxidi]eHn1+cexp(c)

Dowód. Po sprawdzeniu i związaniu z Markovem prawdopodobieństwo to wynosi najwyżej Pr [ ϕ n - 1exp ( eϕ Z dowodu Lemat 1,E[ϕn-1]exp(e

Pr[ϕn1exp(eHn1+c)]E[ϕn1]exp(eHn1+c).
. Zastąpienie tego po prawej stronie powyżej stanowi dowód. E[ϕn1]exp(eHn1)   

Jeśli chodzi o dolną granicę, myślę, że dolna granica następuje dość łatwo, biorąc pod uwagę max i d iln ϕ t - ln n . Ale...(e1)HnO(1)maxidilnϕtlnn [EDYCJA: przemówił zbyt wcześnie]

Nie wydaje się tak łatwo pokazać ciasną dolną granicę ...(1o(1))eHn

Neal Young
źródło
2

Kilka miesięcy temu zastanawiałem się nad tym samym pytaniem (choć w zupełnie innym sformułowaniu), a także nad kilkoma bliskimi wariantami.

Nie mam dla niego rozwiązania w formie zamkniętej (/ asymptotycznej), ale ten widok może ci się przydać (może szukasz tylko górnej granicy?).

Proces, który tu opisujesz, jest uogólnieniem procesu restauracji chińskiej , w którym każdy „stół” jest poddrzewem, którego rodzicem root jest .v0

To daje nam również formułę rekurencyjną dla twojego pytania.

Oznacz przez spodziewane wysokości takiego procesu drzewa z n węzłami.h(n)n

Oznaczmy przez (prawdopodobieństwo rozkładuBwęzłów na poddrzewa).Pn(B)=ΠbB(b1)!n!B

Następnie szukaną ilość podaje:h(n)

h(n)=BBnPn(B)maxbBh(b)

Jeśli chcesz zakodować tę rekurencję, upewnij się, że używasz następujących elementów, aby nie przechodziły w nieskończoną pętlę:

h(n)=BBn{{n}}Pn(B)maxbBh(b)11n!

Bnnh(1)=1


h(n)h

RB
źródło
1
Dzięki za pomysł! Właściwie to pierwszy raz napisałem program monte-carlo, gdy spotkałem się z tym problemem, ale ku mojemu zdziwieniu dokładny wynik jest tak trudny do uzyskania.
zhxchen17