Número promedio de inspecciones

Question

Considere un conjunto de elementos n cuyos valores clave son $$ 0, 1, ..., N-1. $$ Let $ P (i) (0 ≤ i ≤ n-1) $ Sé la probabilidad de que se busque el elemento con la tecla. Supongamos la siguiente distribución de $ P (i) 's $ :

$$ P (i)= \ comienzan {casos} 1/2 ^ {n-1}, & \ texto {si i= 0} \\ 1/2 ^ i, & \ texto {lo contrario} \ End {casos} $$

Supongamos que se usa una búsqueda lineal y cada búsqueda es exitosa: cada elemento que buscamos existe.

¿Cuál es el número promedio de nodos inspeccionados para una búsqueda bajo aleatoria (elementos en la lista vinculada se almacenan en una organización de orden aleatorio) y cuál es el número promedio de nodos si se ordenó en función de su probabilidad decreciente (es decir, comienza con el elemento '1', seguido del elemento '2', luego '3', y así sucesivamente, con el último nodo que contiene elemento '0'). Para valores grandes de n?

Sé que la respuesta para la primera parte es seguramente no $ n / 2 $ (ya que la probabilidad no es la misma para todos los elementos) pero lo hago No sé realmente mucho más que eso ... pero cuando se clasifica, sospecho que debería ser algo cercano a $$ \ sum_ {i= 1} ^ {n-1} i * { 1/2 ^ {i}} + n * 1/2 ^ {n-1} $$ porque toma una comparación para llegar al primer elemento, dos al segundo, etc. y el último toma n Comparaciones veces la probabilidad de 0. También encontré el $$ \ sum_ {i= o} ^ {∞} a * b ^ a= b / (1-b) ^ 2 $ $ que en este caso sería igual a 2 (b= 1/2) pero no tengo ni idea de cómo abordar el caso del borde - '0'. : (

También estoy al tanto de este hilo Pero cada uno de los números tenía la misma probabilidad y no es exactamente lo mismo.

Espero encontrar una respuesta a esto, ya que me ha estado molestando durante bastante tiempo y estoy realmente curioso por el resultado.
Cualquier sugerencia será muy apreciada!

Answer 1

Bueno, veamos. Por favor, señale si entendí el modelo de problema incorrectamente.

Supongamos que tenemos $ n= 5 $ elementos. Supongamos que está ordenado en el camino $ s= [1, 3, 4, 0, 2] $ . Luego, mediante la búsqueda lineal, vamos a convertirnos en probabilidad $ (1/2) ^ 3 $ tiene 2 pasos en nuestra búsqueda y con probabilidad $ (1/2) ^ 4 $ tienen 4 pasos en nuestra búsqueda.

Entonces, ¿cuál es el número promedio de pasos que debemos encontrar un elemento que le da clasificación arbitraria $ s $ ? Digamos $ x $ - Número de pasos necesarios en nuestra búsqueda. Probabilidad de obtener $ x= i $ los pasos es equivalente a solicitar una búsqueda de un elemento $ k \ in \ {0, 1,2, .., N-1 \ span> dando que lo tenemos en el $ i $ th Position. Que es $$ P (x= i)=sum_ {k= 0} ^ {n-1} P (búsqueda \ for \ k \ | \ the \ element \ k k \ es \ en \ en la posición) P (el \ elemento \ k \ es \ en \ en la posición) $$ Luego notamos que $ p (el \ elemento \ k \ is \ en \ \ posición)=frac {(n-1)!} {n!}=frac {1} {n} $ porque tenemos un elemento en una posición fija y $ (n-1)! $ Posibles permutaciones para otros elementos fuera del total de $ posible Permutaciones de nuestro $ n $ elementos. Luego nos dimos cuenta de que $ \ sum_ {k= 0} ^ {n-1} P (búsqueda \ for \ k \ | \ the \ element \ k k \ is \ at \ \ a \ at \ i posición)= 1 $ . Significa que $ P (x= i)=frac {1} {n} $ . Por lo tanto, la expectativa es solo $ \ sum_ {k= 1} ^ {n} \ frac {k} {n}=frac {n + 1} {2} $ .

Por supuesto, la segunda parte es mucho más fácil de derivar, es solo $$ E (x | ordenado \ in \ disminuyendo \ probabilidad)=sum_ {k= 1} ^ {n-1} \ frac {k} {2 ^ {k}} + \ frac {n} {2 ^ {n} {2 ^ {n-1}} $$ (solo observe que los elementos van a ser de < Span Class="Math-contenedor"> $ 1 $ a $ n-1 $ y luego el elemento $ 0 $ , sin embargo, $ 0 $ podría ser el elemento pre-último porque tiene la misma probabilidad que $ n-1 $ ). Por lo tanto, solo calculamos la expectativa de la distribución de probabilidad, aunque esta vez no para la probabilidad conjunta sino condicional.