HOME

TheInfoList



OR:

In mathematics, a random walk is a
random process In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables. Stochastic processes are widely used as mathematical models of systems and phenomena that appe ...
that describes a path that consists of a succession of
random In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...
steps on some
mathematical space In mathematics, a space is a set (sometimes called a universe) with some added structure. While modern mathematics uses many types of spaces, such as Euclidean spaces, linear spaces, topological spaces, Hilbert spaces, or probability spaces ...
. An elementary example of a random walk is the random walk on the integer number line \mathbb Z which starts at 0, and at each step moves +1 or −1 with equal probability. Other examples include the path traced by a molecule as it travels in a liquid or a gas (see
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position ins ...
), the search path of a foraging animal, or the price of a fluctuating stock and the financial status of a gambler. Random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry,
biology Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary ...
, economics, and sociology. The term ''random walk'' was first introduced by Karl Pearson in 1905.


Lattice random walk

A popular random walk model is that of a random walk on a regular lattice, where at each step the location jumps to another site according to some probability distribution. In a ''simple random walk'', the location can only jump to neighboring sites of the lattice, forming a lattice path. In a ''simple symmetric random walk'' on a locally finite lattice, the probabilities of the location jumping to each one of its immediate neighbors are the same. The best-studied example is the random walk on the ''d''-dimensional integer lattice (sometimes called the hypercubic lattice) \mathbb Z^d. If the state space is limited to finite dimensions, the random walk model is called a ''simple bordered symmetric random walk'', and the transition probabilities depend on the location of the state because on margin and corner states the movement is limited.


One-dimensional random walk

An elementary example of a random walk is the random walk on the integer number line, \Z, 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, the marker could now be on -5, -3, -1, 1, 3, 5. With five flips, three heads and two tails, in any order, it will land on 1. There are 10 ways of landing on 1 (by flipping three heads and two tails), 10 ways of landing on −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 Z_1, Z_2,\dots, where each variable is either 1 or −1, with a 50% probability for either value, and set S_0 = 0 and S_n = \sum_^n Z_j. The
series Series may refer to: People with the name * Caroline Series (born 1951), English mathematician, daughter of George Series * George Series (1920–1995), English physicist Arts, entertainment, and media Music * Series, the ordered sets used in ...
\ is called the ''simple random walk on \Z''. This series (the sum of the sequence of −1s and 1s) gives the net distance walked, if each part of the walk is of length one. The expectation E(S_n) of S_n is zero. That is, the mean of all coin flips approaches zero as the number of flips increases. This follows by the finite additivity property of expectation: E(S_n)=\sum_^n E(Z_j)=0. A similar calculation, using the independence of the random variables and the fact that E(Z_n^2)=1, shows that: E(S_n^2)=\sum_^n E(Z_i^2)+2\sum_E(Z_i Z_j)=n. This hints that E(, S_n, )\,\!, the expected translation distance after ''n'' steps, should be of the order of \sqrt n. In fact, \lim_ \frac= \sqrt. This result shows that diffusion is ineffective for mixing because of the way the square root behaves for large N. To answer the question of how many times will a random walk cross a boundary line if permitted to continue walking forever, a simple random walk on \mathbb Z 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 eventually 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 a/(a+b), which can be derived from the fact that simple random walk is a martingale. And these expectations and hitting probabilities can be computed in O(a+b) in the general one-dimensional random walk Markov chain. Some of the results mentioned above can be derived from properties of
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ...
. The number of different walks of ''n'' steps where each step is +1 or −1 is 2''n''. For the simple random walk, each of these walks is 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''. It follows +1 must appear (''n'' + ''k'')/2 times among ''n'' steps of a walk, hence the number of walks which satisfy S_n=k equals the number of ways of choosing (''n'' + ''k'')/2 elements from an ''n'' element set, denoted n \choose (n+k)/2. For this to have meaning, it is necessary that ''n'' + ''k'' be an even number, which implies ''n'' and ''k'' are either both even or both odd. Therefore, the probability that S_n=k is equal to 2^. By representing entries of Pascal's triangle in terms of
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) ...
s and using
Stirling's formula In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of n. It is named after James Stirling, though a related but less p ...
, one can obtain good estimates for these probabilities for large values of n. If space is confined to \mathbb Z+ for brevity, the number of ways in which a random walk will land on any given number having five flips can be shown as . 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. The
central limit theorem In probability theory, the central limit theorem (CLT) establishes that, in many situations, when independent random variables are summed up, their properly normalized sum tends toward a normal distribution even if the original variables themselv ...
and the law of the iterated logarithm describe important aspects of the behavior of simple random walks on \mathbb Z. In particular, the former entails that as ''n'' increases, the probabilities (proportional to the numbers in each row) approach a
normal distribution In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is : f(x) = \frac e^ The parameter \mu i ...
. As a direct generalization, one can consider random walks on crystal lattices (infinite-fold abelian covering graphs over finite graphs). Actually it is possible to establish the central limit theorem and large deviation theorem in this setting.


