3
$\begingroup$

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.

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

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}. $$

Improve this answer
$\endgroup$
9
  • $\begingroup$ But how will i approach if let say there are only 2 nodes in the list. Let say in this graph we have [1,6] in the list ? $\endgroup$ – Disha Nov 9 '16 at 4:01
  • $\begingroup$ My formula works for all trees. $\endgroup$ – Yuval Filmus Nov 9 '16 at 4:02
  • $\begingroup$ So according to your formula (2*8)/(2^2).Is it correct $\endgroup$ – Disha Nov 9 '16 at 4:12
  • $\begingroup$ Please do your own homework. $\endgroup$ – Yuval Filmus Nov 9 '16 at 4:13
  • 1
    $\begingroup$ Try to understand where the formula comes from and why it works, and then you will be able to answer your own question. $\endgroup$ – Yuval Filmus Nov 9 '16 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.