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$ Commented 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
    Commented 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$ Commented Feb 20, 2018 at 13:53
  • $\begingroup$ Yes, $\max\limits_{1\leq k \leq n-1}d_k$ $\endgroup$
    – Amir Sagiv
    Commented 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$ Commented 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$ Commented 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
    Commented 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
    Commented 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
    Commented Feb 19, 2018 at 15:04
  • $\begingroup$ I don't follow. Probably didn't pass that test. $\endgroup$
    – Amir Sagiv
    Commented 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$ Commented Feb 19, 2018 at 16:27

You must log in to answer this question.

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