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.

Player A, picks $n_1$ integers $a_1$,...,$a_{n_1}$ uniformly at random from $1$..$N$,

and player B picks $n_2$ integers $b_1$,...,$b_{n_2}$ the same way.

Given $N$, $n_1$, $n_2$, and $d$, what is the expected number of pairs ($a_i$,$b_j$) where |$a_i$-$b_j$| $=<$ $d$,

A. if A and B are allowed to select duplicates in their lists.

B. if duplicate numbers are not allowed.

Thanks, MG

share|improve this question
    
It seems that for (A) there are two extreme cases: (i) $a_1 = \cdots = a_{n_1}, b_1 = \cdots = b_{n_2}$ where $a_1 = b_1$ or (ii) $a_1 \neq b_1$. –  PEV Feb 22 '11 at 21:31
add comment

2 Answers

up vote 6 down vote accepted

In both cases, the expected number is $n_1n_2p$ where $p$ is the probability that $|a_1-b_1|\le d$. There are $n(d)=N+2(N-1)+\cdots+2(N-d)$ such couples $(a,b)$ hence $p=n(d)/N^2$. Finally $n(d)=(2d+1)N-d(d+1)$, hence the expected number you ask for is $$n_1n_2[(2d+1)N-d(d+1)]/N^{2}.$$

share|improve this answer
add comment

If $d\ge N-1$, then all pairs must be within $d$ of each other, and the total number of close pairs must be exactly $n_1 n_2$. Now assume $d < N-1$. For any $i,j$, the random variables $a_i$ and $b_j$ are independent and uniformly distributed over $[N]=\{1,2,...,N\}$. The points $(x,y)$ in $[N]^2$ with $|x-y|>d$ make up two right triangles with side length $N-1-d$, and the total number of such points is $(N-1-d)(N-d)$, or $(N-d)^2 - (N-d)$. So the probability that a particular pair $(a_i,b_j)$ is close is given by $$ \begin{eqnarray} P\left[|a_i-b_j|\le d\right] &=& \frac{1}{N^2}\left(N^2 - (N-d)^2 + (N-d)\right) \\ &=& \frac{1}{N^2}\left(N(2d+1) - d(d+1)\right). \end{eqnarray} $$ The expected number of close pairs is just $n_1 n_2$ times this probability: $$ E\left[\text{# pairs }(a_i, b_j)\text{ s.t. }|a_i-b_j|\le d\right] = \frac{n_1 n_2}{N^2}\left(N(2d+1) - d(d+1)\right). $$ This is true whether or not $A$ and $B$ are allowed to have duplicates within their individual lists of integers. It does, however, make a difference whether $A$ and $B$ may have duplicates between their lists. If no duplicates are to be allowed even between $A$ and $B$, then $N$ points $(x,x)$ are removed from consideration for each pair $(a_i, b_j)$: the final result will have its $N^2$ denominator replaced by $N(N-1)$.

share|improve this answer
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.