## Pebbles in buckets, a modified random walk

**Moderators:** gmalivuk, Moderators General, Prelates

### Pebbles in buckets, a modified random walk

You come to work one day at the Infinte Random Pebble Factory. You pick up your Perfectly Fair™ n-sided die and your n empty unlimited-capacity buckets labeled 1 through n. You stand next to the conveyor belt, and each time a pebble comes along you roll your die and put that pebble in the corresponding bucket. Your shift lasts until all n of your buckets contain the same number of pebbles as each other.

Well, you’ve been at it for a while and your buckets have [imath]a_1[/imath] through [imath]a_n[/imath] pebbles in them already. What is the expected number of pebbles remaining before your shift ends? For that matter, what is the probability that your shift will ever end?

This just came up in something I was doing for fun. In that context there were three buckets. If there were only two the result would be a simple random walk in one variable. But for three and more buckets it does not appear to be so simple.

Well, you’ve been at it for a while and your buckets have [imath]a_1[/imath] through [imath]a_n[/imath] pebbles in them already. What is the expected number of pebbles remaining before your shift ends? For that matter, what is the probability that your shift will ever end?

This just came up in something I was doing for fun. In that context there were three buckets. If there were only two the result would be a simple random walk in one variable. But for three and more buckets it does not appear to be so simple.

Last edited by Qaanol on Thu Feb 10, 2011 11:20 pm UTC, edited 1 time in total.

wee free kings

- imatrendytotebag
**Posts:**152**Joined:**Thu Nov 29, 2007 1:16 am UTC

### Re: Pebbles in buckets, a modified random walk

My first thought is that you can model this as a type of random walk in n-1 dimensions. For instance, with 4 buckets, you have bucket 1 move you +(1,0,0), bucket 2 +(0,1,0), bucket 3 +(0,0,1) and bucket 4 +(-1,-1,-1). In general, for n buckets, the ith bucket (i < n) moves you +(0,0,...,1,...,0) with a 1 in the ith position, and the nth bucket moves you +(-1,-1,...,-1).

Hey baby, I'm proving love at nth sight by induction and you're my base case.

### Re: Pebbles in buckets, a modified random walk

At each step of an m-dimensional random walk along lattice lines, there are 2m choices of directions. So the 6 bucket case corresponds to the 3-dimensional random lattice walk.

It is a known result that for 1- or 2-dimensional random lattice walks, you will get back to the origin (in terms of buckets, this means all buckets have the same number of pebbles) from any starting position with probability 1. For 3-dimensional (or higher), the probability is less than 1 that you eventually get back to the origin.

It is a known result that for 1- or 2-dimensional random lattice walks, you will get back to the origin (in terms of buckets, this means all buckets have the same number of pebbles) from any starting position with probability 1. For 3-dimensional (or higher), the probability is less than 1 that you eventually get back to the origin.

### Re: Pebbles in buckets, a modified random walk

Hix wrote:At each step of an m-dimensional random walk along lattice lines, there are 2m choices of directions. So the 6 bucket case corresponds to the 3-dimensional random lattice walk.

Almost, but not quite. The bucket walk ends when all buckets have the same value. A 3d walk ends when the three coordinates are zero. The former is less likely to end, since a 3d walk does not need the number of steps on each of the three axes to be equal.

From this:

Hix wrote:For 3-dimensional (or higher), the probability is less than 1 that you eventually get back to the origin.

it then follows that with 6 (or more) buckets there is a positive probability that it never ends.

### Re: Pebbles in buckets, a modified random walk

Glad to see some progress was made!

So somewhere between 2 and 6, it switches from finishing in finite time with probability 1, to finishing in finite time with probability less than one. I’d be interested to know which of 2, 3, 4, 5, and 6 is the smallest value for which it does not finish with probability 1.

So somewhere between 2 and 6, it switches from finishing in finite time with probability 1, to finishing in finite time with probability less than one. I’d be interested to know which of 2, 3, 4, 5, and 6 is the smallest value for which it does not finish with probability 1.

wee free kings

### Re: Pebbles in buckets, a modified random walk

