A full binary tree has every edge colored black or white randomly. What is the probability of having a white path from the root to some leaf?

Question

A full binary tree has every edge colored black or white randomly. What is the probability of having a white path from the root to some leaf?

A) $\Theta(1)$

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

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

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

Every edge has a 0.5 chance of being white and 0.5 chance of being black. The tree is of depth $n$ so therefore it has $2^n$ leafs with distinct paths to them and every path is of length $n$.

I'm not sure how to solve this question. I'm really not sure where to start. The odds of a random path being white is $(\frac{1}{2})^n$ and there are $2^n$ different paths to the leafs, but it's not true that $P=2^n(\frac{1}{2})^n $ Because that just equals 1.

Answer 1

Hint: start from the top and work down. Right from the start, you have a 25% chance of failing (both edges from the root are black). Apply this r recursively.

---

To expand a bit on this, separate into four different cases depending on our two child edges, BB (black/black), BW, WB and WW, each having probability $\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}

Note that for the last case we use $1$ minus the chance that both fail, which gives the chance that at least one succeeds. Simplifying this we get:

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

Also keep in mind that $p(1) = 1$, because the path from a node to itself always exists.

Solving these types of recurrences isn't easy, see Did's answer to go from here (or better, attempt it yourself).

Answer 2

Let $p(n)$ be the probability of a tree with depth n having a white path from the root to a leaf. Starting from the root and working down, notice that there are 3 possibilities for the first level:

1. Both edges are white (probability $.25$), reducing our problem to two independent cases of trees with depth $n-1$
2. Both edges are black (probability $.25$), in which case we've already lost
3. One edge is black, one edge is white (probability $.5$), in which case we simply have a tree with depth $n-1$

Combining these three mutually exclusive cases by the law of total probability yields: \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*}

Can you solve that recurrence and get a closed form? Not to inherently imply the existence of a closed form. I'm simply stating that if you can find such a closed form, that would allow you to finish the problem.

Answer 3

The recursion

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

is a simple consequence of the one-level decomposition of the tree. To deduce some asymptotics of $p(n)$, one first notes that every $p(n)$ is in $(0,1]$ hence $p(n)$ is a nondecreasing function of $p(n-1)$.

Now, one is ready to show that, for every $n\geqslant0$,

$$\frac3{n+3}\leqslant p(n)\leqslant\frac4{n+4}\tag{$\ast$}$$

The $n=0$ case of $(\ast)$ follows from the value $p(0)=1$. (If one is uncomfortable with the (perfectly legit) notion that $p(0)$ exists and that $p(0)=1$, one can instead check $(\ast)$ for $p(1)=\frac34$).

If $(\ast)$ holds for some $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$$ hence, to deduce that $(\ast)$ holds for $n+1$ as well, it suffices to check that, for every $n\geqslant0$, $$\frac3{n+4}\leqslant\frac3{n+3}-\frac14\left(\frac3{n+3}\right)^2\tag{1}$$ and that, for every $n\geqslant0$, $$\frac4{n+4}-\frac14\left(\frac4{n+4}\right)^2\leqslant\frac4{n+5}\tag{2}$$ It happens that $(1)$ and $(2)$ are both direct hence all this proves that $(\ast)$ holds for every $n\geqslant0$. In particular,

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