6
$\begingroup$

Question: Let $X_1, \ldots ,X_n$ be $n$ iid uniformly distributed random variables, i.e., $X_j \sim \mathcal{U}(0,1)$ for each $j=1,\ldots ,n$. What is the PDF of the maximal distance between to nearby elements? More formally, if we denote $X_{(k)}$ as the location of the $k$-th smallest element, what is the PDF of $\max\limits_{k=1,\ldots ,n-1} d_k$, where $d_k := X_{(k+1)} - X_{(k)}$.

The motivation for this question is approximation and interpolation on random grids.

What I know: Each $X_{(k)}$ is distributed by a Beta distribution, but so far I was not able to go on from there.

$\endgroup$
  • 1
    $\begingroup$ The keyword is spacings. A detailed answer to an apparently very similar question (for $\max_{0\le k\le n}d_k$ with $d_0:=X_{(1)}$ and $d_n:=1-X_{(n)}$) is given at stats.stackexchange.com/questions/162560/…. Lots of other relevant information can be found there. $\endgroup$ – Iosif Pinelis Feb 19 '18 at 16:24
4
$\begingroup$

Let us just adapt the reasoning at stats-SE. Let $d_0:=X_{(1)}$ and $d_n:=1-X_{(n)}$. Let $\Delta_j:=d_{j-1}$ for $j\in[n+1]:=\{1,\dots,n+1\}$, so that \begin{equation} \max_{1\le k\le n-1}d_k=\max_{2\le j\le n}\Delta_j. \end{equation} The first key observation at stats-SE is that the $\Delta_j$'s are exchangeable, since $(\Delta_1,\dots,\Delta_{n+1})$ equals $(E_1,\dots,E_{n+1})/S$ in distribution, where $E_1,\dots,E_{n+1}$ are iid standard exponential r.v.'s and $S:=E_1+\dots+E_{n+1}$ (see e.g. formula (2.2.1)). The second key observation at stats-SE is that for any $J$ in the set $\binom{[n+1]}r$ of subsets of cardinality $r$ of the set $[n+1]$ and any $x\ge0$ \begin{equation*} P(\Delta_j>x\ \forall j\in J)=P(\Delta_j>x\ \forall j\in[r])=(1-rx)_+^n, \end{equation*} where $u_+^n:=\max(0,u)^n$.

So, by the inclusion-exclusion formula, we obtain the cdf of $\max_{1\le k\le n-1}d_k$: \begin{align*} P(\max_{1\le k\le n-1}d_k\le x)&=1-P(\max_{2\le j\le n}\Delta_j> x) \\ &=1-P(\max_{1\le j\le n-1}\Delta_j> x) \\ &=\sum_{r=0}^{n-1}(-1)^r \sum_{J\in\binom{[n-1]}r}P(\Delta_j>x\ \forall j\in J) \\ &=\sum_{r=0}^{n-1}(-1)^r \binom{n-1}r (1-rx)_+^n \end{align*} for all $x\ge0$.

Addition in response to a comment by the OP: Let \begin{equation*} M_n:=\max_{1\le k\le n-1}d_k. \end{equation*} Then, using the above expression for the cdf of $M_n$, we have
\begin{multline*} E M_n^2=\int_0^\infty 2x\,P(M_n>x)dx=\sum_{r=1}^{n-1}(-1)^{r-1} \binom{n-1}r \int_0^{1/r} 2x\,(1-rx)^n\,dx \\ = \sum_{r=1}^{n-1}(-1)^{r-1} \binom{n-1}r\,\frac{2}{r^2(n+2)(n+1)} =\frac{\psi(n)^2+2 \gamma \psi(n)- \psi'(n)+\pi ^2/6+\gamma ^2}{(n+2)(n+1)}, \end{multline*} where $\gamma$ is the Euler constant and $\psi:=\Gamma'/\Gamma$ is the digamma function; the latter expression for $E M_n^2$ was obtained by using a computer algebra package. We have $\psi(n)\sim\ln n$ and $\psi'(n)\to0$ as $n\to\infty$ wiki: Polygamma function, whence \begin{equation*} E M_n^2\sim\frac{\ln^2 n}{n^2}. \end{equation*}


Alternatively, without using a computer algebra package, we can obtain exact and asymptotic expressions for $E M_n^2$ as follows: using the formula $\frac1{r^2}=\int_0^\infty xe^{-rx}dx$ for $r>0$, then using the binomial formula, then making the substitution $u=1-e^{-x}$, and then integrating by parts, we have \begin{multline*} \frac{(n+2)(n+1)}{2}\,E M_n^2 = \sum_{r=1}^{n-1}(-1)^{r-1} \binom{n-1}r\,\frac1{r^2} = -\int_0^\infty x\,dx\sum_{r=1}^{n-1} \binom{n-1}r\,(-e^{-x})^r \\ = \int_0^\infty x\,dx\,(1-(1-e^{-x})^{n-1}) = -\int_0^1\ln(1-u)\,\frac{1-u^{n-1}}{1-u}\,du \\ = -\sum_{j=0}^{n-2}\int_0^1\ln(1-u)\,u^j\,du = \sum_{j=0}^{n-2}\frac1{j+1}\int_0^1\,\frac{1-u^{j+1}}{1-u}\,du = \sum_{j=0}^{n-2}\frac1{j+1}\sum_{k=0}^j\int_0^1\,u^k\,du \\ = \sum_{j=0}^{n-2}\frac{H_{j+1}}{j+1} = \sum_{k=1}^{n-1}\frac{H_k}k, \end{multline*} so that \begin{equation} E M_n^2=\frac2{(n+2)(n+1)}\,\sum_{k=1}^{n-1}\frac{H_k}k, \end{equation} where $H_k$ is the $k$th harmonic number. Since $H_k\sim\ln k$ as $k\to\infty$, we have \begin{equation} E M_n^2\sim\frac2{n^2}\,\int_1^n\frac{\ln x}x\,dx=\frac{\ln^2 n}{n^2} \end{equation} as $n\to\infty$, the same result as before.

$\endgroup$
  • $\begingroup$ Brilliant, thanks. By the way, is there an expression for $\mathbb{E} \Delta _{(k+1)} ^2$? $\endgroup$ – Amir Sagiv Feb 20 '18 at 8:27
  • 1
    $\begingroup$ By $\Delta_{(k+1)}$, do you mean $\max_{1\le k\le n-1}d_k$, in your notation? $\endgroup$ – Iosif Pinelis Feb 20 '18 at 13:53
  • $\begingroup$ Yes, $\max\limits_{1\leq k \leq n-1}d_k$ $\endgroup$ – Amir Sagiv Feb 20 '18 at 15:12
  • 1
    $\begingroup$ I have added the exact expression and asymptotics for the 2nd moment of $M_n:=\max_{1\le k\le n-1}d_k$. $\endgroup$ – Iosif Pinelis Feb 20 '18 at 21:28
  • 1
    $\begingroup$ I have added a derivation of an exact expression for $E M_n^2$ without using a computer algebra package. $\endgroup$ – Iosif Pinelis Feb 21 '18 at 20:55
1
$\begingroup$

Let $Y_i$ iid random exponential process, and $S=\sum_i Y_i$ then $(X_{k+1}-X_k)$ has the same random law as $$\frac{Y_k}{S} $$

For $n $ large, $Y_i $ are nearly independent. The maximum will then be given by Gumbel distribution : https://en.wikipedia.org/wiki/Gumbel_distribution

$\endgroup$
  • $\begingroup$ Hey, thanks! Did you mean $X_{(k+1)} - X_{(k)}$? $\endgroup$ – Amir Sagiv Feb 19 '18 at 14:45
  • $\begingroup$ Also, could you refer to a proof/into to the relation between $Y_k /S$ and $d_k$? $\endgroup$ – Amir Sagiv Feb 19 '18 at 14:47
  • $\begingroup$ It is an exercice for licence student: law of $(Y_1,...,Y_n)=e^{-Y_1-Y_2-...-Y_n}dY_1...dY_n=e^{-S}dY_1...dY_n$. Therefore conditional to $S$, the law of $Y_i$ are uniform. $\endgroup$ – RaphaelB4 Feb 19 '18 at 15:04
  • $\begingroup$ I don't follow. Probably didn't pass that test. $\endgroup$ – Amir Sagiv Feb 19 '18 at 15:50
  • 1
    $\begingroup$ The Gumbel distribution does not depend on $n$. So, in this case it can only arise as a limit distribution, but not as the exact distribution for a given $n$. $\endgroup$ – Iosif Pinelis Feb 19 '18 at 16:27

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.