In fact, as imatrendytotebag mentioned, the n-bucket case corresponds to a random walk on an n-1-dimensional lattice, so for 4 (or more) buckets, there is a positive probability that it never ends, and for 3 (or fewer) buckets, it ends with probability 1.jaap wrote:Hix wrote:For 3-dimensional (or higher), the probability is less than 1 that you eventually get back to the origin.

it then follows that with 6 (or more) buckets there is a positive probability that it never ends.

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

### Re: Pebbles in buckets, a modified random walk

antonfire wrote:In fact, as imatrendytotebag mentioned, the n-bucket case corresponds to a random walk on an n-1-dimensional lattice, so for 4 (or more) buckets, there is a positive probability that it never ends, and for 3 (or fewer) buckets, it ends with probability 1.

Can you point out a proof of that?

The 4 bucket case is a random walk with the steps (1,0,0), (0,1,0), (0,0,1), (-1,-1,-1).

The usual 3d random walk allows the steps (1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1).

I don't see how the fact that the latter need not finish is related to whether or not the former does.

### Re: Pebbles in buckets, a modified random walk

My numerical simulations indicate that for three buckets starting at (0, 0, 1), you have about a 50% chance of ending with 23 or fewer pebbles in each bucket. Of course, you have exactly a 4/9 chance of ending with exactly 1 pebble in each bucket, so the next 66 pebbles only give you about a 1/18 chance of finishing if the first 3 didn’t succeed.

I did not run statistical analyses to check how likely it is for a limit less than 1 to exist based on my simulations, but it appears to my eye that there is a limiting probability of around 80% that the process eventually ends in the 3-bucket case.

I did not run statistical analyses to check how likely it is for a limit less than 1 to exist based on my simulations, but it appears to my eye that there is a limiting probability of around 80% that the process eventually ends in the 3-bucket case.

wee free kings

- Yakk
- Poster with most posts but no title.
**Posts:**11129**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

### Re: Pebbles in buckets, a modified random walk

I'd make it a random walk with these steps:

(3,-1,-1,-1)

(-1,3,-1,-1)

(-1,-1,3,-1)

(-1,-1,-1,3)

which has nice symmetry properties, and also terminates iff you return to (0,0,0,0). (Note that only a 3-dimensional subspace is walked by the above defined by w+x+y+z=0, and the pairwise difference in the components of all valid points always equal 0 mod 4).

Looking at all 4-moves, then dividing the coordinates by 4, gives you a different set of primitives and weights, but gets rid of the component difference = 0 mod 4 restriction. That might not be useful...

(3,-1,-1,-1)

(-1,3,-1,-1)

(-1,-1,3,-1)

(-1,-1,-1,3)

which has nice symmetry properties, and also terminates iff you return to (0,0,0,0). (Note that only a 3-dimensional subspace is walked by the above defined by w+x+y+z=0, and the pairwise difference in the components of all valid points always equal 0 mod 4).

Looking at all 4-moves, then dividing the coordinates by 4, gives you a different set of primitives and weights, but gets rid of the component difference = 0 mod 4 restriction. That might not be useful...

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

### Re: Pebbles in buckets, a modified random walk

You’re looking at the 4 buckets case, yes?

I’m still trying to get a handle on 3 buckets. I’ve found that if you constantly rearrange the buckets so they stay in order from smallest to largest number of pebbles currently in them, that is [imath]a_1 < a_2 < \cdots < a_n[/imath], then you can look at “how many more pebbles are needed in each bucket to match the current most-full buckect”.

The last coordinate will always be 0, so this is very similar to the (n-1)-dimensional walk described previously, but now it is restricted to a single octant of the Cartesian plane. I drew it on graph paper with the square centered at (x, y) representing the state where the first bucket has x fewer than the last and the second bucket has y fewer than the last (with [imath]x \leq y[/imath]). Then I drew arrows from each square to the 3 squares that can be reached by adding a pebble to a single bucket (in cases where two buckets have the same number of pebbles I drew 2 arrows for that path since it is twice as likely.)

This gives a situation where the interior of the octant has all squares the same, with a one-third chance of moving vertically toward y = 0, a one-third chance of moving horizontally toward x = 0, and a one third chance of moving diagonally in the positive x and y directions (so away from the origin). But the edge squares are not the same. Along the y-axis you are twice as likely to move diagonally away from the origin as you are to move straight toward it, and along the line y=x you are twice as likely to move into the interior (so horizontally closer to the origin) as you are to move diagonally away from the origin.

