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
  • 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$ Feb 19, 2018 at 16:24

2 Answers 2

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$
8
  • $\begingroup$ Brilliant, thanks. By the way, is there an expression for $\mathbb{E} \Delta _{(k+1)} ^2$? $\endgroup$
    – Amir Sagiv
    Feb 20, 2018 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$ Feb 20, 2018 at 13:53
  • $\begingroup$ Yes, $\max\limits_{1\leq k \leq n-1}d_k$ $\endgroup$
    – Amir Sagiv
    Feb 20, 2018 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$ Feb 20, 2018 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$ Feb 21, 2018 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$
6
  • $\begingroup$ Hey, thanks! Did you mean $X_{(k+1)} - X_{(k)}$? $\endgroup$
    – Amir Sagiv
    Feb 19, 2018 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, 2018 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, 2018 at 15:04
  • $\begingroup$ I don't follow. Probably didn't pass that test. $\endgroup$
    – Amir Sagiv
    Feb 19, 2018 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$ Feb 19, 2018 at 16:27

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.