Example of eight random walks in one dimension starting at 0. The plot shows the time steps (horizontal axis) versus the current position on the line (vertical axis).

A random walk, sometimes called a "drunkard's walk," is a formalization in mathematics, computer science, and physics of the intuitive idea of taking successive steps, each in a random direction. For example, the path traced by a molecule as it travels in a liquid or a gas is a random walk. Image File history File links Random_Walk_example. ... Image File history File links Random_Walk_example. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... This article needs additional references or sources for verification. ... Random redirects here. ... In science, a molecule is a group of atoms in a definite arrangement held together by chemical bonds. ...

Definition

The simplest random walk is a path constructed according to the following rules: In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. ...

• There is a starting point.
• The distance from one point in the path to the next is a constant.
• The direction from one point in the path to the next is chosen at random, and no direction is more probable than another.

One-dimensional random walk

One-dimensional random walk takes place on a line. So, one starts at zero, and at each step one moves by a fixed amount along one of the two directions from the current point, with the direction being chosen randomly.

The average straight-line distance between start and finish points of a one-dimensional random walk of n steps is on the order of , or more precisely, its asymptote converges to . If "average" is understood in the sense of root-mean-square, then the average distance after n steps is times the step length exactly. In mathematics, an average or central tendency of a set (list) of data refers to a measure of the middle of the data set. ... Big O notation is often used to describe how the size of the input data affects an algorithms running time. ... An asymptote is a straight line or curve which a curve approaches as one moves along the curve. ... In mathematics, root mean square (abbreviated RMS or rms), also known as the quadratic mean, is a statistical measure of the magnitude of a varying quantity. ...

Suppose we draw a line some distance from the origin of the walk. How many times will the random walk cross the line? The following, perhaps surprising, theorem is the answer: for any random walk in one dimension, every point in the domain will almost surely be crossed an infinite number of times. [In two (or perhaps three) dimensions, this is equivalent to the statement that any line (or plane) will be crossed an infinite number of times.] This problem has many names: the level-crossing problem, the recurrence problem or the gambler's ruin problem. The source of the last name is as follows: if you are a gambler with a finite amount of money playing a fair game against a bank with an infinite amount of money, you will surely lose. The amount of money you have will perform a random walk, and it will almost surely, at some time, reach 0—and the game will be over. In mathematics, the domain of a function is the set of all input values to the function. ... In probability theory, an event happens almost surely (a. ...

The expected number of steps until a one dimensional random walk goes up to b or down to -a is ab. The probability that the random walk will go up to b steps before going down a steps is

Higher dimensions

Random walk in two dimensions.

Random walk in two dimensions with more, and smaller, steps. In the limit, for very small steps, one obtains the Brownian motion.

Imagine now a drunkard walking randomly in a city. The city is infinite and arranged in a square grid, and at every intersection, the drunkard chooses one of the four possible routes (including the one he came from) with equal probability. Formally, this is a random walk on the set of all points in the plane with integer coordinates. Will the drunkard ever get back to his home from the bar? It turns out that he will (almost surely). This is the high dimensional equivalent of the level crossing problem discussed above. However, in dimensions 3 and above, this no longer holds. In other words, a drunk bird might forever wander the sky, never finding its nest. The formal terms to describe this phenomenon is that a random walk in dimensions 1 and 2 is recurrent, while in dimension 3 and above it is transient. This was proven by Pólya in 1921. Image File history File links Size of this preview: 510 × 599 pixelsFull resolution (842 × 989 pixel, file size: 29 KB, MIME type: image/png) Made by myself with MATLAB. Note. ... Image File history File links Size of this preview: 510 × 599 pixelsFull resolution (842 × 989 pixel, file size: 29 KB, MIME type: image/png) Made by myself with MATLAB. Note. ... Image File history File links Size of this preview: 401 × 600 pixelsFull resolution (661 × 989 pixel, file size: 86 KB, MIME type: image/png) Made by myself with MATLAB. Note. ... Image File history File links Size of this preview: 401 × 600 pixelsFull resolution (661 × 989 pixel, file size: 86 KB, MIME type: image/png) Made by myself with MATLAB. Note. ... Three different views of Brownian motion, with 32 steps, 256 steps, and 2048 steps denoted by progressively lighter colors. ... Two intersecting planes in three-dimensional space In mathematics, a plane is a two-dimensional manifold or surface that is perfectly flat. ... The integers are commonly denoted by the above symbol. ... In mathematics as applied to geometry, physics or engineering, a coordinate system is a system for assigning a tuple of numbers to each point in an n-dimensional space. ... George Pólya (December 13, 1887 – September 7, 1985, in Hungarian Pólya György) was a Hungarian mathematician. ... Year 1921 (MCMXXI) was a common year starting on Saturday (link will display the full calendar). ...

