4
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

$\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).

So,
\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$.

$\endgroup$
4
  • $\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$ Commented Aug 26, 2019 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$ Commented Aug 26, 2019 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$ Commented Aug 26, 2019 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$ Commented Aug 26, 2019 at 13:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .