# Expected distance between tree nodes

I have been given a tree with n nodes and n-1 edges with it's weight. There are two people A and B. I have been given a list of nodes of size k.

A will pick a random node x from this list and B will independently pick a random node y from this list.

I have to find expected distance between these two nodes.

My way of solving it was to find the distance between all the (k*(k-1)/2)nodes of the list and dividing it by number of nodes in the list.

for ex: n=6,k=6 list=[1,2,3,4,5,6]

                    Node--------> 1
\(1)<-----------Weight
\
3
(3) / \(2)
/   \
4     2
(4) / \ (5)
/   \
5     6


My answer was coming out to be 87/6 but the actual answer was 29/6.Please help me find whatever i am doing wrong here.

• "pick a random node" -- random with what probability distribution? – David Richerby Nov 8 '16 at 13:15
• Both random nodes will be taken uniformly over the list of nodes – Disha Nov 8 '16 at 14:11

Let $d(i,j)$ denote the distance between $i$ and $j$. Calculation shows that $$\sum_{i<j} d(i,j) = 87.$$ Hence the average distance is $$\frac{1}{6^2} \sum_{i,j=1}^6 d(i,j) = \frac{1}{36} \left(\sum_{i<j} d(i,j) + \sum_{i>j} d(i,j) + \sum_{i=j} d(i,j)\right) = \frac{2\cdot 87}{36} = \frac{29}{6}.$$
A simple way to do the calculation is as follows. Suppose that there are $n$ nodes, and that edge $e$ of weight $w_e$ cuts the tree into parts of size $k_e,n-k_e$. Then the average distance is $$\frac{2}{n^2} \sum_e w_e k_e (n-k_e).$$ For example, in our case we get $$\frac{2}{36} (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) = \frac{29}{6}.$$