The trajectory of a random walk is the collection of sites it visited, considered as a set with disregard to when the walk arrived at the point. In one dimension, the trajectory is simply all points between the minimum height the walk achieved and the maximum (both are, on average, on the order of √n). In higher dimensions the set has interesting geometric properties. In fact, one gets a discrete fractal, that is a set which exhibits stochastic self-similarity on large scales, but on small scales one can observe "jugginess" resulting from the grid on which the walk is performed. The two books of Lawler referenced below are a good source on this topic. The boundary of the Mandelbrot set is a famous example of a fractal. ... A self-similar object is exactly or approximately similar to a part of itself. ...

Three random walks in three dimensions.

Image File history File links Size of this preview: 542 × 600 pixelsFull resolution (744 × 823 pixel, file size: 26 KB, MIME type: image/png) Isotropic random walk on the euclidean lattice . ... Image File history File links Size of this preview: 542 × 600 pixelsFull resolution (744 × 823 pixel, file size: 26 KB, MIME type: image/png) Isotropic random walk on the euclidean lattice . ...

Random walk on graphs

Assume now that our city is no longer a perfect square grid. 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: In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... An electrical network or electrical circuit is an interconnection of analog electrical elements such as resistors, inductors, capacitors, diodes, switches and transistors. ... The ohm (symbol: Ω) is the SI unit of electric resistance. ... Electrical resistance is a measure of the degree to which an electrical component opposes the passage of current. ...

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.

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.

