Posted by: justpeachie | November 4, 2008

well that’s random

All Roads Lead to Rome—Even in the Honeycomb World
Author: Brani Vidakovic
The American Statistician
, Vol. 48, No. 3 (Aug., 1994), pp. 234-236
Published by: American Statistical Association
Reviewed by: Linda Yao
<http://www.jstor.org.ezp-prod1.hul.harvard.edu/stable/2684723?seq=1&gt;

In his paper, “All Roads Lead to Rome,” Brani Vidakovic addresses a well known but nevertheless interesting result of random walk theory. By proving the recurrence of the symmetric random walk on the hexagonal lattice, he seeks to provide further understanding of random walks and divergent/convergent series in general. This particular result is interesting also because it provides a treatment of the random walk in R^2, as opposed to being confined to the integer spaces Z^p. The topic’s relationship to Math 152 lies in its emphasis on probability and graph theory as well as its use of combinatorics, arithmetic series, and the general concept of symmetry.

The random walk is a stochastic process, which is a mathematical tool that models the outcomes of events based on their probabilities. Stochastic models are used widely in physics (diffusion of molecules), chemistry (gaseous interaction), biology (population dynamics), computer science (estimating the size of the internet), finance (share prices), psychology (decision theory)… Personally, I am interested in stochastic processes in general, their abundant use in the real world, and the flexibility they lend to applications. As they say, there’s nothing you can’t depict with a good Markov chain!

Specifically, as Vidakovic explains, let a particle begin at a given point O in a p-dimensional space R^p. In each time step, the particle moves from point O in one of 2p given directions. The “random walk” is the (infinitely long) path of the particle. The simplest random walks are restricted to integer coordinates in Z^p. For example: Z^1 is the space for a random walk on the integers, and Z^2 the random walk on a square grid. When the probability of moving in any given direction is \frac{1}{2p}, then all movements have equal probability and the random walk is said to be symmetric.

A random walk of degree 2p, where 2p is the number of possible directions to move in a given time step, is said to be recurrent if, over the course of infinity time steps, its trajectory returns it back to the starting point O an infinite number of times. That is, given that the particle leaves from O, it will definitely come back, again and again, like a bad boyfriend. Recurrence (or transience, which is the lack thereof) is one of the most important traits of the random walk. For example, recurrence in Z^1 (where 2p=2) proves the Gambler’s Ruin problem, which states that bankruptcy is certain when gamblers of finite means go against the casinos of infinite wealth, even when playing a fair game.

Beginning from point O, let the probability that the particle returns to O in time step n be denoted p_n. The recurrence of a random walk is given by the infinite sum. If the series diverges, the walk is recurrent. If not, it is transient.

Symmetric random walks are recurrent only in R^1 and R^2. For R^p where p>2, the random walk is transient. The author informs us that recurrence on integer spaces Z^p is easily proven using Stirling’s formula—basically a fancy approximation for estimating factorials. It’s not directly relevant to the honeycomb proof, however, so I won’t elucidate it here.

Thus, we know that the two-directional symmetric random walk in Z^1 and the four-directional walk in Z^2 are recurrent, and that the walks in Z^p for p>2 are not recurrent. While this is all very important, Vidakovic and I find the honeycomb random walk much more interesting

To visualize this problem, imagine a honeybee who has just filled his infinite honeycomb (with the help of infinitely many worker-bee friends) with fresh honey, but the combs have not yet been sealed. If the bee starts at point O and does a random walk in R^2 along this hexagonal lattice, will he ever return to O? How many times? Once we remember that the bee cannot step into the sticky honey and thus cannot traverse the combs themselves, this becomes the question addressed in the paper.

The hexagonal lattice concept seems complicated at first, but the author collapses the problem into that of a straightforward symmetric random walk on integer space Z^2, with the slight modification that the particle only has three directional choices of movement, each with probability \frac{1}{3}, since the walk is symmetric. See the figures below.

Now, how does one address the question of recurrence? The proof is basically done in two steps: Lemma 2.1 finds and expression for p_n and Lemma 2.2 shows that the summation of the series diverges.

Lemma 2.1 The number of different paths of length 2n on the hexagonal lattice that begin and end at O is

Proof In order to calculate the total number of possible paths (to find the numerator of p_n), Vidakovic likens the particle’s random walk to a “word,” with each time step being a different “letter.” This idea evokes the relation of groups and graphs, so if you’re very into this type of thing, explore further the second column of p. 135. Personally, I feel the proof is more easily understood if the concept is taken at face value.

That is, note that in each time step the particle can move in one of three directions: left, right, and up (on odd steps only) or down (on even steps). In order to return back to where the particle started, it must have moved (in total) the same number of steps to the left as it did to the right and the same number up as down. The total number of possible ways to do this can be calculated using some basic combinatorics.

