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



maximal distance of nearby iid unifrom random variables
Let us just adapt the reasoning at [stats-SE](https://stats.stackexchange.com/questions/162560/distribution-of-the-largest-fragment-of-a-broken-stick-spacings). 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](https://stats.stackexchange.com/questions/162560/distribution-of-the-largest-fragment-of-a-broken-stick-spacings) 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)](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&uact=8&ved=0ahUKEwiZ2-Th7bLZAhVk34MKHY90AGQQFghGMAM&url=http%3A%2F%2Fwww.springer.com%2Fcda%2Fcontent%2Fdocument%2Fcda_downloaddocument%2F9789462391352-c2.pdf%3FSGWID%3D0-0-45-1519243-p177383240&usg=AOvVaw0_aq3h5r9On4wekd_tuXYt)). The second key observation at [stats-SE](https://stats.stackexchange.com/questions/162560/distribution-of-the-largest-fragment-of-a-broken-stick-spacings) 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](https://en.wikipedia.org/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. 


