In a group of people rolling dice, what is the probability that you tie for highest roll multiple times in a row?

Question

This problem was inspired by a Reddit post which you can find here.

You are in a group of 40 people. Each of you rolls a 100-sided die. If a single person has the highest roll, then that person wins. But if two or more people tie for the highest roll, then those people — and only those people — roll again. This process repeats until one person wins (i.e., rolls a number greater than all other numbers rolled in that round).

What is the probability that you participate in three rounds of ties before someone ultimately wins on the fourth round?

Can you generalize this to a group of $P$ people, a die with $Q$ sides, and $R$ rounds of ties?

Answer 1

I'll outline a method that will solve the problem, but won't bother doing whatever simplifications that exist.

First off, completely split every round separately. In one round, what you have is a group of $P$ people rolling $Q$ sided dice. You now have a distribution over how many people tie for rolling the highest number, say $1\leq P'\leq P$ (and whether you are in it or not).

In the next round, you have the same problem: $P'$ people are rolling $Q$ sided dice.

Essentially, you have a Markov chain, which is a transition matrix $T$, with $$T_{ij}=\Pr(\text{Round }n+1\text{ has }j\text{ people remaining}\mid\text{Round }n\text{ has }i\text{ people remaining})\text{.}$$ If $\vec{v}$, a row vector, is the distribution of remaining people at round $n$ (for any $n$, including $0$), then $\vec{v}T$ is the distribution at the next round.

At round $0$, there are exactly $P$ people, so $\vec{v}=[0,\dotsc,1]$ (of length $P$). You want to look at the distribution at round $R+1$, and pick off the probability of a unique winner, which is simply $\vec{v}T^{R+1}[1,\dotsc,0]^T$.

It remains to specify $T$. These entries can be computed as follows:

1. Fix $i$, the current players first, then there are going to be $Q^i$ equally likely outcomes.
2. The number of ways, hence probability to get (i) highest number exactly $k$, (ii) with exactly $j\leq i$ people rolling it is simply $$\binom{i}{j}\left(\frac{1}{Q}\right)^j\left(\frac{k-1}{Q}\right)^{i-j}\text{.}$$
3. We don't care about $k$, so simply sum this thing right up: $$T_{ij}=\frac{1}{Q^i}\binom{i}{j}\sum_{k=1}^{Q-1}k^{i-j}\text{.}$$ This sum of powers of integers has been studied extensively, but there's no "simple" formula.
4. In your version of the problem, you additionally have to consider that you are in the set of people who have rolled the highest. If there are $j$ people rolling the highest, your chance of being one of them is... $$T_{ij}=\frac{j}{i}\frac{1}{Q^i}\binom{i}{j}\sum_{k=1}^{Q-1}k^{i-j}$$ Note that the probabilities don't sum to $1$ any more, but that's not a problem - the missing probability mass is "you lost the game".

As a framing challenge, I suggest that focusing on one specified person is not important: anyone could have seen this event and posted about it, so the $p$-value in statistical terms should not count that.