# Probability that all events occur equally often in finite time

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

-
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

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