9
$\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$
  • $\begingroup$ Maybe I'm just dense, but I don't understand what you mean by the shortest path through a set of points. $\endgroup$ – Ben Crowell Oct 6 '14 at 19:37
  • 2
    $\begingroup$ What do you consider nontrivial? $\endgroup$ – Igor Rivin Oct 6 '14 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$ – Will Schaefer Oct 6 '14 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 '14 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 '14 at 12:47
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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Will Schaefer Oct 7 '14 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$ – Noam D. Elkies Oct 7 '14 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})$.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Noam D. Elkies Oct 7 '14 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 '14 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$ – András Salamon Oct 10 '14 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.