4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Would, for example, $XXX$ count as 2 pairs or 1 pair + 1 $X$? $\endgroup$
    – Alex
    Commented Jun 9, 2020 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
    Commented Jun 9, 2020 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
    Commented Jun 9, 2020 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
    Commented Jun 9, 2020 at 21:53

1 Answer 1

3
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .