retagged by
30,315 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

Best answer
132 votes
132 votes

Two leaves a and b of T are chosen uniformly and independently at random.

See the word "independently" here. It means that choice of $a$ must not affect choice of $b$ and vice versa. This implies that both $a$ and $b$ can even be the same node.

Now, we are given that the binary tree has $8$ leaves. $\left(2^3 = 8\right) \implies$ we have $3$ levels in the tree starting from $0.$ The distance in terms of number of edges between any two leaf nodes will always be even. If we consider any two leaves (not necessarily distinct)

  • No. of pairs with path length $0 = 8.$ (When $a = b)$
  • No. of pairs with path length $2 = 8.$ (For each of the $8$ leaf nodes, we have a pair and since the selection is independent order of the pair is also significant)
  • No. of pairs with path length $4 = 16.$ (For each leaf node we have to go two levels up and while coming down we have $2$ choices. So, we get $8 \times 2 = 16$ pairs)
  • No. of pairs with path length $6 = 32.$ (For each leaf node we have to go till the root, and from there while coming down it has $2 \times 2 = 4$ choices. Thus we get $8 \times 4 = 32 $ pairs.

Total number of possible pairs $ = 8 \times 8 = 64$

So, expected path length

$\quad =0 \times \frac{8}{64}  + 2 \times \frac{8}{64}+4 \times \frac{16}{64}+6 \times \frac{32}{64}= \frac{272}{64}=4.25$

edited by
152 votes
152 votes

A full binary tree of $8$ leaves

Let's say we take node $H.$ The distances from $H$ to all other nodes (including itself) would be:

$\begin{array}{|c|c|c|c|c|c|c|c|}\hline
H&I&J&K&L&M&N&O\\\hline
0&2&4&4&6&6&6&6\\\hline
\end{array}$

If another node is taken, a similar table (to the one above) is attained. Therefore, all nodes have the same distances when added together. 

So, if a node is considered, the probability of choosing another node would be $1/8$ (including itself - independent choosing]. 

Therefore, $E = \frac{1}{8} \left[0+2+4+4+6+6+6+6\right] = 4.25$

edited by
11 votes
11 votes

Path can only have distinct vertices. If two leaves are same , path cannot be defined between them. distance(a,b) is not defined if a and b are same vertex.

This answer is according to definition of path given in two books which I came across:

1. Anaytics combinatorics by Alan Tucker

http://noahc.me/Applied%20Combinatorics%206th%20edition.pdf

page 4

2. Graph theory by Frank Harary.

https://shyam.nitk.ac.in/Books/GT%20Books/Harary.pdf page 13

3. mit book on discrete maths

https://courses.csail.mit.edu/6.042/spring17/mcs.pdf page 384-385

see the comment below by ahabnnc

 

 

edited by
7 votes
7 votes
Ans should be 4.25,Becoz path length 0 is also possible as it is not said "distinct leafs"
edited by
Answer:

Related questions

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