We're playing a game in the Puzzles and Other Games (POG) section of 2p2 & I have a question about odds.

I won't go into too much into detail about all of the specifics of the game and will focus just on the question I have.

There are 15 of us playing. We are identified as Player A, B, C, D, etc. Each round consists of 3 groups of 5 players. Each group has 4 villagers and 1 chameleon. The 15 of us are randomly assigned a group and then randomly assigned a role within that group. So in any given round of the game, there's a 4 in 5 chance that I'll be a villager in my group.

We have played 13 rounds thus far, and one player (Player G) has been a villager every single time. It seems like a pretty simple calculation to determine the odds of this happening. (4/5)^13. Or roughly 1 in 18. But that's the likelihood that Player G, specifically would be a villager 13 times in a row to start the game.

My question is this. What is the likelihood, that any one of us would start the game by being a villager for 13 consecutive rounds? I know it's a lot more likely that 1 in 18, but I'm at a loss of how to construct the formula to answer this.

Thanks for your help!

I think it's this: 15(4/5)^13 - C(15,2)*(4/5 * 4/7)^13 + C(15,3)*(4/5 * 4/7 * 4/13)^13 ≈ 82.06%

I used inclusion-exclusion. The first product double-counts the chance of two players being villager every time, so I subtract that (the 2nd product). For it to happen to two players, they have to be in different groups, for which there is a 10/14 or 5/7 chance, so it's 4/5 * 5/7 * 4/5 = 4/5 * 4/7. And then I add back the over-subtracted case of 3 players being villager every time.

As you can see, the first product is already close to the answer, and that's because the chance of it happening to more than one player is slim.

So you're saying that the fact that we've gone 13 rounds and one of us has been a villager in every round is actually quite likely. I was one of the last two remaining players through 8 rounds, but then I landed on chameleon in round 9. Since then, we've all been wondering how long it will take before the last player finally takes a turn as a chameleon.

Thanks for the help!

It can be done with inclusion-exclusion, but the 2nd and 3rd terms are uglier than heehaww's.

His first term is correct: the expected number of "unmarked" villagers is 15(4/5)^n after the n-th round, and after 13 rounds this is 0.8246. This means that there is less than a 82.46% chance of it happening, because there may be more than one villager.

At each round, if there are k unmarked villagers, and we randomly draw 3 people to mark, there will be k-i unmarked villagers in the next round with probability (k C i ) (15-k C 3-i) / (15 C 3).

After 1 round, there will always be 12 unmarked villagers.
After 2 rounds, there will be 9, 10, 11, or 12 unmarked villagers, with probability 44/91, 198/455, 36/455, and 1/455 respectively.

We can find the exact distribution of outcomes after n rounds by building ourselves a Markov chain. If we do so, we'll find the situation after 13 rounds is:

No unmarked villagers - 39.30% (176798797208157578719462291776 / 449882097396212029388505859375, if you want to be precise);
1 - 42.05%
2 - 15.78%
3 - 2.65%
4 - 0.21%
5 - 0.008%
6 - 0.00013%, etc.

A person who didn't want to do all that multiplying might also have guessed that a Poisson distribution with mean 15(4/5)^n would get us close. It gets us at least sort of close: Poisson would have said P(0 unmarked villages)=.4384 instead of .4205.

Incidentally, you were somewhat unlucky to be one of only two left after 8 rounds: there's about a 30% chance of 2 or 3 left, and 15% chance of 1 or 4 left, at that point. Only a 2.7% chance of hitting everyone in the first 8 rounds.

Edited to add the correct inclusion-exclusion terms:

The first term is the number of people, times the chance of one person being missed every time, to the 13th power: 15(4/5)^13 = .8246.

The second term is the number of pairs of people, times the chance of both people being missed every time, to the 13th power: 15C2 * (13C3/15C3)^13 = 105 * (286/455)^13 ~ 0.2511

The third term: 15C3 * (12C3/15C3)^13 = 455 (220/455)^13 ~ .0359.

The true probability of at least one person being missed, .6070, is indeed between .8246-.2511=.4735 and .8245-.2511+.0359=.6094, and closer to the latter.

And a shout out to the POG folks!

I was very active in POG from roughly 2006 to 2010. Then had a job that blocked the site, then was busy and didn't seem to know anyone or what the new popular games were.

I agree with Siegmund.

I started out thinking about villager, but then part of my calculation assumed we wanted chameleon and it became a jumbled mess. Also, it's not necessary to think about the groups of 5, even if we were interested in chameleon.

Up to 12 people can be villager every time, so the full PIE solution has 12 products, not 3. But the products quickly shrink.

15(4/5)^13 -
C(15,2) * [C(12,2) / C(15,2)]^13 +
C(15,3) * [C(12,3) / C(15,3)]^13 -
C(15,4) * [C(12,4) / C(15,4)]^13 +
...

Evaluating the first 5 lines and gives 60.70%

Final answer, no simulation necessary.