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

5 votes
5 votes
Choose any two leaves at random where first leaf is 'a' and second leaf 'b'. As it is mentioned 'independently' both the chosen leaves could be same and in that case path length = 0.

Now to find the expected path length, we have to

= $\frac{\sum\ pathLen\ *\ 8\ *\ pathsPerLeaf} {\sum TotalNoOfPaths} $

= $\frac{0*(8*1) + 1*0 + 2*(8*1) + 3*0 + 4*(8*2) + 5*0 + 6*(8*4)}{8*1+8*1+8*2+8*4}$

= 272/64 = 4.25
2 votes
2 votes

This is a very beautiful question on set theory and cartesian product.

I hope my solution explains why the asnwer is 4.25

0 votes
0 votes
I think answer is 4.596 assume a,b,c,d,e,f,g,h are at leave level in this order)

0 length =8(self people only) again because of two magical words (independent and uniform). since uniform irrespective of the fact any how probability of choosing two leaves is 1 so my concern is leaves only not internal node , I mean to say i will only choose from leaves  not from any where  

2 length =3 (a-a,a-b,b-b)(now if i choose c and b(no matter what 2 length is not there ,but 4 length is there(for this case it will be consider ,which i had covered latter)

4 length =10(a-a,a-b,a-c,a-d,b-b,b-c,b-d,------)(4+3+2+1) since unique path i ruled out those case in which a-b=b-a) some one might put up question what if i select b-a path rather then a-b (no matter what it will be unique path only, this is an assumption tell me if i am wrong here)

6 length=36(8+7---------1)

now expected length(average )=((36*6)+(10*4)+(3*2)+(0*8))/57=4.596~4.60 If I need correction please let me know. May be I have done blunder in this solution.
Answer:

Related questions

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