Variance of the number of couples seated together

1.1k Views Asked by At

Suppose that the $10$ people of $5$ married couples are randomly seated around a round table. Letting $X$ be the number of wives who are seated next to their husband, give the value of $Var(X)$.

$$E(X)=5\cdot\frac{2\cdot8!}{9!}=\frac{10}{9}$$

Since if we seat wife $i$ somewhere, there are $2$ places to seat her husband, $8!$ ways to seat the other $8$ people, and $9!$ ways to seat her husband and the other $8$ people.

$$\begin{align*} E(X^2) &= 0\cdot{5\choose{0}} {2\over{9}}^0 \cdot {7\over{9}}^{5}+1\cdot{5\choose{1}} {2\over{9}}^1 \cdot {7\over{9}}^{4}+4\cdot{5\choose{2}} {2\over{9}}^2 \cdot {7\over{9}}^{3}\\\\ &+ 9\cdot{5\choose{3}} {2\over{9}}^3 \cdot {7\over{9}}^{2} + 16\cdot{5\choose{4}} {2\over{9}}^4 \cdot {7\over{9}}^{1}+25\cdot{5\choose{5}} {2\over{9}}^5 \cdot {7\over{9}}^{0}\\\\ &= 2.098765 \\\\ \end{align*}$$

Then $$Var(X)=E(X^2)-E(X)^2=2.098765-\frac{10}{9}^2 \approx.864$$

It just occurred to me that I could have just done

$$Var(X)=npq=5\cdot\frac{2}{9}\cdot\frac{7}{9}\approx.864$$

However, looking at a similar problem, it looks like covariance comes into play. Covariance is a new concept for me but I have the formulas so I'll give it a go.

$$\begin{align*} Var(X) &= \sum_{i=1}^n Var(X_i)+\sum_{i=1}^n \sum_{i \neq j} Cov(X_i, X_j)\\\\ &= \sum_{i=1}^n Var(X_i)+\sum_{i=1}^n \sum_{i \neq j} E(X_i X_j)-E(X_i)\cdot E(X_j)\\\\ &= \sum_{i=1}^n Var(X_i)+\sum_{i=1}^n \sum_{i \neq j} P(X_i)P(X_j=1|X_i=1)-E(X_i)\cdot E(X_j)\\\\ &= .864+5\cdot 4 \left(\frac{2}{9}\times\frac{2\cdot 7}{8\cdot 7} - \frac{2}{9}^2\right)\\\\ &= \frac{80}{81} \\\\ \end{align*}$$

Did I do this correctly? Also, I am a little confused about this part of the formula:

$$\sum_{i=1}^n \sum_{i \neq j} Cov(X_i, X_j)$$

Is the sum set up this way because, in terms of this problem, we have $5$ wives, and once we seat one wife with her husband, that affects the probabilities for the other $4$ wives?

1

There are 1 best solutions below

1
On BEST ANSWER

It is true that for any wife seated at the table, the probability that their husband is seated next to them is $2/9$. However, you cannot treat this as a binomial problem with $n/2$ trials and success probability $2/9$, as the partnering probabilities are not independent. If one wife is matched, then the pool for the people seated next to another wife is reduced, and the chances for her to be matched increases.

To work this out in general, let there be $n_c$ couples, so the total number of people seated is $n=2n_c$, and index the people by $i$ which increases to the right. For person $i$, let $R_i = 1$ if their partner is seated to their right and $R_i = 0$ otherwise. By looking only to the right, we don't double count the partnerships. We are interested in the number of matches: $$X=\sum_{i=1}^n R_i$$ The expectation is $$E[X]=\sum_{i=1}^n E[R_i]=\sum_{i=1}^n P(R_i)=\sum_{i=1}^n {1\over n-1}={n\over n-1}$$ The variance is $$Var(X)=\sum_{i=1}^n\sum_{j=1}^n Cov(R_i,R_j)$$ where the sum includes $n$ terms of the type: $$Cov(R_i,R_i)=Var(R_i)=E[R_iR_i]-E[R_i]E[R_i]={1\over n-1}-{1\over (n-1)^2}={n-2\over(n-1)^2}$$ The other $Cov(R_i,R_j)$ terms where $i\ne j$ depend on whether or not $i$ and $j$ are neighbors. If they are neighbors, $R_iR_j=0$ since both cannot have their partners to the right. There are $2n$ such neighboring elements in the covariance matrix and each term is $$Cov_{\rm{neighbor}}=Cov(R_i,R_{i+1})=E[R_iR_{i+1}]-E[R_i]E[R_{i+1}]=0-{1\over (n-1)^2}$$ For non-neighboring $i$ and $j$, $$E[R_iR_j]=P(R_i,R_j)=P(R_i)P(R_j|R_i)={1\over n-1}{1\over n-3}$$ because if person $i$ has their partner to their right, then there are two less people in the pool who are not partners for person $j$. The covariance matrix has $n^2-3n$ such terms, which are $$Cov(R_i,R_j)=E[R_iR_j]-E[R_i]E[R_j]={1\over n-1}{1\over n-3}-{1\over (n-1)^2}={2\over (n-1)^2(n-3)}$$ Adding all of these terms gives $$Var(X)={n(n-2)\over(n-1)^2}-{2n\over(n-1)^2}+{2(n^2-3n)\over (n-1)^2(n-3)}=1-{1\over (n-1)^2}$$ It is interesting to note that if Y is binomial with $n$ trials with success probability $p={1\over(n-1)}$, then $$E[Y]={n\over n-1}$$ and $$Var(Y)=np(1-p)=1-{1\over (n-1)^2}$$ the identical properties for $X$. For the case $n=10$ the variance is in fact $80/81$.