5
$\begingroup$

Let's suppose you are playing a game similiar to “Among Us”. There are $10$ players and $2$ of them are impostor/traitors.

Normally, they would kill people secretly stab people, convince, manipulate, lie and etc. to win the game but lets spice things up and suppose that all players decide to eliminite one person at a time and no one leaves the election room! These are the rules.

  1. $-$ No killing between rounds other than elections.

  2. $-$ They can't vote two people at the same round, one at a time!

  3. $-$ Vote priority is determined by number of persons seat. They vote by the numbers $(1,2,3,\dots).$

  4. $-$ Seats are given randomly.

Normally, this would be a fairly simple question if there was just one impostor/traitor.

For a impostor to win the game, he must either be the last man standing or there must be just one innocent. That means he must sit on one of the green seats like this:

One impostor situation

Probability of an impostor/traitor win is $\frac{2}{10} = \frac{1}{5}$ (in percentage, $20\%$).

But what if there were two impostors/traitors?

By the way, for an impostor win, innocent players must be at least $n$ where $n$ is the number of impostors in the game.

You may have noticed that I said this for a one impostor/traitor situation too. For example, if the $2$ impostors/traitors are in the $7$ and $8$ seats, game is over when the $6$ is out of the election because the only innocent players that are alive are $9$ and $10$ and we have $2$ impostors/traitors. So $n=2$ and voila! Impostor/traitors won.

Question is: What is the probabilty for an impostor/traitor win where there are $2$ of them?

Side note: I am new to this site so if there is something wrong with the question please let me know.

$\endgroup$
2
  • $\begingroup$ Haha, I've been playing this game way too much lately! I'm a bit confused regarding the question though: Are you trying to find the probability that if $2$ impostors are randomly assigned among the $10$ seats, and players are sequentially voted off, the number of impostors would at one point be at least the number of "crewmates"? $\endgroup$ Sep 25 '20 at 0:56
  • $\begingroup$ Yeah exactlty Varun $\endgroup$ Sep 25 '20 at 8:23
2
$\begingroup$

More generally, we can ask the question: What is the probability, denoted $f(k, n)$, that with $k$ impostors and $n$ other players (referred to as "crewmates" in the game), the impostors will win? For your specific question, $k = 2$ and $n = 8$.

Clearly $f(k, n) = 1$ for $k \ge n$ and $0$ for $k = 0$. Otherwise, we can make a recurrence where a player is eliminated each time. The probability would be given by $$f(k, n) = P(\text{first player being impostor}) \cdot f(k-1, n) + P(\text{first player being crewmate}) \cdot f(k, n-1)$$

These probabilities would be given by $\frac{k}{k+n}$ and $\frac{n}{k+n}$ respectively, so the recurrence is $$f(k, n) = \frac{k}{k+n}f(k-1, n) + \frac{n}{k+n}f(k, n-1)$$ For $k = 2$, $n = 8$, this evaluates to $\frac{2}{5}$.

Making the substitution $g(k, n) = (k+n)f(k, n)$ makes the recurrence $$g(k, n) = \frac{k}{k+n-1}g(k-1, n) + \frac{n}{k+n-1}g(k, n-1)$$

You already know that $g(0, n) = 0$ and $g(k, n) = k+n$ for $k \ge n$. Then given that $g(1, 1) = 2$, it is easy to show that $g(1, n) = g(1, 1) = 2$. Similarly, given that $g(2, 2) = 4$, you can show that $g(2, n) = g(2, 2) = 4$. In general, $g(k, n) = 2k$, and so $$f(k, n) = \frac{2k}{k+n}$$

Intuitively, this sort of makes sense, since we are trying to find the probability that the total number of seats the impostors occupy is at least half as many of the total number of seats at one point (i.e. the probability that $\frac{2k}{n+k} \ge 1$ at one point).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.