Suppose that $n \geq 2$ players independently draw numbers from a discrete distribution with a maximum possible value $x$. If one player draws a higher number than all the others, then that player is the winner of the game. However, if a number of players $m \geq 2$ all draw the highest number, then one of the $m$ tying players is chosen at random and with equal probability to win the game (so each of the tying players has a $1/m$ chance of winning).
Suppose that I draw my number and it is the highest possible number $x$. Intuitively, one would expect that my probability of winning (given that my number is $x$) falls as the number of players rises: after all, increasing the number of players makes it more likely that others have drawn the maximum $x$ as well. Unfortunately, however, I am struggling to prove this formally. Does anyone have any ideas?
My thoughts so far:
Let $p \in (0, 1)$ denote the probability that a player draws the maximum $x$. Given that my number is the maximum $x$ and I have $n – 1$ opponents, my chance of winning is
$$ (1 -p)^{n-1} + (1 – p)^{n-2}p(n-1)\left(\frac{1}{2}\right) + … + (1 – p)p^{n-2}(n-1)\left(\frac{1}{n-1}\right) + p^{n-1}\frac{1}{n}.$$
In other words, my chance of winning (given that my number is $x$) is
$$ \sum_{i=1}^{n} (1 – p)^{n-i}p^{i – 1}{n-1\choose i – 1}\frac{1}{i} $$
where the $1/i$ term captures the chance of winning if tied against $i = 1, 2, …$ opponents and the $n-1$ choose $i – 1$ term captures the fact that the relevant events can happen in various ways.
Now, if we could show that this sum falls at $n$ increases, we would be done. And indeed each individual term does fall as $n$ increases (since we are raising probabilities to a higher power). But as $n$ rises, we are also adding new terms! (Compare $n = 2$ and $n = 3$.) Is there any way to argue that the 'new terms' effect is smaller? Or is there a simpler way to proceed?
Best Answer
Outline: using the identity $\binom{n-1}{i-1}\frac1i = \binom ni\frac1n$, you can evaluate the sum in closed form as $$ \frac{1-(1-p)^n}{np}. $$ To show this is a decreasing function of the integer $n$, we consider the differences $$ \frac{1-(1-p)^n}{np} - \frac{1-(1-p)^{n+1}}{(n+1)p} = \frac{1 - (1 - p)^n (1 + n p)}{n(n+1)p}; $$ since $1+np < \sum_{k=0}^\infty \binom{n+k-1}k p^k = (1-p)^{-n}$, this difference is positive.