Expected distance between 2 uniformly chosen arbitary points in an Undirected Weighted Planar Graph

Question

Given a Undirected Weighted Planar Graph with $N$ nodes and $N-1$ edges each having different weight $w$. Between two nodes there is exactly one path that goes through the edges and nodes such that no node appears in the path more than once.

Given some nodes $A$₁, $A$₂$, ...,A$ _K. $2$ nodes are taken at random from these nodes.

How to calculate the distance between those two randomly chosen nodes ?( The answer will be in a form of rational numbers)

By the way, I tried taking all pairs of points in the list $A$₁, $A$₂$, ...,A$ _K and added sum of the distances between them i.e $(k*(k-1))/2$ pairs and divided it by K i.e. total number of points in the list. But this gives wrong answer. It is giving more in numerator.

Answer 1

Without specific conditions imposed on the shape of the graph $G$, weights $w_e$ of its edges $e$, the given set $\{A_1,\dots, A_k\}$ of nodes and on the probability $p_{ij}$ (for $i<j$) of the random choice of each pair $\{A_i, A_j\}$ of the given nodes I can propose a straightforward algorithm, which has a complexity polynomial with the respect to the number of nodes of the graph $G$.

First of all we do a preprocessing which calculates the weighted distance $d_w(v,u)$ between each pair $v$ and $u$ of nodes of the graph $G$. This can be done recursively as follows. Let $v$ be a leaf of the graph $G$. Calculate the weighted distances between each pair of nodes of the induced graph $G - v$. Let $u$ be a unique neighbor of the node $v$. For each node $u’$ of the graph $G- v$ put $$d_w(u’,v)= d_w(u’,u)+w(u,v).$$

Now the expectation which you are asking for is

$$\sum_{1\le i<j\le K} p_{ij}d_w(A_i,A_j).$$

Update. In particular, if “2 nodes are taken at random from these nodes” means that the pair $\{A, B\}$ of the given (not necessarily distinct) nodes is constructed by independently picking nodes $A$ and $Bj$ such that each of them has a probability $r_i=P\{A=A_i\}= P\{B=B_i\}$ (in particular, for the uniform distribution $r_i=1/K$) then $p_{ii}=r_i^2$ (anyway, we don’t sum weighted distances $d_w(A_i,A_j)$ because they are zero) and $p_{ij}=2r_ir_j$ if $i<j$.

Answer 2

If your question involves two different people picking the two nodes, then every pair $(u,v)$ that you pick should be treated as an ordered pair. So you should add the weights between every pair and multiply it by $2$. This will give you the numerator. Also, the denominator will be $(2*{n \choose 2} + n)$. The additional $n$ corresponds to the fact that both of them might choose the the same node(in such cases $d(u,v)$ will be $0$, so they won't affect the numerator). For the above example data, your numerator will be $87*2=174$ and the denominator will be $2*15 + 6 = 36$. This, on reduction to simplest form will give you ${29 \over 6}$.