4
$\begingroup$

In an MO question here @IosifPinelis shows that the ratio of expectations $\mathbb{E}(A)/\mathbb{E}(B)$ of the largest (say $A$) and smallest (say $B$) gap resulting from $n$ uniform random variables on $(0,1]$ tends to infinity as $n\rightarrow \infty.$

In an earlier question, linked in the above question, he also showed that $\mathbb{E}(A/B)$ equals to infinity for all $n>2.$

I have a related question (thanks @YuvalPeres for your comments):

Let $G_{(1)}$ be the smallest, $G_{(2)}$ be the second smallest, etc. and let $G_{(n)}$ be the largest gap.

What is the fastest growing sequence $\ell(n)$ such that $$\lim_{n\rightarrow \infty} \frac{\mathbb{E} G_{(\ell(n))}}{\mathbb{E} G_{(1)}}<\infty?$$

Edit: Simulations seem to confirm the proof by @MattF. that $\ell(n)=2$ yields $7/3.$

$\endgroup$
16
  • 1
    $\begingroup$ @kodlu : I guess you wanted something else, because the probability under the limit sign is just $1$. $\endgroup$ Aug 26, 2019 at 13:49
  • 1
    $\begingroup$ Perhaps any unbounded $\ell(n)$ violates this condition. $\endgroup$
    – user44143
    Aug 26, 2019 at 23:05
  • 1
    $\begingroup$ I think Matt's intuition about unbounded $\ell(n)$ is right. Moreover, because for the density of the standard exponential distribution we have $e^{-x}\sim1$ as $x\downarrow0$, I think $EG_{(\ell(n))}/EG_{(1)}\sim\ell(n)$ if $1\le\ell(n)=o(n)$. (Think of a histogram for a sample from the exponential distribution. Also, recall that, as noted in the linked answer, the gaps $G_i$ are proportional to iid random variables $H_i$ each having the exponential distribution.) Also, I think you meant $EG_{(\ell(n))}$ in place of $EG_{\ell(n)}$. $\endgroup$ Aug 27, 2019 at 2:49
  • 1
    $\begingroup$ In the case $n=4$, we can use math.stackexchange.com/questions/2631988/… to get an exact result of $EG_2/EG_1=(7/48)/(1/16)=7/3$, by EG1 = Integrate[Min[1 - ma, (1 - u) (ma - mi), u (ma - mi), mi] 12 (ma - mi)^2, {ma, 0, 1}, {mi, 0, ma}, {u, 0, 1}]; EG2 = Integrate[Min[ma - mi, u ma + (1 - u) mi, (1 - u) ma + u mi, 1 - (ma - mi), 1 - (u ma + (1 - u) mi), 1 - ((1 - u) ma + u mi)] 12 (ma - mi)^2, {ma, 0, 1}, {mi, 0, ma}, {u, 0, 1}] - EG1 $\endgroup$
    – user44143
    Aug 27, 2019 at 3:26
  • 2
    $\begingroup$ @MattF. : The value $7/3$ for $EG_{(2)}/EG_{(1)}$ looks plausible to me: it is somewhat close to the limit $2$ (which latter is what my conjecture predicts for $n\to\infty$) but also a bit greater than $2$ (which reflects the fact that the exponential density is decreasing on $(0,\infty)$ and hence the sample values tend to be sparser farther away from $0$). $\endgroup$ Aug 27, 2019 at 4:31

1 Answer 1

1
$\begingroup$

It is now shown that for $i=1,\dots,n-1$ \begin{equation}\label{eq:EG} E G_{n-1:i}=\frac{H_{n-1}-H_{n-1-i}}{n+1}, \end{equation} where $G_{n-1:i}$ is the $i$th smallest value among the gaps $G_1,\dots,G_{n-1}$ defined in the linked post and \begin{equation*} H_k:=1+\frac12+\dots+\frac1k \end{equation*} is the $k$th harmonic number, with $H_0:=0$.

In particular, this confirms my conjecture made in an above comment that $$r_{n-1:i}:=\frac{E G_{n-1:i}}{E G_{n-1:1}}\sim i $$ if $1\le i=o(n)$.

It also follows that $r_{4-1:2}=5/2$ and $r_{5-1:2}=7/3$. This seems to differ a bit from Matt's results, perhaps because Matt used notations differing from those in the linked post.

$\endgroup$

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.