Let $Z_1,\dots,Z_n$ be iid random variables (r.v.'s) each uniformly distributed on $[0,1]$. Let $Z_{n:1}\le\cdots\le Z_{n:n}$ be the corresponding order statistics. For $i=1,\dots,n-1$, let $G_i:=Z_{n:i+1}-Z_{n:i}$, the $i$th spacing/gap. Let \begin{equation} A_n:=G_{n-1:1}=\min_{i\le n-1}G_i,\quad B_n:=G_{n-1:n-1}=\max_{i\le n-1}G_i. \end{equation}

In comments at Expected value ..., Brendan McKay asked if $EB_n/EA_n\to\infty$ (as $n\to\infty$), and Anthony Quas asked if $med(B_n/A_n)\to\infty$, where $med$ denotes the median. The purpose here is to answer these questions (affirmatively).


$\newcommand{\eD}{\overset{\text{D}}\to} \newcommand{\D}{\overset{\text{D}}=}$ As was noted on the linked MO page Expected value ..., the gaps $G_1,\dots,G_{n-1}$ between the adjacent points are jointly distributed as $\frac{H_1}{H_1+\dots+H_{n+1}},\dots,\frac{H_{n-1}}{H_1+\dots+H_{n+1}}$, where the $H_i$'s are iid standard exponential random variables (r.v.'s); see e.g. Theorem 6.6(c).

\begin{equation*} B_n\D M_n:=\frac{H_{n-1:n-1}}{S_{n+1}}=\frac1{S_{n+1}}\,\max_{i\le n-1}H_i, \end{equation*} where $\D$ means the equality in distribution, and $S_{n+1}:=H_1+\dots+H_{n+1}$. Next, for any real $x$ and all large enough natural $n$, \begin{multline*} P(H_{n-1:n-1}-\ln n<x)=P(\max_{i\le n-1}H_i<x+\ln n) =P(H_1<x+\ln n)^{n-1} \\ =(1-e^{-x-\ln n})^{n-1} \to e^{-e^{-x}}=P(Y<x) \end{multline*} for some r.v. $Y$, so that \begin{equation*} Y_n:=H_{n-1:n-1}-\ln n\eD Y, \end{equation*} where $\eD$ means the convergence in distribution. Also, by the strong law of large numbers (SLLN) $\frac n{S_{n+1}}\to1$ almost surely and hence in distribution. So, \begin{equation*} \frac n{\ln n}\,B_n\D\frac n{\ln n}\,M_n=\frac n{\ln n}\,\frac{H_{n-1:n-1}}{S_{n+1}} =\frac{Y_n+\ln n}{\ln n}\,\frac n{S_{n+1}}\eD1. \tag{1} \end{equation*} So, by the Fatou lemma, \begin{equation*} \liminf_n\frac n{\ln n}\,EB_n\ge1. \end{equation*}

On the other hand,
\begin{equation*} A_n\le G_1, \end{equation*} and $G_1$ has the beta distribution with parameters $1,n$. So,
\begin{equation*} EA_n\le EG_1=\frac1{n+1}. \end{equation*} So, \begin{equation*} \liminf_n\frac{EB_n}{EA_n}\ge\lim_n\frac{\ln n}n\,(n+1)=\infty. \end{equation*} Thus, it is confirmed that $EB_n/EA_n\to\infty$.

Also, \begin{equation} \frac{B_n}{A_n}\ge \frac{B_n}{G_1} \D\frac{nB_n}{H_1}\,\frac{S_{n+1}}n\eD\infty, \end{equation} because, by (1), $nB_n\eD\infty$ and, by the SLLN, $\frac{S_{n+1}}n\eD1$. Thus, $\frac{B_n}{A_n}\eD\infty$ and hence indeed $med(B_n/A_n)\to\infty$.

  • $\begingroup$ It’s interesting that you did the work on the length of the longest interval instead of the shortest one. You show the longest one is $\log n$ times the average gap; while it’s also true that the shortest one is about $1/n$ times the shortest gap (so I would have expected that to be the easier place to look for a big ratio). $\endgroup$ – Anthony Quas Aug 26 '19 at 2:43
  • $\begingroup$ What you are saying is of course correct (I gather you meant "$1/n$ times the average gap"), and I did have that in mind. My preference, however, was to give an answer as simple and short as possible to both questions at once. Since I wanted to use the straightforward Fatou lemma, it looked like I had to work mainly with $B_n$ rather than $A_n$. $\endgroup$ – Iosif Pinelis Aug 26 '19 at 3:48
  • 1
    $\begingroup$ Fair enough. I was surprised that the largest gap was that long, while the shortest gap feels like the birthday paradox. $\endgroup$ – Anthony Quas Aug 26 '19 at 4:34
  • $\begingroup$ I too was surprised how short the shortest gap is. Was not intuitive to me at first, even though formulas tell me that right away. $\endgroup$ – Iosif Pinelis Aug 26 '19 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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