# 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$?

-
So you want the mean value of $x$ or the distribution? –  yo' Nov 26 '12 at 20:12
@tohecz, hmm.. good point. I'm not sure, but for now I think mean value of $x$ (as a function of $m$ and $n$) will be enough. –  max taldykin Nov 26 '12 at 20:21
@user1551, fixed, thanks for pointing. –  max taldykin Nov 26 '12 at 20:43
Connected to which, $0\in\mathbb N$ or not? –  yo' Nov 26 '12 at 20:46
The answer is $(2 \pm o(1)) n/m \pm O(1)$. –  Yury Nov 27 '12 at 4:11

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

-
I need some time to understand this but accepting it for now. Thanks for answering. –  max taldykin Nov 27 '12 at 13:58