2
$\begingroup$

Q: We have a tree node with probability 0.5 to produce a left branch, 0.5 to produce a right branch (independent events), with each branch acting as an own sub-tree, what is the expected height of the tree?

My thought process is as follows: for starting node and each child node, there's equal probability of 0.25 for 4 events: having left but no right branch (LR'), having right but no left branch (L'R), having no branch (L'R'),and having both branches (LR).

Thus, if X = height of the tree, then

$$ \begin{aligned} E[X] &= E[X|LR']*P(LR') + E[X|L'R]*P(L'R)+E[X|L'R']*P(L'R')+E[X|LR]*P(LR)\\ &= (1+E[X])/4 + (1+E[X])/4 + 0 + ??? \end{aligned} $$

I'm stuck at $E[X|LR]$, the expected height given we have a left and right branch. Maybe I should be using the max function here? Or is it still just $(1+E[X])$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your process is a critical branching process (the expected number of offsprings is $1$), and you are asking for its expected extinction time. The expected extinction time of a critical branching process is infinite. See for example Problem 4 in these lecture notes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I am pretty sure it is not his case. I think it is not well described but think that it is a 2 stage choice, chose the leaf and then chose left or right. For N choices there is a finite maximum length (N) and a minimum length (log2(N)) hence there is a mean length. $\endgroup$
    – Eric Johnson
    Commented Jan 10, 2022 at 7:58
  • $\begingroup$ Ah i see. I'm still wrapping my head around the fact that the expected extinction time is infinite even though the probability of extinction time is actually 1. Thank you! $\endgroup$
    – wwyws
    Commented Jan 13, 2022 at 2:30
  • $\begingroup$ This is similar to a random walk on the integer line — you return to the origin with probability $1$, but the expected return time is infinite. $\endgroup$
    – Yuval Filmus
    Commented Jan 13, 2022 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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