Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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
add comment

1 Answer

up vote 2 down vote accepted

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.

Added

You might want to look at: Klamkin, M. S. and Newman, D. J. "Extensions of the Birthday Surprise." J. Combin. Th. 3, 279-282, 1967.

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$.

share|improve this answer
    
Any chance of an asymptotic? I am interested in cases where n is large (millions). –  Charles Sep 13 '12 at 15:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.