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.

I had devised two derivations, one using a Markov chain (here the Stirling numbers appear through their combinatorial meaning), other using a recursion for the probabilities distributions for different $N,M$ (this leads to a recursion like that of eBusiness' answer). I post here the first one, because it's simpler and the later is more difficult to justify. At the end, some asympotics.

Let number the urns relatively to the current position, so that urn $1$ is the next one to be visited, urn $N$ is the most recently visited one.

The key to get a solvable Markov chain is to define the states in an seemingly "inflated" way: instead of the natural state, with $M$ components, (for each ball, list its position), the state will be a vector of $N$ components, taking values in $1 \cdots M$. The state vector lists, for each urn, the last ball placed there (assume that all urns have already been visited at least once).

Notice that all ball numbers must appear in the list. Some will repeat; but we can spot in which urn a ball currently is: it's the righmost (largest index=most recent) one. Then, we will have a hit if the first component is not repeated. And the state transition rule is : if hit, shift and rotate the elements to left; if miss, shift to the left and place in the last position a random number (the selected ball).

For example, for the position in the diagram (N=9, M=6; we assumed some arbitrary past for the currently empty urns), assuming we are about to visit the top urn, we could have this state sequence (the asterisks correspond the empty urns; they are just those numbers having some repetition to the right).

S(t)   = [ 3  4* 5  2* 4  2  6* 1  6 ]
                                       hit
S(t+1) = [ 4* 5  2* 4  2  6* 1  6  3 ]   
                                       miss; ball '6' was randomly chosen
S(t+2) = [ 5  2* 4  2  6* 1  6* 3  6 ]   

Notice that:

• A valid state corresponds to a surjective mapping from $\{1 \cdots N\}$ to $\{1 \cdots M\}$ (all ball numbers must appear).
• All valid states are reachable from any other.
• A state can have either one outgoing transition with probability 1 (hit state), or $M$ transitions equally probable. Hence the transition matrix have only $1$ and $1/M$ as non zero entries.
• In-going transitions: (this is the key) each state has either one in-going transition with probability 1 or M with $1/M$; in the example above: we can tell that state $S(t+1)$ is post-hit with only one possible previous state); and that state $S(t+2)$ is post-miss, with $M$ possible previous states. Hence both the rows and the columns of the transition matrix sum up to one: it's doubly stochastic.

But an irreducible [edited: actually also ergodic, as noted in the comments] and doubly-stochastic Markov chain, in steady state, has equiprobable states.

Now, the total number of states (number of mappings) is equivalent to the number of ways of placing $N$ objects in $M$ bins, with no empty bin; this is given by Stirling Number of second Kind (multiplied by $M!$ to account for distinguishable balls): $\#S= M! \; S(N,M)$

To count the hit states $S_h$: the first component must be unique, so $\#S_h = M (M-1)! \; S(N-1,M-1) = M! \; S(N-1,M-1)$

The probability of hit, then, is just the number of hit states over the total number of states.

$$p = \frac{\#S_h}{\#S} = \frac{S(N-1,M-1)}{S(N,M)}$$

Some values:

       M    2        3        4          5        6         7        8  
     N  
     3   0.33333
     4   0.14286  0.50000
     5   0.06666  0.28000  0.60000
     6   0.03226  0.16666  0.38462   0.66667
     7   0.01587  0.10299  0.25714   0.46429   0.71429
     8   0.00787  0.06522  0.17695   0.33333   0.52632   0.75000
     9   0.00392  0.04198  0.12432   0.24471   0.39683   0.57576  0.77778

BTW, for the example diagram (9,6), the hit rate is about 40%.

Asymptotics: For large $N,M$, the Stirling numbers of second kind grow quickly and its asympotics are rather tricky. Here goes very simple probabilistic approach.

Suppose we have just visited the top urn; it must be occupied. We can estimate the probability that the ball survives in that position after a full round as the probability that in $N-1$ tries it never happen the event "miss and my ball was selected". This survival corresponds to a hit event. Then, asumming independence:

$$p \approx (1 - \frac{1-p}{M})^{N-1} \approx e^{-r(1-p)}$$

with $N,M \to \infty$ and $r = N/M$. The implicit $p(r)$ could be explicitly expressed using the Lambert function (see here).

The independence assumption is not exact, but the error is asympotically negligible. I have another (better) probabilistic argument, which leads to the same expression, I'll spare you that (in case someone is interested, send me a message).