8
$\begingroup$

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.

  • 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?2012-09-15
  • 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.)2012-12-11
  • 0
    @StevenStadnicki: I'd be happy to see either answer.2012-12-11

1 Answers 1