patternMinor
Expected distance between tree nodes
Viewed 0 times
nodesdistanceexpectedbetweentree
Problem
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]
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.
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 6My 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.
Solution
Let $d(i,j)$ denote the distance between $i$ and $j$. Calculation shows that
$$
\sum_{ij} 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}.
$$
$$
\sum_{ij} 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}.
$$
Context
StackExchange Computer Science Q#65729, answer score: 4
Revisions (0)
No revisions yet.