Each horizontal band at y = k has only k+1 squares on it (in particular, this is a finite number) so if we naïvely thought all of them were equally likely we could check and see k arrows moving vertically toward the origin, k+2 moving vertically away from the origin (along a diagonal), k+1 moving horizontally toward the origin, and (the same as before) k+2 moving horizontally away from the origin (along a diagonal). That would indicate a random drift tending away from the origin.

But of course we cannot make that naïve assumption without warrant, so I’m not sure if this helps. It does restrict the problem to a region with finite cross-sections however.

I’m still trying to get a handle on 3 buckets. I’ve found that if you constantly rearrange the buckets so they stay in order from smallest to largest number of pebbles currently in them, that is [imath]a_1 < a_2 < \cdots < a_n[/imath], then you can look at “how many more pebbles are needed in each bucket to match the current most-full buckect”.

The last coordinate will always be 0, so this is very similar to the (n-1)-dimensional walk described previously, but now it is restricted to a single octant of the Cartesian plane. I drew it on graph paper with the square centered at (x, y) representing the state where the first bucket has x fewer than the last and the second bucket has y fewer than the last (with [imath]x \leq y[/imath]). Then I drew arrows from each square to the 3 squares that can be reached by adding a pebble to a single bucket (in cases where two buckets have the same number of pebbles I drew 2 arrows for that path since it is twice as likely.)

This gives a situation where the interior of the octant has all squares the same, with a one-third chance of moving vertically toward y = 0, a one-third chance of moving horizontally toward x = 0, and a one third chance of moving diagonally in the positive x and y directions (so away from the origin). But the edge squares are not the same. Along the y-axis you are twice as likely to move diagonally away from the origin as you are to move straight toward it, and along the line y=x you are twice as likely to move into the interior (so horizontally closer to the origin) as you are to move diagonally away from the origin.

Each horizontal band at y = k has only k+1 squares on it (in particular, this is a finite number) so if we naïvely thought all of them were equally likely we could check and see k arrows moving vertically toward the origin, k+2 moving vertically away from the origin (along a diagonal), k+1 moving horizontally toward the origin, and (the same as before) k+2 moving horizontally away from the origin (along a diagonal). That would indicate a random drift tending away from the origin.

But of course we cannot make that naïve assumption without warrant, so I’m not sure if this helps. It does restrict the problem to a region with finite cross-sections however.

wee free kings

### Re: Pebbles in buckets, a modified random walk

No, but I can point you to a post that calls it a "standard result in random walk theory". I pretty much took that at face value without looking up a proof. I live on the edge.jaap wrote:Can you point out a proof of that?

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

### Re: Pebbles in buckets, a modified random walk

antonfire wrote:No, but I can point you to a post that calls it a "standard result in random walk theory". I pretty much took that at face value without looking up a proof. I live on the edge.jaap wrote:Can you point out a proof of that?

Good find. Note though, the quote there says the standard result is, “Any genuinely d-dimensional walk on a hypercubic lattice is not recurrent if d>2”, which if true does (I believe) imply that the pebble problem has sub-unital probability of terminating for four or more buckets, since those walks are three or more dimensional.

However, it by no means implies the converse. There may well be some genuinely 1- or 2-dimensional walks that are not recurrent. Thus I claim that, even if the linked quote is correct, it does not imply the 3-bucket problem terminates with probability 1.

Of course, I have not studied random walks formally, so I’m not clear what counts as “genuinely” d-dimensional, nor exactly what is meant by “recurrent” (eventually reaching every possible state, and returning to each prior state infinitely often, with probability 1?)

wee free kings

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: Pebbles in buckets, a modified random walk

Also, that refers to lattice random walks, which this is not, since we can walk in a direction but not its opposite. Do the results generalize to this case?

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

### Re: Pebbles in buckets, a modified random walk

Here’s what my simulations show. I ran the simulation for a given n until it either terminated or reached the cap I had set on the number of pebbles. I did this many times to see, for that n and that cap, what proportion of trials terminated before reaching the cap. I then raised the cap and did the whole thing over.

