Qual é a profundidade esperada de uma árvore gerada aleatoriamente?

19

Eu pensei sobre esse problema há muito tempo, mas não tenho idéias.

O algoritmo de geração é o seguinte. Assumimos que existem nós distintos numerados de a . Então, para cada em , tornamos o pai do nó na árvore um nó aleatório em . Faça a iteração de cada para que o resultado seja uma árvore aleatória com o nó raiz . (Talvez isso não seja aleatório o suficiente, mas isso não importa.) $n$ $0$ $n - 1$ $i$ $\{1, \dotsc, n - 1\}$ $i$ $\{0, \dotsc, i - 1\}$ $i$ $0$

Qual é a profundidade esperada dessa árvore?

pr.probability zhxchen17
fonte

Presumo que seja root e você quis dizer: "Então, para cada em , criamos o pai do ésimo nó ...". Certo?

v_{0}

$v_0$

i

$i$

[1, n)

$[1,n)$

i

$i$

Sem título

O que você tentou? Você já tentou escrever uma relação de recorrência, digamos para qual é a profundidade esperada do nó ?

d (i)

$d(i)$

i

$i$

DW

3

Esses objetos são conhecidos sob o nome "árvore recursiva aleatória".

James Martin

15

Acho que há um resultado de concentração sobre , mas ainda não preenchi os detalhes. $e \log n$

Podemos obter um limite superior para a probabilidade de que node tem antepassados não incluindo . Para cada cadeia completa possível de ancestrais diferentes de zero , a probabilidade de que a cadeia é . Isso corresponde a vezes um termo de onde os termos são solicitados. Portanto, um limite superior para essa probabilidade é que é o ° número harmônico $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}$ . . Para fixo e , a probabilidade de o nó estar na profundidade é no máximo $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)$

Pela aproximação de Stirling, podemos estimar isso como

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

Para grande , qualquer coisa muito maior que , a base do exponencial é pequena, portanto esse limite é pequeno, e podemos usar a união vinculada para dizer que a probabilidade de existir pelo menos um nó com ancestrais diferentes de zero é pequeno. $d$ $e \log n$ $d$

Vejo

Luc Devroye, Omar Fawzi, Nicolas Fraiman. "Propriedades de profundidade de árvores recursivas aleatórias de anexo em escala."

B. Pittel. Observe as alturas das árvores recursivas aleatórias e das árvores de pesquisa aleatória. Random Structures and Algorithms, 5: 337–348, 1994.

O primeiro afirma que o último mostrou que a profundidade máxima é com alta probabilidade e oferece outra prova. $(e+o(1))\log n$

Douglas Zare
fonte

2

Muito agradável. Para esclarecer para outros leitores: como você não pode repetir um , o termo é apenas um limite superior .

a_{i}

$a_i$

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

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

quer

3

Esta pergunta foi respondida há vários anos, mas, apenas por diversão, aqui está uma prova simples do limite superior. Damos um limite à expectativa, depois um limite à cauda.

Defina rv como a profundidade do nó . Defina $d_i$ $i\in\{0,1,\ldots,n-1\}$ $\phi_i = \sum_{j=0}^i e^{d_j}.$

lema 1. A profundidade máxima esperada, é no máximo . $E[\max_i d_i]$ $e\, H_{n-1}$

Prova. A profundidade máxima é no máximo . Para finalizar, mostramos . $\ln \phi_{n-1}$ $E[\ln \phi_{n-1}] \le e\, H_{n-1}$

Para qualquer , condicionado em , pela inspeção de , $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}.$

Por indução, segue-se que

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

Portanto, pela concavidade do logaritmo,

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$

Aqui está a cauda:

lema 2. Corrija qualquer . Então é no máximo . $c \ge 0$ $\Pr[\max_i d_i] \ge e\,H_{n-1} + c$ $\exp(-c)$

Prova. Pela inspeção de e do limite de Markov, a probabilidade em questão é no máximo A partir da prova do Lema 1, . Substituir isso no lado direito acima completa a prova. $\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$

~~Quanto ao limite inferior, acho que o limite inferior de segue com bastante facilidade considerando . Mas... $(e-1)H_n - O(1)$ $\max_i d_i \ge \ln\phi_t - \ln n$~~ [EDIT: falou cedo demais]

Não parece tão fácil mostrar o limite inferior apertado, de ... $(1-o(1))e H_n$

Neal Young
fonte

2

Na verdade, eu pensei na mesma pergunta (embora em uma formulação completamente diferente) há alguns meses atrás, bem como em algumas variantes próximas.

Eu não tenho uma solução de forma fechada (/ assintótica), mas você pode achar útil esse ponto de vista (você está procurando apenas o limite superior, talvez?).

O processo que você descreve aqui é uma generalização do Processo de Restaurante Chinês , em que cada "tabela" é uma subárvore cujo pai da raiz é . $v_0$

Isso também nos fornece uma fórmula de recursão para sua pergunta.

Denote por as alturas esperadas de um processo dessa árvore com nós. $h(n)$ $n$

Denotado por (A probabilidade de distribuição dos nós em subárvores). $P_n(B)=\frac{\Pi_{b\in B} (b-1)!}{n!}$ $B$

Então a quantidade que você está procurando, , é dada por: $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)$

Se você deseja codificar essa recursão, use o seguinte para que não entre em loop infinito:

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!}}$

Onde é o conjunto de todas as partições de bolas idênticas em qualquer número de compartimentos não vazios, . $\mathcal B_n$ $n$ $h(1)=1$

Na prática, quando eu precisei disso, usei apenas um método simples de monte-carlo para estimar , pois tentar calcular por esse método é extremamente ineficiente. $h(n)$ $h$

RB
fonte

11

Obrigado pela ideia! Na verdade, escrevi um programa de Monte Carlo na primeira vez em que me deparei com esse problema, mas, para minha surpresa, o resultado exato é tão difícil de obter.

precisa saber é o seguinte

Qual é a profundidade esperada de uma árvore gerada aleatoriamente?

Respostas: