Derandomized random walk in one and two dimensions: some cellular automata inspired by probability theory Jim Propp, UMass Lowell November 12, 2008 ------------------------------------------------------- Thanks to the organizers for inviting me! This lecture is being recorded with the Camtasia session recording tool, so if all goes well, the screen-image plus audio-track should be available on the web in a few days. Please make sure I repeat any questions that are asked, since otherwise it may be hard for people watching the video to make sense of my answers. ------------------------------------------------------- Unbiased random walk Problem 1: If a particle starts at location 0 and does random walk on Z, how many times on average does it visit location i before returning to location 0? Answer: the mean number of visits is 1 (independent of i) A nonrandom sequence that looks like a random sequence vis-a-vis the mean-number-of-visits property: 0,1,0,-1,0,1,2,1,0,-1,-2,-1,0,1,2,3,2,1,0,-1,... In fact, ANY walk, random or not, that goes left half the time and right half the time from each location will have the aforementioned property; the one I showed you is the simplest. Principle: Many facts about random walk have nothing to do with randomness per se Fluid flow on graphs has the same properties Discrete flows with low discrepancy Subrandomness; quasirandomness (in the sense of Niederreiter, not the sense of Chung, Graham, and Wilson) Rotor-routers are one good way to achieve subrandomness ------------------------------------------------------- Problem 2: If a particle starts at location 0 and does random walk on Z (or equivalently N), what's the probability that the number of steps it takes before its first return to location 0 is congruent to 2 mod 4? Answer: sqrt(2)/2 Note that the simple-minded rotor-scheme 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, ... gives the wrong answer! Compare quasirandomness with pseudorandomness: "One size fits all" vs. "What do you want to know?" For this question, we need a more complicated deterministic sequence: 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 3, 4, 3, 4, 3, 2, 1, 0, ... Write it as 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 3, 4, 3, 4, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0, ... ... to see the pattern. "Spacetime rotors" vs. "space rotors" sqrt(2)/2 = .7071... How many of the first n excursions from 0 have run-length congruent to 2 mod 4? n=10: 7 n=100: 71 n=1000: 705 n=10000: 7070 (Compare this with the discrepancy we'd get from random simulation of the original random process: sqrt(n).) Question: What size discrepancy do we get? (Bounded?) Run-lengths: 2,4,2,6,2,8,2,10,2,4,2,12,2,14,2,16,2,4,2,... (not in Sloane). Conjecture: the record-breaking run lengths increase by 2 Conjecture: We hit all the c.f. convergents for sqrt(2)/2! (Verified up through at least 1393/1970) Suggestive of a unifying structure I have no immediate plans to work on this on my own, but I'd be glad to collaborate or just give the problem away. Ditto for many of the other examples I'll talk about. ------------------------------------------------------- Think of it as n particles loaded simultaneously Galton board picture / quincunx 8 8 4 4 2 2 1 2 1 1 2 1 1 1 1 1 1 1 1 1 Rule: If there are m particles at a site, ceiling(m/2) of them go left and floor(m/2) of them go right (unless the site is in the leftmost column) Spreadsheet: SRW.xls ------------------------------------------------------- Switch to Simple Random Walk on Z, with no absorbing site. Problem 3: What is the distribution governing the location of the particle after k steps of SRW? Answer: The distribution Binomial(k,1/2), which is close to a Gaussian 8 4 4 2 4 2 1 3 3 1 Keep going, using rightward-biased rounding. Rule: If there are m particles at a site, floor(m/2) of them go left and ceiling(m/2) of them go right 8 4 4 2 4 2 1 3 3 1 2 3 2 1 1 2 3 1 1 2 2 2 1 1 1 2 2 1 1 1 2 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Show 1to1-wide.xls (a skewed Galton board) Show the particle point of view Show 1to1-narrow.xls; show the arithmetic-progression patterns How do these patterns establish themselves? ------------------------------------------------------- Show Ander's applet (a Galton board on its side) How quickly does the distribution of the locations of the first n chips (after each has taken k steps) converge to the binomial distribution? ------------------------------------------------------- Biased random walk Problem 4: If a particle starts at location 1 and does rightward-biased random walk (p_left = 1/3, p_right = 2/3) with absorption at location 0, what's the probability that it will eventually get absorbed at 0? Answer: 1/2 Space rotors: 1,0 (success); 1,2,1,2,3,2,3,4,3,4,5,4,... (failure); 1,0 (success); 1,2,1,2,3,2,3,4,3,4,5,4,... (failure); 1,0 (success); etc. Couldn't be better! But let's try something different anyway, that's worse (i.e. exhibits higher discrepancy) but much more interesting! On a Galton board, the most natural thing to do is round: Rule: If there are m particles at a site, round(m/3) of them go left and round(2m/3) of them go right (note that round(m/3) + round(2m/3) = m) E.g., for n=8, 8 3 5 2 3 1 2 2 1 2 1 0 2 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 Here the 8 chips get split into 4 that get absorbed at 0 and 4 that wander off to infinity. This exact split doesn't hold for all even values of n: 4 1 3 1 2 0 2 1 1 1 1 0 1 1 1 Still, let's look at this derandomization scheme. Let a(n) be the number of chips that get absorbed at 0 when n chips are fed into the system (so that a(8) = 4, a(4) = 1, etc.) The remaining n - a(n) chips eventually forming a solid armada of solitary chips moving steadily rightward. We expect a(n) to be close to n/2, and it is. But it is seldom equal to n/2 exactly: indeed, the only values of n up to n=500 for which a(n) equals n/2 are 2, 8, 48, 50, and 200. Moreover, the distribution of a(n) - n/2 is lopsided: Steve Witham discovered that the first value of n for which a(n) exceeds n/2 is 5495. Show spreadsheet 2to1.xls Explain where the new particle goes What's the size of the discrepancy between a(n) and n/2? Show Steve's applet: http://www.tiac.net/~sw/2008/04/RounderRouter/ ------------------------------------------------------- Problem 5: If a particle does random walk in Z^2 starting from (0,0), what's the probability that the particle will hit (1,1) without returning to (0,0)? Answer: pi/8 Show initial rotor-setting in Canary-Wong applet Run it for a few stages State recurrence property As far as I can tell, the number of successes in the first n trials never differs from (pi/8)n by more than a constant. The best current result (Holroyd and Propp) is that the difference is never bigger than a constant times log n. Proof involves an idea and a trick Idea: Global discrepancy = sum_v local discrepancy at v, where: global discrepancy = number of successes minus n times the success probability, local discrepancy at v = sum_w N(v,w)(h(w)-h(v)), h(v) = probability of success starting from v (for random walk), and N(v,w) = number of times a particle went from v to w in the quasirandom walk. The function h( ) satisfies sum_w p(v,w)(h(w)-h(v)) = 0, where p(v,w) is the transition probability from v to w, so if the N(v,w)'s are nearly proportional to the p(v,w)'s the local discrepancy at v will be small. Problem: If you bound each local discrepancy by the natural bound B(v), sum_v B(v) diverges like the harmonic series! Trick: The special initial conditions permit one to prove combinatorially that if you add n chips to the system and let them do rotor-router walk until they've all been absorbed at (0,0) or (1,1), the diameter of the set of visited sites doesn't grow faster than linearly as a function of n, which lets us replace 1 + 1/2 + 1/3 + ... by 1 + 1/2 + ... + 1/n ~ log n, because the local discrepancy at a site that hasn't been visited yet is zero. (I call this a trick because there are lots of initial conditions in which the trick can't be applied, but the discrepancy seems to be just as small as it is in the special case where it does apply.) Show rotor-router walk on Z^2 How does the picture continue to evolve? ------------------------------------------------------- Please make sure I repeat any questions that are asked. Thank you!