(Notice that this means p_n for n odd equals zero, since for each step up, one must be taken down; for each step left, one must be taken right; and for each step right, one must be taken left. The cancellation of pairs necessarily ensures that the probability p_n of return is positive only when n is even, which is why the lemma only considers these cases p_{2n}.)

Look at the equation for f_{2n}. Out of n odd-numbered time steps, the particle moves up n-k times: this is n \choose k, since n \choose k = n \choose {n-k}. Given this, out of the n even steps, it must also move down on n-k chosen occasions: n \choose k again. Finally, after subtracting these 2(n-k) up/down movements from the 2n total movements, 2k steps remain, of which half must be to the left: 2k \choose k. Multiply these together to get the total number of O-to-O paths, then sum over all possible k to receive the grand total f_{2n}. \square

This is only the numerator. The denominator of p_{2n} is the total number of possible pathways of length 2n, regardless of whether it ends at O: 3^{2n}. Finally this gives p_{2n} = \frac{f_{2n}}{3^{2n}}. This is very straightforward probability theory.

Lemma 2.2 p_{2n}\frac{K}{n}, where K can be taken as \frac{\sqrt{6}}{24}.

If the above is true, then p_{2n} is large enough such that the summation will diverge.

Proof The proof itself is not conceptually complex, but requires some tricky algebraic manipulation. It also uses many combinatorial identities which we shall simply take as given.

First, the author shows that there exists some C_1 and C_2 such that

(inequality a).

To do this, he first uses an easily proven inequality:

and the following combinatoric identity:

to perform some clever algebraic manipulation, yielding C_1 = \frac{1}{2} and C_2 = \frac{\sqrt{6}}{4}. Using this and inequality (a), we find:

(inequality b).

Note that this is the summation expression for f_{2n} found in Lemma 2.1. Next, a couple of combinatorial identities are manipulated to yield:


(equation c), which we will take as given.

Next, using (b) and (c), respectively, in the equation for p_{2n} found in Lemma 2.1:

Remembering that p_n for odd n is zero, then . \square

Thus, the honeycomb random walk is recurrent. The probability that the particle will eventually return to origin O equals one, and it will return infinitely many times.

Theorem The random walk on a hexagonal lattice in R^2 is recurrent.

This result promotes the possibility of recurrent random walks on other types of lattices over the real numbers, not just restricted to Z^p, though it is notable that the ease of the honeycomb proof lies precisely in its reduction to a Z^2 problem.

I have already elucidated the fact that recurrence in general is a significant concept, whose consequences affect stochastic modeling across a wide array of field applications. In math, the random walk is used with Laplace’s equation, harmonic measure, Gibb’s samplers, and combinatorics. In the financial world, the behavior of stocks can be seen as a continuous random walk–indeed, they are most often modeled using Brownian motion, basically an infinitesimal limit of a symmetric random walk. In physics, the walk is used to study polymers. Population drift, molecule diffusion, neuron firing, eye movement, and gambling behavior all lend themselves to these models, as well. More specifically, the honeycomb random walk itself has recently been used to model light transport in foams <http://hera.physik.uni-konstanz.de/publications/publ/2003_Stark_Persistent%20random%20walk.pdf&gt; and gas diffusion <http://www.iop.org/EJ/abstract/0022-3719/18/34/005&gt;.

Thus, as the title of the article suggests, “all roads lead to Rome,” with “Rome” being the world of stochastic modeling, of course! Any process leading to uncertain outcomes that can be predicted using probabilities roughly follows a stochastic process—the most common of which are random walks.

Advertisements

Responses

  1. Sorry, just to clarify: This is my reading project, guys, not an obese blog post — in case you thought I had gone crazy or something!

  2. I enjoyed your enthusiasm for stochastic modeling. It’s true that that sort of math can be very powerful and I enjoyed learning about the honeycomb random walk.

    I also like your question about other lattices. There are lots of lattices you could invent and study. Eventually, you might get a big long list of different kinds of lattices or tilings and whether they are recurrent. You could move up in dimension also, and expand the list even further. Eventually, it would be nice to know what property really determines recurrence. Is there some measure of a lattice that would predict whether it is recurrent? Something like degree of the vertices? It should depend on dimension too? Probably the answer is complicated.

  3. Gold bracelet is one of the shemportant pieces of jewelry for every woman. Known as the gold
    bangle, admittedly. Possessor, gold bracelet, gold with 96.5%, along a deskard weight ranging from 3 to 25 satang half
    bath great price am up and down, as the cost of gold on the
    market each day. Gold bangle is a sarong kind of jewelry, gold
    cost, so itt depends on the format, because the price is itn the
    section of kamnet.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: