Provando pular listas fortemente equilibradas em relação às expectativas

Dada uma lista de pulos de altura , qual é o comprimento esperado para um fator constante (multiplicativo)?$n$

Na seção 2.2 das Árvores B sem cache , as Árvores de pesquisa fortemente equilibradas são definidas como:

Para alguma constante , todo nó na altura tem descendentes .$d$$v$$h$$\Theta(d^h)$

Eles afirmam:

As árvores de pesquisa que atendem às Propriedades 1 e 2 incluem árvores B com ponderação de peso, listas de pulos determinísticos e listas de pulos no sentido esperado.

Eu já perguntei sobre a reivindicação de listas de pulos deterministas. Esta pergunta é sobre a reivindicação de ignorar listas.

Acredito que as listas de ignorados têm essa propriedade em expectativa, mas não consigo encontrar uma razão rigorosa. A probabilidade inversa (qual é a altura, dado o comprimento) pode ser calculada diretamente dentro de um fator constante. Uma análise sofisticada é fornecida em A transformação binomial e a análise de ignorar listas .

Editar:

Existem várias noções diferentes para definir "descendentes" em pular listas; esse termo não é usado no artigo original de Pugh. Algumas interpretações possíveis de "descendentes" vêm da exibição de listas de pulos como árvores. Diferentes maneiras de fazer isso estão incluídas no

• Uma teoria de limites para listas aleatórias de pulos
• Listas de pulos deterministas
• Ignorar árvores, uma estrutura de dados alternativa para ignorar listas em uma abordagem simultânea
• Explorando a dualidade entre listas de ignoradas e árvores de pesquisa binária

Usando a noção de "Lista de pulos determinísticos", acho que essa é outra maneira de fazer a mesma pergunta:

Se eu pegar uma moeda justa, jogue-a algumas vezes para que meu último resultado seja coroa , e a sequência contínua mais longa de cabeças tenha o comprimento , qual é o valor esperado do número de vezes que eu vi coroa ?$n$

Eu também estaria interessado em provas não construtivas de forte equilíbrio de peso na expectativa, mesmo sem uma solução de formulário fechado para .$d$

Como você perguntou, a pergunta sobre o comprimento esperado (dada a altura) não faz sentido sem uma distribuição prévia no comprimento da string.

Em vez disso, você deve considerar o número de vezes que obtém coroa antes de obter cabeças seguidas, pois isso fornecerá o número de descendentes de um nó de altura em uma lista de ignorados. Vamos representar esse valor com a variável aleatória . Quando começamos, ou logo após recebermos coroa, a probabilidade de começar e terminar uma sequência de ou mais caras antes de voltar a coroa é . Se nós batemos caudas antes de começar cabeças em uma fileira, estamos de volta para um quadrado. Assim, é realmente distribuído como e temos .h X = X ( h ) h 2 - h h X G e o m e t r i c ( 2 - h ) E ( X ) = ( 1 - 2 - h ) 2 $h$$h$$X=X(h)$$h$$2^{-h}$$h$$X$$\mathrm{Geometric}(2^{-h})$$\mathrm{E}(X) = (1-2^{-h})2^h$

Editar:

Desculpe, isso fornece o número esperado de torres na subárvore esquerda. O número de nós na subárvore esquerda será da mesma ordem de magnitude, pois as torres entre o primeiro e o último terão altura geometricamente distribuída com o valor esperado 2. Além disso, se você quiser considerar também a subárvore direita, qual provavelmente faz mais sentido, basta ir até obter cabeças seguidas em vez de apenas . Nesse caso, você obtém o número de descendentes, conforme definido no artigo de Devroye ao qual você vinculou.$h+1$$h$

Na sua reformulação da questão, você fixa o número de vezes que joga a moeda? Caso contrário, não é necessário fazer uma distribuição para quando você parar de jogar a moeda?

Permita que para defina variáveis ​​aleatórias sobre com (altura da torre ). Seja com . Então:$H_i$$i \in \mathbb{N}^+$$\mathbb{N}^+$$Pr[H_i = k] = 2^{-k-1}$$i$$H = \max \{H_i \mid i=1,\dots,N\}$$N \in \mathbb{N}^+$

$Pr[H \geq k \mid N] = 1 - \prod_{i=1}^{N} Pr[H_i < k] = 1 - (1 - 2^{-k})^n$ .

Agora podemos calcular a probabilidade de dado : . O zero da primeira derivada parcial wrt da expressão é encontrado em (usando Wolfram Alpha). Observe que eu não era capaz / estava ansioso o suficiente para verificar se isso é realmente o máximo. Se for, é o estimador de probabilidade máxima para o comprimento da lista de pulos dada a altura máxima da torre .$H=k$$N$$Pr[H = k \mid N] = Pr[H \geq k \mid N] - Pr[H \geq k + 1 \mid N] = (1-2^{-k-1})^n - (1-2^{-k})^n$$N$$N^*_k = \frac{\ln\left( \frac{\ln(1 - 2^{-k})}{\ln(1 - 2^{-k - 1})}\right) }{ \ln(1 - 2^{-k-1}) - \ln(1 - 2^{-k})}$$N^*_k$$N$$k$

Alguns valores, arredondados para o número inteiro mais próximo:

k    N^*_k
1    2
2    5
3    11
4    22
5    44
10   1419
20   1.5e6

Isso parece razoável; convém verificar se . Espero que a altura esperada de uma lista de pulos de comprimento fixo seja um resultado padrão.$\mathbb{E}[k \mid N^*_k] \approx k$

Alguém tem uma boa idéia de como obter um assintótico para ? A expressão que encontrei não é muito útil.$N^*_k$