Physics 305 Computational Physics
2/13/2006
1. Introduction
We will look at two different programs involving random walks. In the first case we will consider an unconstrained 2-dimensional random walk which can move in any direction at each step, up to a maximum step length. This is just one of an infinite variety of random walk possibilities, many of which have interesting physics applications. [1]Here are some of the possible applications: [2]
- In economics, random walk is used to model shares prices and other factors. Empirical studies found some deviations from this model, especially short term and long term correlations. See share prices.
- In population genetics, random walk describes the statisical properties of genetic drift
- In physics, random walks are used as simplified models of physical Brownian motion and the random movement of molecules in liquids and gases. See for example diffusion-limited aggregation.
- Also in physics, random walks and some of the self interacting walks play a role in quantum field theory.
- In Polymer physics, random walk describes an ideal chain. It is the simplest model to study polymers.
- In other fields of mathematics, random walk is used to calculate solutions to Laplace's equation, to estimate the harmonic measure, and for various constructions in analysis and combinatorics.
In all these cases, random walk is often substituted for Brownian motion.
- In Brain Research, random walks and reinforced random walks are used to model cascades of neuron firing in the brain.
- In psychology, random walks explain accurately the relation between the time needed to make a decision and the probability that a certain decision will be made.
- Random walk can be used to sample from a state space which is unknown or very large, for example to pick a random page off the internet or, for research of working conditions, a random illegal worker in a given country.
- When this last approach is used in computer science it is known as Markov Chain Monte Carlo or MCMC for short. Often, sampling from some complicated state space also allows one to get a probabilistic estimate of the space's size. The estimate of the permanent of a large matrix of zeros and ones was the first major problem tackled using this approach.
- Bacteria engage in a biased random walk.
- And lest we forget, the random walk started its life in modeling of gambling
In mathematics and physics, a random walk is a formalization of the
intuitive idea of taking successive steps, each in a random direction.
[2]
Random walk can also be looked at as a Markov chain whose state
space is given by the integers 
, for some number 0
< p < 1, Pi,i
+ 1 = p = 1 − Pi,i − 1.
We can call it a random walk
because we may think of it as being a model for an individual walking
on a straight line who at each point of time either takes one step to
the right with probability p or
one step to the left with probability 1 − p.
[2]
A random walk is a simple stochastic process. [2]
A random walk is sometimes called a "drunkard's walk". Drunkard's
Walk is also the name of a 1960 science fiction novel by Frederik
Pohl. [2]
Assume now that our city is no longer orderly. When our drunkard reaches a certain junction he picks between the various available roads with equal probability. Thus, if the junction has seven exits the drunkard will go to each one with probability one seventh. This is a random walk on a graph. Will our drunkard reach his home? It turns out that under rather mild conditions, the answer is still yes. For example, if the lengths of all the blocks are between a and b (where a and b are any two finite positive numbers), then the drunkard will, almost surely, reach his home. Notice that we do not assume that the graph is planar, i.e. the city may contain tunnels and bridges. One way to prove this result is using the connection to electrical networks. Take a map of the city and place a one ohm resistor on every block. Now measure the "resistance between a point and infinity". In other words, choose some number R and take all the points in the electrical network with distance bigger than R from our point and wire them together. This is now a finite electrical network and we may measure the resistance from our point to the wired points. Take R to infinity. The limit is called the resistance between a point and infinity. It turns out that the following is true: [2]
Theorem: a graph is transient if and only if the resistance between a point and infinity is finite. It is not important which point is chosen. [2]
In other words, in a transient system, one only needs to overcome a finite resistance to get to infinity from any point. In a recurrent system, the resistance from any point to infinity is infinite. [2]
It also turns out that this characterization of recurrence and transience is very useful, and specifically it allows to analyze the case of a city drawn in the plane with the distances bounded. [2]
A random walk on a graph is a very special case of a Markov chain. Unlike a general Markov chain, random walk on a graph enjoys a property called time symmetry or reversibility. Roughly speaking, this property, also called the principle of detailed balance, means that the probabilities to traverse a given path in one direction or in the other have a very simple connection between them (if the graph is regular, they are just equal). It turns out that this property has important consequences. [2]
Starting from the 80s, much research has gone into connecting properties of the graph to random walks. In addition to the electrical network connection described above, there are important connections to isoperimetric inequalities, see more here, functional inequalities such as Sobolev and Poincaré inequalities and properties of solutions of Laplace's equation. A significant portion of this research was focused on Cayley graphs of finitely generated groups. For example, the proof of Persi Diaconis that 7 riffle shuffles are enough to mix a pack of cards (see more details under shuffle) is in effect a result about random walk on the group Sn, and the proof uses the group structure in an essential way. In many cases these discrete results carry over to, or are derived from Manifolds and Lie groups. [2]
