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

  • 0
    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$.2011-02-22

2 Answers 2

6

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

2

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