8
$\begingroup$

This can be viewed as a toy version of this 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.)

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

This 1965 paper of Naus contains formulas for the exact probabilities. Turning them into the asymptotic results you want might take a little effort but since Naus' paper is cited in at least 255 places there is fair chance someone did the work already.

$\endgroup$
4
  • $\begingroup$ MathSciNet lists 4 citations of Naus's paper. $\endgroup$ Jul 17, 2014 at 6:38
  • $\begingroup$ Thanks for the reference; in fact, this follow-up paper amstat.tandfonline.com/doi/abs/10.1080/… seems more relevant still, but even this seems a far cry from answering my question. $\endgroup$ Jul 17, 2014 at 7:13
  • $\begingroup$ @ChristianRemling: for the most part, MathSciNet only lists citations from papers indexed in MathSciNet beginning sometime in the 1990s, so it misses almost all citations older than that and many newer ones as well. (It looks like Naus's paper has lots of citations from papers in other fields.) $\endgroup$ Jul 17, 2014 at 15:32
  • $\begingroup$ @MarkMeckes: This is a valid point, but a quick glance at the actual link also confirms that almost all the papers that cite Naus are from other disciplines (medicine for example), as you pointed out. Be that as it may, the formulae seem to be getting out of hand as $n\to\infty$, and I'd really love to have a more explicit answer to my question (about the large $n$ asymptotics), if possible. $\endgroup$ Jul 17, 2014 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.