3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Can you define "hit this target"? $\endgroup$ Commented Sep 27, 2019 at 13:05
  • $\begingroup$ @OliverRoche successfully reach the target, with the traversal starting from the root $\endgroup$
    – nz_21
    Commented Sep 27, 2019 at 13:07
  • $\begingroup$ Like, with a $\frac{1}{2}$ probability of chosing each son at each step? $\endgroup$ Commented Sep 27, 2019 at 13:10
  • $\begingroup$ What is the probability that the burned-out node is at depth $1$? Depth 2? Given that the burned-out node is at depth $x$, what is the probability that the target can be reached? $\endgroup$ Commented Sep 27, 2019 at 13:15
  • $\begingroup$ The burnt node is uniformly random among all nodes (internal and leaves), but what about the target? Is that (A) uniformly random among all original nodes (internal & leaves) or (B) uniformly random among all original leaves (i.e. uniform random walk of length $6$)? Those are different questions. $\endgroup$
    – antkam
    Commented Sep 27, 2019 at 13:23

3 Answers 3

2
$\begingroup$

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}.$$

$\endgroup$
2
  • $\begingroup$ wow, thanks! This seems super math-heavy...I'm wondering if there's any intuition to get an approximate $\endgroup$
    – nz_21
    Commented Sep 27, 2019 at 13:35
  • 1
    $\begingroup$ this answer assumes the "target" is a random leaf (as opposed to a random node (internal or leaf)) of the original tree. if this assumption is correct, a much faster way to arrive at $p=7/127$ is to realize that no matter which target leaf $L$ is picked, it no longer exists iff the burned node is along the path from root to $L$. there are $7$ such nodes (including root and $L$) along that path, among the $2^7-1 = 127$ nodes in the original tree. $\endgroup$
    – antkam
    Commented Sep 27, 2019 at 16:59
1
$\begingroup$

There are $1+2+4+\dots+64=127$ nodes in this tree.

  • There is a $\frac{64}{127}$ chance that the burnt node is at the lowest level. In that case, the chance you hit the burnt node is $\frac1{64}$. The probability of hitting the burnt node at this level is therefore $\frac{64}{127}\cdot \frac{1}{64}=\frac1{127}$.

  • There is a $\frac{32}{127}$ chance that the burnt node is at the second lowest level. In that case, the chance you hit the burnt node is $\frac1{32}$. The probability of hitting the burnt node at this level is therefore $\frac{32}{127}\cdot \frac{1}{32}=\frac1{127}$.

  • There is a $\frac{16}{127}$ chance that the burnt node is at the third lowest level. In that case, the chance you hit the burnt node is $\frac1{16}$. The probability of hitting the burnt node at this level is therefore $\frac{16}{127}\cdot \frac{1}{16}=\frac1{127}$.

  • $\vdots$

You see the pattern. For each level, the probability of hitting the burnt node at that level is $\frac1{127}$. Adding up for each level, the probability of hitting the burnt node is $\frac{7}{127}$.

$\endgroup$
1
$\begingroup$

There are two randomly chosen nodes, the burned one $B$, and the target $T$. You specified that $B$ is uniformly random among the $127$ nodes. However, the final answer also depends on how the target is chosen - in particular, is it uniformly random among the $127$ nodes or among just the $64$ leaves?

If $T$ is uniformly random among the $64$ leaves, the answers by Mike Earnest and Hagen von Eitzen already addressed this case. Here's a shorter proof: For whichever leaf $T$ you choose, it is unreachable iff $B$ is along $T$'s path to the root, and this path consists of $7$ nodes (including $T$ and the root). So the probability is $7/127$ for any leaf $T$, which means it is also $7/127$ averaged over all leaves $T$.

If $T$ is uniformly random among all $127$ nodes, let $H(T) \in [0, 6]$ denote the height of $T$, e.g. $H(root)=0$ and $H(any\ \ leaf)=6$. Then, for whichever $T$ you choose it is unreachable iff $B$ is along $T$'s path to the root, and this path consists of $H(T)+1$ nodes (including $T$ and the root). So the probability is ${H(T)+1 \over 127}$ for any given $T$. For the overall probability you need to average over all $T$, so the answer is ${E[H(T)]+ 1 \over 127}$.

Now you need to calculate the average height $E[H(T)]$. This is simple by explicit counting:

$$E[H(T)] = 0 \times {1 \over 127} + 1 \times {2 \over 127} + 2 \times {4 \over 127} + \dots 6 \times {64 \over 127}\approx 5.06$$

$$Prob(\text{$T$ is unreachable}) = {E[H(T)] + 1 \over 127} \approx {6.06 \over 127} \approx 0.048$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .