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.)
Jaka jest oczekiwana głębokość tego drzewa?
pr.probability
zhxchen17
źródło
źródło
Odpowiedzi:
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 ) ( 1n d 0 d (a1,a2,...,ad) 1(1a1)(1a2)⋯(1ad)×1n (1+11n 1(1+12+13+⋯1n−1)d Hn-1n-11+11n ( d! )H.ren - 1 H.n - 1 n - 1 Hn-1≈log(n-1)+γdn→∞nd+11 + 12)+ . . . + 1n - 1 . . Dla stałych i prawdopodobieństwo, że węzeł jest na głębokości wynosi co najwyżejH.n - 1≈ log( n - 1 ) + γ re n → ∞ n re+ 1
Przez przybliżenie Stirlinga możemy to oszacować jako
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.re e logn re
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
źródło
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 .di i∈{0,1,…,n−1} ϕi=∑ij=0edj.
lemat 1. Oczekiwana maksymalna głębokość, wynosi co najwyżej eE[maxidi] .eHn−1
Dowód. Maksymalna głębokość wynosi co najwyżej . Na koniec pokazujemy E [ ln ϕ n - 1 ] ≤ elnϕn−1 .E[lnϕn−1]≤eHn−1
Dla dowolnego , uzależnienie od ϕ i - 1 , przez sprawdzenie ϕ i , E [ ϕ ii≥1 ϕi−1 ϕi
Z indukcji wynika, że
Zatem przez wklęsłość logarytmu
Oto granica ogona:
lemat 2. Napraw dowolne . Następnie Pr [ max i d i ] ≥ ec≥0 wynosi co najwyżej exp ( - c ) .Pr[maxidi]≥eHn−1+c exp(−c)
Dowód. Po sprawdzeniu i związaniu z Markovem prawdopodobieństwo to wynosi najwyżej Pr [ ϕ n - 1 ≥ exp ( eϕ
Z dowodu Lemat 1,E[ϕn-1]≤exp(e
Jeśli chodzi o dolną granicę, myślę, że dolna granica następuje dość łatwo, biorąc pod uwagę max i d i ≥ ln ϕ t - ln n . Ale...(e−1)Hn−O(1) maxidi≥lnϕt−lnn [EDYCJA: przemówił zbyt wcześnie]Nie wydaje się tak łatwo pokazać ciasną dolną granicę ...(1−o(1))eHn
źródło
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)=Πb∈B(b−1)!n! B
Następnie szukaną ilość podaje:h(n)
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ę:
źródło