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?

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$.

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}$.

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$.

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?

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$.