A probabilistic game with balls and urns

Given: $$ f(a,a)=1 $$ $$ f(0,a)=0 $$ $$ f(a,b)=a \cdot f(a,b-1)+f(a-1,b-1) $$ The probability is: $$ P(M,N)=\frac{f(M-1,N-1)}{f(M,N)} $$ This was what I found after:

• Generating a bunch of approximations using a simulation.
• Guesstimating their exact values as fractions.
• Spotting and extending patterns for $M=N-1$ and $M=2$
• Spotting the slight hint of a pattern that the denominator of one number is the numerator of another.
• Shifting fractions to the representation required to make the pattern absolute.
• Using this pattern to make further guesses.
• Staring for a long time on a bunch of seemingly scrambled numbers.

Yet to be done is:

• Finding out why this formula works, I don't know, but at least for now I'll give it a rest.
• Finding a representation providing more efficient calculation, (is that actually possible?), current formula is $O(M \cdot (N-M))$.

In the long run, the system will reach a stationary state in which each step rotates the probability distribution by one urn so that it remains the same relative to the urn to be visited next (the "current urn"). Thus, there will be a stationary distribution over the possible ball patterns relative to the current urn. This distribution can be determined explicitly, and it implies the recursion that eBusiness found.

In analyzing the ball patterns, we can ignore the last urn (in clockwise direction from the current urn), which was the current urn of the previous step, since it always contains a ball. I'll consider only states with a ball in the last urn, and I won't be including that ball in representations of ball patterns in the following.

