Probabilistic Behavior of Shortest Paths Over Unbounded Regions

Abstract:

Let $k^>^1$ and $P$ be a probability distribution over $R sup k$ with
all its absolute $mu$-th moments being finite for some $mu ^ >
^k/(k^-^1)$. Let $v sub 1$,$v sub 2$, $cdot cdot cdot$ be an infinite
sequence of random points, each independently distributed according to
$P$. It is shown that the length of the shortest traveling-salesman's
tour through $v sub 1$,$v sub 2$,$cdot cdot cdot$,$v sub n$ is, for
large $n$, almost surely around $alpha p n sup (k-1)/K$ for some
constant $alpha p$. This proves a conjecture of Beardwood, Halton and
Hammersley (Proc. Camb. Phil. Soc. 55 (1959), 299-327).