The plots below have y-axis showing the fraction of trials that terminated before the cap, as a function of the cap, which is on the x-axis. The values listed on the axis as the caps are the number of batches of n pebbles that were processed (obviously the buckets can only ever have equal quantities when the total number of pebbles is a multiple of n). Also note the points on the x-axis for which values were calculated are spaced logarithmically.

The first plot shows, for n=2 through n=5, what happens through the first 1024 batches of n pebbles, with 1000 trials performed at each cap value (except for n=5 where only 500 trials were performed—also note that only half as many cap values were calculated there, to keep the running time reasonable):

The second plot shows, for n=2 through n=5, what happens through the first 65536 batches of n pebbles, but with only a tenth as many trials per cap value as before (so 100 trials each for n=2 through n=4, and 50 for n=5):

The plots below have y-axis showing the fraction of trials that terminated before the cap, as a function of the cap, which is on the x-axis. The values listed on the axis as the caps are the number of batches of n pebbles that were processed (obviously the buckets can only ever have equal quantities when the total number of pebbles is a multiple of n). Also note the points on the x-axis for which values were calculated are spaced logarithmically.

The first plot shows, for n=2 through n=5, what happens through the first 1024 batches of n pebbles, with 1000 trials performed at each cap value (except for n=5 where only 500 trials were performed—also note that only half as many cap values were calculated there, to keep the running time reasonable):

**Spoiler:**

The second plot shows, for n=2 through n=5, what happens through the first 65536 batches of n pebbles, but with only a tenth as many trials per cap value as before (so 100 trials each for n=2 through n=4, and 50 for n=5):

**Spoiler:**

wee free kings

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: Pebbles in buckets, a modified random walk

I'd say its hard to draw much inference from that data. We're talking about events that occur after an expected infinity of steps, so... *shrug*. On the larger trial set, it looks like n=3 is still trending up, and it could still be significantly higher than the ~0.7 that it arrives at.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Re: Pebbles in buckets, a modified random walk

jestingrabbit wrote:I'd say its hard to draw much inference from that data. We're talking about events that occur after an expected infinity of steps, so... *shrug*. On the larger trial set, it looks like n=3 is still trending up, and it could still be significantly higher than the ~0.7 that it arrives at.

Yes, it’s true we want the expected result after infinite steps, and I’m still looking for a way to go about proving it. I’d be rather greatly surprised, however, if the result were anything other than “n=3 terminates with limiting probabilty between 0.65 and 0.85”. (Well, surprised, and/or motivated to review my simulation carefully to see if I made any mistakes in the scripting.)

Which graph do you mean by “the larger trial set”? The first graph has 10 times more trials per data point, but only goes out to a cap of 1024. I certainly agree that the trend is still rising at that point.

The second graph has fewer trials per data point, but the data points go out to a cap of 65,536, so I would call this the larger trial set. If we just look at the “tail” of the graph, say after 10,000, then the trendline (if Excel can be trusted) is increasing with slope just shallower than 1.9233×10

^{-7}. If we only look at what’s beyond 15,000 then the trendline is decreasing with slope slightly steeper than -5.6084×10

^{-7}.

Of course, it’s hard to get a good read on a trendline when the data points are spaced logarithmically, as that naturally biases the results toward the behavior at the left end of the abcissa window.

wee free kings

- Yakk
- Poster with most posts but no title.
**Posts:**11129**Joined:**Sat Jan 27, 2007 7:27 pm UTC**Location:**E pur si muove

### Re: Pebbles in buckets, a modified random walk

The symmetrical two dimensional case.

Vectors are (2,-1) and (-1,2).

The non-symmetrical two dimensional case gives us vectors of (1), (-1), which is of course the 1 dimensional standard random walk.

Oh wait, the non-symmetrical case has a recursive relationship.

When we have vector v_k as the kth unit vector, except v_n being (-1, ..., -1), in order for a sequence of steps to be a solution, the sequence of steps with the v_n elements removed must be an answer to the n-1 dimensional case.

So an n-1 dimensional solution to the problem of length C generates (C+n choose n) n dimensional solutions to the problem of length C+n.

For an n dimensional problem, the solutions of length k*n number (k choose k)(2k choose k)(3k choose k)...(nk choose k). There are no solutions other than positive solutions of length Zn. (I use positive Z, because it looks prettier than Nn). Divide by the total number of games of that length, and do the infinite sum maybe? Doesn't look trivial.

