Say I sample $n$ points uniformly at random in the unit square, and then I look for the shortest path through $\sqrt{n}$ of those points (rounding up, say). What happens to the length of this path as $n\rightarrow\infty$? Does it increase, decrease, or converge (or "none of the above")?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ I think it should decrease, even if it were n^c many points rounded up, for fixed positive c less than 1. Set d to satisfy 2d +c=1, and consider a kxk square partition for k = floor(n^d). One of those pieces will have n^c points in it, and the length of the path should be O(n^-d), or some appropriate power. $\endgroup$– The Masked AvengerCommented Jul 15, 2014 at 6:50
-
$\begingroup$ Hmm. Maybe asking c greater than 1/2 is ambitious. I still think it should converge for c=1/2. $\endgroup$– The Masked AvengerCommented Jul 15, 2014 at 6:57
-
16$\begingroup$ The quantity you're interested in is certainly bounded, because the length of the shortest path through all $n$ points (i.e. the TSP tour) has a length that is bounded by $\sqrt{2n} + 1.75$, as proven in [1], which we can approximate as simply $\sqrt{2n}$ since $n$ is large. If you take this tour and break it into segments consisting of $\sqrt{n}$ points each, you know that one of those segments has length of at most $\sqrt{2}$. [1] Few, L. "The shortest path and the shortest road through n points." Mathematika 2.02 (1955): 141-144. $\endgroup$– John Gunnar CarlssonCommented Jul 15, 2014 at 18:08
-
1$\begingroup$ Using the known TSP bound that John Gunnar Carlsson mentioned, one can probably get a heuristic bound by first asking what the typical size is of the smallest square that countains $\sqrt{n}$ points in the unit square. $\endgroup$– Alex R.Commented Jul 15, 2014 at 19:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
The following is a partial answer.
It is useful to rescale. So think of a Poisson process in the plane and consider the box of side $n$. There will be roughly $n^2$ points there. Let $A_{[a,b]}$ be the random variable you described, but in the box $[a,b]^2$. You are really interested in $A_{[0,n]}/n$. You have essentially that $A_{[0,2n]}\leq A_{[0,n]}+A_{[n,2n]}$ (there is an error due to the segment connecting the path in the first box and the path in the second; probably that error is negligible but I did not check that). An application of the sub-additive ergodic theorem then gives that $A_{[0,n]}/n$ converges to a deterministic number. Going from a Poisson number of particles to a fixed number of points is routine.
The above argument becomes rigorous if you ask your path to start at $(0,0)$ and end at $(1,1)$ and go through $\sqrt{n}$ points.
A simple bound (independent of the above reasoning) is obtained by looking at the longest (in terms of number of points) increasing path. This is equivalent to the length of the longest increasing subsequence of a random permutation, and the number of points is $(2+o(1))\sqrt{n}$. The length of the increasing path going through all these points is roughly $\sqrt{2}$. You can of course take only $\sqrt{n}$ of these points, I do not think the length will change much. Interestingly, the constant $\sqrt{2}$ shows up again, as in John's answer. I suspect this might be the correct answer. Did you try to simulate?
answered Jul 16, 2014 at 0:23
-
1$\begingroup$ Actually, the $\sqrt{2}$ is a fairly weak upper bound and can be improved by using the Beardwood-Halton-Hammersley theorem, which says that for a sufficiently large set of uniform samples in the unit square, we have $L_n/\sqrt{n} \rightarrow \kappa$ (almost surely), where $L_n$ represents the TSP tour of $n$ points, and $\kappa$ is the "TSP constant" which is known to satisfy $0.6250\leq\kappa\leq0.9204$, and it is conjectured that $\kappa \approx 0.7124$. This is described in formulas (18) and (19) of mathworld.wolfram.com/TravelingSalesmanConstants.html. $\endgroup$ Commented Jul 16, 2014 at 16:53
-
2$\begingroup$ (continued) This tells us that $\kappa$ (whatever its value is) is also a valid bound for the quantity of interest, which is less than $\sqrt{2}$. $\endgroup$ Commented Jul 16, 2014 at 16:53
-
$\begingroup$ John's argument applies to a worst case scenario. For what it's worth, I'd be quite surprised if with the additional randomness from the OP, the quantity in question didn't go to zero. (For example, this would follow if it could be shown that suitably selected $n/4$ points cluster in a square of sidelength $q$, for a fixed $q<1/2$.) $\endgroup$ Commented Jul 16, 2014 at 18:28
-
1$\begingroup$ In fact, for the modified problem I defined (path starting at (0,0) and ending at (1,1), $\sqrt{2}$ is a trivial lower bound and also an upper bound from the LIS analysis. So for that modified problem, $\sqrt{2}$ is the correct answer. $\endgroup$ Commented Jul 17, 2014 at 2:46
$\begingroup$
$\endgroup$
8
The comment by John Gunnar Carlsson and answer by Ofer Zeitouni give an upper bound. Comments by two people suggested that the actual behavior should be to decrease to $0$. In fact, there is a positive lower bound: The probability that there is a path through $\sqrt{n}$ points of length less than $0.214$ goes to $0$ as $n\to \infty$.
The idea is that if we pick a random path, the probability that this path is short is extremely small. Then we use the union bound over all possible paths of length $\sqrt{n}$ out of $n$ points.
It suffices to consider points chosen from a fine grid, or equivalently a large square subset of $\mathbb Z^2$, and to use the $L^1$ metric instead of $L^2$.
Roughly how many paths are there in $\mathbb Z^2$ on $m$ points of $L^1$ length at most $d$, where $d \gg m$, and we start at a fixed point? We can divide the distance into $m-1$ steps plus the unused distance. The number of ways to do this is ${d+m-1 \choose m-1} \sim d^{m-1}/(m-1)! = o\left(\left(\frac{ed}{m}\right)^{m-1}\right)$. For any such division of distances, we can choose a lattice point on each "circle." There are $4r$ lattice points of distance $r \gt 0$ from the origin and for $d \gg m$ we can increase the count by making each distance nonzero. By the AM-GM inequality, the count of these choices is at most the case where they are all equal, $\left(\frac{4d}{m-1}\right)^{m-1}$. So, the number of paths is
$$\begin{eqnarray} & o\left(\left(\frac{ed}{m}\right)^{m-1} \left( \frac{4d}{m}\right)^{m-1}\right) \newline &=o\left( \left(\frac{2\sqrt{e}d}{m} \right)^{2m-2}\right).\end{eqnarray}$$
The total number of paths in $\lbrace 1, 2, ..., d/c \rbrace^2$ of $m$ lattice points starting at a fixed point is $(\frac{d}{c})^{2m-2}$. So, the probability that a random path of $m$ points has $L^1$ length at most $c$ times the grid dimension is
$$o\left( \left(\frac{2\sqrt{e}c}{m} \right)^{2m-2}\right). $$
Let $n=m^2$. The number of paths of length $m$ among $n$ points is $n(n-1)\cdots(n-m+1) \lt m^{2m}$. So, if we choose $c$ so that the probability is $o(m^{-2m})$ then the probability that there is a path that short in the $L^1$ norm goes to $0$ as $n\to \infty$. This is accomplished by setting $c \lt \frac{1}{2\sqrt{e}}$. Since the $L^2$ norm is smaller by at most a factor of $\sqrt{2}$, for any $c \lt \frac{1}{\sqrt{8e}} =0.2144$ the probability that there is a path whose Euclidean length is shorter than $c$ goes to $0$ as $n\to \infty$.
While the constant might be improved, the probability bound is good enough to say that if we add the points one by one, then almost surely only finitely many times will there be a path on $\sqrt{n}$ points of length smaller than $c$.
answered Jul 17, 2014 at 1:20
-
$\begingroup$ This is a nice analysis, but the final step left me mildly confused. You seem to be assuming that the actual experiment (uniformly distributed points, then pick the shortest path) can be approximately described by instead imposing a uniform distribution on the paths. Is that clear? $\endgroup$ Commented Jul 17, 2014 at 1:50
-
$\begingroup$ @Christian Remling: If you pick $n$ points IID uniform, then each of the roughly $n^{\sqrt{n}}$ possible paths is uniformly distributed, just as though you only picked those $\sqrt{n}$ points. They aren't independent, but the union bound/linearity of expectation does not depend on independence. We can count the expected number of paths of length less than $0.214$ and find it is asymptotically much less than $1$. Thus, the probability that the shortest path is shorter than $0.214$ is small. $\endgroup$ Commented Jul 17, 2014 at 7:35
-
$\begingroup$ By the way, it looks nicer to do this analysis with integrals instead of sums, integrating over a simplex. The measure of a circle is still linear. I used a discrete sum to avoid worrying about the Jacobian. Also, the actual integral can be done instead of using the AM-GM inequality, but I think it is a little tricky and it would just affect the constant. One variation of that integral was on the Putnam exam. $\endgroup$ Commented Jul 17, 2014 at 7:43
-
1$\begingroup$ @JohnGunnarCarlsson: I think I can answer this: it's the number of ways to partition the total distance $d$ into $m$ individual steps, where a step can be zero (this accounts for the extra $m-1$ on the top). This isn't the number of paths yet, it's the number of possible distance sequences we can encounter as we travel along a path of length $\le d$. $\endgroup$ Commented Jul 17, 2014 at 22:28
-
1$\begingroup$ @John Gunnar Carlsson: It was from allocating the total distance $d$ into $m$ bins consisting of the $m-1$ steps and the unused distance. Equivalently, sum over the ways to allocate distances $0,1,2,...,d$ into $m-1$ bins. If $d=10$ then the path $(0,0)\to(1,1)\to(1,1)\to(3,4)$ would correspond to steps of $L^1$ sizes $2,0,5$ with $3$ unused. Allocating $d$ objects into $m$ bins is equivalent to choosing $m-1$ separators out of $d+m-1$ objects and separators. $\endgroup$ Commented Jul 17, 2014 at 22:30