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$?


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.

  • $\begingroup$ Would, for example, $XXX$ count as 2 pairs or 1 pair + 1 $X$? $\endgroup$ – Alex Jun 9 at 21:37
  • $\begingroup$ Thank you for asking. The total number of shapes is always even (n is even), so we always have n/2 pairs. We don't consider the case when n is odd. $\endgroup$ – Ziqi Yang Jun 9 at 21:42
  • $\begingroup$ Ok, so all allocations are done on pairs that can't be split, i.e. allocatio $XOOX$ is impossible, unlike $XXOO$ or $OOXX$ $\endgroup$ – Alex Jun 9 at 21:45
  • $\begingroup$ It's possible, just imagine randomly put these four elements into a 2 by 2 matrix, and look at each row of the matrix to see if shapes in each row is same or not. $\endgroup$ – Ziqi Yang Jun 9 at 21:53

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.

| cite | improve this answer | |
  • $\begingroup$ Thank you so much, I think this is the right answer. $\endgroup$ – Ziqi Yang Jun 9 at 21:44

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.