6
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you have a specific question in mind, James? $\endgroup$
    – Tom LaGatta
    Commented Jun 11, 2010 at 5:15
  • $\begingroup$ 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. $\endgroup$
    – Roland Bacher
    Commented Jun 11, 2010 at 18:06
  • $\begingroup$ 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? $\endgroup$
    – James Propp
    Commented Jun 12, 2010 at 1:47
  • $\begingroup$ Roland: Your variation looks sensible. So do some others that can be derived from the various rules for rounding described in en.wikipedia.org/wiki/Rounding . E.g., the odd-chip-moves-randomly rule is related to stochastic rounding, aka dithering, and the rotor-router rule described in arxiv4.library.cornell.edu/abs/0904.4507 is related to the round-half-alternatingly rule. All such variants are of potential interest to me. My question is "What's already known?" $\endgroup$
    – James Propp
    Commented Jun 12, 2010 at 1:55

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .