HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Expected distance between tree nodes

Submitted by: @import:stackexchange-cs··
0
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]

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.

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

Context

StackExchange Computer Science Q#65729, answer score: 4

Revisions (0)

No revisions yet.