0
$\begingroup$

Any node of a binary tree has the same probability p to have two children nodes (and has no children nodes with the probability of (1-p)). What is the expected depth of the binary tree?

$\endgroup$
  • 1
    $\begingroup$ What did you try $\endgroup$ – Rishi Sep 16 '19 at 16:23
  • $\begingroup$ Every branch got two nodes and then two and so on and few branches end soon few goes longer. So do you mean length of longest branch by depth of the tree? $\endgroup$ – Rishi Sep 16 '19 at 16:43
  • $\begingroup$ Is $p=\frac12$ a critical value? $\endgroup$ – Henry Sep 16 '19 at 17:38
  • $\begingroup$ It does appear that when $p=\frac12$ the expected depth of the tree, truncating at a maximum depth of $n$, grows like $1+\sqrt{n}$, so that for $p=\frac12$ the expected depth may be infinite. $\endgroup$ – Mark Fischler Sep 16 '19 at 19:51
  • $\begingroup$ @Rishi Yes, I mean the longest branch. I tried to compute the probability of each specific tree depth, but it soon becomes too complicated. I also tried to formulate the recursive equation, something like E(Depth) = p[E(Max(Depth_of_left_child, Depth_of_right_child))+1) + (1-p) = p E(Max(Depth_of_left_child, Depth_of_right_child)) + 1, which can be rewrite in the form of probability density function. But it also goes to nowhere further. $\endgroup$ – tlyzbcy Sep 17 '19 at 1:31
0
$\begingroup$

Adapting one of the answers at a related question, which considered $p=\frac12$:

Let $H$ denote the height of the random binary tree and set $h(n):=\mathbb{P}(H>n)$, the probability that the tree's height exceeds $n$. The tree's height exceeds $n+1$ if it has more than the root node, and at least one of the subtrees has height exceeding $n$. It follows that $$h(0)=p$$ $$h(n+1)=p\bigg(1-\big(1-h(n)\big)^2\bigg),\quad n\geq 0$$ $$\mathbb{E}(H)=\sum_{n=0}^\infty \mathbb{P}(H>n)=\sum_{n=0}^\infty h(n) $$

This gives

  • $\mathbb{E}(H)=\infty$ when $p \ge \frac12$
  • $\mathbb{E}(H)\approx 1.4045314$ when $p = \frac25$
  • $\mathbb{E}(H)\approx 0.8334768$ when $p = \frac13$
  • $\mathbb{E}(H)\approx 0.4610126$ when $p = \frac14$
  • $\mathbb{E}(H)\approx 0.3179676$ when $p = \frac15$
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, it really helps a lot. How did you calculate the detailed values? Is there an analytical solution? $\endgroup$ – tlyzbcy Sep 17 '19 at 14:48
  • $\begingroup$ @tlyzbcy I just used the recursion until the values became small. Does it match your simulations? $\endgroup$ – Henry Sep 17 '19 at 18:04
  • $\begingroup$ Yeah, it matches perfectly. $\endgroup$ – tlyzbcy Sep 18 '19 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.