Un árbol binario completo tiene cada arista coloreada en blanco o negro de forma aleatoria. Cuál es la probabilidad de tener un camino blanco desde la raíz hasta alguna hoja?

Question

Un árbol binario completo tiene cada arista coloreada en blanco o negro al azar. ¿Cuál es la probabilidad de tener un camino blanco desde la raíz hasta alguna hoja?

A) $\Theta(1)$

B) $\Theta(\frac{1}{n})$

C) $e^{-\Theta(n)}$

D) $(\log n)^{-\Theta(1)}$

Cada arista tiene una probabilidad de 0,5 de ser blanca y 0,5 de ser negra. El árbol tiene una profundidad $n$ por lo que tiene $2^n$ hojas con caminos distintos hacia ellas y cada camino es de longitud $n$ .

No estoy seguro de cómo resolver esta cuestión. Realmente no estoy seguro de por dónde empezar. La probabilidad de que un camino al azar sea blanco es $(\frac{1}{2})^n$ y hay $2^n$ diferentes caminos hacia las hojas, pero no es cierto que $P=2^n(\frac{1}{2})^n $ Porque eso es igual a 1.

Answer 1

Sugerencia: empezar desde arriba y trabajar hacia abajo. Desde el principio, tienes un 25% de posibilidades de fallar (ambos bordes desde la raíz son negros). Aplique esta r de forma recursiva.

---

Para ampliar un poco esto, separar en cuatro casos diferentes en función de nuestros dos bordes hijos, BB (negro/negro), BW, WB y WW, cada uno con probabilidad $\frac{1}{4}$ :

\begin{align} p(n) &= \frac{1}{4}\cdot 0 \quad &\text{(BB)}\\ &+\frac{1}{4}\cdot p(n-1) &\text{(BW)}\\ &+\frac{1}{4}\cdot p(n-1) &\text{(WB)}\\ &+\frac{1}{4}\cdot (1 - (1 - p(n-1))^2) &\text{(BB)}\\ \end{align}

Nótese que para el último caso utilizamos $1$ menos la posibilidad de que ambos falla que da la posibilidad de que al menos uno tenga éxito. Simplificando esto obtenemos:

$$p(n) = p(n-1) - \frac{1}{4}p(n-1)^2$$ $$p(n) = p(n-1)(1 - \frac{1}{4}p(n-1))$$

También hay que tener en cuenta que $p(1) = 1$ porque el camino de un nodo a sí mismo siempre existe.

Resolver este tipo de recurrencias no es fácil, vea la respuesta de Did para pasar a la acción (o mejor, inténtelo usted mismo).

Answer 2

La recursión

$$p(n)=p(n-1)-\frac14p(n)^2$$

es una simple consecuencia de la descomposición de un nivel del árbol. Para deducir algunas asintóticas de $p(n)$ En primer lugar, se observa que cada $p(n)$ está en $(0,1]$ por lo que $p(n)$ es una función no decreciente de $p(n-1)$ .

Ahora, uno está listo para demostrar que, para cada $n\geqslant0$ ,

$$\frac3{n+3}\leqslant p(n)\leqslant\frac4{n+4}\tag{$ \N - El brindis $}$$

El $n=0$ caso de $(\ast)$ se deduce del valor $p(0)=1$ . (Si uno se siente incómodo con la noción (perfectamente legítima) de que $p(0)$ existe y que $p(0)=1$ En cambio, se puede comprobar $(\ast)$ para $p(1)=\frac34$ ).

Si $(\ast)$ se mantiene para algunos $n\geqslant0$ , $$\frac3{n+3}-\frac14\left(\frac3{n+3}\right)^2\leqslant p(n+1)\leqslant\frac4{n+4}-\frac14\left(\frac4{n+4}\right)^2$$ por lo que se deduce que $(\ast)$ se mantiene para $n+1$ también, basta con comprobar que, para cada $n\geqslant0$ , $$\frac3{n+4}\leqslant\frac3{n+3}-\frac14\left(\frac3{n+3}\right)^2\tag{1}$$ y que, por cada $n\geqslant0$ , $$\frac4{n+4}-\frac14\left(\frac4{n+4}\right)^2\leqslant\frac4{n+5}\tag{2}$$ Sucede que $(1)$ y $(2)$ son ambas directas por lo que todo esto demuestra que $(\ast)$ es válida para cada $n\geqslant0$ . En particular,

$$p(n)=\Theta\left(\frac1n\right)$$

Answer 3

Dejemos que $p(n)$ sea la probabilidad de que un árbol con profundidad n tenga un camino blanco desde la raíz hasta una hoja. Empezando por la raíz y trabajando hacia abajo, observe que hay 3 posibilidades para el primer nivel:

1. Ambos bordes son blancos (probabilidad $.25$ ), reduciendo nuestro problema a dos casos independientes de árboles con profundidad $n-1$
2. Ambos bordes son negros (probabilidad $.25$ ), en cuyo caso ya hemos perdido
3. Una arista es negra, otra blanca (probabilidad $.5$ ), en cuyo caso simplemente tenemos un árbol con profundidad $n-1$

Combinando estos tres casos mutuamente excluyentes por la ley de la probabilidad total se obtiene: \begin{align*} p(n) &= .25(1 - (1 - p(n-1))^2) + .5p(n-1) \\ &= -\frac{1}{4}p(n-1)^2 + p(n-1) \end{align*}

¿Puedes resolver esa recurrencia y obtener una forma cerrada? No es que implique intrínsecamente la existencia de una forma cerrada. Simplemente estoy afirmando que si puedes encontrar dicha forma cerrada, que te permita terminar el problema.