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!