Start with a single large pile of chips at position zero. At each time each pile is halved and half the chips are sent one unit to the left, while the other half is moved one unit to the right. This game clearly corresponds to the random walk on the line: after t steps the distribution of the chips is the same as the distribution after t steps of the unbiased random walk. But sooner or later some piles will be odd and to execute the above rule we need to break some chips. To avoid this we send one more chips to one direction than to the other. This preferred direction is arbitrary the first time an odd pile appears in any position, but to balance its effects we alternate the preferred directions in later times when the same position has an odd pile again.

How far do we get with this process (called Propp's simulator) from the exact process where the chips are halved (and further subdivided) as needed? We show that the difference between the size of a pile in the two processes is bounded by 2.3 - independent of the number of chips and the length of the process. Further results show that maximal difference of the number of chips in an interval growth logarithmically with the length of the interval. Similar questions can be studied in other graphs. Grids in higher dimensions behave similarly as the line, but the 3-regular tree is fundamentally different: the difference of the size of a single pile in the two processes is unbounded.

This is joint work with Joshua Cooper, Benjamin Doerr and Joel Spencer.