This can be viewed as a toy version of [this](https://mathoverflow.net/questions/176158/shortest-path-through-sqrtn-points-out-of-n) wonderful question. (I'm removing the TSP component, and I'll zoom in on the statistical part.)


Let $X\_1,\ldots, X\_n$ be iid, with uniform distribution in $[0,1]$. Let $\ell\_n$ be the length of the shortest subinterval of $[0,1]$ that contains $n^{\alpha}$ of the points $X\_j$, with $0<\alpha<1$. What can we say about the distribution of the normalized length $L\_n=n^{1-\alpha}\ell\_n$? For example, what are the asymptotics of $EL\_n$?


As a warm-up of sorts, we can in fact also consider the shortest interval with $cn$ points and $L\_n=\ell\_n/c\,$; the answers to the linked question seem to suggest that $EL\_n\to 1$ in this case.


(This sounds like it should be well studied, but I couldn't locate anything on the internet.)



Clusters of uniformly distributed random points
As in the $2$-dimensional problem linked, the probability that a particular interval much shorter than $n^{\alpha-1}$ contains $n^\alpha$ points is very small, and we can use the union bound over a small set of such intervals to bound the probability that the shortest interval containing $n^\alpha$ points is small. This implies $EL\_n \to 1$ and more precise statements about the difference with $1$.


Suppose we want to bound the probability that $L\_n \gt 1-2\epsilon$. Consider intervals of length $(1-\epsilon)n^{\alpha-1}$ starting at $0, \epsilon n^{\alpha-1}, ...$. There are fewer than $n^{1-\alpha}/\epsilon$ such intervals and every interval of length $(1-2\epsilon)n^{\alpha-1}$ fits into one of these. Let us bound the probability that there are $n^\alpha$ points in a particular interval of length $(1-\epsilon)n^{\alpha-1}$ and then use the union bound.


The number of points in an interval of length $(1-\epsilon)n^{\alpha-1}$ is a binomial random variable with mean $(1-\epsilon)n^\alpha$ and standard deviation under $\sqrt{n^\alpha}$. So, having $\epsilon n^\alpha$ points more than average is more than $\epsilon n^{\alpha/2}$ standard deviations above the mean. A normal approximation would suggest that the probability drops rapidly as $n$ increases. To be rigorous we can use a Chernoff bound. For $0 \lt \delta \lt 1,$


$\textrm{Prob}[\textrm{Binom} \ge (1+\delta)\mu] \le \exp(-\mu \delta^2/3).$


We can choose $\delta = \epsilon$, since $(1+\epsilon) \mu = (1+\epsilon)(1-\epsilon)n^\alpha = (1-\epsilon^2)n^\alpha \lt n^\alpha$.


$\textrm{Prob}[\textrm{Binom} \ge n^\alpha] \le \exp (-c\_\epsilon n^\alpha).$


So, the probability that the shortest interval containing $n^\alpha$ points is shorter than $(1-2\epsilon)n^{\alpha-1}$ is at most $\frac{n^{1-\alpha}}{\epsilon}\exp (-c\_\epsilon n^\alpha).$ As $n\to\infty$ the exponential term dominates and the probability drops to $0$. As $n\to \infty$, $L\_n$ is close to $1$ with high probability. 