For each ball pattern, starting at the current urn and moving clockwise, form a "gap product" containing one "gap factor" for each empty urn ("gap"), the gap factor being the number of balls yet to be encountered. For instance, for $N=8$, $M=4$, the pattern *--*-*- (where '*' represents a ball and '-' represents a gap; remember the last ball isn't shown) is associated with the product $3\cdot3\cdot2\cdot1$. The stationary distribution over the patterns is given by these products, normalized by their sum.

To prove this, we have to show that the process leaves this distribution invariant; that is, for each pattern $i$, we must have

$$\sum_jp_ip_{ij}=p_j\;,$$

where $p_i$ is the stationary probability and $p_{ij}$ is the transition probability from state $i$ to state $j$. We can multiply this equation by the normalization constant (the sum of the gap products) to express it in terms of the gap products instead of the normalized probabilities. I'll show that this holds by induction over $M+N$.

The initial case $M=1$ is easily checked: There is only one possible state, in which the single ball is in the last urn, and thus its probability correctly comes out as $1$. Since $N\ge M$, this grounds the induction.

For general $M$ and $N$, we can distinguish two kinds of patterns, depending on whether the urn before the last urn (the "penultimate urn"), which was the current urn two steps ago (in the "penultimate step") contains a ball.

The case where it doesn't is relatively simple. The penultimate step left a ball in the penultimate urn. If there is no ball there, that means that the previous step took the ball from there, and hence didn't take a ball from anywhere else. Thus, in this case there is only one possible predecessor pattern, and it's the same pattern except that all the balls except the last one have been shifted forward by one. The probability for this transition is $1/M$, and this is also the ratio of the gap products, since the shift has converted one gap with $M$ balls to come into a gap with $1$ ball to come. Thus, the stationarity condition is fulfilled in this case.

The second case, in which the penultimate urn contains a ball, is a bit more complicated; this is where we need the induction hypothesis. To see what states such a pattern could have arisen from, we can shift it backward by one (creating a gap at the front). This is how it looked to the previous step, except that there's a gap where the ball that's now in the last urn was. So we get the possible predecessor patterns by placing a ball in one of these gaps.

Now let's truncate the (unshifted) pattern by removing the first urn, and then shift the truncated pattern, too (creating a gap at the front of the truncated pattern). Again we have to consider two cases, depending on whether the first urn contains a ball. If it does, the truncated pattern has $M'=M-1,N'=N-1$; if it doesn't, then $M'=M,N'=N-1$.

Again, the first case (where the first urn contains a ball) is relatively simple. It helps to consider an example; let's consider the (untruncated, unshifted) pattern **-*--**; then we have the following patterns:

• **-*--** (original)
• -**-*--* (shifted)
• *-*--** (truncated)
• -*-*--* (truncated and shifted).

The unshifted patterns have the same gap products. The gaps in the shifted patterns are in one-to-one correspondence to each other and are associated with the same gap factors, except the gap at the front, which is worth $M$ in the untruncated pattern and $M-1$ in the truncated pattern. Thus, if we fill the gap at the front, all the gap factors are the same, whereas if we fill any other gap, we get a factor $M-1$ instead of $M$ in the truncated pattern. But this works out perfectly, since the transition probabilities are $1$ if we fill the gap at the front, and if we fill any other gap, $1/(M-1)$ in the truncated case and $1/M$ in the untruncated case. Thus the stationarity condition for the untruncated pattern follows from the one for the truncated pattern, which holds by the induction hypothesis.

The second case (where the first urn is empty) is a bit more complicated. Let's use an example again:

• -*-*--** (original)
• --*-*--* (shifted)
• *-*--** (truncated)
• -*-*--* (truncated and shifted).

Now there's one more gap in the untruncated shifted pattern than in the truncated shifted one (two at the front instead of just one), so there's one more term in the stationarity condition. If we number the gaps in the shifted untruncated pattern beginning with $0$ at the front and denote the gap products we get by filling in gap $i$ in the untruncated and truncated shifted patterns by $g_i$ and $g_i'$, respectively, and the gap products of the unshifted patterns by $g$ and $g'$, the stationarity conditions are

$$ \begin{eqnarray} 1\cdot g_0+\frac1Mg_1+\frac1M\sum_{i>1}g_i &=& g\,\,\,\text{(untruncated),}\\ 1\cdot g_1'+\frac1M\sum_{i>1}g_i' &=& g'\,\,\,\text{(truncated).} \end{eqnarray} $$

But $Mg_0=(M-1)g_1$, since the corresponding patterns differ only in whether the first gap is before or after the first ball, so the first condition can be rewritten as

$$ 1\cdot g_1+\frac1M\sum_{i>1}g_i=g\;. $$

The gap factors are the same in the truncated and untruncated cases, except for an additional factor $M$ for the untruncated patterns, so this is just a multiple of the condition for the truncated case, which holds by the induction hypothesis. That completes the proof by induction.

The hit rate is the sum of the stationary probabilities of all patterns with a ball in the first urn, which is the sum of the gap products for all such patterns divided by the sum of the gap products for all patterns. Let's denote by $f(M,N)$ the sum of the gap products for all patterns. Then the sum of the gap products for patterns with a ball in the first urn is $f(M-1,N-1)$, since the corresponding patterns with the first urn and ball removed have the same gap products. On the other hand, the sum of the gap products for patterns with no ball in the first urn is $Mf(M,N-1)$, since the corresponding patterns with the first urn and gap removed contain one less factor $M$ for the missing gap. Thus we have $f(M,N)=f(M-1,N-1)+Mf(M,N-1)$, and the hit rate is $f(M-1,N-1)/f(M,N)$. Together with the initial conditions $f(0,N)=0$ (since there must always be a ball in the last urn) and $f(N,N)=1$ (since in this case there's just one state and its empty gap product is $1$), this is the recursion that eBusiness found.

P.S.: Note that there's a direct correspondence between the state counts in leonbloy's answer and the gap products in mine, since my gap factors correspond to the number of possible colours for the gap in leonbloy's approach.

It seems that the probability $p$ is given by $p=S(n-1,m-1)/S(n,m)$ where $S(\cdot,\cdot)$ denotes the Stirling numbers of the second kind. Terefore we should view our story of balls and urns in such a way that these numbers play a rôle. I propose the following:

The Stirling number $S(n,k)$ counts the number of ways to partition the set $[n]:=\{1,2,\ldots, n\}$ into $k$ nonempty subsets. Let the balls be colored by $m$ different colors. Assume that we just have visited the urn $n\equiv 0$ and that the red ball is now in this urn. In the next $n$ steps each urn $1$, $\ldots$, $n-1$ sees exactly one ball – either the ball is already there or it is fetched somewhere else. Urn number $n$ may see a new ball or not. When the $n$ steps are over a partition of $[n]$ into $m$ blocks has been realized: The urns that saw a ball of the same color belong to the same block. We have a hit in the $n^{\rm th}$ step iff the red block consists only of urn number $n$.

Now there are $S(n,m)$ partitions of $[n]$ into $m$ blocks and $S(n-1,m-1)$ partitions of $[n]$ where the element $n$ is a one-element-block. So if one could prove that in the long run all these partitions are equiprobable we would be done.