Random walk

Random walk

Discussion
Ask a question about 'Random walk'
Start a new discussion about 'Random walk'
Answer questions from other users
Full Discussion Forum
 
Encyclopedia
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule
Molecule
A molecule is an electrically neutral group of at least two atoms held together by covalent chemical bonds. Molecules are distinguished from ions by their electrical charge...

 as it travels in a liquid or a gas, the search path of a foraging
Foraging
- Definitions and significance of foraging behavior :Foraging is the act of searching for and exploiting food resources. It affects an animal's fitness because it plays an important role in an animal's ability to survive and reproduce...

 animal, the price of a fluctuating stock
Random walk hypothesis
The random walk hypothesis is a financial theory stating that stock market prices evolve according to a random walk and thus the prices of the stock market cannot be predicted. It is consistent with the efficient-market hypothesis....

 and the financial status of a gambler can all be modeled as random walks. The term random walk was first introduced by Karl Pearson
Karl Pearson
Karl Pearson FRS was an influential English mathematician who has been credited for establishing the disciplineof mathematical statistics....

 in 1905. Random walks have been used in many fields: ecology
Ecology
Ecology is the scientific study of the relations that living organisms have with respect to each other and their natural environment. Variables of interest to ecologists include the composition, distribution, amount , number, and changing states of organisms within and among ecosystems...

, economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...

, psychology
Psychology
Psychology is the study of the mind and behavior. Its immediate goal is to understand individuals and groups by both establishing general principles and researching specific cases. For many, the ultimate goal of psychology is to benefit society...

, computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

, chemistry
Chemistry
Chemistry is the science of matter, especially its chemical reactions, but also its composition, structure and properties. Chemistry is concerned with atoms and their interactions with other atoms, and particularly with the properties of chemical bonds....

, and biology
Biology
Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...

. Random walks explain the observed behaviors of processes in these fields, and thus serve as a fundamental model
Statistical model
A statistical model is a formalization of relationships between variables in the form of mathematical equations. A statistical model describes how one or more random variables are related to one or more random variables. The model is statistical as the variables are not deterministically but...

 for the recorded stochastic activity
Stochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...

.

Various different types of random walks are of interest. Often, random walks are assumed to be Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...

s or Markov process
Markov process
In probability theory and statistics, a Markov process, named after the Russian mathematician Andrey Markov, is a time-varying random phenomenon for which a specific property holds...

es, but other, more complicated walks are also of interest. Some random walks are on graphs
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, others on the line, in the plane, or in higher dimensions, while some random walks are on groups
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...

. Random walks also vary with regard to the time parameter. Often, the walk is in discrete time, and indexed by the natural numbers, as in . However, some walks take their steps at random times, and in that case the position is defined for the continuum of times . Specific cases or limits of random walks include the drunkard's walk and Lévy flight
Lévy flight
A Lévy flight is a random walk in which the step-lengths have a probability distribution that is heavy-tailed. When defined as a walk in a space of dimension greater than one, the steps made are in isotropic random directions...

. Random walks are related to the diffusion
Diffusion
Molecular diffusion, often called simply diffusion, is the thermal motion of all particles at temperatures above absolute zero. The rate of this movement is a function of temperature, viscosity of the fluid and the size of the particles...

 models and are a fundamental topic in discussions of Markov process
Markov process
In probability theory and statistics, a Markov process, named after the Russian mathematician Andrey Markov, is a time-varying random phenomenon for which a specific property holds...

es. Several properties of random walks, including dispersal distributions, first-passage times and encounter rates, have been extensively studied.

Lattice random walk


A popular random walk model is that of a random walk on a regular lattice, where at each step the walk jumps to another site according to some probability distribution. In simple random walk, the walk can only jump to neighbouring sites of the lattice. In simple symmetric random walk on a locally finite lattice, the probabilities of walk jumping to any one of its neighbours are the same. The most well-studied example is of random walk on the d-dimensional integer lattice (sometimes called the hypercubic lattice) .

One-dimensional random walk


An elementary example of a random walk is the random walk on the integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 number line, , which starts at 0 and at each step moves +1 or −1 with equal probability.

