Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

An experiment with $n$ equally likely events is repeated until all events have occurred equally often. What is the probability that the stopping time is finite ? The probability could be denoted by $p(n)$.

For which $n$ does the equation $p(n)=1$ hold?

And is there a way to calculate $p(n)$ for arbitrary $n$?

share|cite|improve this question
How many events can happen at a single moment of time: just one, or multiple? – Ilya Jun 21 '13 at 12:59
Does one ask that each event occurs at least once? – Did Jun 21 '13 at 16:41
up vote 1 down vote accepted

If $X_j(t)$ is the number of times we've seen event $j$ up to and including time $t$, then $$(X_2(t)-X_1(t), X_3(t)-X_1(t),\dots, X_n(t)-X_{1}(t))\tag1$$ is a mean zero random walk in $\mathbb{Z}^{n-1}$ starting at the origin. For instance, when $n=3$ the two dimensional random walk jumps in one of the three directions $(1,0)$, $(0,1)$, and $(-1,-1)$ each with probability $1/3$.

The random walk (1) is at the origin exactly when all events have occurred equally often. The general theory of random walks guarantees a return to the origin if and only if the dimension of the state space is one or two, but not higher. So the answer to the first question is $p(n)=1$ if and only if $n-1\leq 2$, i.e., $n\leq 3$.

Otherwise, if $\phi$ is the multidimensional characteristic function of the jump distribution of the random walk, then the expected number of visits to the origin (including the visit at time zero) is $$\mathbb{E}(V)={1\over (2\pi)^{n-1}}\int_{(-\pi,\pi)^{n-1}} {1\over 1-\phi(u)}\,du,\tag2$$ and the probability of a return visit is $$p(n)=1-{1\over \mathbb{E}(V)}.\tag3$$

In general, the integral in (2) can't be simplified but must be calculated numerically, and the same for the probability of a return visit. This could be done similarly as the calculation of Polya's random walk constants.

share|cite|improve this answer

Your Answer


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.