retagged by
30,342 views
71 votes
71 votes
Let $T$ be a full binary tree with $8$ leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. The expected value of the distance between $a$ and $b$ in $T$ (ie., the number of edges in the unique path between $a$ and $b$) is (rounded off to $2$ decimal places) _________.
retagged by

9 Answers

0 votes
0 votes

Expectation = Summation(Output*Probability of Output)

→ Now for output 0 : Chose any node first, but for 2nd ,you have only 1 choice out of 8,that is the same node,so probability =(1/8)

→ Now for output 2 : Chose any node first, but for 2nd ,you have only 1 choice out of 8,that is the node beside it,so probability =(1/8)

→ Now for output 4 : Chose any node first, but for 2nd ,you have only 2 choices out of 8,which are the 2 nodes at distance 4 from it,so probability =(2/8)

→ Now for output 6 : Chose any node first, but for 2nd ,you have only 4 choices out of 8,which are the 4 nodes at distance 6 from it,so probability =(4/8)

=Summation(0*(1/8) + 2*(1/8) + 4*(2/8) + 6*(4/8)) = 34/8 = 4.25

Answer:

Related questions

40 votes
40 votes
4 answers
2
18 votes
18 votes
4 answers
3
20 votes
20 votes
4 answers
4