1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – PrimeNumber Feb 22 '11 at 21:31
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.