Expected value of minimum distance I'm trying to estimate average complexity of some algorithm and the problem I'm currently stuck with can be stated very simply.
Let $a_i$ be a list of $m$ uniformly distributed integers not greater than some $n$: $a_i \in \mathbb{N} \land a_i \leq n$ for $i={1..m}$.
Then I pick some $j$ randomly and calculate minimum distance between $a_j$ and other $a_i$'s: $x = \min_{j \neq i} |a_j - a_i|$.
The question is how to calculate expected value of $x$?
 A: Answer: $\left(\frac{1}{2}+o(1)\right) \frac{n}{m} + \delta$, where $|\delta| < 1$ and $o(1)$ tends to $0$ as $m\to \infty$.
First of all, note that since all $a_i$ are independently and identically distributed,
$$\mathbb{E}[x| j =1] = \mathbb{E}[x| j = 2] = \dots = \mathbb{E}[x| j =m],$$
so it doesn't matter whether we choose $j$ randomly or just let $j=1$. Let's assume that $j=1$. 
It's easier to work with continuous random variables. So let's assume that we choose independent random numbers $y_1, \dots, y_m \in_U (0,1)$ and then let $x_i = \lceil ny_i\rceil$. Note that 
$$n|y_i - y_j| - 1 < |x_i - x_j| < n|y_i - y_j| + 1.$$
Therefore, if we are only interested in an approximate answer, it suffices to find the expectation $\mathbb{E}[|y_i - y_j|]$. We reduced our problem to the following problem.

We are given $m$ independent random variables $y_1, \dots, y_m$ uniformly distributed on $(0,1)$. Compute the expectation of $\xi = \min_{i>1} |y_1-y_i|$.

Here is an informal solution to this problem. 
\begin{align*}\mathbb{E}[\xi] &= \int_0^1 \Pr[\xi > t] dt =  \int_0^1 \Pr[|y_1 - y_i| > t \text{ for every } i > 2]\, dt \\ &= \int_0^1 \mathbb{E}[\Pr[|y_1 - y_2| > t]^{m-1}|y_1] \,dt.
\end{align*}
Since there are $m$ numbers $\{y_i\}$ on $(0,1)$, we expect that the distance between consecutive numbers will be about $1/m$; it's very unlikely that the distance is more than $\tau = \log m /m$. Thus $\xi < \tau$ with very high probability, also $y_1 \in(\tau, 1 - \tau)$ w.h.p. Let us condition on $y_1 = y^*$ where $y^* \in (\tau, 1 - \tau)$. Then we have 
\begin{align*}
\int_0^1 \Pr[|y_1 - y_2| > t | y_1 = y^*]^{m-1} dt &\approx \int_0^{\tau} \Pr[|y_2 - y^*| > t]^{m-1} dt \\
&= \int_0^{\tau} \Pr[y_2\notin [y^* -t, y^*+t]]^{m-1} dt\\
&=\int_0^{\tau} (1 - 2t)^{m-1} dt.
\end{align*}
Since $y_1 \in(\tau, 1 - \tau)$ w.h.p, we have
$$\mathbb{E}[\xi] \approx \int_0^{\tau} (1 - 2t)^{m-1} dt \approx \frac{1}{2m}. 
$$
Finally, $\mathbb{E}[\xi] \in (n\mathbb{E}[\xi] - 1, n\mathbb{E}[\xi] +1)$. Plugging in the expression for $\mathbb{E}[\xi]$, we get
$$\mathbb{E}[\xi] \in \left(\left(\frac{1}{2}+o(1)\right) \frac{n}{m} -1 , \left(\frac{1}{2}+o(1)\right) \frac{n}{m}  +1\right).$$
Note that this bound is not particularly useful when $m\approx n$.