This walk can be illustrated as follows. A marker is placed at zero on the number line and a fair coin is flipped. If it lands on heads, the marker is moved one unit to the right. If it lands on tails, the marker is moved one unit to the left. After five flips, it is possible to have landed on 1, −1, 3, −3, 5, or −5. With five flips, three heads and two tails, in any order, will land on 1. There are 10 ways of landing on 1 or −1 (by flipping three tails and two heads), 5 ways of landing on 3 (by flipping four heads and one tail), 5 ways of landing on −3 (by flipping four tails and one head), 1 way of landing on 5 (by flipping five heads), and 1 way of landing on −5 (by flipping five tails). See the figure below for an illustration of the possible outcomes of 5 flips.

To define this walk formally, take independent random variables , where each variable is either 1 or −1, with a 50% probability for either value, and set and The series
Series (mathematics)
A series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....

  is called the simple random walk on . This series (the sum of the sequence of −1s and 1s) gives the distance walked, if each part of the walk is of length one.
The expectation
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

  of is zero. That is, the mean of all coin flips approaches zero as the number of flips increase. This follows by the finite additivity property of expectation:
.

A similar calculation, using the independence of the random variables and the fact that , shows that:
.

This hints that , the expected
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

 translation distance after n steps, should be of the order of
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

 . In fact,

Derivation of dispersion proportionality


If we have the situation where the probabilities of moving either left or right are equal, and , the probability of taking steps to the right out of a total of steps is given by


since there are possible ways of taking and steps to the right and left, respectively. The probability of taking any of these independent steps is 1/2, and so we have the product . Now, the expectation value of taking steps is


It is generally the case that . Note the identity we have used with the binomial coefficient . We use it again below. We must then calculate the expectation value of :


It is generally the case that . The dispersion is


This result shows that diffusion becomes quite an ineffective way to mix solutions because of the way the square root behaves for large .

How many times will a random walk cross a boundary line if permitted to continue walking forever? A simple random walk on will cross every point an infinite number of times. This result has many names: the level-crossing phenomenon, recurrence or the gambler's ruin. The reason for the last name is as follows: a gambler with a finite amount of money will always lose when playing a fair game against a bank with an infinite amount of money. The gambler's money will perform a random walk, and it will reach zero at some point, and the game will be over.

If a and b are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits b or −a is ab. The probability that this walk will hit b before −a is , which can be derived from the fact that simple random walk is a martingale
Martingale (probability theory)
In probability theory, a martingale is a model of a fair game where no knowledge of past events can help to predict future winnings. In particular, a martingale is a sequence of random variables for which, at a particular time in the realized sequence, the expectation of the next value in the...

.
Some of the results mentioned above can be derived from properties of Pascal's triangle
Pascal's triangle
In mathematics, Pascal's triangle is a triangular array of the binomial coefficients in a triangle. It is named after the French mathematician, Blaise Pascal...

. The number of different walks of n steps where each step is +1 or −1 is clearly 2n. For the simple random walk, each of these walks are equally likely. In order for Sn to be equal to a number k it is necessary and sufficient that the number of +1 in the walk exceeds those of −1 by k. Thus, the number of walks which satisfy is precisely the number of ways of choosing (n + k)/2 elements from an n element set (for this to be non-zero, it is necessary that n + k be an even number), which is an entry in Pascal's triangle denoted by . Therefore, the probability that is equal to . By representing entries of Pascal's triangle in terms of factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

s and using Stirling's formula, one can obtain good estimates for these probabilities for large values of .

This relation with Pascal's triangle is demonstrated for small values of n. At zero turns, the only possibility will be to remain at zero. However, at one turn, there is one chance of landing on −1 or one chance of landing on 1. At two turns, a marker at 1 could move to 2 or back to zero. A marker at −1, could move to −2 or back to zero. Therefore, there is one chance of landing on −2, two chances of landing on zero, and one chance of landing on 2.

n −5 −4 −3 −2 −1 0 1 2 3 4 5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1


The central limit theorem
Central limit theorem
In probability theory, the central limit theorem states conditions under which the mean of a sufficiently large number of independent random variables, each with finite mean and variance, will be approximately normally distributed. The central limit theorem has a number of variants. In its common...

 and the law of the iterated logarithm
Law of the iterated logarithm
In probability theory, the law of the iterated logarithm describes the magnitude of the fluctuations of a random walk. The original statement of the law of the iterated logarithm is due to A. Y. Khinchin . Another statement was given by A.N...

 describe important aspects of the behavior of simple random walk on .

