10
$\begingroup$

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?

More precisely: if I sample $n$ points uniformly at random in the unit square, then it is known that as $n$ becomes large, the shortest path $L_n$ through these points satisfies

$$L_n/\sqrt{n} \to \beta \approx 0.71~,$$

with probability one, where $\beta$ is the "Euclidean TSP constant". My question is: for a given (small) length $\ell$, say $\ell = c\sqrt{n}$ for small $c<\beta$ , does a non-trivial lower bound for $\Pr(L_n \leq \ell)$ exist?

$\endgroup$
8
  • $\begingroup$ Maybe I'm just dense, but I don't understand what you mean by the shortest path through a set of points. $\endgroup$
    – user21349
    Oct 6, 2014 at 19:37
  • 2
    $\begingroup$ What do you consider nontrivial? $\endgroup$
    – Igor Rivin
    Oct 6, 2014 at 19:56
  • $\begingroup$ @IgorRivin, the bound by Robert Israel looks very nice to me. Would be nice to know if there's anything even tighter. $\endgroup$ Oct 6, 2014 at 22:11
  • $\begingroup$ Bob Israel's bound is very nice, but I am quite sure that it is not tight (I am sure he would agree...) $\endgroup$
    – Igor Rivin
    Oct 6, 2014 at 22:28
  • 1
    $\begingroup$ Here is a study (not sure what drugs Dropbox used to generate the previous link in the deleted answer): dl.dropboxusercontent.com/u/5188175/tsp.pdf $\endgroup$
    – Igor Rivin
    Oct 7, 2014 at 12:47

4 Answers 4

5
$\begingroup$

Robert Israel proved a lower bound proportional to $n^2 (c/\beta)^{2n}$. I claim an upper bound of much the same shape, $O(n(Bc)^{2n})$, for some constant $B > \beta^{-1}$, namely $\sqrt{\pi e/2} = 2.066\ldots$ (while $1/\beta$ is about $1.41$). In fact I claim that the expected number of paths of length less than $c \sqrt{n}$ is $O(n(Bc)^{2n})$, which will imply the same bound for the probability that this number is at least $1$.

It will be convenient to use not $n$ but $n+1$ points $P_0,P_1,\ldots,P_n$ in the unit square $\cal S$ (this change affects only the $O(\cdot)$ constant), so that a path consists of $n$ segments. Given $A$, the expected number of paths of length $\leq A$ is then $(n+1)!$ times the probability that the path $P_0 P_1 \cdots P_n$ has length $\leq A$. But this probability is the volume of a region in ${\cal S}^{n+1}$ that's less than the volume of the region of $(P_0,P_1,\ldots,P_n) \in ({\bf R}^2)^{n+1}$ satisfying $P_0 \in \cal S$ and $\sum_{i=1}^n |P_i - P_{i-1}| \leq A$ (without requiring also $P_i \in \cal S$ for $i>0$). By repeated application of Cavalieri's principle, this equals the volume of the region of $(v_1,\ldots,v_n) \in ({\bf R}^2)^n$ satisfying $\sum_{i=1}^n |v_i| \leq A$. Taking $x_i = |v_i|$, we see that this volume is $(2\pi)^n$ times the integral of $x_1 \cdots x_n$ over the simplex $x_i \geq 0, \sum_{i=1}^n x_i \leq A$; and this is an elementary Dirichlet integral that evaluates to $A^{2n} / (2n)!$.

In conclusion, the probability that there is a path of length at most $A$ is bounded above by $$ \frac{(n+1)!}{(2n)!} (2\pi A^2)^n. $$ Now for large $n$ Stirling's approximation gives $(n+1)!/(2n)! \sim 2^{-1/2} n (e/4n)^n$. Hence if $A = c \sqrt{n}$ the factors of $n^n$ cancel out and our bound is asymptotically proportional to $n (Bc)^{2n}$, QED.

$\endgroup$
2
  • $\begingroup$ That is pretty awesome. So, the fact that this is an upper bound comes from the fact that the region whose volume you take doesn't have to lie in $\mathcal{S}^{n}$? $\endgroup$ Oct 7, 2014 at 5:03
  • $\begingroup$ Thanks. Yes, the restriction to ${\cal S}^n$ is one reason (though a typical path of total length $c\sqrt{n}$ has a good chance of staying in $\cal S$ anyway); another is that there may be more than one short path (for starters they always come in pairs because the path can be traversed in either direction), so the probability that there's at least one short path might be significantly less than the expected number of short paths. $\endgroup$ Oct 7, 2014 at 5:08
4
$\begingroup$

Let $A$ be the event that all points are actually in a square of side $c/\beta$. Then $\text{Pr}(L_n \le c \sqrt{n}|A) = \text{Pr}(L_n \le \beta \sqrt{n})$. Since $P(A) \sim n^2 (c/\beta)^{2n-2} (1-c/\beta)^2 $ and $\text{Pr}(L_n \le \beta \sqrt{n}) = \Omega(1)$, we have $\text{Pr}(L_n \le c \sqrt{n}) = \Omega(n^2 (c/\beta)^{2n})$.

$\endgroup$
2
$\begingroup$

The distribution of the shortest path through $n$ points

The following 4 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20, 50$ and 100 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

  • $n = 3$:

(source)

  • $n = 20$:

(source)

  • $n = 50$:

(source)

  • $n = 100$:

(source)

Even when $n = 100$, the stated asymptote of $0.71 \sqrt{n}$ leaves a substantial component of the distribution in the left tail, to the left of the asymptote. Depending on whether you are interested in large or small values of $n$, an exercise such as the above will provide a simple way to select your desired $c$, to minimise any left-tail probability.


It is also apparent that using the distribution (or simulated distribution) is more helpful than just looking at expected values (or asymptotic expected values, or bounds on expected values of shortest paths), which is what most of the literature seems to do. For instance, the following diagram compares:

  • Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

  • Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

  • The actual expected shortest path [ round dots ]

  • The OP's stated asymptote: $.71 \sqrt{n}$

(source)

... but, for your problem, you really should be looking at the distribution ... not just the first moment.

$\endgroup$
1
$\begingroup$

It seems that even the constant in front of the $\sqrt{n}$ is not known, but there are experimental results which seem to describe the distribution pretty well. In particular, it seems that the variance of the shortest path (however they compute it) is essentially $0.$ Anyway, look at the linked paper and the references therein.

$\endgroup$
3
  • 4
    $\begingroup$ Something's wrong with the URL for "experimental results": it takes me to a Dropbox screen that shows eleven images, only a few of which are data plots (none of them seems relevant), and a few of the other images are quite NSFW. $\endgroup$ Oct 7, 2014 at 5:40
  • $\begingroup$ @NoamD.Elkies Good, I am not sure where the other link came from (it certainly did not have the right form for a DB link). Sorry about the confusion. $\endgroup$
    – Igor Rivin
    Oct 7, 2014 at 14:57
  • $\begingroup$ A pointer that is likely to be longer-lived is dx.doi.org/10.1016/j.ejor.2006.12.066 i.e. Vig and Palekar, EJOR 186 (2008). $\endgroup$ Oct 10, 2014 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.