7

Suppose there are 34 poeople standing in a row in random order, among them 18 are male and 16 are female. If two people adjacent to each other belong to different genders, we consider them to be a couple, how many couples are we expected to see on average?

Xiaowen Li
  • 303

3 Answers3

13

First, we find the probability that two adjacent individuals are of different genders. Those two people are equally likely to be any of the ${34 \choose 2}$ pairs of people, of which $18 \times 16$ are male-female pairs, so this probability is $(18 \times 16)/{34 \choose 2}$.

The total number of pairs is $X_1 + X_2 + \cdots + X_{33}$ where $X_i$ is an indicator random variable that is 1 if person $i$ and person $i+1$ are of opposite genders and 0 otherwise. Its expectation is $E(X_1) + \cdots + E(X_{33})$, but all these variables have the same expectation, the probability we found above. So the answer is

$$ 33 \times {18 \times 16 \over {34 \choose 2}} = {33 \times 18 \times 16 \over (34 \times 33)/2} = {18 \times 16 \over 17} = {17^2 - 1 \over 17} = 17 - {1 \over 17} \approx 16.94.$$

This agrees with Bernhard's simulation.

More generally, if you have $m$ males and $f$ females and the same problem you get

$$ (m+f-1) {mf \over {m+f \choose 2}} = {(m+f-1) mf \over (m+f)(m+f-1)/2} = {2mf \over m+f}$$

which can also be checked by simulation.

Michael Lugo
  • 711
  • Amazing derivation. How did you avoid getting trapped into thinking about drawing random samples without replacement? – Xiaowen Li Feb 17 '21 at 16:20
  • 4
    Lots of practice. Seriously, though, if you're only looking for the expected value then using indicator random variables is usually the way to go. (You can derive the variance this way as well but it's more work - you end up having to consider two indicators at a time.) – Michael Lugo Feb 17 '21 at 17:17
  • 2
    This is a really nice solution. I did not expect the answer to be the harmonic mean of $m$ and $f$, but there it is! – Sammy Black Feb 18 '21 at 00:13
  • 2
    Even more generally, one should look for any excuse to use linearity of expectation—which means that writing a random variable as a complicated sum of simple random variables is usually a productive way to find the expectation. – Greg Martin Feb 18 '21 at 07:53
  • Would you mind if I include a link to this answer in the hint for https://github.com/atorch/probability_puzzles/blob/master/app/src/main/res/values/strings.xml#L651 ? – Adrian Feb 19 '21 at 06:20
  • 1
    @Adrian - go ahead! Sadly I can't actually see the app as an iOS user, but from what I can see at the link it looks like a nice bunch of puzzles! – Michael Lugo Feb 19 '21 at 16:38
5

Someone much wiser then me will post a theoretical and exact solution. Meanwhile my attempt at a simulation:

once <- function(){
    row <- sample(c(rep("m", 18), rep("f",16)))
    count <- 0
    for(i in 1:33){
        if(row[i]!=row[i+1]) 
        count <- count + 1
    }
    return(count)
}

run <- replicate(1e5, once())
plot(table(run))

enter image description here

> table(run)
run
    6     7     8     9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25    26    27    28    29 
    5    25    79   280   663  1643  3070  5555  8057 11169 12883 14309 12818 11020  7682  5279  2931  1535   635   261    78    17     4     2

> summary(run)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   6.00   15.00   17.00   16.96   19.00   29.00
Bernhard
  • 8,427
  • 17
  • 38
  • Thanks for the simulation. Unfortunately this is a job interview question. If I could run simulations many problems could be in solved very easily. – Xiaowen Li Feb 17 '21 at 15:20
  • 2
    @XiaowenLi: If you have a job interview definitely outline a simulation approach too. (And I hope it goes well of course!) – usεr11852 Feb 17 '21 at 23:44
0

Alternative solution :

Imagine the 34 people form a circle instead of a row. Then for any given female A :

E( # couples A is in) =

E( # righthand couples A is in) + E( # lefthand couples A is in) =

P(to A's right is a man) + P(to A's left is a man) = m/(m+f-1) + m/(m+f-1) = 2m/(m+f-1)

So E( total # of couples) = f * E( # couples A is in) = 2mf/(m+f-1)

This is the expectation when the people form a circle. To form a row the circle is cut in a random place. The number of potential couples decreases from (m+f) to (m+f-1), i.e. with a factor (m+f-1)/(m+f) and the expected number of couples decreases proportionally:

(2mf/(m+f-1)) * (m+f-1)/(m+f) = 2mf/(m+f)

Boudewijn
  • 1