As a Markov chain


A one-dimensional random walk can also be looked at as a Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...

 whose state space is given by the integers For some number p satisying , the transition probabilities (the probability Pi,j of moving from state i to state j) are given by.

Gaussian random walk


A random walk having a step size that varies according to a normal distribution is used as a model for real-world time series data such as financial markets. The Black–Scholes formula for modeling option prices, for example, uses a gaussian random walk as an underlying assumption.

Here, the step size is the inverse cumulative normal distribution where 0 ≤ z ≤ 1 is a uniformly distributed random number, and μ and σ are the mean and standard deviations of the normal distribution, respectively.

For steps distributed according to any distribution with zero mean and a finite variance (not necessarily just a normal distribution), the root mean square
Root mean square
In mathematics, the root mean square , also known as the quadratic mean, is a statistical measure of the magnitude of a varying quantity. It is especially useful when variates are positive and negative, e.g., sinusoids...

 translation distance after n steps is

Higher dimensions




Imagine now a drunkard walking randomly in an idealized city. The city is effectively 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
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...

 with integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 coordinates
Coordinate system
In geometry, a coordinate system is a system which uses one or more numbers, or coordinates, to uniquely determine the position of a point or other geometric element. The order of the coordinates is significant and they are sometimes identified by their position in an ordered tuple and sometimes by...

. Will the drunkard ever get back to his home from the bar? It turns out that he will. This is the high dimensional equivalent of the level crossing problem discussed above. The probability of returning to the origin decreases as the number of dimensions increases. In three dimensions, the probability decreases to roughly 34%. A derivation, along with values of p(d) are discussed here: Pólya's Random Walk Constants.

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
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...

, that is a set which exhibits stochastic self-similarity
Self-similarity
In mathematics, a self-similar object is exactly or approximately similar to a part of itself . Many objects in the real world, such as coastlines, are statistically self-similar: parts of them show the same statistical properties at many scales...

 on large scales, but on small scales one can observe "jaggedness" resulting from the grid on which the walk is performed. The two books of Lawler referenced below are a good source on this topic.

Relation to Wiener process


A Wiener process
Wiener process
In mathematics, the Wiener process is a continuous-time stochastic process named in honor of Norbert Wiener. It is often called standard Brownian motion, after Robert Brown...

 is a stochastic process with similar behaviour to Brownian motion
Brownian motion
Brownian motion or pedesis is the presumably random drifting of particles suspended in a fluid or the mathematical model used to describe such random movements, which is often called a particle theory.The mathematical model of Brownian motion has several real-world applications...

, the physical phenomenon of a minute particle diffusing in a fluid. (Sometimes the Wiener process
Wiener process
In mathematics, the Wiener process is a continuous-time stochastic process named in honor of Norbert Wiener. It is often called standard Brownian motion, after Robert Brown...

 is called "Brownian motion", although this is strictly speaking a confusion of a model with the phenomenon being modeled.)

A Wiener process is the scaling limit
Scaling limit
In physics or mathematics, the scaling limit is a term applied to the behaviour of a lattice model in the limit of the lattice spacing going to zero. A lattice model which approximates a continuum quantum field theory in the limit as the lattice spacing goes to zero corresponds to finding a second...

 of random walk in dimension 1. This means that if you take a random walk with very small steps you get an approximation to a Wiener process (and, less accurately, to Brownian motion). To be more precise, if the step size is ε, one needs to take a walk of length L2 to approximate a Wiener process walk of length L. As the step size tends to 0 (and the number of steps increases proportionally) random walk converges to a Wiener process 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, a Wiener process in several dimensions is the scaling limit of random walk in the same number of dimensions.

A random walk is a discrete fractal
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...

 (a function with integer dimensions; 1, 2, ...), but a Wiener process trajectory 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 r2. This fact is the discrete version of the fact that a Wiener process walk is a fractal of Hausdorff dimension
Hausdorff dimension
thumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...

 2
.
In two dimensions, the average number of points the same random walk has on the boundary of its trajectory is r4/3. This corresponds to the fact that the boundary of the trajectory of a Wiener process is a fractal of dimension 4/3, a fact predicted by Mandelbrot
Benoît Mandelbrot
Benoît B. Mandelbrot was a French American mathematician. Born in Poland, he moved to France with his family when he was a child...

 using simulations but proved only in 2000
