You have $n$ people, $m$ of whom are traitors. You keep killing them randomly until all the traitors are gone (which you presumably have some way to verify). On average, how many people $X$ will you have to kill until there are no traitors left?

At a glance, it seems related to the coupon collector problem, but all the slick methods of solving the coupon collecting problem don't work here for one reason or another. Are there any assumptions you can make on $m$ and $n$ (e.g. their proportion as they go to infinity) that gives some simple answer? Also, even better, I'd really like to know the probability that one kills all the innocents before the traitors (as a function of $n$ and $m$), or at least what relationship $n$ and $m$ should have so that it's 50-50 whether you kill all the traitors before the innocents.

For now, all I have is a brute force sum that'll give you the answer.

$$\mathbb{E}(X) = \sum_{k=m}^n \Pr[X = k] \cdot k$$ where $$\\Pr[X=k] = \frac{m\cdot{n-m \choose n-k}\cdot(n-k)!\cdot (k-1)!}{n!}$$ $$=\frac{m\cdot(n-m)!\cdot(k-1)!}{n!\cdot(k-m)!}$$ This is because there are $n!$ orderings you can kill everyone. To take exactly $k$ people to kill the traitors, first you have $m$ choices for the last traitor killed at step $k$, then you choose $n-k$ people to survive from the $n-m$ innocents, then you order the survivors in $(n-k)!$ ways, and order the killed in $(k-1)!$ ways.

Also, just to note, it's fairly obvious that the coupon collector problem gives an upper bound on this problem, but the bound it gives ($n \ln (m)$), is worse than the trivial bound of $n$.

Edit: Realized it's obvious that $m=n/2$ is when it's equally likely that traitors will be killed before innocents. As for the probability innocents are killed first, it's the probability that the last person killed (if you were to kill all $n$ people in a random order) is a traitor, which is literally just $\frac{m}{n}$.


As pointed out in the comment, this is a special case of the Negative Hypergeometric distribution. So the answer is, on average, $$\frac{m}{m+1}(n-m)$$ innocents will be killed before all $m$ traitors are killed, meaning $$\mathbb{E}(X) = \frac{m}{m+1}(n-m) + m$$ people total are killed on average. In other words, $\frac{1}{m+1}$ will be the average fraction of innocents that survive (independent of the total number of innocents). Pretty interesting result IMO. Even if you have a million innocents and just 9 traitors, only 10% of the innocents will survive on average if you keep killing randomly till the traitors are all gone.

| cite | improve this answer | |
  • $\begingroup$ Your question is "On average, how many people $X$ will you have to kill until there are no traitors left?" If we consider the simple case $n=m$ where everyone is a traitor, obviously all $n$ people must be killed but your formula just as obviously gives $0.$ That needs fixing. $\endgroup$ – whuber Mar 29 '19 at 18:40
  • $\begingroup$ @whuber My answer I give here, for compactness, is "how many innocents will one kill on average", which is correct even in the case that $m=n$ (there are 0 innocents to kill). In order to recover my original quarry of "how many people total must be killed", you simply add $m$ to account for the traitors you kill along with the innocents. $\endgroup$ – chausies Mar 30 '19 at 3:28
  • 1
    $\begingroup$ When you frame the answer to a question in terms that differ from how the question was stated, confusion ensues. In this case, as the poser and the respondent, you have every opportunity to make the answer consistent with the question. $\endgroup$ – whuber Mar 30 '19 at 14:22
  • 2
    $\begingroup$ @whuber got it. Updated my answer to reflect the terms of the original query $\endgroup$ – chausies Mar 30 '19 at 14:39

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.