Matching couples at a party (mean and variance)

[Master1022]

Homework Statement

At a party there are $n$ couples. When the last song comes on, each person randomly picks a dance partner. What is the: (a) mean, (b) variance of the number of couples that are paired together?

Relevant Equations

Expected value
Variance

Hi,

I was attempting the following problem and I didn’t know how to start it off correctly.

Question: At a party there are $n$ couples. When the last song comes on, each person randomly picks a dance partner. What is the: (a) mean, (b) variance of the number of couples that are paired together?

Attempt:
For (a), I was thinking of using some indicator variables $X_i$ for $i \in {1,2,…,n}$ where $X_i = 1$ when couple $i$ is actually paired up with one another, and the variable equals 0 otherwise. Thus, we have:

$$ \text{number of couples actually paired up} = Z = X_1 + X_2 + … + X_n $$

Thus, we can get the expected value $E(Z)$ by using the linearity of expectation:

$$ E(Z) = E(X_1 + X_2 + … + X_n) = \sum_{i = 1}^{n} E(X_i) $$
where $E(X_i) = P(X_i = 1)$. To get this probability, all I could currently think of is: $P(X_i = 1) = 1 \cdot \frac{1}{2n - 1} = \frac{1}{2n - 1}$
and thus I get $E(Z) = \frac{n}{2n - 1}$, which doesn’t really seem correct from an algebraic point of view.

Where have I gone wrong? [EDIT: I am guessing I have gone wrong in finding the probability or the general method]

Any help would be greatly appreciated.

 

[anuttarasammyak]

Easy cases

for n=1 couples
expectation value = 1
sigma = 0

for n=2 couples
2 couples : 2 cases
1 couple : (2C1)^2 (2-1)^2= 4 cases
All the vote = 2^4=16
expectation value = (2*2+1*4+0*12)/16=0.5
sigma = $\sqrt{2(2-0.5)^2+4(1-0.5)^2+12(0-0.5)^2}$

You may go this way to higher n.

 

[PeroK]

Easy cases

for n=2 couples
2 couples : 2 cases
1 couple : (2C1)^2 (2-1)^2= 4 cases
All the vote = 2^4=16
expectation value = (2*2+1*4+0*12)/16=0.5
sigma = $\sqrt{2(2-0.5)^2+4(1-0.5)^2+12(0-0.5)^2}$

You may go this way to higher n.

This doesn't look right. For $n =2$ I get a mean of $\frac 2 3$. As $p(0) = \frac 2 3$ and $p(2) = \frac 1 3$. Note that $p(1)=0$.

I'm not sure how to calculate these quantities for general $n$. I suspect it's not easy.

 

[PeroK]

There is a quick way to calculate the mean. I'm not sure how to get the variance.

 

[anuttarasammyak]

Easy cases

for n=1 couples
expectation value = 1
sigma = 0

for n=2 couples
2 couples : 2 cases
1 couple : (2C1)^2 (2-1)^2= 4 cases
All the vote = 2^4=16
expectation value = (2*2+1*4+0*12)/16=0.5
sigma = $\sqrt{2(2-0.5)^2+4(1-0.5)^2+12(0-0.5)^2}$

You may go this way to higher n.

Ya, I was wrong.
For n=2
1 couple : 2C1 ^2 (2^2-1)=12
0 couple: 2 cases
Expectation value = 1
Sigma=0.5
I hope it is right.

 

[PeroK]

Ya, I was wrong.
For n=2
1 couple : 2C1 ^2 (2^2-1)=12
0 couple: 2 cases
Expectation value = 1
Sigma=0.5
I hope it is right.

That's not right. I've posted the correct probabilities in post #3.

 

[PeroK]

There's also a simple way to get a general expression for the mean for $n$ couples.

I can't see a way to get the variance for general $n$.

 

[PeroK]

Ya, I was wrong.
For n=2
1 couple : 2C1 ^2 (2^2-1)=12
0 couple: 2 cases
Expectation value = 1
Sigma=0.5
I hope it is right.

Ah, okay, assuming each couple is one of each sex etc. I was assuming anyone could be paired with anyone else. That changes things.

 

[PeroK]

The problem simplifies with the interpretation of @anuttarasammyak.

The mean should be easy and I have a recursive inductive proof for the variance. It's not that simple, but not too complicated either.

 

[WWGD]

If you refer to a person matched with their original partner, the count is given by the number of Edit: @PeroK Derangements. As n grows, the proportion approaches 1/e.

 

[anuttarasammyak]

Ah, okay, assuming each couple is one of each sex etc. I was assuming anyone could be paired with anyone else. That changes things.

I interpreted it in my old standard. The standard might have been changed.

 

[PeroK]

I interpreted it in my old standard. The standard might have been changed.

You were right. I initially assumed anyone could be paired with anyone else, but I'm sure that's wrong.

There's a neat solution.

 

[Master1022]

Hi, sorry for late replies. Thanks @PeroK , @anuttarasammyak , and @WWGD for the replies. I did a bit of reading around earlier today and also came across the mention of 'derangements' (as mentioned by @WWGD). I'll have a bit more of a look into that to see whether I can make any progress and then post back here with my updates.

@PeroK : in post #12, did you suggest that the above solution methods in the thread were correct, or are they still wrong (due to different interpretation based on my unclear wording)?

 

[PeroK]

@PeroK : in post #12, did you suggest that the above solution methods in the thread were correct, or are they still wrong (due to different interpretation based on my unclear wording)?

It's definitely the case that if you have two couples $A_1, A_2, B_1, B_2$, then $A_1$ may only be paired with either $A_2$ or $B_2$. And $A_1$ cannot be paired with $B_1$.

Here's how I approached the probl;em.

First, I calculated the probabilities, mean and variance for $n = 2, 3$ and $4$. The pattern was obvious, so it was a question of proving it.

The mean was easy. Think about repeating the experiment many times and the relationship between a single couple being paired together and the expected number of couples being paired together each time.

The variance, as I said, was trickier. Then I had an idea that I might be able to relate $p_{n+1}(k+1)$ to $p_n(k)$ - where this is the probability of $k$ couples out of $n$ being paired together. I looked at the data for $n = 2, 3, 4$ and spotted the relationship. I then proved it.

Using this, I was able to relate the variance for $n+1$ to the expectation for $n$. And, this gave me the inductive step.

I hope that makes sense.

 

[anuttarasammyak]

@PeroK : in post #12, did you suggest that the above solution methods in the thread were correct, or are they still wrong (due to different interpretation based on my unclear wording)?

I suppose another interpretation of the problem is stated as :

There are 2n pupils in the class. Teacher said they should be paired for some class work. Calculate p(m), probability of m pairs matched after the first vote of with whom they want to make a pair.

In order to make it mathematical ideal, the teacher give 1 to 2n number cards to the pupils. They know only their own number and should vote a number of not their own.

First easy cases
For n=1
1pair : 1 case
e.v.=1, sigma=0

For n=2
2 pairs : 3 cases
1 pair : 4C2 *(3^2-1)= 48 cases
0 pair : 3^4-3-48=30 cases
e.v. = 54/81=2/3=0.667
sigma = $\sqrt{96/(81*9)}=0.363$

[EDIT]
Some class consists of odd number pupils. For class of 3 pupils
1 pair : 6 vote cases
0 pair : 2 vote cases
p(0)=1/4, p(1)=3/4=e.v., sigma=3/8