by Lawler
Greg Lawler
Gregory Francis Lawler is an American mathematician working in probability theory and best known for his work since 2000 on the Schramm-Loewner evolution.He received his Ph.D. from Princeton in 1979 under the supervision of Edward Nelson...

, Schramm
Oded Schramm
Oded Schramm was an Israeli-American mathematician known for the invention of the Schramm–Loewner evolution and for working at the intersection of conformal field theory and probability theory.-Biography:...

 and Werner
Wendelin Werner
Wendelin Werner is a German-born French mathematician working in the area of self-avoiding random walks, Schramm-Loewner evolution, and related theories in probability theory and mathematical physics. In 2006, at the 25th International Congress of Mathematicians in Madrid, Spain he received the...

 .

A Wiener process enjoys many symmetries
Symmetry
Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...

 random walk does not. For example, a Wiener process walk 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 Wiener processes are 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 a Wiener process, 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.

Random walk and Wiener process
Wiener process
In mathematics, the Wiener process is a continuous-time stochastic process named in honor of Norbert Wiener. It is often called standard Brownian motion, after Robert Brown...

 can be coupled
Coupling (probability)
In probability theory, coupling is a proof technique that allows one to compare two unrelated variables by "forcing" them to be related in some way.-Definition:...

, 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.

The convergence of a random walk toward the Wiener process is controlled by the central limit theorem
Central limit theorem
In probability theory, the central limit theorem states conditions under which the mean of a sufficiently large number of independent random variables, each with finite mean and variance, will be approximately normally distributed. The central limit theorem has a number of variants. In its common...

. For a particle in a known fixed position at t = 0, the theorem tells us that after a large number of independent
Statistical independence
In probability theory, to say that two events are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other occurs...

 steps in the random walk, the walker's position is distributed according to a normal distribution of total variance
Variance
In probability theory and statistics, the variance is a measure of how far a set of numbers is spread out. It is one of several descriptors of a probability distribution, describing how far the numbers lie from the mean . In particular, the variance is one of the moments of a distribution...

:


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

This corresponds to the Green function
Green's function
In mathematics, a Green's function is a type of function used to solve inhomogeneous differential equations subject to specific initial conditions or boundary conditions...

 of the diffusion equation that controls the Wiener process, which demonstrates that, after a large number of steps, the random walk converges toward a Wiener process.

In 3D, the variance corresponding to the Green's function
Green's function
In mathematics, a Green's function is a type of function used to solve inhomogeneous differential equations subject to specific initial conditions or boundary conditions...

 of the diffusion equation is:


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 Wiener process 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 , or is only one third of this value (still in 3D).

Anomalous Diffusion
Anomalous Diffusion
Anomalous diffusion is a term used to describe a diffusion process with a non-linear relationship to time, in contrast to a typical diffusion process, in which the mean squared displacement , σr2, of a particle is a linear function of time....


In disordered systems such as porous media and fractals may not be proportional to but to . The exponent is called the anomalous diffusion
Anomalous Diffusion
Anomalous diffusion is a term used to describe a diffusion process with a non-linear relationship to time, in contrast to a typical diffusion process, in which the mean squared displacement , σr2, of a particle is a linear function of time....

 exponent and can be larger or smaller than 2.

Applications




