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.

Earlier, I asked a question about a series of competitions:

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.

Now I am able to ask my full question. In this scenario, what is the expected time until all players have been in the lead at least once? (Say, with probability at least 1/2 -- though other measures of central tendency are probably fine if they're easier to work with.)

For $n=1$ this takes only one match. For $n=2$ this is just a 1-D random walk (essentially, start at 1 and see how many steps you take until you become negative); I find that after 9 matches both players have been in the lead with probability 65/128 > 50%. Even with $n=3$ it gets hard to find an exact answer because of the exponential blow-up (it is at least several hundred).

So what I'm really looking for is an asymptotic, since my interests lie in $n$ much larger than 3.

share|improve this question
1  
What would be a simple argument to show that with 3 players, indeed each of them is in the lead at some time, with full probability? –  Did Sep 15 '12 at 8:54
1  
Note that 'time at which (all players have been in the lead at least once) with probability at least 1/2' and 'expected time at which (all players have been in the lead at least once)' are two entirely different notions. (Consider the event 'I have rolled a 1 on a six-sided die'; then the expected time to the event is 6 trials, but with probability $\frac{671}{1296}\gt\frac{1}{2}$ you will have succeeded at least once after 4 trials.) –  Steven Stadnicki Dec 11 '12 at 6:49
    
@StevenStadnicki: I'd be happy to see either answer. –  Charles Dec 11 '12 at 16:06
add comment

1 Answer 1

I don't have a complete answer, but I do have a train of thought which might prove useful and which I intend to expand upon as time allows.

Keeping track of $n$ different scores is obviously difficult as $n$ gets large, so I intend to keep track of only a few significant statistics and use probability distributions to calculate expectations.

At any time $t$ we can divide the players into two groups, those have have been in the lead at some point, and those who have not, but rather then keeping the individual scores of each person in the group we can instead keep track of three relevant statistics: $n_i$ the number of people in the group, $\mu_i$ the average score of the people in the group, and $\sigma_i$ the standard deviation of the scores of the people in the group. Letting $i=1$ be the group who have been in the lead and $i=0$ be the people who have not.

Now we must work out how these number evolve over time. At $t=1$ there is one person with a score of $1$ and everyone else has a score of $0$, so our statistics are:- $$t=1,\;\;\;n_1=1,\;\mu_1=1,\;\sigma_1=0,\;\;\;n_0=n-1,\;\mu_0=0,\;\sigma_0=0 $$ After each competition we must adjust these statistics based on who won and then test to see if there are any new leaders. Each group has probability $n_i/n$ of including the winner, and the group with the winner will clearly increase the average score, and possibly also the standard deviation depending on who in the group won.

Now if we had kept all the scores $x_i$ of the people in each group we would simply increment the score of the winner $i$ by one, $x_i^{t+1}=x_i^t+1$ but what effect would this have on our statisitcs? $$\mu_t=\frac1n\sum_{i=1}^n{x_i}\;\;\;\;\;\sigma_t^2=\frac1n\sum_{i=1}^n{x_i^2}-\mu_t^2$$ Assuming player $1$ won for conveniance let us calcualte the values a time $t+1$ $$\mu_{t+1} =\frac1n(x_1+1)+\frac1n\sum_{i=2}^n{x_i} =\frac1n{x_1}+\frac1n\sum_{i=2}^n{x_i}+\frac1n =\frac1n\sum_{i=1}^n{x_i}+\frac1n =\mu_t+\frac1n$$ So the average value of the group increases by one divided by the number of people in the group no matter which person won, as we would expect. Now what happens to the variance? $$\sigma_{t+1}^2 =\frac1n(x_1+1)^2+\frac1n\sum_{i=2}^n{x_i^2}-\mu_{t+1}^2 =\frac1n(x_1^2+2x_1+1)+\frac1n\sum_{i=2}^n{x_i^2}-(\mu_t+\frac1n)^2$$ $$=\frac1n(x_1^2)+\frac1n\sum_{i=2}^n{x_i^2}+\frac1n(2x_1+1)-(\mu_t^2+\frac{2\mu_t}n+\frac1{n^2})$$ $$=\frac1n\sum_{i=1}^n{x_i^2}-\mu_t^2+\frac1n(2x_1+1-2\mu_t-\frac1n)$$ $$=\sigma_t^2+\frac1n(2x_1+1-2\mu_t-\frac1n)$$ Unlike with the average, we still have a term $x_1$ left, so clearly who wins is important. And this ties well with our intuition that if the lowest person increased their score it would bunch them up lowering the variance, but of the person with the highest score gets even further ahead it increases the variance. But the expected value of $x_i$ is $\mu$, and so over many such steps we will assume it balances out and the $2x_1$ term cancels the $2\mu$ term and we are left with:- $$\sigma_{t+1}^2=\sigma_t^2+\frac1n(1-\frac1n)=\sigma_t^2+\frac1n-\frac1{n^2}$$ Does this look reasonable? Well, for $n=1$ (where we expect $\sigma$ to remain zero for all $t$) the $\frac1n$ and $\frac1{n^2}$ terms cancel out, and $\sigma_{t+1}^2=\sigma_t^2$ as desired. For larger groups these terms are unequal and cause the variance to slowly increase as more games are played, as we would expect.

If the winner was someone from the group of people who have never been in the lead, we must now estimate the probability that one of them is now in the lead and should therefore be moved to the other group.

Since we have not stored all the individual score we make them up using our distribtions, so we have $n_0$ random variables $X_i$ with distribution $F(\mu_0,\sigma_0)$ and $n_1$ random variables $Y_i$ with distribution $F(\mu_1,\sigma_1)$.

$\mathbb{P}($Person with highest score is in group 0$)=\mathbb{P}(X_{Max}>Y_{Max})$

$$X_{Max}=\max\limits_{i=1}^{n_0}(X_i), Y_{Max}=\max\limits_{i=1}^{n_1}(Y_i)$$ $$\mathbb{P}(X_{Max}\ge x)=(\mathbb{P}(X_i))^{n_0}$$ What distribution should we use? I belive the correct one is the Binomial distribution with $p=\frac1n$ we can approximate with Normal due to large n, but since p is related to n we might not be best doing this as it is skewed. Also, the normal distribution is not very easy to find the order statistics for, so instead I'm going to use the Gumbel distribution with cumulative distribution function $$F(x)=e^{-e^{-x}}$$ Which has the rather nice property that:- $$\mathbb{E}(X_{Max})=\mathbb{E}(X)+\frac{\sqrt{6\mathbb{Var}(X)}\log(n)}{\pi}=\mu_0+\frac{\sigma_0\sqrt6\log(n_0)}\pi$$

We then calculated the expected time for someone to move between the groups.

TODO:- calculate effect of someone changing group on statistics

Finally we sum the expected times for all $n$ people to get into the leaders group.

share|improve this answer
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.