MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone know of any work on the following model or variants thereof?:

Finitely many chips are distributed on the integers at time 0. To find the distribution at time $t+1$, take all the chips at each location $n$ at time $t$ and send equal numbers of them to $n-1$ and $n+1$, with the proviso that if the numbers of chips at $n$ at time $t$ was odd, say $2k+1$, then $k$ chips go left, $k$ chips go right, and the last chip goes either left or right, as determined by a coin flip. (We assume that the coin used at location $n$ at time $t$ is independent of all the coin flips at all other locations and times.)

Note that if the ``odd chip'' is required to stay put at $n$, this is precisely the chip-firing or sandpile analogue of random walk on the integers, as described for instance in R. J. Anderson, L. Lovasz, P. W. Shor, J. Spencer, E. Tardos and S. Winograd, Disks, balls and walls: Analysis of a combinatorial game, American Math. Monthly 96, pp. 481-493 (1989).

share|cite|improve this question
Do you have a specific question in mind, James? – Tom LaGatta Jun 11 '10 at 5:15
What about the following deterministic variation? ... if the number of chips at $n$ is odd, say $2k+1$ then $k$ go left and $k+1$ go right if $n$ is even, respectively $k$ go right and $k+1$ go left if $n$ is odd. – Roland Bacher Jun 11 '10 at 18:06
Tom: I have a number of specific questions in mind. One is, how big could the discrepancy be between the number of chips at $n$ at time $t$ under odd-chip-moves-randomly and the expected number of chips at $n$ at time $t$ under every-chip-moves-randomly, starting from the same initial state? This is a question I already know the answer to, thanks to private email from Joel Spencer. But has Joel rediscovered something that's already in the literature? – James Propp Jun 12 '10 at 1:47
Roland: Your variation looks sensible. So do some others that can be derived from the various rules for rounding described in . E.g., the odd-chip-moves-randomly rule is related to stochastic rounding, aka dithering, and the rotor-router rule described in is related to the round-half-alternatingly rule. All such variants are of potential interest to me. My question is "What's already known?" – James Propp Jun 12 '10 at 1:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.