The following are some applications of random walk:
  • In economics
    Economics
    Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...

    , the "random walk hypothesis
    Random walk hypothesis
    The random walk hypothesis is a financial theory stating that stock market prices evolve according to a random walk and thus the prices of the stock market cannot be predicted. It is consistent with the efficient-market 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 price
    Share price
    A share price is the price of a single share of a number of saleable stocks of a company. Once the stock is purchased, the owner becomes a shareholder of the company that issued the share.-Behavior of share prices:...

    s.
  • In population genetics
    Population genetics
    Population genetics is the study of allele frequency distribution and change under the influence of the four main evolutionary processes: natural selection, genetic drift, mutation and gene flow. It also takes into account the factors of recombination, population subdivision and population...

    , random walk describes the statistical properties of genetic drift
    Genetic drift
    Genetic drift or allelic drift is the change in the frequency of a gene variant in a population due to random sampling.The alleles in the offspring are a sample of those in the parents, and chance has a role in determining whether a given individual survives and reproduces...

  • In physics
    Physics
    Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...

    , random walks are used as simplified models of physical Brownian motion
    Brownian motion
    Brownian motion or pedesis is the presumably random drifting of particles suspended in a fluid or the mathematical model used to describe such random movements, which is often called a particle theory.The mathematical model of Brownian motion has several real-world applications...

     and diffusion such as the random movement
    Motion (physics)
    In physics, motion is a change in position of an object with respect to time. Change in action is the result of an unbalanced force. Motion is typically described in terms of velocity, acceleration, displacement and time . An object's velocity cannot change unless it is acted upon by a force, as...

     of molecules in liquids and gases. See for example diffusion-limited aggregation
    Diffusion-limited aggregation
    Diffusion-limited aggregation is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. This theory, proposed by Witten and Sander in 1981, is applicable to aggregation in any system where diffusion is the primary means...

    . Also in physics, random walks and some of the self interacting walks play a role in quantum field theory
    Quantum field theory
    Quantum field theory provides a theoretical framework for constructing quantum mechanical models of systems classically parametrized by an infinite number of dynamical degrees of freedom, that is, fields and many-body systems. It is the natural and quantitative language of particle physics and...

    .
  • In mathematical ecology, random walks are used to describe individual animal movements, to empirically support processes of biodiffusion
    Diffusion
    Molecular diffusion, often called simply diffusion, is the thermal motion of all particles at temperatures above absolute zero. The rate of this movement is a function of temperature, viscosity of the fluid and the size of the particles...

    , and occasionally to model population dynamics
    Population dynamics
    Population dynamics is the branch of life sciences that studies short-term and long-term changes in the size and age composition of populations, and the biological and environmental processes influencing those changes...

    .
  • In polymer physics
    Polymer physics
    Polymer physics is the field of physics that studies polymers, their fluctuations, mechanical properties, as well as the kinetics of reactions involving degradation and polymerisation of polymers and monomers respectively....

    , random walk describes an ideal chain
    Ideal chain
    An ideal chain is the simplest model to describe a polymer. It only assumes a polymer as a random walk and neglects any kind of interactions among monomers...

    . It is the simplest model to study polymers.
  • In other fields of mathematics, random walk is used to calculate solutions to Laplace's equation
    Laplace's equation
    In mathematics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace who first studied its properties. This is often written as:where ∆ = ∇² is the Laplace operator and \varphi is a scalar function...

    , to estimate the harmonic measure
    Harmonic measure
    In mathematics, especially potential theory, harmonic measure is a concept related to the theory of harmonic functions that arises from the solution of the classical Dirichlet problem. In probability theory, harmonic measure of a bounded domain in Euclidean space R^n, n\geq 2 is the probability...

    , and for various constructions in analysis
    Mathematical analysis
    Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...

     and combinatorics
    Combinatorics
    Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

    .
  • In computer science
    Computer science
    Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

    , 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.
  • In image segmentation
    Segmentation (image processing)
    In computer vision, segmentation refers to the process of partitioning a digital image into multiple segments . The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze...

    , random walks are used to determine the labels (i.e., "object" or "background") to associate with each pixel. This algorithm is typically referred to as the random walker
    Random Walker (Computer Vision)
    The random walker algorithm is an algorithm for image segmentation. In the first description of the algorithm, a user interactively labels a small number of pixels with known labels , e.g., "object" and "background"...

     segmentation algorithm.

In all these cases, random walk is often substituted for Brownian motion.
  • In brain research
    Human brain
    The human brain has the same general structure as the brains of other mammals, but is over three times larger than the brain of a typical mammal with an equivalent body size. Estimates for the number of neurons in the human brain range from 80 to 120 billion...

    , 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
    Psychology
    Psychology is the study of the mind and behavior. Its immediate goal is to understand individuals and groups by both establishing general principles and researching specific cases. For many, the ultimate goal of psychology is to benefit society...

    , random walks explain accurately the relation between the time needed to make a decision and the probability that a certain decision will be made. (Nosofsky, 1997)
  • 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 worker in a given country.
  • When this last approach is used in computer science
    Computer science
    Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

     it is known as Markov Chain Monte Carlo
    Markov chain Monte Carlo
    Markov chain 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 equilibrium distribution. The state of the chain after a large number of steps is then used as a sample of the...

     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
    Permanent
    The permanent of a square matrix in linear algebra, is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix...

     of a large matrix
    Matrix (mathematics)
    In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

     of zeros and ones was the first major problem tackled using this approach.
  • In wireless networking, random walk is used to model node movement.
  • Motile bacteria engage in a biased random walk
    Biased random walk (biochemistry)
    In cell biology, a biased random walk enables bacteria to search for food and flee from harm. Bacteria propel themselves with the aid of flagella in a process called chemotaxis, and a typical bacteria trajectory has many characteristics of a random walk. They move forward for a certain distance,...

    .
  • Random walk is used to model gambling
    Gambling
    Gambling is the wagering of money or something of material value on an event with an uncertain outcome with the primary intent of winning additional money and/or material goods...

    .
  • In physics, random walks underlying the method of Fermi estimation.

