Let's start with a simple problem:
A and B enter a paintball duel, where each one has a 50% chance of tagging another. The game will last until there is one player left, who will become the winner. A goes first. Calculate the probability of A being the winner.
Let's call the probability of A being the winner is $x$.
When A goes first, A has a $1/2$ chance of tagging B, and the other $1/2$ B will has a $1/2$ chance of tagging A, and so on. Let's look at how symmetric this problem is: when A misses, B will play the game as if B goes first, in other word, B will take the role of A and have an $x$ chance of winning, which makes A has a $1-x$ chance of winning.
Therefore, we have the equation: $x = 1/2 + 1/2(1-x)\Leftrightarrow x=2/3$.
So the probability of A winning is $2/3$, B winning is $1/3$.
Another way to solve this problem is to think about the fact that when A and B both miss, which happens in $1/4$ of the time, where the game will return to its initial state, where A has an $x$ chance of winning,
We have another equation: $x = 1/2 + (1/4)(x)\Leftrightarrow x=2/3$.
Now, let's move on to the harder one:
A, B and C enter a paintball duel, where each one has a 50% chance of tagging another. Each player will aim at the player of next turn. The game will last until there is one player left, who will become the winner. A goes first, then B, then C. Calculate the probability of A being the winner.
This problem is harder because A does not automatically win when A tags B, because C will take the next turn and have a 50% chance of tagging A. But if we look carefully, we can see another pattern here, C will play against A where C goes first, which means this problem is reduced to a 2-way duel, where we already have the solution.
Let's call the probability of A being the winner is $x$.
A will have a $1/2$ chance of tagging B, and then C will go first against A, which means A only have $1/3$ chance of winning.
A will have a $1/2$ chance of not tagging B, then B will have a $1/2$ chance of tagging C and then A will go first against B, where A will win with $2/3$ chance; or B will have a $1/2$ chance of not tagging C and then C will have a $1/2$ chance of not tagging A, which makes the game return to its initial state, where A will have an $x$ chance of winning.
Therefore, we have the equation:
$x = (1/2)(1/3 + (1/2)(2/3 + (1/2)(x)))\Leftrightarrow x=8/21$
So the probability of A winning is $8/21$
B will have a 50% chance to take the role of A, only when A misses the first shot. So the probability of B winning is $4/21$
The probability of C winning will be $9/21 $
What's important to take note here is that C will not lose regardless of the result of A aiming at B and have the highest chance of winning despite going last.
I tried to use Python to simulate the n-ways duel, record the winner of a large number of matches (desirably 100000) and the only pattern I got from the results is the probability of the first player winning is double the probability of the second player winning, while I can't figure out the pattern of the remaining ones.
My questions are, how can I figure out the probability of each player winning in an n-way duel without calculating every single case. Is there a pattern or recursive manner hidden in this problem? Why does the denominator 21 exist in a 3-way duel?
Thanks for your time reading through all of this.
Best Answer
Assume there are $n$ players. As easy to understand the probability $r(n,k)$ that the $k$-th player will be tagged is: $$ r(n,k)=\frac1{2^n-1}\times\begin{cases} 1,&k=1;\\ 2^{n-k+1},&k\ne1. \end{cases}\tag1 $$ After the $k$-th player leaves, we have the duel of $n-1$ players with shifted indices so that the $k+1$-th player becomes the first, and $k-1$-th player becomes the last $n-1$-th one.
Thus the probability that the $k$-th player survives all rounds can be recursively computed as ($1\le k\le n$): $$ p(n,k)=\begin{cases}1,&n=1;\\ \sum\limits_{1\le i<k}r(n,i)p(n-1,k-i)+ \sum\limits_{k<i\le n}r(n,i)p(n-1,k-i+n),&n>1. \end{cases}\tag2 $$
The solutions of the recurrence (2) are rational numbers $\frac{P_{nk}}{Q_n}$. The numerators $P_{nk}$ for small values $n$ and $k$ are given in the following table: $$ \begin{array}{l|lrrrrr|r} n&k\to&1&2&3&4&5&Q_n\\ \hline 1&&1&0&0&0&0&1\\ 2&&2&1&0&0&0&3\\ 3&&8&4&9&0&0&21\\ 4&&104&52&86&73&0&315\\ 5&&2272&1136&2180&1896&2281&9765 \end{array} $$
The denominators (last column of the table) have the form: $$ Q_n=\prod_{i=1}^n (2^i-1). $$