As a Markov chain

A one-dimensional ''random walk'' can also be looked at as a Markov chain whose state space is given by the integers i=0,\pm 1,\pm 2,\dots . For some number ''p'' satisfying \,0 < p < 1, the transition probabilities (the probability ''Pi,j'' of moving from state ''i'' to state ''j'') are given by \,P_=p=1-P_.


Heterogeneous generalization


Higher dimensions

In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discrete
fractal In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as il ...
, that is, a set which exhibits stochastic self-similarity on large scales. On small scales, one can observe "jaggedness" resulting from the grid on which the walk is performed. The trajectory of a random walk is the collection of points 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 and the maximum height the walk achieved (both are, on average, on the order of \sqrt ). To visualize the two-dimensional case, one can imagine a person walking randomly around a city. The city is effectively infinite and arranged in a square grid of sidewalks. At every intersection, the person randomly chooses one of the four possible routes (including the one originally travelled from). Formally, this is a random walk on the set of all points in the
plane Plane(s) most often refers to: * Aero- or airplane, a powered, fixed-wing aircraft * Plane (geometry), a flat, 2-dimensional surface Plane or planes may also refer to: Biology * Plane (tree) or ''Platanus'', wetland native plant * ''Planes' ...
with integer
coordinates In geometry, a coordinate system is a system that uses one or more numbers, or coordinates, to uniquely determine the position of the points or other geometric elements on a manifold such as Euclidean space. The order of the coordinates is sign ...
. To answer the question of the person ever getting back to the original starting point of the walk, this is the 2-dimensional equivalent of the level-crossing problem discussed above. In 1921 George Pólya proved that the person
almost surely In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
would in a 2-dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%. The mathematician Shizuo Kakutani was known to refer to this result with the following quote: "A drunk man will find his way home, but a drunk bird may get lost forever". Another variation of this question which was also asked by Pólya is: "if two people leave the same starting point, then will they ever meet again?" It can be shown that the difference between their locations (two independent random walks) is also a simple random walk, so they almost surely meet again in a 2-dimensional walk, but for 3 dimensions and higher the probability decreases with the number of the dimensions. Paul Erdős and Samuel James Taylor also showed in 1960 that for dimensions less or equal than 4, two independent random walks starting from any two given points have infinitely many intersections almost surely, but for dimensions higher than 5, they almost surely intersect only finitely often. The asymptotic function for a two-dimensional random walk as the number of steps increases is given by a Rayleigh distribution. The probability distribution is a function of the radius from the origin and the step length is constant for each step. P(r) = \frac e^


Relation to Wiener process

