Tiempo esperado del algoritmo de búsqueda en árbol con una entrada aleatoria

Question

Tenemos un árbol binario perfecto en 2^k-1 nodos. Cada nodo del árbol está marcado con probabilidad 1/2, y un nodo está marcado o no está marcado. Queremos encontrar un nodo marcado y devolverlo. Nuestro algoritmo es el siguiente

procedure find(v);
 if (v is marked)
   print(v)
 else if (v is not a leaf)
   v1 is the left child of v
   v2 is the right child of v
   find(v1) ( recursive call )
   find(v2) ( recursive call )

Así que el algoritmo básicamente comienza desde arriba. Busca hacia abajo en el árbol de una manera de profundidad primero, y devuelve al menos un nodo marcado si hay alguno. Tenga en cuenta que el algoritmo puede fácilmente devolver múltiples nodos marcados.

Ahora lo que quiero hacer es decir algo sobre el número esperado de nodos que el algoritmo considerará en un árbol aleatorio (1/2 probabilidad de marcar nodos), cuando el algoritmo se ejecuta en la raíz del árbol.

Answer 1

Suponiendo que los nodos se marcan con lanzamientos de moneda independientes, el orden en que se visitan los nodos no tiene ningún efecto. Por lo tanto, el número esperado de nodos visitados es exactamente el número esperado de lanzamientos de moneda justos para obtener cara: 2.

Answer 2

Supongamos, como sugiere Yuval, que se trata de 2^k - 1 nodos.

Podemos obtener una expresión recursiva para el número esperado de nodos N(k), donde el caso base es N(1) = 1, es decir, que si tenemos un nodo, tenemos que visitarlo (tanto si resulta estar marcado como si no).

Si k > 1, entonces con probabilidad 1/2 se marcará el nodo superior o raíz del árbol binario, y por tanto sólo se visitará el nodo superior. En la alternativa tenemos que visitar tanto los subárboles de la izquierda como los de la derecha. Así:

N(k+1) = 1/2 + (1/2)*[N(k) + N(k)] = 1/2 + N(k)

La solución de esta relación de recurrencia + condición inicial es simplemente:

N(k) = (k+1)/2

independientemente de si hay o no nodos marcados.

saludos, hm

Corrección: Como señala Ross (ver comentario), la recurrencia es N(k) = 1 + N(k), con solución N(k) = k, debido a que siempre visitaremos el nodo superior (antes de saber si está marcado).

Answer 3

Idea: calcular recursivamente el número esperado de nodos que el algoritmo visita en un árbol binario completo de altura $n$ suponiendo que al menos un nodo esté marcado . Obsérvese que este supuesto altera ligeramente las probabilidades de los acontecimientos relevantes.

EDIT: Esta idea sólo tiene sentido si se detiene después de encontrar el primer nodo marcado, en cuyo caso la solución de JeffE es mucho mejor.