Variants of random walks


A number of types of stochastic process
Stochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...

es have been considered that are similar to the pure random walks but where the simple structure is allowed to be more generalized. The pure structure can be characterized by the steps being being defined by independent and identically distributed random variables
Independent and identically distributed random variables
In probability theory and statistics, a sequence or other collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent....

.

Random walk on graphs


A random walk of length k on a possibly infinite graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 G with a root 0 is a stochastic process with random variables such that and
is a vertex chosen uniformly at random from the neighbors of .
Then the number is the probability that a random walk of length k starting at v ends at w.
In particular, if G is a graph with root 0, is the probability that a -step random walk returns to 0.

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
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

, 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
Electrical resistance
The electrical resistance of an electrical element is the opposition to the passage of an electric current through that element; the inverse quantity is electrical conductance, the ease at which an electric current passes. Electrical resistance shares some conceptual parallels with the mechanical...

 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 (an elementary proof can be found in the book by Doyle and Snell):

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 if the graph is connected.

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
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...

. 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
Detailed balance
The principle of detailed balance is formulated for kinetic systems which are decomposed into elementary processes : At equilibrium, each elementary process should be equilibrated by its reverse process....

, 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
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

, they are just equal). This property has important consequences.

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
Isoperimetry
The isoperimetric inequality is a geometric inequality involving the square of the circumference of a closed curve in the plane and the area of a plane region it encloses, as well as its various generalizations. Isoperimetric literally means "having the same perimeter"...

, see more here, functional inequalities such as Sobolev
Sobolev inequality
In mathematics, there is in mathematical analysis a class of Sobolev inequalities, relating norms including those of Sobolev spaces. These are used to prove the Sobolev embedding theorem, giving inclusions between certain Sobolev spaces, and the Rellich–Kondrachov theorem showing that under...

 and Poincaré
Poincaré inequality
In mathematics, the Poincaré inequality is a result in the theory of Sobolev spaces, named after the French mathematician Henri Poincaré. The inequality allows one to obtain bounds on a function using bounds on its derivatives and the geometry of its domain of definition. Such bounds are of great...

 inequalities and properties of solutions of Laplace's equation
Laplace's equation
In mathematics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace who first studied its properties. This is often written as:where ∆ = ∇² is the Laplace operator and \varphi is a scalar function...

. A significant portion of this research was focused on Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...

s of finitely generated
Glossary of group theory
A group is a set G closed under a binary operation • satisfying the following 3 axioms:* Associativity: For all a, b and c in G, • c = a • ....

 groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

. For example, the proof of Dave Bayer
Dave Bayer
Dave Bayer is an American mathematician. He is currently a professor of mathematics at Barnard College, Columbia University. He was math consultant for the film A Beautiful Mind, and also acted in it as one of the "Pen Ceremony" professors. He is also one of few people to have both an Erdős number...

 and Persi Diaconis
Persi Diaconis
Persi Warren Diaconis is an American mathematician and former professional magician. He is the Mary V. Sunseri Professor of Statistics and Mathematics at Stanford University....

 that 7 riffle shuffles
Shuffle
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.-Shuffling techniques:...

 are enough to mix a pack of cards (see more details under shuffle
Shuffle
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.-Shuffling techniques:...

) is in effect a result about random walk on the group Sn
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...

, and the proof uses the group structure in an essential way. In many cases these discrete results carry over to, or are derived from Manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....

s and Lie group
Lie group
In mathematics, a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure...

