Berapa kedalaman yang diharapkan dari pohon yang dihasilkan secara acak?

19

Saya sudah memikirkan masalah ini sejak lama, tetapi tidak tahu.

Algoritma pembangkitnya adalah sebagai berikut. Kami berasumsi ada $n$ diskrit bernomor dari $0$ hingga $n - 1$ . Kemudian untuk setiap $i$ di $\{1, \dotsc, n - 1\}$ , kita menjadikan orang tua simpul ke- $i$ di pohon menjadi simpul acak di $\{0, \dotsc, i - 1\}$ . Iterasi melalui masing-masing $i$ agar hasilnya adalah pohon acak dengan simpul akar $0$ . (Mungkin ini tidak cukup acak tetapi ini tidak masalah.)

Berapa kedalaman yang diharapkan dari pohon ini?

pr.probability zhxchen17
sumber

Saya berasumsi

v_{0}

$v_0$ adalah root dan Anda bermaksud mengatakan: "Lalu untuk setiap

i

$i$ di

[1, n)

$[1,n)$ , kami membuat induk simpul ke-

i

$i$ ...". Baik?

Tanpa judul

Apa yang sudah kamu coba? Sudahkah Anda mencoba menulis relasi perulangan, katakan untuk

d (i)

$d(i)$ yang merupakan kedalaman yang diharapkan dari simpul

i

$i$ ?

DW

3

Objek-objek ini dikenal dengan nama "pohon rekursif acak".

James Martin

15

Saya pikir ada hasil konsentrasi tentang $e \log n$ , tetapi saya belum mengisi detailnya.

Kita bisa mendapatkan batas atas untuk probabilitas bahwa simpul memiliki leluhur tidak termasuk . Untuk setiap kemungkinan rantai lengkap nenek moyang nol , probabilitas rantai yang $n$ $d$ $0$ $d$ $(a_1,a_2,...,a_d)$ . Ini sesuai dengan $(\frac{1}{a_1})(\frac{1}{a_2})\cdots (\frac{1}{a_d}) \times \frac{1}{n}$ kali jangka waktu $\frac{1}{n}$ tempat ketentuan dipesan. Jadi, batas atas untuk probabilitas ini adalah $(1+\frac{1}{2} + \frac{1}{3}+ \cdots \frac{1}{n-1})^d$ di manaadalahst harmonik nomor $\frac{1}{n (d!)} H_{n-1}^d$ $H_{n-1}$ $n-1$ . . Untuk fixdan, probabilitas simpulpada kedalamanadalah paling banyak $1 + \frac{1}{2} + ... + \frac{1}{n-1}$ $H_{n-1} \approx \log (n-1) + \gamma$ $d$ $n \to \infty$ $n$ $d+1$

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

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

Dengan perkiraan Stirling, kita dapat memperkirakan ini sebagai

\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.$

Untuk besar , apa pun yang jauh lebih besar dari , basis eksponensial kecil, jadi ikatan ini kecil, dan kita dapat menggunakan ikatan terikat untuk mengatakan bahwa probabilitas bahwa setidaknya ada satu simpul dengan leluhur bukan nol adalah kecil. $d$ $e \log n$ $d$

Lihat

Luc Devroye, Omar Fawzi, Nicolas Fraiman. "Kedalaman sifat lampiran pohon rekursif acak skala."

B. Pittel. Perhatikan ketinggian pohon rekursif acak dan pohon pencarian m-ary acak. Struktur dan Algoritma Acak, 5: 337–348, 1994.

Mantan klaim yang terakhir menunjukkan kedalaman maksimum adalah dengan probabilitas tinggi, dan menawarkan bukti lain. $(e+o(1))\log n$

Douglas Zare
sumber

2

Sangat bagus. Untuk memperjelas bagi pembaca lainnya: karena Anda tidak bisa mengulangi

, istilah

a_{i}

$a_i$

hanyalah batas atas.

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

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

Peter Shor

3

Pertanyaan ini dijawab beberapa tahun yang lalu, tetapi, hanya untuk bersenang-senang, ini adalah bukti sederhana dari batas atas. Kami memberi batasan pada harapan, lalu ekor terikat.

Tentukan rv menjadi kedalaman simpul . Mendefinisikan $d_i$ $i\in\{0,1,\ldots,n-1\}$ $\phi_i = \sum_{j=0}^i e^{d_j}.$

lemma 1. Kedalaman maksimum yang diharapkan, paling banyak $E[\max_i d_i]$ . $e\, H_{n-1}$

Bukti. Kedalaman maksimum paling banyak pada . Untuk menyelesaikannya kami menunjukkan $\ln \phi_{n-1}$ . $E[\ln \phi_{n-1}] \le e\, H_{n-1}$

Untuk setiap , pengkondisian pada , dengan memeriksa , $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}.$

Dengan induksi maka

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

Jadi, dengan konkavitas logaritma,

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$

Inilah ekor yang diikat:

lemma 2. Perbaiki . Kemudian $c \ge 0$ $\Pr[\max_i d_i] \ge e\,H_{n-1} + c$ $\exp(-c)$

$\phi$

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

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

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

◻

$~~~\Box$

~~$(e-1)H_n - O(1)$ $\max_i d_i \ge \ln\phi_t - \ln n$~~ [EDIT: bicara terlalu cepat]

$(1-o(1))e H_n$

Neal Young
sumber

2

Saya sebenarnya telah memikirkan pertanyaan yang sama (walaupun dalam formulasi yang sama sekali berbeda) beberapa bulan yang lalu, serta beberapa varian yang dekat.

Saya tidak punya solusi bentuk tertutup (/ asimptotik) untuk itu, tetapi Anda mungkin menganggap ini berguna (apakah Anda hanya mencari batas atas?).

$v_0$

Ini juga memberi kami formula rekursi untuk pertanyaan Anda.

$h(n)$ $n$

$P_n(B)=\frac{\Pi_{b\in B} (b-1)!}{n!}$ $B$

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

Jika Anda ingin membuat kode rekursi ini, pastikan Anda menggunakan yang berikut ini agar tidak masuk ke loop tak terbatas:

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$

BPR
sumber

1

Terima kasih atas idenya! Sebenarnya saya menulis program monte-carlo pertama kali ketika saya bertemu dengan masalah ini, tetapi yang mengejutkan saya hasil yang akurat sangat sulit didapat.

zhxchen17

Berapa kedalaman yang diharapkan dari pohon yang dihasilkan secara acak?

Jawaban: