Distribution/expected length of the shortest path in infinite random geometric graphs

Consider an infinite random geometric graph $G(\rho,d)$ in which vertices are uniformly and independently scattered over the 2D plane with density $\rho$ and edges connect the vertices that are closer than $d$.

What is the distribution/expected value of the length of the shortest path from a vertex $v_0$ to another vertex $v_1$ which is $k$ hops faraway?

Note:

We know that the length of the edges follow the following PDF:

$$
f(l)=
\begin{cases}
\frac{2 l}{d^2} \;\quad l \le d \\
0 \qquad\; l > d
\end{cases}
$$

However, I guess the expected length of the shortest path is not simply $k \times$ the expected length of the edges because in a shortest path longer edges are more likely to be chosen, right?

Answer

Attribution
Source : Link , Question Author : Helium , Answer Author : Community

Leave a Comment