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.

$\endgroup$
2
  • $\begingroup$ "pick a random node" -- random with what probability distribution? $\endgroup$ Nov 8, 2016 at 13:15
  • $\begingroup$ Both random nodes will be taken uniformly over the list of nodes $\endgroup$
    – Disha
    Nov 8, 2016 at 14:11

1 Answer 1

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

$\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, 2016 at 4:01
  • $\begingroup$ My formula works for all trees. $\endgroup$ Nov 9, 2016 at 4:02
  • $\begingroup$ So according to your formula (2*8)/(2^2).Is it correct $\endgroup$
    – Disha
    Nov 9, 2016 at 4:12
  • $\begingroup$ Please do your own homework. $\endgroup$ Nov 9, 2016 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$ Nov 9, 2016 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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