Expected number of matching pairs from a random list

236 Views Asked by At

Question

A random list of length $n$ (even number) consists of $n_1$ stars $\star$ and $n_2$ squares $\square$. Suppose we randomly put these shapes into $n/2$ pairs, denote:

$X_1$ to be the number of matching pairs of $\star$

$X_2$ to be the number of matching pairs of $\square$

What is the expected number of $X_1$ and $X_2$?

Example

For example, if $n=10$, $n_1=7, n_2=3$, suppose we have a random pattern of 5 pairs

\begin{align*} \star ~\square \\ \star ~\star \\ \square ~\square \\ \star ~\star \\ \star ~\star \end{align*} Because there are 3 matching pairs for $\star$ and 1 matching pair for $\square$, we have $X_1=3, X_2=1$. If we repeat this process many times, we should have different patterns of pairs, and produce different values of $X_1$ and $X_2$. I'm wondering how to calculate their expected values $E[X_1]$ and $E[X_2]$, which should be functions on $n_1$ and $n_2$.

The problem comes from my research project. Thank you in advance.

1

There are 1 best solutions below

1
On BEST ANSWER

The chance that the first pair is both stars is $\frac {n_1(n_1-1)}{n(n-1)}.$ By symmetry, that is the chance any given pair is both stars if we ignore the distribution of the rest of the pairs. By the linearity of expectation, the expected number of pairs of stars is $\frac n2\cdot\frac {n_1(n_1-1)}{n(n-1)}$. Change the subscript to get the expected number of pairs of squares.