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.) $n$ $0$ $n - 1$ $i$ $\{1, \dotsc, n - 1\}$ $i$ $\{0, \dotsc, i - 1\}$ $i$ $0$

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

pr.probability

— 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?

v_{0}

$v_0$

i

$i$

[1, n)

$[1,n)$

i

$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)

$d(i)$

i

$i$

— DW

3

Obiekty te są znane pod nazwą „losowe drzewo rekurencyjne”.

— James Martin

15

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

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ą harmonicznych $n$ $d$ $0$ $d$ $(a_1,a_2,...,a_d)$ $(\frac{1}{a_1})(\frac{1}{a_2})\cdots (\frac{1}{a_d}) \times \frac{1}{n}$ $\frac{1}{n}$ $(1+\frac{1}{2} + \frac{1}{3}+ \cdots \frac{1}{n-1})^d$ $\frac{1}{n (d!)} H_{n-1}^d$ $H_{n-1}$ $n-1$ $1 + \frac{1}{2} + ... + \frac{1}{n-1}$ . . Dla stałych i prawdopodobieństwo, że węzeł jest na głębokości wynosi co najwyżej $H_{n-1} \approx \log (n-1) + \gamma$ $d$ $n \to \infty$ $n$ $d+1$

\frac{(\log n)^{re}}{n (re!)} (1 + o (1))

$\frac{(\log n)^d}{n (d!)} \left(1+o(1)\right)$

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

\frac{1}{n \sqrt{2 π d}} {(\frac{e \log n}{d})}^{d} .

$\frac{1}{n\sqrt{2\pi d}} \left( \frac{e \log n}{d} \right)^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. $d$ $e \log n$ $d$

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))\log n$

— Douglas Zare
źródło

2

Bardzo dobrze. W celu wyjaśnienia dla innych czytelników: ponieważ nie można powtórzyć

, termin

a_{i}

$a_i$

jest tylko górną granicą.

(1 + \frac{1}{2} + \dots + \frac{1}{n - 1})^{d}

$(1 + \frac{1}{2} + \ldots + \frac{1}{n-1})^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 . Zdefiniuj $d_i$ $i\in\{0,1,\ldots,n-1\}$ $\phi_i = \sum_{j=0}^i e^{d_j}.$

lemat 1. Oczekiwana maksymalna głębokość, wynosi co najwyżej $E[\max_i d_i]$ . $e\, H_{n-1}$

Dowód. Maksymalna głębokość wynosi co najwyżej . Na koniec pokazujemy $\ln \phi_{n-1}$ . $E[\ln \phi_{n-1}] \le e\, H_{n-1}$

Dla dowolnego , uzależnienie od , przez sprawdzenie , $i\ge 1$ $\phi_{i-1}$ $\phi_i$

E [ϕ_{i} | ϕ_{i - 1}] = ϕ_{i - 1} + E [e^{d_{i}}] = ϕ_{i - 1} + \frac{e}{i} ϕ_{i - 1} = (1 + \frac{e}{i}) ϕ_{i - 1} .

$\textstyle E[\phi_i\, |\, \phi_{i-1}] \,=\,\phi_{i-1} + E[e^{d_i}] \,=\, \phi_{i-1} + \frac{e}{i} \phi_{i-1} \,=\, (1+\frac{e}{i}) \phi_{i-1}.$

Z indukcji wynika, że

E [ϕ_{n - 1}] = \prod_{i = 1}^{n - 1} (1 + \frac{e}{i}) < \prod_{i = 1}^{n - 1} \exp (\frac{e}{i}) = \exp (e H_{n - 1}) .

$\textstyle E[\phi_{n-1}] \,=\, \prod_{i=1}^{n-1} (1+\frac{e}{i}) \,<\, \prod_{i=1}^{n-1} \exp(\frac{e}{i}) \,=\, \exp(e\, H_{n-1}).$

Zatem przez wklęsłość logarytmu

E [\ln ϕ_{n - 1}] \leq \ln E [ϕ_{n - 1}] < \ln \exp (e H_{n - 1}) = e H_{n - 1} . ◻

$E[\ln \phi_{n-1}] \,\le\, \ln E[\phi_{n-1}] \,<\, \ln \exp(e\, H_{n-1}) \,=\, e\, H_{n-1}.~~~~~~~\Box$

Oto granica ogona:

lemat 2. Napraw dowolne . Następnie $c \ge 0$ wynosi co najwyżej . $\Pr[\max_i d_i] \ge e\,H_{n-1} + c$ $\exp(-c)$

Dowód. Po sprawdzeniu i związaniu z Markovem prawdopodobieństwo to wynosi najwyżej $\phi$ Z dowodu Lemat 1,

Pr [ϕ_{n - 1} \geq \exp (e H_{n - 1} + c)] \leq \frac{E [ϕ_{n - 1}]}{\exp (e H_{n - 1} + c)} .

$\Pr[\phi_{n-1} \ge \exp(e\,H_{n-1} + c)] \,\le\,\frac{E[\phi_{n-1}]}{\exp(e\,H_{n-1} + c)}.$

. Zastąpienie tego po prawej stronie powyżej stanowi dowód.

E [ϕ_{n - 1}] \leq \exp (e H_{n - 1})

$E[\phi_{n-1}]\le \exp(e\,H_{n-1})$

◻

$~~~\Box$

~~Jeśli chodzi o dolną granicę, myślę, że dolna granica następuje dość łatwo, biorąc pod uwagę . Ale... $(e-1)H_n - O(1)$ $\max_i d_i \ge \ln\phi_t - \ln n$~~ [EDYCJA: przemówił zbyt wcześnie]

Nie wydaje się tak łatwo pokazać ciasną dolną granicę ... $(1-o(1))e H_n$

— 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 . $v_0$

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

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

Oznaczmy przez (prawdopodobieństwo rozkładuwęzłów na poddrzewa). $P_n(B)=\frac{\Pi_{b\in B} (b-1)!}{n!}$ $B$

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

h (n) = \sum_{B \in B_{n}} P_{n} (B) \cdot max_{b \in B} h (b)

$h(n)=\sum_{B\in \mathcal B_n}P_n(B)\cdot \max_{b\in B} h(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) = \frac{\sum_{B \in B_{n} ∖ {{n}}} P_{n} (B) \cdot max_{b \in B} h (b)}{1 - \frac{1}{n!}}

$h(n)=\frac{\sum_{B\in \mathcal B_n\setminus \{\{n\}\}}P_n(B)\cdot \max_{b\in B} h(b)}{1-\frac{1}{n!}}$

$\mathcal B_n$ $n$ $h(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