Closed form for BAPC 2019 lucky draw problem

43 Views Asked by At

The competition BAPC 2019 had a problem called Lucky Draw. The problem statement is as follows:

At the casino, $n$ players start with $k$ lives each. Each round, each player loses a life with probability $1 − p$. You win if you are the only one remaining. What is the probability of a draw?

In the competition you could solve this using the series:

\begin{align} \mathbb P(\text{draw}) &= 1 - \mathbb P(\text{someone wins}) \\ &= 1 - n \cdot \sum_{i=1}^\infty \mathbb P(\text{Player 1 dies round $i$, other players die before round $i$}) \\ &=1 - n\cdot\sum_{i=1}^\infty\mathbb P(\text{Player 1 dies round $i$}) \cdot \mathbb P(\text{Player 1 dies before round $i$})^{n-1} \end{align}

These probabilities can be computed using the formula

\begin{equation} \mathbb P(\text{Player 1 dies round $i$}) = \binom{i-1}{k-1}p^{i-k}(1-p)^k. \end{equation}

which can be summed to obtain $\mathbb P(\text{Player 1 dies before round $i$})$.

Since this was a programming competition, summing this series until the terms vanished was enough, but is it possible to express the series in a closed form?