Shortest path through $\sqrt{n}$ points out of $n$ 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")?
 A: 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$.
A: 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?
