Probability of the Same Pair of Balls Drawn from Two Separate Urns

This morning, my friends and I discussed following problem.

Problem:

There are two persons named Mr. A and Mr. B. Each person has his own urn containing $N$ different balls. They uniformly randomly draw a ball twice with replacement from their own urns.

What is the probability that they draw the same pair of balls?

Example:

Let $N = 3$ and let's label them with integer $i$, where $1 \leq i \leq N$. Let $A_k$ and $B_k$, where $k \in \{1,2\}$, be the events when Mr. A and Mr. B draw ball $i$ at the $k$ drawing, respectively.

The pair $((A_1,B_1),(A_2,B_2))$ denotes an outcome from the drawing process.

Events of interest are, for example, $((1,1),(2,2)), ((1,1),(3,3)), \mathrm{or}~ ((1,2),(2,1)).$

Number of sample space $|\Omega|$ is $\binom{N}{2}\times\binom{N}{2}$. Number of possible outcomes is $\binom{N}{2}$. The probability is $\frac{1}{\binom{N}{2}}$.

$|\Omega| = N^4$.

Let $X$ be an event where they both draw the same ordered pair of balls, e.g., $((1,1),(2,2)) \mathrm{or}~ ((1,1),(3,3)).$

Let $Y$ be an event where they both draw the same "cross-ordered" pair of balls, e.g., $((1,2),(2,1)) \mathrm{or}~ ((1,3),(3,1)).$

$|X| = N^2$, and $|Y| = N\times(N-1).$

Hence, the probability is $\frac{N^2 + N\times(N-1)}{N^4}$.

Question:

Is either of these answers correct?

• It is with replacement, so the second is right. – André Nicolas Dec 3 '15 at 7:24
• Thanks. I also agree with the second answer. – Ardevara Dec 3 '15 at 12:12

We denote with $[N]:=\{1,2,3,\ldots,N\}$ and consider all $N^4$ tuples in \begin{align*} \mathcal{A}=\{((A_1,B_1),(A_2,B_2))|A_j,B_j\in[N],j=1,2\} \end{align*}

We denote with $E(A_j=B_k), 1\leq j,k\leq 2$ the event that balls $A_j$ and $B_k$ are drawn and are equal.

Using the inclusion-exclusion principle we can calculate the number of events of drawing equal pairs. We obtain \begin{align*} &\#\left(E(A_1=B_1)\cap E(A_2=B_2)\right)\\ &\qquad+\#\left(E(A_1=B_2)\cap E(A_2=B_1))\right)\\ &\qquad-\#\left(E(A_1=B_1)\cap E(A_2=B_2)\cap E(A_1=B_2) \cap E(A_2=B_1)\right)\\ &=|\{(A_1,A_1),(A_2,A_2)|A_1,A_2\in[N]\}|\\ &\qquad+|\{(A_1,A_2),(A_2,A_1)|A_1,A_2\in[N]\}|\\ &\qquad -|\{(A_1,A_1),(A_1,A_1)|A_1\in[N]\}|\\ &=N^2+N^2-N\\ &=2N^2-N \end{align*}

The number of all events according to OPs rule is $|[N]|^4=N^4$. We conclude the probability $P(N)$ that Mr. A and Mr. B draw equal pairs of balls (with replacement) from urns containing $N$ balls is

\begin{align*} P(N)=\frac{2N-1}{N^3} \end{align*}

There are $\binom{N}{2}$ pairs. There is 1 way to order the match. The probability of getting a match for a particular pair is $(1/\binom{N}{2})^2$. Thus, $$P(\text{Match}) = 1\cdot\binom{N}{2}\frac{1}{\binom{N}{2}}\frac{1}{\binom{N}{2}} = \frac{1}{\binom{N}{2}}.$$

• Could you please give me some examples based on your reasonings? – Ardevara Dec 3 '15 at 8:39
• Actually, my answer should be wrong because I forgot to add one step back in. Essentially I reduced it to a dice matching problem. I'm missing one thing, but I can't think of it at the moment. Meaning I have to multiply this answer by something. – Em. Dec 3 '15 at 9:06
• Any comments are very welcome. I'll patiently wait your next revision. Thanks – Ardevara Dec 3 '15 at 11:09

I think the answer should be $\frac{2}{N^2}$ because the probability that they draw balls in the same order is $\frac{1}{N^2}$ and I do not see why it'd be different for the cross-ordered case as we can swap the order of drawing without any affect to the outcome. And as they're independent cases, we can say that the chance that one of them occurs is $\frac{2}{N^2}$.

• You cannot form the crossed-order pair of balls if they draw the same balls at the first drawing. For example, at the first drawing Mr. A draws ball $2$ ($A_1 = 2$), and Mr. B draws ball $2$ ($B_1 = 2$). In this case there is no way you can form the crossed-order pair of balls, e.g., $((1,2),(2,1))$. That's why the number of the event $Y$ happens is $N\times(N-1)$. – Ardevara Dec 3 '15 at 11:07