This characterization of recurrence and transience is very useful, and specifically it allows us to analyze the case of a city drawn in the plane with the distances bounded.

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). This property has important consequences. In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ... In mathematics, and in statistical mechanics in physics, a Markov process is said to show detailed balance if the transition rates between each pair of states i and j in the state space obey where P is the Markov transition matrix (transition probability), ie Pij = P( Xt =j | Xt−1... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ...

Starting in the 1980s, 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 S_n, 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. Isoperimetry literally means having an equal perimeter. In mathematics, isoperimetry is the general study of geometric figures having equal boundaries. ... In mathematics, the isoperimetric dimension of a manifold is a notion of dimension that tries to capture how the large scale behavior of the manifold resembles that of a Euclidean space (unlike the topological dimension or the Hausdorff dimension which compare different local behaviors against those of the Euclidean space). ... Sobolev, Sergei Lvovich (Russian: Сергей Львович Соболев) (6 October 1908- 3 January 1989) was a Russian mathematician, working in mathematical analysis and partial differential equations. ... Jules TuPac Henri Poincaré (April 29, 1854 – July 17, 1912) (IPA: [][1]) was one of Frances greatest mathematicians and theoretical physicists, and a philosopher of science. ... In mathematics, Laplaces equation is a partial differential equation named after its discoverer, Pierre-Simon Laplace. ... The Cayley graph of the free group on two generators a and b In mathematics, a Cayley graph, named after Arthur Cayley, is a graph that encodes the structure of a group. ... Please refer to group theory for a general description of the topic. ... This picture illustrates how the hours on a clock form a group under modular addition. ... Persi Diaconis at Stanford (Summer 2004). ... The riffle Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. ... The riffle Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ... On a sphere, the sum of the angles of a triangle is not equal to 180°. A sphere is not a Euclidean space, but locally the laws of the Euclidean geometry are good approximations. ... In mathematics, a Lie group, named after Norwegian mathematician Sophus Lie (IPA pronunciation: , sounds like Lee), is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure. ...

A good reference for random walk on graphs is the online book by Aldous and Fill. For groups see the book of Woess. If the graph itself is random, this topic is called "random walk in random environment" — see the book of Hughes.

Relation to Brownian motion

Simulated steps approximating Brownian motion in two dimensions.

Brownian motion is the scaling limit of random walk in dimension 1. This means that if you take a random walk with very small steps you get an approximation to Brownian motion. To be more precise, if the step size is ε, one needs to take a walk of length L/ε² to approximate a Brownian motion of length L. As the step size tends to 0 (and the number of steps increased comparatively) random walk converges to Brownian motion in an appropriate sense. Formally, if B is the space of all paths of length L with the maximum topology, and if M is the space of measure over B with the norm topology, then the convergence is in the space M. Similarly, Brownian motion in several dimensions is the scaling limit of random walk in the same number of dimensions. Note that Brownian motion in the present article refers to the mathematical definition of the term, rather than the actual physical phenomenon of a minute particle diffusing in a fluid. Image File history File links Download high resolution version (874x840, 161 KB) Summary An image of Brownian motion, done with three different step sizes. ... Image File history File links Download high resolution version (874x840, 161 KB) Summary An image of Brownian motion, done with three different step sizes. ... Three different views of Brownian motion, with 32 steps, 256 steps, and 2048 steps denoted by progressively lighter colors. ... If we wish to have a lattice model which approximates a continuum quantum field theory in the limit as the lattice spacing goes to zero, then this corresponds to finding a second order phase transition of the model. ... Three different views of Brownian motion, with 32 steps, 256 steps, and 2048 steps denoted by progressively lighter colors. ...

A random walk is a discrete fractal, but Brownian motion is a true fractal, and there is a connection between the two. For example, take a random walk until it hits a circle of radius r times the step length. The average number of steps it performs is r². This fact is the discrete version of the fact that Brownian motion is a fractal of Hausdorff dimension 2 ^[1]. In two dimensions, the average number of points the same random walk has on the boundary of its trajectory is r^{4 / 3}. This corresponds to the fact that the boundary of the trajectory of Brownian motion is a fractal of dimension 4/3, a fact predicted by Mandelbrot using simulations but proved only in 2000 (Science, 2000). The boundary of the Mandelbrot set is a famous example of a fractal. ... In mathematics, the Hausdorff dimension is an extended non-negative real number associated to any metric space. ... Benoît B. Mandelbrot, PhD, (born November 20, 1924) is a Franco-American mathematician, best known as the father of fractal geometry. Benoît Mandelbrot was born in Poland, but his family moved to France when he was a child; he is a dual French and American citizen and was... 2000 (MM) was a leap year starting on Saturday of the Gregorian calendar. ...

Brownian motion enjoys many symmetries random walk does not. For example, Brownian motion is invariant to rotations, but random walk is not, since the underlying grid is not (random walk is invariant to rotations by 90 degrees, but Brownian motion is invariant to rotations by, for example, 17 degrees too). This means that in many cases, problems on random walk are easier to solve by translating them to Brownian motion, solving the problem there, and then translating back. On the other hand, some problems are easier to solve with random walks due to its discrete nature. Sphere symmetry group o. ...

Random walk and Brownian motion can be coupled, namely manifested on the same probability space in a dependent way that forces them to be quite close. The simplest such coupling is the Skorokhod embedding, but other, more precise couplings exist as well. Three different views of Brownian motion, with 32 steps, 256 steps, and 2048 steps denoted by progressively lighter colors. ... In mathematics, coupling is a proof technique that allows to compare two unrelated variables by forcing them to be related in some way. ...

The convergence of a random walk toward the Brownian motion is controlled by the central limit theorem. For a particle in a known fixed position at t=0, the theorem tells us that after a large number of independent steps in the random walk, the walker's position is distributed according to a normal distribution of total variance: A central limit theorem is any of a set of weak-convergence results in probability theory. ... The normal distribution, also called the Gaussian distribution, is an important family of continuous probability distributions, applicable in many fields. ... In probability theory and statistics, the variance of a random variable (or somewhat more precisely, of a probability distribution) is a measure of its statistical dispersion, indicating how its possible values are spread around the expected value. ...

, where t is the time elapsed since the start of the random walk, ε is the size of a step of the random walk, and δt is the time elapsed between two successive steps.

This corresponds to the Green function of the diffusion equation that controls the Brownian motion, which demonstrates that, after a large number of steps, the random walk converges toward a Brownian motion. The heat equation or diffusion equation is an important partial differential equation which describes the variation of temperature in a given region over time. ...

In 3D, the variance corresponding to the Green's function of the diffusion equation is: In mathematics, a Greens function is a type of function used to solve inhomogeneous differential equations subject to boundary conditions. ...

By equalizing this quantity with the variance associated to the position of the random walker, one obtains the equivalent diffusion coefficient to be considered for the asymptotic Brownian motion toward which the random walk converges after a large number of steps:

(valid only in 3D)

Remark: the two expressions of the variance above correspond to the distribution associated to the vector that links the two ends of the random walk, in 3D. The variance associated to each component R_x, R_y or R_z is only one third of this value (still in 3D).

Self-interacting random walks

There are a number of interesting models of random paths in which each step depends on the past in a complicated manner. All are more difficult to analyze than the usual random walk — some notoriously so. For example

• The self-avoiding walk. See the Madras and Slade book.
• The loop-erased random walk. See the two books of Lawler.
• The reinforced random walk.
• The exploration process.

A self-avoiding walk (SAW) is a sequence of moves on a lattice which does not visit the same point more than once. ... In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics and, in physics, quantum field theory. ...

Applications

• In economics, the "random walk hypothesis" is used to model shares prices and other factors. Empirical studies found some deviations from this theoretical model, especially in short term and long term correlations. See share prices.
• In population genetics, random walk describes the statistical 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 computer science and the www, random walks are used to estimate the size of the web. In the World Wide Web conference-2006, bar-yossef et.al. published their findings and algorithms for the same. (This was awarded the best paper for the year 2006).

In all these cases, random walk is often substituted for Brownian motion. This article needs additional references or sources for verification. ... The random walk hypothesis is a financial theory, close to the efficient market hypothesis, stating that market prices evolve according to a random walk and thus cannot be predicted. ... In economics and financial theory, analysts use random walk techniques to model behavior of asset prices, in particular share prices on stock markets, currency exchange rates and commodity prices. ... Population genetics is the study of the distribution of and change in allele frequencies under the influence of the four evolutionary forces: natural selection, genetic drift, mutation, and migration. ... In population genetics, genetic drift is the statistical effect that results from the influence that chance has on the success of alleles (variants of a gene). ... This article needs additional references or sources for verification. ... Random redirects here. ... This article or section is in need of attention from an expert on the subject. ... In science, a molecule is the smallest particle of a pure chemical substance that still retains its chemical composition and properties. ... A DLA cluster grown from a copper sulfate solution in an electrodeposition cell Diffusion-limited aggregation (DLA) is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. ... Quantum field theory (QFT) is the quantum theory of fields. ... Polymer physics is the field of physics associated to the study of polymers, their fluctuations, mechanical properties, as well as the kinetics of reactions involving degradation and polymerisation of polymers and monomers respectively. ... An ideal chain (or freely-jointed chain) is the simplest model to describe a polymer. ... A polymer is a long, repeating chain of atoms, formed through the linkage of many molecules called monomers. ... In mathematics, Laplaces equation is a partial differential equation named after its discoverer, Pierre-Simon Laplace. ... In mathematics — specifically, in stochastic analysis — an Itō diffusion is a solution to a specific type of stochastic differential equation. ... Analysis has its beginnings in the rigorous formulation of calculus. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Graphic representation of the world wide web around Wikipedia The World Wide Web (WWW, or simply Web) is an information space in which the items of interest, referred to as resources, are identified by global identifiers called Uniform Resource Identifiers (URI). ...

• In brain research, random walks and reinforced random walks are used to model cascades of neuron firing in the brain.
• In vision science, fixational eye movements are well described by a random walk.
• 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.
• In wireless networking, random walk is used to model node movement.
• Bacteria engage in a biased random walk.
• Random walk is used to model gambling.
• During World War II a random walk was used to model the distance that an escaped prisoner of war would travel in a given time.

The human brain is the most complex organ in the human body. ... Fixational eye movements (also known as fixational instability, retinal jitter) are small, involuntary eye movements that occur during visual fixation. ... Psychology (from Greek: ψυχή, psukhē, spirit, soul; and λόγος, logos, knowledge) is both an academic and applied discipline involving the scientific study of mental processes and behavior. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods) are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its stationary distribution. ... For the hair treatment see Permanent wave. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ... Wireless networks are telephone or computer networks that use radio as their carrier or physical layer. ... In cell biology, a biased random walk enables bacteria to source for food and flee from harm. ... The term gambling has had many different meanings depending on the cultural and historical context in which it is used. ... Combatants Allied powers: China France Great Britain Soviet Union United States and others Axis powers: Germany Italy Japan and others Commanders Chiang Kai-shek Charles de Gaulle Winston Churchill Joseph Stalin Franklin Roosevelt Adolf Hitler Benito Mussolini Hideki Tōjō Casualties Military dead: 17,000,000 Civilian dead: 33,000... Geneva Convention definition A prisoner of war (POW) is a soldier, sailor, airman, or marine who is imprisoned by an enemy power during or immediately after an armed conflict. ...

