Let T be a full binary tree with $8$ leaves. (A full binary tree has every level full). Suppose that 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 (i.e number of edges in the unique path between a and b) is ?
My Attempt:
This question is really simple. The only thing I want to confirm is whether the answer to this question will be $4.86$ or $4.25$ ? As per me the answer should be $4.86$. I solved it this way: sum of distances from a particular leaf to the remaining $7$ leaves is $34$. The sum would remain the same for each leaf node. Therefore total sum of distance of all the leaf nodes $= 34\times8$. So, expectation $= (34 \times 8)/(8 \times 7) = 4.86$.
Am I correct with the answer?
Your answer assumes that once $a$ is chosen, there are $7$ possibilities for the $b$, at an average distance of $34/7$ (and this value doesn't depend on $a$). But this ignores the possibility that $a$ and $b$ are equal (distance $0$); since they are chosen independently this can happen, and so in fact there are $8$ possibilities for $b$ at an average distance of $34/8$.