I'm trying to solve this puzzle:
We're given a full binary tree of height $6$, and told that there exists $1$ node, $n$, in this tree that's burned down: that means $n$ and its descendants do not exist anymore. Each node has an equal chance of being burned out.
If we select a target at random and try to reach it starting from the root, what's the probability that we'll actually reach the target?
I'm not sure where to even start — I can't quite get the intuition to solve this problem.
Best Answer
So with $d=6$, there are $2^{d+1}-1$ nodes in total. Depending on its position, the burned down node $n$ covers between $1$ leaf (only itself) and $2^d$ leaves (if $n$ is the root). More generally, if $E_d$ is the expected number of leaves covered by a random node in a full binary tree of height $d$, then we have the recursion $$ E_{d}=\frac1{2^{d+1}-1}\cdot 2^d+\left(1-\frac1{2^{d+1}-1}\right)\cdot E_{d-1}=\frac{2^d+2\cdot(2^{d}-1)E_{d-1}}{2^{d+1}-1}$$ with initial condition $E_0=1$. One finds (and then quickly verifies) that this leads to $$ E_d=\frac{(d+1)2^d}{2^{d+1}-1}.$$So in our situation, the expected number of leaves covered by $n$ is $$ E_6=\frac{7\cdot 64}{127}=\frac{448}{127}.$$ How does this help with the original question? A random walk from the root will end up at a leaf of the (un-burnt) tree, uniformly(!) picked from its $2^6$ leaves. On the way, we hit $n$ if and only if the final leaf is among the leaves covered by $n$. We conclude that the probability of hitting $n$ is $$ p=\frac{E_6}{2^6}=\frac 7{127}.$$