# First player to win k matches

A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I'm looking for a probabilistic description of the outcome when looking at the first player to win 1, 2, ... matches.

For example, if player #3 is the first player to win 400 matches, she has a better than 1/n chance to be the first player to win 401 matches.

In particular: how many matches need to be played before some player wins k? (The dominant term is of course kn but what is the next (negative) term?) How often does the lead change places? (I expect infinitely often, but with decreasing frequency... maybe sqrt-ly many times?)

I have a decent math background but have not studied any probability since a basic undergrad class.

Related question: How long until everyone is in the lead?

-
Title is somewhat misleading when reading your text. Do you want to win $n$ matches as in there are $n$ competitors or are you interested in winning $k$ matches for some $k$ independant of $n$, the number of players? –  Jean-Sébastien Sep 10 '12 at 0:38
There seem to be three quite different questions (or more) here. 1) Probability that player A is the first to win $k+1$ games, given that he was the first to win $k$ games. 2) how many matches (expectation? full distribution) need to be played before some player wins $k$. 3) distribution of the event "the leader changed" (what about ties?) –  leonbloy Sep 10 '12 at 0:47
@Jean-Sébastien: I edited the title. –  Charles Sep 18 '12 at 13:33

This is not simple.

For $n=2$ you can base this on the probability or number of ways of reaching the previous step of having one of the players having one have won $k-1$ games and nobody else having won more, giving the expression $$2 \sum_{j=k}^{2k-1} \left. j {j-1 \choose k-1} \middle/ 2^j \right.$$ $$= 2k \left(1 - {2k \choose k} \middle/ 4^k \right).$$

For $n \gt 2$ you can develop a similar approach based on

$$n \sum_{j=k}^{nk-n+1} \left. j {j-1 \choose k-1} f(j-k,n-1,k-1) \middle/ n^j \right.$$

where $f(a,b,c)$ is the number of ways of putting $a$ labelled balls into $b$ labelled boxes subject to each box having no more than $c$ balls.

I have not read it, but apparently it gives expressions like $$\int_0^\infty \left(e_{k-1}\left(\frac{t}{n}\right)\right)^n \, e^{-t} \, dt$$ where $e_{k-1}(x) = 1+\frac{x^1}{1!}+\cdots + \frac{x^{k-1}}{(k-1)!}$ is a truncated exponential, and asymptotic values like $$\left(k!\right)^{1/k} \,\Gamma\left(1+\frac{1}{k}\right) \, n^{1-1/k}$$ for fixed $k$ as $n$ increases. For $n=365$ and and $k=2$, the first of these gives about $24.616585894$, which is correct (we are looking for the mean not the median of the birthday problem) and the second gives about $23.9$.