Bah. Nevermind -- you being "near" a solution at step kn correlates with winning at steps (k+1) and (k+2), so simple counting won't work.

Vectors are (2,-1) and (-1,2).

The non-symmetrical two dimensional case gives us vectors of (1), (-1), which is of course the 1 dimensional standard random walk.

Oh wait, the non-symmetrical case has a recursive relationship.

When we have vector v_k as the kth unit vector, except v_n being (-1, ..., -1), in order for a sequence of steps to be a solution, the sequence of steps with the v_n elements removed must be an answer to the n-1 dimensional case.

So an n-1 dimensional solution to the problem of length C generates (C+n choose n) n dimensional solutions to the problem of length C+n.

For an n dimensional problem, the solutions of length k*n number (k choose k)(2k choose k)(3k choose k)...(nk choose k). There are no solutions other than positive solutions of length Zn. (I use positive Z, because it looks prettier than Nn). Divide by the total number of games of that length, and do the infinite sum maybe? Doesn't look trivial.

Bah. Nevermind -- you being "near" a solution at step kn correlates with winning at steps (k+1) and (k+2), so simple counting won't work.

One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: Pebbles in buckets, a modified random walk

Qaanol wrote:jestingrabbit wrote:I'd say its hard to draw much inference from that data. We're talking about events that occur after an expected infinity of steps, so... *shrug*. On the larger trial set, it looks like n=3 is still trending up, and it could still be significantly higher than the ~0.7 that it arrives at.

Yes, it’s true we want the expected result after infinite steps, and I’m still looking for a way to go about proving it. I’d be rather greatly surprised, however, if the result were anything other than “n=3 terminates with limiting probabilty between 0.65 and 0.85”. (Well, surprised, and/or motivated to review my simulation carefully to see if I made any mistakes in the scripting.)

I wasn't meaning that its the probability after an infinite number of steps, I was meaning that the expected time to get to equal piles is in all instances infinite, even if we only consider the walks that get to that state at some point in time. This is a simple consequence of what happens in the one dimensional discrete random walk: it will hit every point with probability 1, and the expected number of steps to get anywhere is in every case infinity.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Re: Pebbles in buckets, a modified random walk

This thread is of significant interest to me for completely non-mathematical related reasons. Also, I'm as sick as a dog and may have had slightly too much cough syrup, so please forgive any nonsense or redundancy in the following.

So, n buckets can only contain an equal number of pebbles after some multiple of n steps, that's obvious. After nk steps, there are n

So for n buckets we're looking for some reasonable way to actually calculate [imath]1 - \displaystyle\prod_{k=1}^{∞}{1-\frac{(nk)!}{{k!}^{n}n^{nk}}}[/imath] ? 'Cause that looks kinda ugly. W|A has no idea what to do with it.

--------

Okay, so, some exhaustive mapping of putting pebbles into buckets seems to confirm this formula, even if it isn't very convenient to work with. The approximate (rounding each term to 10

For 4 buckets, it strongly appears to be converging to an ~25% chance of ever finishing. At 200 pellets you have a 22.6% chance of having finished, at 1000 pellets you have a 24.1% chance of having finished, and at 12000 pellets you have a 24.96% chance of having finished. I'm going to run this one for a bit longer though, because it's actually starting to look like it might be a smidgen more than 25% chance to succeed, which might indicate either an ugly closed form or that I'm starting to get rounding errors.

--------

Yes, by 16000 pellets (4000 terms) it's crept above 25% chance of success. Guess I have to do it again with a higher precision to be sure.

For more buckets it seems to converge faster, and your odds of success drop off rapidly. 5 buckets seems to have an ~7% chance of success. 6 buckets converges fairly quickly to 2.223% - after 250 terms, each additional 50 terms changes the partial product by less than one one millionth.

So, n buckets can only contain an equal number of pebbles after some multiple of n steps, that's obvious. After nk steps, there are n

^{nk}sequences of pebbles going into buckets, (nk)!/(k!^{n}) of which should have resulted in all buckets being equally full, yes?So for n buckets we're looking for some reasonable way to actually calculate [imath]1 - \displaystyle\prod_{k=1}^{∞}{1-\frac{(nk)!}{{k!}^{n}n^{nk}}}[/imath] ? 'Cause that looks kinda ugly. W|A has no idea what to do with it.

