probability of selecting two nodes in a tree

Question

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.

Answer 1

Two mistakes:

1. You should include pairs like $(1,1)$ which have distance $0$.
2. You should divide by $k^2$ (in your case $\frac{k(k-1)}{2}$ because of the previous mistake), not $k$.

Using your numbers we get $\frac{2\cdot 87+6\cdot 0}{36} = \frac{29}{6}$. The multiplication by two is because you are counting undirected pairs, while I count directed pairs (so that $(1,1)$ will get counted exactly once, not $0.5$ times).

I hope this helps $\ddot\smile$