A Wiener process is a stochastic process with similar behavior to
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position ins ...
, the physical phenomenon of a minute particle diffusing in a fluid. (Sometimes the Wiener process 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 In mathematical physics and mathematics, the continuum limit or scaling limit of a lattice model refers to its behaviour in the limit as the lattice spacing goes to zero. It is often useful to use lattice models to approximate real-world process ...
of random walk in dimension 1. This means that if there is a random walk with very small steps, there is 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''/ε2 to approximate a Wiener length of ''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 (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''2. This fact is the ''discrete version'' of the fact that a Wiener process walk is a fractal of
Hausdorff dimension In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of ...
 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 using simulations but proved only in 2000 by Lawler, Schramm and Werner. A Wiener process enjoys many
symmetries Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
a random walk does not. For example, a Wiener process walk is invariant to rotations, but the 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 a 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 can be ''coupled'', namely manifested on the same probability space in a dependent way that forces them to be quite close. The simplest such coupling is the Skorokhod embedding, but there exist more precise couplings, such as
Komlós–Major–Tusnády approximation In probability theory, the Komlós–Major–Tusnády approximation (also known as the KMT approximation, the KMT embedding, or the Hungarian embedding) refers to one of the two strong embedding theorems: 1) approximation of random walk by a standar ...
theorem. The convergence of a random walk toward the Wiener process is controlled by the
central limit theorem In probability theory, the central limit theorem (CLT) establishes that, in many situations, when independent random variables are summed up, their properly normalized sum tends toward a normal distribution even if the original variables themselv ...
, and by Donsker's theorem. For a particle in a known fixed position at ''t'' = 0, the central limit theorem tells us that after a large number of independent steps in the random walk, the walker's position is distributed according to a
normal distribution In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is : f(x) = \frac e^ The parameter \mu i ...
of total variance: \sigma^2 = \frac\,\varepsilon^2, where ''t'' is the time elapsed since the start of the random walk, \varepsilon is the size of a step of the random walk, and \delta t is the time elapsed between two successive steps. This corresponds to the
Green's function In mathematics, a Green's function is the impulse response of an inhomogeneous linear differential operator defined on a domain with specified initial conditions or boundary conditions. This means that if \operatorname is the linear differentia ...
of the diffusion equation that controls the Wiener process, which suggests 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 In mathematics, a Green's function is the impulse response of an inhomogeneous linear differential operator defined on a domain with specified initial conditions or boundary conditions. This means that if \operatorname is the linear differentia ...
of the diffusion equation is: \sigma^2 = 6\,D\,t. 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: D = \frac (valid only in 3D). The two expressions of the variance above correspond to the distribution associated to the vector \vec R that links the two ends of the random walk, in 3D. The variance associated to each component R_x, R_y or R_z is only one third of this value (still in 3D). For 2D: D = \frac. For 1D: D = \frac.


Gaussian random walk

A random walk having a step size that varies according to a
normal distribution In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is : f(x) = \frac e^ The parameter \mu i ...
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 \Phi^(z,\mu,\sigma) where 0 ≤ ''z'' ≤ 1 is a uniformly distributed random number, and μ and σ are the mean and standard deviations of the normal distribution, respectively. If μ is nonzero, the random walk will vary about a linear trend. If vs is the starting value of the random walk, the expected value after ''n'' steps will be vs + ''n''μ. For the special case where μ is equal to zero, after ''n'' steps, the translation distance's probability distribution is given by ''N''(0, ''n''σ2), where ''N''() is the notation for the normal distribution, ''n'' is the number of steps, and σ is from the inverse cumulative normal distribution as given above. Proof: The Gaussian random walk can be thought of as the sum of a sequence of independent and identically distributed random variables, Xi from the inverse cumulative normal distribution with mean equal zero and σ of the original inverse cumulative normal distribution: :Z = \sum_^n , but we have the distribution for the sum of two independent normally distributed random variables, , is given by \mathcal(\mu_X + \mu_Y, \sigma_X^2 + \sigma_Y^2) (see here). In our case, and yield \mathcal(0, 2\sigma^2) By induction, for ''n'' steps we have Z \sim \mathcal(0, n \sigma^2). For steps distributed according to any distribution with zero mean and a finite variance (not necessarily just a normal distribution), the
root mean square In mathematics and its applications, the root mean square of a set of numbers x_i (abbreviated as RMS, or rms and denoted in formulas as either x_\mathrm or \mathrm_x) is defined as the square root of the mean square (the arithmetic mean of the ...
translation distance after ''n'' steps is (see Bienaymé's identity) :\sqrt = \sqrt = \sigma \sqrt. But for the Gaussian random walk, this is just the standard deviation of the translation distance's distribution after ''n'' steps. Hence, if μ is equal to zero, and since the root mean square(RMS) translation distance is one standard deviation, there is 68.27% probability that the RMS translation distance after ''n'' steps will fall between \pm \sigma \sqrt. Likewise, there is 50% probability that the translation distance after ''n'' steps will fall between \pm 0.6745 \sigma \sqrt.


Number of distinct sites

The number of distinct sites visited by a single random walker S(t) has been studied extensively for square and cubic lattices and for fractals. This quantity is useful for the analysis of problems of trapping and kinetic reactions. It is also related to the vibrational density of states, diffusion reactions processes and spread of populations in ecology.


Information rate

The
information rate In telecommunications and computing, bit rate (bitrate or as a variable ''R'') is the number of bits that are conveyed or processed per unit of time. The bit rate is expressed in the unit bit per second (symbol: bit/s), often in conjunction ...
of a Gaussian random walk with respect to the squared error distance, i.e. its quadratic rate distortion function, is given parametrically by R(D_\theta) = \frac \int_0^1 \max\ \, d\varphi, D_\theta = \int_0^1 \min\ \, d\varphi, where S(\varphi) = \left(2 \sin (\pi \varphi/2) \right)^. Therefore, it is impossible to encode using a
binary code A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, also ...
of less than NR(D_\theta)
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented ...
s and recover it with expected mean squared error less than D_\theta. On the other hand, for any \varepsilon>0, there exists an N \in \mathbb N large enough and a
binary code A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, also ...
of no more than 2^ distinct elements such that the expected mean squared error in recovering from this code is at most D_\theta - \varepsilon.


Applications

As mentioned the range of natural phenomena which have been subject to attempts at description by some flavour of random walks is considerable, particularly in physicsRisken H. (1984) ''The Fokker–Planck Equation''. Springer, Berlin.cDe Gennes P. G. (1979) ''Scaling Concepts in Polymer Physics''. Cornell University Press, Ithaca and London. and chemistry,Van Kampen N. G. (1992) ''Stochastic Processes in Physics and Chemistry'', revised and enlarged edition. North-Holland, Amsterdam. materials science,Doi M. and Edwards S. F. (1986) ''The Theory of Polymer Dynamics''. Clarendon Press, Oxford and biology.Goel N. W. and Richter-Dyn N. (1974) ''Stochastic Models in Biology''. Academic Press, New York. Redner S. (2001) ''A Guide to First-Passage Process''. Cambridge University Press, Cambridge, UK.Cox D. R. (1962) ''Renewal Theory''. Methuen, London. The following are some specific applications of random walks: *In
financial economics Financial economics, also known as finance, is the branch of economics characterized by a "concentration on monetary activities", in which "money of one type or another is likely to appear on ''both sides'' of a trade". William F. Sharpe"Financi ...
, the random walk hypothesis is used to model shares prices and other factors. Empirical studies found some deviations from this theoretical model, especially in short term and long term correlations. See share prices. *In
population genetics Population genetics is a subfield of genetics that deals with genetic differences within and between populations, and is a part of evolutionary biology. Studies in this branch of biology examine such phenomena as adaptation, speciation, and pop ...
, random walk describes the statistical properties of genetic drift *In physics, random walks are used as simplified models of physical Brownian motion and diffusion such as the
random In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...
movement Movement may refer to: Common uses * Movement (clockwork), the internal mechanism of a timepiece * Motion, commonly referred to as movement Arts, entertainment, and media Literature * "Movement" (short story), a short story by Nancy Fu ...
of
molecules A molecule is a group of two or more atoms held together by attractive forces known as chemical bonds; depending on context, the term may or may not include ions which satisfy this criterion. In quantum physics, organic chemistry, and bioche ...
in liquids and gases. See for example diffusion-limited aggregation. Also in physics, random walks and some of the self interacting walks play a role in quantum field theory. *In mathematical ecology, random walks are used to describe individual animal movements, to empirically support processes of biodiffusion, and occasionally to model population dynamics. *In
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.P. Flory, ''Principles of ...
, random walk describes an
ideal chain Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...
. It is the simplest model to study polymers. *In other fields of mathematics, random walk is used to calculate solutions to
Laplace's equation In mathematics and physics, 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 \nabla^2\! f = 0 or \Delta f = 0, where \Delta = \na ...
, to estimate the
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, the harmonic measure of a subset of the ...
, and for various constructions in
analysis Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (3 ...
and combinatorics. * In computer science, random walks are used to estimate the size of the
Web Web most often refers to: * Spider web, a silken structure created by the animal * World Wide Web or the Web, an Internet-based hypertext system Web, WEB, or the Web may also refer to: Computing * WEB, a literate programming system created by ...
. * In image segmentation, 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 segmentation algorithm. *In
brain research ''Brain Research'' is a peer-reviewed scientific journal focusing on several aspects of neuroscience. It publishes research reports and " minireviews". The editor-in-chief is Matthew J. LaVoie (University of Florida). Until 2011, full reviews were ...
, random walks and reinforced random walks are used to model cascades of neuron firing in the brain. *In
vision science Vision science is the scientific study of visual perception. Researchers in vision science can be called vision scientists, especially if their research spans some of the science's many disciplines. Vision science encompasses all studies of visio ...
, ocular drift tends to behave like a random walk. According to some authors,
fixational eye movements Fixation or visual fixation is the maintaining of the gaze on a single location. An animal can exhibit visual fixation if it possess a fovea in the anatomy of their eye. The fovea is typically located at the center of the retina and is the poin ...
in general are also well described by a random walk. *In psychology, random walks explain accurately the relation between the time needed to make a decision and the probability that a certain decision will be made. *Random walks 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. In computer science, this method is known as Markov Chain Monte Carlo (MCMC). *In
wireless networking A wireless network is a computer network that uses wireless data connections between network nodes. Wireless networking is a method by which homes, telecommunications networks and business installations avoid the costly process of introducing c ...
, a random walk is used to model node movement. * Motile bacteria engage in a biased random walks. *In physics, random walks underlie the method of Fermi estimation. *On the web, the Twitter website uses random walks to make suggestions of whom to followGupta, Pankaj et al
WTF: The who-to-follow system at Twitter
Proceedings of the 22nd international conference on World Wide Web
* Dave Bayer and Persi Diaconis have proven that 7 riffle shuffles are enough to mix a pack of cards (see more details under shuffle). This result translates to a statement about random walk on the symmetric group which is what they prove, with a crucial use of the group structure via Fourier analysis.


Variants

A number of types of
stochastic process In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables. Stochastic processes are widely used as mathematical models of systems and phenomena that appea ...
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 defined by independent and identically distributed random variables. Random walks can take place on a variety of spaces, such as graphs, the integers, the real line, the plane or higher-dimensional vector spaces, on curved surfaces or higher-dimensional Riemannian manifolds, and on
groups A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
. It is also possible to define random walks which take their steps at random times, and in that case, the position has to be defined for all times . Specific cases or limits of random walks include the
Lévy flight A Lévy flight is a random walk in which the step-lengths have a Lévy distribution, 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 directi ...
and diffusion models such as
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position ins ...
.


On graphs

A random walk of length ''k'' on a possibly infinite graph ''G'' with a root ''0'' is a stochastic process with random variables X_1,X_2,\dots,X_k such that X_1=0 and is a vertex chosen uniformly at random from the neighbors of X_i. Then the number p_(G) 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'', p_ is the probability that a 2k-step random walk returns to ''0''. Building on the analogy from the earlier section on higher dimensions, assume now that our city is no longer a perfect square grid. When our person reaches a certain junction, he picks between the variously available roads with equal probability. Thus, if the junction has seven exits the person will go to each one with probability one-seventh. This is a random walk on a graph. Will our person reach his home? It turns out that under rather mild conditions, the answer is still yes, but depending on the graph, the answer to the variant question 'Will two persons meet again?' may not be that they meet infinitely often almost surely. An example of a case where the person will reach his home almost surely is when the lengths of all the blocks are between ''a'' and ''b'' (where ''a'' and ''b'' are any two finite positive numbers). Notice that we do not assume that the graph is
planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...
, 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 Ohm (symbol Ω) is a unit of electrical resistance named after Georg Ohm. Ohm or OHM may also refer to: People * Georg Ohm (1789–1854), German physicist and namesake of the term ''ohm'' * Germán Ohm (born 1936), Mexican boxer * Jörg Ohm (bor ...
resistor A resistor is a passive two-terminal electrical component that implements electrical resistance as a circuit element. In electronic circuits, resistors are used to reduce current flow, adjust signal levels, to divide voltages, bias active ...
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 transience and recurrence is very useful, and specifically it allows us to analyze the case of a city drawn in the plane with the distances bounded. A random walk on a graph is a very special case of a Markov chain. Unlike a general Markov chain, random walk on a graph enjoys a property called ''time symmetry'' or ''reversibility''. Roughly speaking, this property, also called the principle of detailed balance, means that the probabilities to traverse a given path in one direction or the other have a very simple connection between them (if the graph is regular, 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, see more
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a ...
, functional inequalities such as Sobolev and Poincaré inequalities and properties of solutions of
Laplace's equation In mathematics and physics, 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 \nabla^2\! f = 0 or \Delta f = 0, where \Delta = \na ...
. A significant portion of this research was focused on
Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayl ...
s of finitely generated groups. In many cases these discrete results carry over to, or are derived from
manifold In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a ...
s and
Lie group In mathematics, a Lie group (pronounced ) is a group that is also a differentiable manifold. A manifold is a space that locally resembles Euclidean space, whereas groups define the abstract concept of a binary operation along with the ad ...
s. In the context of random graphs, particularly that of the Erdős–Rényi model, analytical results to some properties of random walkers have been obtained. These include the distribution of first and last hitting times of the walker, where the first hitting time is given by the first time the walker steps into a previously visited site of the graph, and the last hitting time corresponds the first time the walker cannot perform an additional move without revisiting a previously visited site. A good reference for random walk on graphs is the online book b
Aldous and Fill
For groups see the book of Woess. If the transition kernel p(x,y) is itself random (based on an environment \omega) then the random walk is called a "random walk in random environment". When the law of the random walk includes the randomness of \omega, the law is called the annealed law; on the other hand, if \omega is seen as fixed, the law is called a quenched law. See the book of Hughes, the book of Revesz, 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 every 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 computers. Examples include: * The self-avoiding walk. The self-avoiding walk of length ''n'' on \mathbb^d is the random ''n''-step path which starts at the origin, makes transitions only between adjacent sites in \mathbb^d, never revisit a site, and is chosen uniformly among all such paths. In two dimensions, due to self-trapping, a typical self-avoiding walk is very short, while in higher dimension it grows beyond all bounds. This model has often been used in
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.P. Flory, ''Principles of ...
(since the 1960s). * The
loop-erased random walk In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See al ...
. * The reinforced random walk. * The exploration process. * The
multiagent random walk An agent-based model (ABM) is a computational model for simulating the actions and interactions of autonomous agents (both individual or collective entities such as organizations or groups) in order to understand the behavior of a system and wha ...
.


Biased random walks on graphs


Maximal entropy random walk

Random walk chosen to maximize
entropy rate In the mathematical theory of probability, the entropy rate or source information rate of a stochastic process is, informally, the time density of the average information in a stochastic process. For stochastic processes with a countable index, the ...
, has much stronger localization properties.


Correlated random walks

Random walks where the direction of movement at one time is correlated with the direction of movement at the next time. It is used to model animal movements.


See also

*
Branching random walk In probability theory, a branching random walk is a stochastic process that generalizes both the concept of a random walk and of a branching process. At every generation (a point of discrete time), a branching random walk's value is a set of elem ...
*
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position ins ...
* Law of the iterated logarithm *
Lévy flight A Lévy flight is a random walk in which the step-lengths have a Lévy distribution, 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 directi ...
*
Lévy flight foraging hypothesis The Lévy flight foraging hypothesis is a hypothesis in the field of biology that may be stated as follows: ''Since Lévy flights and walks can optimize search efficiencies, therefore natural selection should have led to adaptations for Lévy fligh ...
*
Loop-erased random walk In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See al ...
* Maximal entropy random walk * Self-avoiding walk *
Unit root In probability theory and statistics, a unit root is a feature of some stochastic processes (such as random walks) that can cause problems in statistical inference involving time series models. A linear stochastic process has a unit root if ...


References


Bibliography

* * * Feller, William (1968), ''An Introduction to Probability Theory and its Applications'' (Volume 1). * Hughes, Barry D. (1996), ''Random Walks and Random Environments'', Oxford University Press. * Norris, James (1998), ''Markov Chains'', Cambridge University Press. * Pólya G.(1921)
"Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz"
, '' Mathematische Annalen'', 84(1–2):149–160, March 1921. * Révész, Pal (2013), ''Random Walk in Random and Non-random Environments (Third Edition)'', World Scientific Pub Co. * * Weiss G. ''Aspects and Applications of the Random Walk'', North-Holland, 1994. * Woess, Wolfgang (2000), ''Random Walks on Infinite Graphs and Groups'', Cambridge tracts in mathematics 138, Cambridge University Press.


External links


Pólya's Random Walk Constants

Random walk in Java Applet

Quantum random walk

Gaussian random walk estimatorElectron Conductance Models Using Maximal Entropy Random Walks
Wolfram Demonstrations Project {{DEFAULTSORT:Random Walk Stochastic processes Variants of random walks