21
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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|$. $\endgroup$ – Peter Shor Jun 19 '15 at 11:18
  • $\begingroup$ @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$. $\endgroup$ – Zhu Cao Jun 19 '15 at 12:02
  • 1
    $\begingroup$ @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\}$. $\endgroup$ – usul Jun 21 '15 at 19:55
  • 1
    $\begingroup$ @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. $\endgroup$ – James Martin Jun 21 '15 at 20:48
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Jun 22 '15 at 0:52
7
$\begingroup$

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<m/2\}\cap[1,\epsilon n]$. The number of $i$ with $i<m/2$ such that $a_i<\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}$.

Suppose that indeed $G$ holds, i.e. there are at least $\sqrt{n}$ distinct values of $a_i$ less than $\epsilon n$, for $i<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$.

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.

$\endgroup$
  • 1
    $\begingroup$ Are you treating each difference as independent in the expression $1-(1-\epsilon/n)^{\omega(n)}$, and if so, is it justified? $\endgroup$ – usul Jun 21 '15 at 19:12
  • $\begingroup$ @James Oh, now i see where i missed that $n$. Thank you. $\endgroup$ – Daniel Soltész Jun 21 '15 at 20:14
  • $\begingroup$ @usul: indeed, apologies, my argument was sloppy and incomplete. I've expanded it - I think it holds water now. $\endgroup$ – James Martin Jun 21 '15 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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