<p>Assume as given that $m=\omega(\sqrt{n})$.</p>

<p>Fix any $\epsilon&gt;0$. We will consider $r\in[1,n]$ with $r&lt;(1-\epsilon)n$. The aim is to show that with high probability as $n\to\infty$, $r$ is included in the set of differences.</p>

<p>First consider the set $A=\{a_i:i&lt;m/2\}\cap[1,\epsilon n]$. The number of $i$ with $i&lt;m/2$ such that $a_i&lt;\epsilon n$ is binomial with expectation around $\epsilon m/2$. So with high probability as $n\to\infty$, the number of such $i$ will be at least $\epsilon m/4$, which is $\omega(\sqrt{n})$. Then (claim, "left as exercise", not hard to show) with high probability as $n\to\infty$, the set $A$ has size at least $\sqrt{n}$. Let us write $G$ for this "good event", that $|A|\geq\sqrt{n}$.</p>

<p>Suppose that indeed $G$ holds, i.e. there are at least $\sqrt{n}$ distinct values of $a_i$ less than $\epsilon n$, for $i&lt;m/2$. Note that for each such value, there is a value $k\in [1,n]$ which is precisely $r$ larger. Now consider the values of $a_i$ for $i\geq m/2$. These are independent and each one has probability at least $\sqrt{n}/n=1/\sqrt{n}$ of being at distance $r$ from an element of the set $A$. The probability that no difference $r$ is produced is then at most $(1-1/\sqrt{n})^{m/2}$ which goes to 0 as $n\to\infty$ since $m=\omega(\sqrt{n})$. So indeed, the probability that $G$ holds but no difference of size $r$ exists tends to 0 as $n\to\infty$. </p>

<p>So (uniformly in $r&lt;(1-\epsilon)n$) the probability that $r$ is included in the set of differences tends to 1 as $n\to\infty$. 
Hence using linearity of expectation,
$$
\liminf
\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}\right] \geq 1-\epsilon.$$
Since $\epsilon$ is arbitrary, the limit is 1 as desired. </p>

CC BY-SA 3.0
2015-06-21T19:12:08.663Z
Are you treating each difference as independent in the expression $1-(1-\epsilon/n)^{\omega(n)}$, and if so, is it justified?
usul
CC BY-SA 3.0
2015-06-21T20:14:57.510Z
@James Oh, now i see where i missed that $n$. Thank you.
Daniel Soltész
CC BY-SA 3.0
2015-06-21T20:43:07.433Z
@usul: indeed, apologies, my argument was sloppy and incomplete. I've expanded it - I think it holds water now.
James Martin
CC BY-SA 3.0
2015-06-21T18:39:22.520Z
2015-06-23T07:39:38.863Z
2015-06-23T07:39:38.863Z
James Martin
<p>I encountered the following result during my research. </p>

<blockquote>
  <p>$$\lim\limits_{n\to \infty} \mathbb{E}\left[ 
\frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}
\right] = 1$$
  where $m=\omega(\sqrt n)$ and $a_1,\cdots,a_m$ are chosen at random from $[n]$.</p>
</blockquote>

<p>I am looking for a reference/a direct proof.</p>

<hr>

<p><a href="https://mathoverflow.net/questions/209817/">Crossposted on MO</a></p>

CC BY-SA 3.0
2015-06-19T11:18:26.107Z
If $m = \sqrt{n}$, the maximum number of different differences you can get is $m(m-1)/2 < n/2$. So you really need $m$ to grow ***faster*** than $\sqrt{n}$ for this to be true. What I would do is try to calculate the probability that a number $d$ is *not* a difference $d = |a_i - a_j|$.
Peter Shor 
CC BY-SA 3.0
2015-06-19T12:02:23.790Z
@Shor:thanks, I updated the question. And indeed since $\mathbb E(\sum x_i)=\sum \mathbb E(x_i)$, it is easier to calculate for a specific difference $d$.
Zhu Cao
CC BY-SA 3.0
2015-06-20T09:33:22.213Z
Let $m = \sqrt{(2+2\varepsilon)n}$.  Then $m(m-1)/2 \ge n$ whenever $n \ge (1+\varepsilon)/2\varepsilon^2$.  So instead of $m = \omega(\sqrt{n})$, it might be possible that $m \ge \sqrt{2(1+\varepsilon)n}$ is enough, for some $\varepsilon > 0$.
András Salamon
CC BY-SA 3.0
2015-06-21T03:12:20.583Z
@Salamon:thanks for the comment. However, $m=c\sqrt{n}$ may not be enough. Consider the following heuristics. In $1,...,n/c^3$ and $n-n/c^3,...,n$, about $2\sqrt{n}/c^2$ numbers are selected. Then absolute differences in [n(1-1/c^3),n] will appear for 4n/c^4 times. Thus when $n\to\infty$, the upper bound on the expectation value is $1-1/2c^3$, not $1$.
Zhu Cao
CC BY-SA 3.0
2015-06-21T12:03:49.280Z
I think that if you move this to mathoverflow and tag probability, you will get an answer much faster.
domotorp
CC BY-SA 3.0
2015-06-21T13:03:58.103Z
@domotorp:thanks for the advice. Crossref http://mathoverflow.net/questions/209817/
Zhu Cao
CC BY-SA 3.0
2015-06-21T17:12:13.847Z
Presumably the $m$ samples are independent and uniform from the $n$ discrete values.  Let $D_n$ denote the number of different differences in a sample of $n/2 = \omega(\sqrt{n})$ numbers chosen from $\{1,2,\dots,n\}$.  If the result in the question is true, then $\lim_{n\to\infty} Pr[D_n = n] = 1$.  Is this really the case?
András Salamon
CC BY-SA 3.0
2015-06-21T19:55:17.643Z
@ZhuCao, when you say "choose $m$ integers $a_1,...,a_m$ randomly from $[1,n]$", what distribution do you mean exactly? I was assuming i.i.d. uniform $\{1,\dots,n\}$.
usul
CC BY-SA 3.0
2015-06-21T20:48:45.063Z
@Andras no, it is not the case. For example, if the number $1$ is not chosen (which happens with probability bounded away from 0) then the difference $n-1$ cannot appear, and $D_n<n$. But why does it need to be the case? The question only asks that the expectation of $D_n/n$ gets close to 1, not that $D_n$ is equal to 1 with high probability.
James Martin
CC BY-SA 3.0
2015-06-22T00:52:08.460Z
Please don't cross-post on multiple Stack Exchange sites.  Our site policy forbids simultaneous cross-posting: it says, at a minimum, wait a week.  And if you get no good answer, you can always flag it for moderator attention to ask that it be migrated.
D.W.
<reference-request><co.combinatorics><pr.probability>
Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$
Zhu Cao
# Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