s.

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 transition kernel is itself random (based on an environment ) then the random walk is called a "random walk in random environment". When the law of the random walk includes the randomness of , the law is called the annealed law; on the other hand, if is seen as fixed, the law is called a quenched law. See the book of Hughes or the lecture notes of Zeitouni.

We can think about choosing every possible edge with the same probability as maximizing uncertainty (entropy) locally. We could also do it globally – in maximal entropy random walk (MERW) we want all paths to be equally probable, or in other words: for each two vertexes, each path of given length is equally probable. This random walk has much stronger localization properties.

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 complex for solving analytically than the usual random walk; still, the behavior of any model of a random walker is obtainable using computer. Examples include:
  • The self-avoiding walk
    Self-avoiding walk
    In mathematics, a self-avoiding walk is a sequence of moves on a lattice that does not visit the same point more than once. A self-avoiding polygon is a closed self-avoiding walk on a lattice...

     (Madras and Slade 1996). Here, the random walk is taking place in a discrete system, and it is like a real chain that extends its length each jump, and so when a jump is attempted for a site that is taken, it is rejected. This model is also used frequently in polymer physics
    Polymer physics
    Polymer physics is the field of physics that studies polymers, their fluctuations, mechanical properties, as well as the kinetics of reactions involving degradation and polymerisation of polymers and monomers respectively....

     (since 60s).
  • The loop-erased random walk
    Loop-erased random walk
    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. It is intimately connected to the uniform spanning tree, a model for a random tree...

     (Gregory Lawler).
  • The reinforced random walk (Robin Pemantle 2007).
  • The exploration process.
  • The multiagent random walk.


Correlated Steps


The above descriptions assume that the steps in the random walk are independent.
A variant of the model allows for correlated steps.
This results in more steps being taken in either direction, and leads to larger displacements from the origin.
Specifically, when the steps are independent, the expected displacement after steps is .
If the steps are long-range dependent
Long-range dependency
Long-range dependency is a phenomenon that may arise in the analysis of spatial or time series data. It relates to the rate of decay of statistical dependence, with the implication that this decays more slowly than an exponential decay, typically a power-like decay...

 (called also long-range correlated), however, the expected displacement becomes for .
is the Hurst parameter (called also Hurst exponent).

Long range correlated time series is found in many biological, climatological and economic systems, including heartbeat, temperature records and volatility of stocks.

Long range correlated walks


Long range correlated time series are found in many biological, climatological and economic systems.
  • Heartbeat records
  • Non-coding DNA sequences
  • Volatility time series of stocks
  • Temperature records around the globe

Heterogeneous random walks in one dimension



Heterogeneous random walks in one dimension can have either discrete time or continuous time. The interval is also either discrete or continuous, and it is either finite or without bounds. In a discrete system, the movements are between adjacent states. The dynamics are either Markovian
Markov process
In probability theory and statistics, a Markov process, named after the Russian mathematician Andrey Markov, is a time-varying random phenomenon for which a specific property holds...

, Semi-Markovian
Semi-Markov process
A continuous-time stochastic process is called a semi-Markov process or 'Markov renewal process' if the embedded jump chain is a Markov chain, and where the holding times are random variables with any distribution, whose distribution function may depend on the two states between which the move is...

, or even not-Markovian depending on the model. Heterogeneous random walks in 1D have jump probabilities that depend on the location in the system, and/or different jumping time probability density functions (PDFs) that depend on the location in the system.

See also

  • Branching random walk
    Branching random walk
    In probability theory, a branching random walk is a stochastic process that generalizes both the concept of random walk and of branching process. At every generation , a branching random walk's value is a set of elements that are located in some linear space, such as the real line...

  • Brownian motion
    Brownian motion
    Brownian motion or pedesis is the presumably random drifting of particles suspended in a fluid or the mathematical model used to describe such random movements, which is often called a particle theory.The mathematical model of Brownian motion has several real-world applications...

  • Law of the iterated logarithm
    Law of the iterated logarithm
    In probability theory, the law of the iterated logarithm describes the magnitude of the fluctuations of a random walk. The original statement of the law of the iterated logarithm is due to A. Y. Khinchin . Another statement was given by A.N...

  • Loop-erased random walk
    Loop-erased random walk
    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. It is intimately connected to the uniform spanning tree, a model for a random tree...

  • Self avoiding walk

External links