Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
So you want the mean value of $x$ or the distribution? –  tohecz 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
2  
Connected to which, $0\in\mathbb N$ or not? –  tohecz Nov 26 '12 at 20:46
1  
The answer is $(2 \pm o(1)) n/m \pm O(1)$. –  Yury Nov 27 '12 at 4:11
show 9 more comments

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
I need some time to understand this but accepting it for now. Thanks for answering. –  max taldykin Nov 27 '12 at 13:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.