(Asked by: username_0 on 2015-06-19)

I encountered the following result during my research.

> $$\lim\limits\_{n\to \infty} \mathbb{E}\left[
> \frac{\#\{|a\_i-a\_j|,1\le i,j\le m \}}{n}
> \right] = 1$$
> where $m=\omega(\sqrt n)$ and $a\_1,\cdots,a\_m$ are chosen at random from $[n]$.

I am looking for a reference/a direct proof.

---

[Crossposted on MO](https://mathoverflow.net/questions/209817/)

**Tags:** reference-request, co.combinatorics, pr.probability
> **Comments:**
> **username_1**: If $m = \sqrt{n}$, the maximum number of different differences you can get is $m(m-1)/2 < n/2$. So you really need $m$ to grow ***faster*** than $\sqrt{n}$ for this to be true. What I would do is try to calculate the probability that a number $d$ is *not* a difference $d = |a_i - a_j|$.  
> **username_0**: @Shor:thanks, I updated the question. And indeed since $\mathbb E(\sum x_i)=\sum \mathbb E(x_i)$, it is easier to calculate for a specific difference $d$.  
> **username_2**: Let $m = \sqrt{(2+2\varepsilon)n}$.  Then $m(m-1)/2 \ge n$ whenever $n \ge (1+\varepsilon)/2\varepsilon^2$.  So instead of $m = \omega(\sqrt{n})$, it might be possible that $m \ge \sqrt{2(1+\varepsilon)n}$ is enough, for some $\varepsilon > 0$.  
> **username_0**: @Salamon:thanks for the comment. However, $m=c\sqrt{n}$ may not be enough. Consider the following heuristics. In $1,...,n/c^3$ and $n-n/c^3,...,n$, about $2\sqrt{n}/c^2$ numbers are selected. Then absolute differences in [n(1-1/c^3),n] will appear for 4n/c^4 times. Thus when $n\to\infty$, the upper bound on the expectation value is $1-1/2c^3$, not $1$.  
> **username_3**: I think that if you move this to mathoverflow and tag probability, you will get an answer much faster.  
> **username_0**: @domotorp:thanks for the advice. Crossref http://mathoverflow.net/questions/209817/  
> **username_2**: Presumably the $m$ samples are independent and uniform from the $n$ discrete values.  Let $D_n$ denote the number of different differences in a sample of $n/2 = \omega(\sqrt{n})$ numbers chosen from $\{1,2,\dots,n\}$.  If the result in the question is true, then $\lim_{n\to\infty} Pr[D_n = n] = 1$.  Is this really the case?  
> **username_4**: @ZhuCao, when you say "choose $m$ integers $a_1,...,a_m$ randomly from $[1,n]$", what distribution do you mean exactly? I was assuming i.i.d. uniform $\{1,\dots,n\}$.  
> **username_5**: @Andras no, it is not the case. For example, if the number $1$ is not chosen (which happens with probability bounded away from 0) then the difference $n-1$ cannot appear, and $D_n<n$. But why does it need to be the case? The question only asks that the expectation of $D_n/n$ gets close to 1, not that $D_n$ is equal to 1 with high probability.  
> **username_6**: Please don't cross-post on multiple Stack Exchange sites.  Our site policy forbids simultaneous cross-posting: it says, at a minimum, wait a week.  And if you get no good answer, you can always flag it for moderator attention to ask that it be migrated.  

---

## 1 answers

### Answer by username_5 on 2015-06-21. Score: 7 | Accepted answer

Assume as given that $m=\omega(\sqrt{n})$.

Fix any $\epsilon>0$. We will consider $r\in[1,n]$ with $r<(1-\epsilon)n$. The aim is to show that with high probability as $n\to\infty$, $r$ is included in the set of differences.

First consider the set $A=\{a\_i:i

Suppose that indeed $G$ holds, i.e. there are at least $\sqrt{n}$ distinct values of $a\_i$ less than $\epsilon n$, for $i

So (uniformly in $r<(1-\epsilon)n$) the probability that $r$ is included in the set of differences tends to 1 as $n\to\infty$.
Hence using linearity of expectation,
$$
\liminf
\limits\_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a\_i-a\_j|,1\le i,j\le m \}}{n}\right] \geq 1-\epsilon.$$
Since $\epsilon$ is arbitrary, the limit is 1 as desired.

> **Comments:**
> **username_4**: Are you treating each difference as independent in the expression $1-(1-\epsilon/n)^{\omega(n)}$, and if so, is it justified?  
> **username_7**: @James Oh, now i see where i missed that $n$. Thank you.  
> **username_5**: @usul: indeed, apologies, my argument was sloppy and incomplete. I've expanded it - I think it holds water now.  

---

