Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have $N$ urns forming a circle and $M<N$ balls (for example, $N=9,M=6$ in the diagram). In each step we visit, sequentially, clockwise, an urn. If it's occupied by a ball, we say a $hit$ has ocurred. Elsewhere (miss), we pick randomly one of the $M$ balls and move it to the current urn. The goal is to compute the average hit rate, for arbitrary $N,M$, in the long run.

enter image description here

I was confronted with this problem some years ago, for some concrete application (some cache model). It's not terribly difficult, but not as simple as it might seem. It's also interesting to contrast with the intuition (on which side would you bet in this example?).

I have a solution, (with two different proofs - I'll post them soon posted in answer below) but I'd like to hear about other attempts - or perhaps some reference - this should probably have been studied somewhere.

A few (exact) results:

 N  M   p
------------
 3  2  1/3
 4  2  1/7
 5  3  7/25

Edited: as found out semi-empirically in an answer below, the hit rate is given by $$p= \frac{S(N-1,M-1)}{S(N,M)}$$ where $S(N,M)$ are Stirling numbers of the second kind.

share|improve this question
    
The numbers on the balls play no rôle in this description of the problem; is that what you intend? –  Brian M. Scott Jul 21 '11 at 21:23
    
Yes, they are unimportant. –  leonbloy Jul 21 '11 at 21:25
7  
Downvotes can be more helpful (to the poster and to the site) if accompanied by some comment... –  leonbloy Jul 21 '11 at 21:27
2  
It could be that the downvoter didn't know that the FAQ encourages posting questions that one knows the answer to? –  joriki Jul 21 '11 at 23:13
2  
I deleted my answer because as you rightly pointed out it made unwarranted independence assumptions. I can reproduce your individual results by individual Markov processes, but I haven't figured out how to generalize them yet. –  joriki Jul 22 '11 at 1:08
show 6 more comments

5 Answers 5

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))$.
share|improve this answer
2  
Looking at the recursion for $f$ one sees that $f(a,b)=S(b,a)$ where $S(n,k)$ denotes the Stirling numbers of the second kind. See Stanley I, p. 33. –  Christian Blatter Jul 22 '11 at 13:24
    
Yep, that's correct. –  leonbloy Jul 22 '11 at 13:42
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
+1 That was, roughly, how I worked it out. See my answer. –  leonbloy Jul 23 '11 at 11:33
add comment
up vote 5 down vote accepted

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).

enter image description here

share|improve this answer
    
This is a very nice solution; much more aesthetic than mine :-) –  joriki Jul 23 '11 at 14:33
    
I suspect that your solution is similar to my other approach - which was my first solution, but which I never could justify fully. I'll give it a look. –  leonbloy Jul 23 '11 at 14:35
    
There's a direct correspondence between your state counts and my gap products, since the gap factor in my approach is the number of possible colours for the gap in your approach. –  joriki Jul 23 '11 at 14:39
1  
I think you're not using the term "reversible" in the standard sense here. It's the fact that the transition matrix is doubly stochastic that allows you to infer that the equilibrium distribution is uniform; the process isn't reversible, since most of the transitions are one-way. Neither of these properties is a special case of the other -- the Metropolis algorithm is reversible but not doubly stochastic, and a cycle with transitions in only one direction is doubly stochastic but not reversible. –  joriki Jul 23 '11 at 15:50
    
@joriki: You're right, I'm deleting that. I was using the term "reversible" in a loosy way, meaning that if you "invert the arrows" you get not only a valid markov chain but "esentially the same chain" (same structure, though with some permutation of states). This is a slightly stronger property that doubly-stochastic, but it doesn't add anything to the solution, and a "reversible Markov chain" is technically a very different (and orthogonal, as you state) thing. Indeed, here, we practically never have a path from $i \to j$ and from $j \to i$. Thanks. –  leonbloy Jul 23 '11 at 16:18
show 3 more comments

For $M=2$ I get $\frac{1}{2^{N-1}-1}$. If we ever hit, the two balls are in the last two bins, so after each $1$ there will be a run of $0$'s at least $N-2$ long. If we pick the ball that we just hit $N-2$ times in a row, we will hit the other ball and the run will be $N-2$. If we pick the ball that was behind $N-1$ times in a row we will have a run of $N-1$. If we pick the two different balls successively, we are in the same state of having the two balls in the last two bins visited, so the average run from now on is the same as an average run. With probability $\frac{1}{2}$ we pick AB or BA and add two zeros to the average run. With probability $\frac{1}{4}$ we pick AAB or BBA and add three zeros. This continues up to $\frac{1}{2^{N-3}}$ we add $N-2$ zeros, plus $\frac{1}{2^{N-1}}$ we add $N-1$ zeros. So if $r$ is the average run, we have $$r=\frac{N-2}{2^{N-2}}+\frac{N-1}{2^{N-1}}+\sum_{i=1}^{N-3}\frac{i+1+r}{2^i}+\frac{N-1+r}{2^{N-1}}$$ $$\frac{3}{2^{N-1}}r=3-\frac{N}{2^{N-3}}+\frac{N-2}{2^{N-2}}+\frac{N-1}{2^{N-1}}+\frac{N-1}{2^{N-1}}$$ $$r=2^{N-1}-2$$

So the density of ones is $1$ in $2^{N-1}-1$

Added: another way to see this is to use the Markov transition matrix. There is a ball in the urn we are currently at. Define state $1$ to have the other ball in the next urn up to state $N-1$ having the other ball in the last bin visited. State $1$ returns a hit and transitions to state $N-1$. All other states $k$ return a miss and transition with probability $0.5$ to state $k-1$ and probability $0.5$ to state $N-1$. So for $N=6$, the matrix looks like $$\left(\begin {array} {c c c c c} 0&.5&0&0&0\\0&0&.5&0&0\\0&0&0&.5&0\\0&0&0&0&.5\\1&.5&.5&.5&.5\end{array}\right)$$ and the eigenvector corresponding to eigenvalue $1$ is $(1,2,4,8,16)^T$ giving a hit ratio of $\frac{1}{31}$ as claimed.

share|improve this answer
    
This and the opposite case $N=M-1$ (a single "hole") are the only cases I could handle correctly for general $N$ with my stationary-state approach. The penultimate urn has a ball with probability $1$ after a hit and $1/2$ after a miss, so its stationary-state probability is $(1+p)/2$, where $p$ is the hit probability. With each step the probability that this ball remains in place is halved, so the sum over the probabilities of all urns except the last is $(1+p)/2$ times the geometric sum $(1-2^{-(N-1)})/(1-1/2)$, and setting this to $1$ yields $p=1/(2^{N-1}-1)$. –  joriki Jul 22 '11 at 3:26
    
@joriki: I can also do $N=M$ and $M=1$, but am not too proud of those. –  Ross Millikan Jul 22 '11 at 3:31
add comment

Your Answer

 
discard

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.