**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**.

isvery 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