Probabilistic interpretation

A one-dimensional random walk can also be looked at as a Markov chain whose state space is given by the integers , for some number , . 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. In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ...

A random walk is a simple stochastic process. In the mathematics of probability, a stochastic process is a random function. ...

See also

• Bertrand's ballot theorem
• Bacterial chemotaxis
• Coin-tossing problems.
• Diffusion-limited aggregation
• Law of the iterated logarithm
• Martingale (probability theory)
• Markov chain
• Quantum random walk (random walk with extra chirality parameter)
• Wiener process (random walk with infinitesimal step size)

In combinatorics, Bertrands ballot theorem is the solution to the question: In an election where one candidate receives p votes and the other q votes with p≥q, what is the probability that the first candidate will be strictly ahead of the second candidate throughout the count? The... Chemotaxis is a kind of taxis, in which bodily cells, bacteria, and other single-cell or multicellular organisms direct their movements according to certain chemicals in their environment. ... Coin flipping or coin tossing is the practice of throwing a coin in the air to resolve a dispute between two parties. ... A DLA cluster grown from a copper sulfate solution in an electrodeposition cell Diffusion-limited aggregation (DLA) is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. ... In probability theory, the law of the iterated logarithm is the name given to several theorems which describe the magnitude of the fluctuations of a random walk. ... A stopped Brownian motion as an example for a martingale In probability theory, a martingale is a stochastic process (i. ... In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ... The probability distribution for a one-dimensional QRW using the below unitary matrix, after 1000 timesteps. ... A single realization of a one-dimensional Wiener process A single realization of a three-dimensional Wiener process In mathematics, the Wiener process is a continuous-time stochastic process named in honor of Norbert Wiener. ...

References

1. ^ Hence the drunkard's random walk would eventually cover all of the city streets (2 Euclidean dimensions) and he will eventually return home, whereas the bird taking a 'random walk' flight through the air (3 Euclidean dimensions) will not cover all space, and will not return to their starting point.

Bibliography

• David Aldous and Jim Fill, Reversible Markov Chains and Random Walks on Graphs, http://stat-www.berkeley.edu/users/aldous/RWG/book.html
• William Feller (1968), An Introduction to Probability Theory and its Applications (Volume 1). ISBN 0-471-25708-7

Chapter 3 of this book contains a thorough discussion of random walks, including advanced results, using only elementary tools.

• Barry D. Hughes (1996), Random walks and random environments, Oxford University Press. ISBN 0-19-853789-1
• Gregory Lawler (1996), Intersection of random walks, Birkhäuser Boston. ISBN 0-8176-3892-X
• Gregory Lawler, Conformally Invariant Processes in the Plane, http://www.math.cornell.edu/~lawler/book.ps
• Neal Madras and Gordon Slade (1996), The Self-Avoiding Walk, Birkhäuser Boston. ISBN 0-8176-3891-1
• Springer Pólya (1921), "Über eine Aufgabe der Wahrscheinlichkeitstheorie betreffend die Irrfahrt im Strassennetz", Mathematische Annalen, 84(1-2):149–160, March 1921.
• Pal Révész (1990), Random walk in random and non-random environments, World Scientific Pub Co. ISBN 981-02-0237-7
• Wolfgang Woess (2000), Random walks on infinite graphs and groups, Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3

• The XScreenSaver has a hack wander that shows random walk on the plane with the color changing with time.
• Mackenzie, Dana, "Taking the Measure of the Wildest Dance on Earth", Science, Vol. 290, 8 December, 2000.

William (Vilim) Feller (July 7, 1906 - January 14, 1970) was a Croatian-American mathematician specializing in probability theory. ...

External links

• Pólya's Random Walk Constants
• Javascript builds a distribution from 50 step walks
• Flash-based example of a random walk
• Random walk in Java Applet