Probar listas de omisión fuertemente balanceadas en peso

Dada una lista de salto de altura $n$ , ¿cuál es su longitud esperada, dentro de un factor constante (multiplicativo)?

En la sección 2.2 de Cache-Ajeno B-Trees , Fuertemente Peso equilibrado de la búsqueda árboles se definen como:

Para alguna constante $d$ , cada nodo $v$ a la altura $h$ tiene descendientes $\Theta(d^h)$ .

Ellos reclaman:

Los árboles de búsqueda que satisfacen las Propiedades 1 y 2 incluyen árboles B con equilibrio de peso, listas de omisión deterministas y listas de omisión en el sentido esperado.

Ya pregunté sobre el reclamo de listas de omisión deterministas. Esta pregunta es sobre el reclamo de listas de omisión.

Creo que las listas de omisión tienen esta propiedad en expectativa, pero no puedo encontrar una razón rigurosa. La probabilidad al revés (cuál es la altura, dada la longitud) se puede calcular directamente dentro de un factor constante. Se da un análisis sofisticado en La transformación binomial y el análisis de las listas de omisión .

Editar:

Hay varias nociones diferentes para definir "descendientes" en las listas de omisión; Este término no se utiliza en el documento original de Pugh. Algunas posibles interpretaciones de "descendientes" provienen de ver las listas de salto como árboles. Se incluyen diferentes formas de hacer esto en

• Una teoría de límites para listas de salto aleatorias
• Listas de salto deterministas
• Omitir árboles, una estructura de datos alternativa para omitir listas en un enfoque concurrente
• Explorando la dualidad entre las listas de salto y los árboles de búsqueda binarios

Usando la noción de "listas de omisión deterministas", creo que esta es otra forma de hacer la misma pregunta:

Si tomo una moneda justa, luego la lanzo varias veces de modo que mi último resultado sea colas , y la secuencia continua más larga de caras fue de longitud , ¿cuál es el valor esperado de la cantidad de veces que vi colas ?$n$

También me interesarían las pruebas no constructivas de un fuerte equilibrio de peso en expectativa, incluso sin una solución de forma cerrada para .$d$

Como lo hizo, la pregunta sobre la longitud esperada (dada la altura) no tiene sentido sin una distribución previa de la longitud de la cadena.

$h$$h$$X=X(h)$$h$$2^{-h}$$h$$X$$\mathrm{Geometric}(2^{-h})$$\mathrm{E}(X) = (1-2^{-h})2^h$

Editar:

$h+1$$h$

En su reformulación de la pregunta, ¿fija el número de veces que lanza la moneda? Si no, ¿no es necesario dar una distribución para cuando deje de lanzar la moneda?

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

Ahora podemos calcular la probabilidad de dado : . El cero de la primera derivada parcial de esta expresión wrt se encuentra en (usando Wolfram Alpha). Tenga en cuenta que no pude / estaba ansioso por comprobar si era o no, eso es realmente un máximo. Si es así, es el estimador de máxima probabilidad para la longitud de la lista de omisión dada la altura máxima de la 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 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$

Algunos valores, redondeados al entero más cercano:

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

Esto se siente razonable; es posible que desee comprobar si . Espero que la altura esperada de una lista de salto para longitud fija sea un resultado estándar.$\mathbb{E}[k \mid N^*_k] \approx k$

¿Alguien tiene una buena idea de cómo obtener un asintótico para ? La expresión que encontré no es muy útil.$N^*_k$