Random walk - AbsoluteAstronomy.com

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

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 2ⁿ. For the simple random walk, each of these walks are equally likely. In order for S_n 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.

−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

whose state space is given by the integers

For some number p satisying

, the transition probabilities (the probability P_i,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 L/ε² 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 r². 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 r^4/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

. 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

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

. 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

) is in effect a result about random walk on the group S_n

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.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Lattice random walk

One-dimensional random walk

Derivation of dispersion proportionality

As a Markov chain

Gaussian random walk

Higher dimensions

Relation to Wiener process

Anomalous DiffusionAnomalous DiffusionAnomalous 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....

Applications

Variants of random walks

Random walk on graphs

Self-interacting random walks

Correlated Steps

Long range correlated walks

Heterogeneous random walks in one dimension

See also

External links

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