The distribution of the shortest path through $n$ points 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?
 A: 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.
A: 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})$.  
A: 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.
A: 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.
