Variance of couples seated across from each other at a rectangular table.

Question

Let N couples be randomly seated at a rectangular table, men on one side and women on the other. Let X be the random variable describing the number of couples that end up being seated across from each other. What is the variance of X?

I uncovered this problem in my book and have found the following:

1. The seating arrangements are not independent.

2. the $E(X)$ is 1 if you use indicator variables, ie. if $I_k$ is the indicator variable that is 1 if a couple k is seated across from one another and 0 otherwise. so $X=\sum_{k=1}^n I_k$ and the $E(X)$ is worked out to be 1.

I believe I am correct so far, however, I am stuck here. Since the each $E_k$ is not entirely independent, I tried using $Var(X)= E(X^2) - (E(X))^2 = E(X^2) - 1$

So I need $E(X^2)$, which is a double sum. I do not know if this is solvable or if there is some term missing. Any direction would be appreciated.

Edit: Okay, so I also know that $ p(I_k)=1/n $ and by the same rational $p(I_k*I_j)= 1/(n^2-n)$. So I am assuming I am missing some term because each k is not independent. I will try the other definition of variance, but I am almost sure (frustratingly so) I am missing something.

Answer 1

Your work so far is perfect. Now you need

\begin{align} \mathbb E\left(X^2\right)&=\mathbb E\left(\left(\sum_{k=1}^nI_k\right)^2\right)\\ &=\mathbb E\left(\sum_{k=1}^nI_k^2+\sum_{j\ne k}I_jI_k\right)\\ &=\mathbb E\left(\sum_{k=1}^nI_k\right)+\mathbb E\left(\sum_{j\ne k}I_jI_k\right)\\ &=1+n(n-1)\mathbb E(I_1I_2)\;. \end{align}

Fixing couples $1$ and $2$ leaves $(n-2)!$ out of $n!$ arrangements, so $\mathbb E(I_1I_2)=\frac1{n(n-1)}$ and thus

$$ \mathbb E\left(X^2\right)=1+n(n-1)\frac1{n(n-1)}=2\;. $$

Answer 2

Outline: Indicator random variables will work. It is enough to compute $E(X^2)$, which is $E((I_1+I_2+\cdots +I_n)^2)$. Expand the square. We get $\sum I_k^2$ plus a sum of "mixed" terms.

Since $I_k^2=I_k$, you have already calculated $E(\sum I_k^2)$.

It remains to find $E(I_iI_j)$ where $i\ne j$. The probability that $I_i=1$ is $\frac{1}{n}$. Given that $I_i=1$, the probability that $I_j=1$ is $\frac{1}{n-1}$. Thus $E(I_iI_j)=\frac{1}{n(n-1)}$ (if $n\gt 1$).

For the expectation of the sum of products of mixed terms, multiply by $n(n-1)$. Now it remains to put the pieces together.

Answer 3

Let the RV $X$ be the number of fixed points of a random permutation. Observe that the species of permutations with fixed points marked is

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \cdots).$$

This gives the generating function $$G(z, u) = \exp\left(uz + \frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \frac{z^5}{5} + \cdots\right)$$

which is $$G(z, u) = \exp\left((u-1)z + \log\frac{1}{1-z}\right) = \frac{\exp((u-1)z)}{1-z} = \exp(uz) \frac{\exp(-z)}{1-z}.$$

As this is an EGF we get the OGF of $\mathrm{E}(X)$ $$\left.\frac{\partial}{\partial u} G(z, u)\right|_{u=1} = z \exp(z) \frac{\exp(-z)}{1-z} = z \frac{1}{1-z}.$$

Therefore $$\mathrm{E}(X) = 1.$$

Similarly we get the OGF of $\mathrm{E}(X(X-1))$ $$\left.\frac{\partial}{\partial u}\frac{\partial}{\partial u} G(z, u)\right|_{u=1} = z^2 \exp(z) \frac{\exp(-z)}{1-z} = z^2 \frac{1}{1-z}.$$

Therefore when $n\ge 2$ $$\mathrm{E}(X(X-1)) = 1.$$

This yields

$$\mathrm{Var}(X) = \mathrm{E}(X(X-1)) + \mathrm{E}(X) - \mathrm{E}(X)^2 = 1 + 1 - 1 = 1.$$