--------

Okay, so, some exhaustive mapping of putting pebbles into buckets seems to confirm this formula, even if it isn't very convenient to work with. The approximate (rounding each term to 10

^{-20}before multiplying to prevent super massive ratios slowing things down) product of the first 3000 terms for the 3 bucket case indicates that you have an at least 90% chance of finishing your task, and your chance of not finishing is still decreasing by 0.4% (multiplicatively) per 150 pellets at this point. It's getting really slow though, and becoming quite the memory hog, so I think I'm going to stop it now. Final tally is 90.65% chance of having finished after 10500 pellets and 3 buckets.For 4 buckets, it strongly appears to be converging to an ~25% chance of ever finishing. At 200 pellets you have a 22.6% chance of having finished, at 1000 pellets you have a 24.1% chance of having finished, and at 12000 pellets you have a 24.96% chance of having finished. I'm going to run this one for a bit longer though, because it's actually starting to look like it might be a smidgen more than 25% chance to succeed, which might indicate either an ugly closed form or that I'm starting to get rounding errors.

--------

Yes, by 16000 pellets (4000 terms) it's crept above 25% chance of success. Guess I have to do it again with a higher precision to be sure.

For more buckets it seems to converge faster, and your odds of success drop off rapidly. 5 buckets seems to have an ~7% chance of success. 6 buckets converges fairly quickly to 2.223% - after 250 terms, each additional 50 terms changes the partial product by less than one one millionth.

All Shadow priest spells that deal Fire damage now appear green.

Big freaky cereal boxes of death.

### Re: Pebbles in buckets, a modified random walk

In the 3 bucket case, the probability of a return after [imath]3n[/imath] steps is [imath]\binom{3n}{n,n,n}3^{-3n}[/imath], which is [imath]\Theta(n^{-1})[/imath] by Stirling's approximation. Hence, the expected number of returns is infinite, and by a standard result the state is recurrent.

In the 4 bucket case, the probability of a return after [imath]4n[/imath] steps is [imath]\binom{4n}{n,n,n,n}4^{-4n}[/imath], which is [imath]\Theta(n^{-3/2})[/imath] by Stirling's approximation. Hence, the expected number of returns is finite, and by a standard result the state is transient.

In the 4 bucket case, the probability of a return after [imath]4n[/imath] steps is [imath]\binom{4n}{n,n,n,n}4^{-4n}[/imath], which is [imath]\Theta(n^{-3/2})[/imath] by Stirling's approximation. Hence, the expected number of returns is finite, and by a standard result the state is transient.

### Re: Pebbles in buckets, a modified random walk

Hmm, despite increasing the rounding error to less than 10

^{-50}, it still becomes greater than 25% after about 4000 terms. So a nice neat closed form does not look promising.All Shadow priest spells that deal Fire damage now appear green.

Big freaky cereal boxes of death.

### Re: Pebbles in buckets, a modified random walk

WarDaft wrote:After nk steps, there are n^{nk}sequences of pebbles going into buckets, (nk)!/(k!^{n}) of which should have resulted in all buckets being equally full, yes?

If I’m reading it right, that’s the number of ways for the buckets to be matched after exactly nk pebbles. But there are also a lot of ways for the buckets to have already matched at some point before that, some of which go on to match again at nk and some of which do not.

Nitrodon wrote:In the 3 bucket case, the probability of a return after [imath]3n[/imath] steps is [imath]\binom{3n}{n,n,n}3^{-3n}[/imath], which is [imath]\Theta(n^{-1})[/imath] by Stirling's approximation. Hence, the expected number of returns is infinite, and by a standard result the state is recurrent.

In the 4 bucket case, the probability of a return after [imath]4n[/imath] steps is [imath]\binom{4n}{n,n,n,n}4^{-4n}[/imath], which is [imath]\Theta(n^{-3/2})[/imath] by Stirling's approximation. Hence, the expected number of returns is finite, and by a standard result the state is transient.

Am I correct in believing that “the state is recurrent” means the probability of reaching the desired end state is necessarily 1, and that “the state is transient” means the probability of reaching the desired end state is necessarily less than one?

wee free kings

### Re: Pebbles in buckets, a modified random walk

Qaanol wrote:If I’m reading it right, that’s the number of ways for the buckets to be matched after exactly nk pebbles. But there are also a lot of ways for the buckets to have already matched at some point before that, some of which go on to match again at nk and some of which do not.

Yes, but as it's an infinite product, should we not be interested strictly in the odds of that term having the pebbles properly distributed amongst the buckets? To be honest, I am not particularly sure.

All Shadow priest spells that deal Fire damage now appear green.

Big freaky cereal boxes of death.

- skeptical scientist
- closed-minded spiritualist
**Posts:**6142**Joined:**Tue Nov 28, 2006 6:09 am UTC**Location:**San Francisco

### Re: Pebbles in buckets, a modified random walk

Qaanol wrote:WarDaft wrote:After nk steps, there are n^{nk}sequences of pebbles going into buckets, (nk)!/(k!^{n}) of which should have resulted in all buckets being equally full, yes?

If I’m reading it right, that’s the number of ways for the buckets to be matched after exactly nk pebbles. But there are also a lot of ways for the buckets to have already matched at some point before that, some of which go on to match again at nk and some of which do not.

That's true. The formula WarDaft gave assumes independence. If the events "returned after n steps" and "returned after 2n steps" are not independent (and they aren't), then the probability of returning after either n or 2n steps will not necessarily be 1-(1-p(n))(1-p(2n)), and so on for more terms (including infinitely many).

Qaanol wrote:Nitrodon wrote:In the 3 bucket case, the probability of a return after [imath]3n[/imath] steps is [imath]\binom{3n}{n,n,n}3^{-3n}[/imath], which is [imath]\Theta(n^{-1})[/imath] by Stirling's approximation. Hence, the expected number of returns is infinite, and by a standard result the state is recurrent.

In the 4 bucket case, the probability of a return after [imath]4n[/imath] steps is [imath]\binom{4n}{n,n,n,n}4^{-4n}[/imath], which is [imath]\Theta(n^{-3/2})[/imath] by Stirling's approximation. Hence, the expected number of returns is finite, and by a standard result the state is transient.

Am I correct in believing that “the state is recurrent” means the probability of reaching the desired end state is necessarily 1, and that “the state is transient” means the probability of reaching the desired end state is necessarily less than one?

Yes, you are correct. Nitrodon's post completely solved the problem (since the 4 bucket case not ending with positive probability implies that the n bucket case won't end with positive probability, for n>4 - just look at the first four buckets). Unless you care about finding the exact probabilities of eventually matching for n>3, which may or may not have a nice closed form.

Last edited by skeptical scientist on Mon Feb 14, 2011 10:19 pm UTC, edited 1 time in total.

I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

"With math, all things are possible." —Rebecca Watson

- gmalivuk
- GNU Terry Pratchett
**Posts:**26824**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Pebbles in buckets, a modified random walk

Yeah, the two questions in the OP can have answers that might seem on first glance to be contradictory. You might finish with probability 1, but with an infinite expected wait time.jestingrabbit wrote:I wasn't meaning that its the probability after an infinite number of steps, I was meaning that the expected time to get to equal piles is in all instances infinite, even if we only consider the walks that get to that state at some point in time.

### Re: Pebbles in buckets, a modified random walk

Thanks everyone (especially Nitrodon for the solution!)

Is there a standard term for the x value at which the probability reaches a desired value? For instance, the first number at which the probability is 50% (or 75%, 90%, 95%, etc.) that the 3-bucket case will have already finished. That is, the number of (multiples of n) pebbles which, at the beginning, you have a certain confidence level that the process will end prior to.

Is there a standard term for the x value at which the probability reaches a desired value? For instance, the first number at which the probability is 50% (or 75%, 90%, 95%, etc.) that the 3-bucket case will have already finished. That is, the number of (multiples of n) pebbles which, at the beginning, you have a certain confidence level that the process will end prior to.

wee free kings

- gmalivuk
- GNU Terry Pratchett
**Posts:**26824**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Pebbles in buckets, a modified random walk

Quantile comes to mind.

### Who is online

Users browsing this forum: No registered users and 12 guests