Suppose we have a game where each round, a random winner is chosen among $m$ players. The game ends when a person has won $k$ rounds. What's the expectation value of total rounds played in the game?
This is a question I came up with when playing a card game and has been bothering me ever since.
For convenience of the expressions below I will redefine $k\mapsto k+1$, so that $k+1$ wins of a player are required to end the game.
In terms of generating functions the probability that the game will end in $n+1$ rounds is:
$$ P_n(m,k)=\frac{n!C_{n}(m,k)}{m^{n}}\tag1 $$ where $$ C_n(m,k)=[x^n]\frac{x^k}{k!}\left(\sum_{i=0}^k\frac{x^i}{i!}\right)^{m-1},\tag2 $$ with $[x^n]$ being the coefficient extractor.
The expected number of rounds can then be computed as: $$ R(m,k)=\sum_{n\ge0}(n+1)P_n(m,k)=\sum_{n=k}^{km}\frac{(n+1)!C_{n}(m,k)}{m^{n}}.\tag3 $$
For the case $m=2$ it is not hard to find the closed form of the above expressions: $$\begin{align} P_n(2,k)&=\binom{n}{k}\frac1{2^n},\quad k\le n\le 2k,\\ R(2,k)&=(2k+1)\left[1-\binom{2k}k\frac1{4^k}\right]+1. \end{align}$$
