Part of a series on statistics |

Probability theory |
---|

In mathematics, a **random walk** is a mathematical object, known as a stochastic or random process, that describes a path that consists of a succession of random steps on some mathematical space such as the integers.

- Lattice random walk
- One-dimensional random walk
- Higher dimensions
- Relation to Wiener process
- Gaussian random walk
- Anomalous diffusion
- Number of distinct sites
- Information rate
- Applications
- Variants
- On graphs
- Self-interacting random walks
- Long-range correlated walks
- Biased random walks on graphs
- Maximal entropy random walk
- Correlated random walks
- See also
- References
- Bibliography
- External links

An elementary example of a random walk is the random walk on the integer number line, , 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), the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler: all can be approximated by random walk models, even though they may not be truly random in reality.

As illustrated by those examples, random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology. Random walks explain the observed behaviors of many processes in these fields, and thus serve as a fundamental model for the recorded stochastic activity. As a more mathematical application, the value of π can be approximated by the use of a random walk in an agent-based modeling environment.^{ [1] }^{ [2] } The term *random walk* was first introduced by Karl Pearson in 1905.^{ [3] }

Various types of random walks are of interest, which can differ in several ways. The term itself most often refers to a special category of Markov chains, but many time-dependent processes are referred to as random walks, with a modifier indicating their specific properties. Random walks (Markov or not) can also take place on a variety of spaces: commonly studied ones include graphs, others on the integers or the real line, in the plane or higher-dimensional vector spaces, on curved surfaces or higher-dimensional Riemannian manifolds, and also on groups finite, finitely generated or Lie. The time parameter can also be manipulated. In the simplest context the walk is in discrete time, that is a sequence of random variables (*X ^{t}*) = (

Random walks are a fundamental topic in discussions of Markov processes. Their mathematical study has been extensive. Several properties, including dispersal distributions, first-passage or hitting times, encounter rates, recurrence or transience, have been introduced to quantify their behavior.

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** 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 of random walk on the *d*-dimensional integer lattice (sometimes called the hypercubic lattice) .^{ [4] }

If the state space is limited to finite dimensions, the random walk model is called** 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.^{ [5] }

An elementary example of a random walk is the random walk on the integer 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, 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 , where each variable is either 1 or −1, with a 50% probability for either value, and set and The series is called the **simple random walk on **. 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 of 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:

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

This hints that , the expected translation distance after *n* steps, should be of the order of . In fact,^{ [6] }

This result shows that diffusion is ineffective for mixing because of the way the square root behaves for large .^{[ citation needed ]}

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 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 , which can be derived from the fact that simple random walk is a martingale.

Some of the results mentioned above can be derived from properties of Pascal's triangle. 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 *S _{n}* to be equal to a number

If space is confined to + for brevity, the number of ways in which a random walk will land on any given number having five flips can be shown as {0,5,0,4,0,1}.

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.

k | −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 and the law of the iterated logarithm describe important aspects of the behavior of simple random walks on . In particular, the former entails that as *n* increases, the probabilities (proportional to the numbers in each row) approach a normal distribution.

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.^{ [8] }^{ [9] }

A one-dimensional **random walk** can also be looked at as a Markov chain whose state space is given by the integers For some number *p* satisfying , the transition probabilities (the probability *P _{i,j}* of moving from state

In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discrete fractal, 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. Two books of Lawler referenced below are a good source on this topic. 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 ).

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 with integer coordinates.

Will the person ever get 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 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%.^{ [10] } 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".^{ [11] }

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?^{ [12] } 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.^{ [13] }

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.

A Wiener process is a stochastic process with similar behavior to Brownian motion, 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 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*/ε^{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}.^{[ citation needed ]} This fact is the *discrete version* of the fact that a Wiener process walk is a fractal of Hausdorff dimension 2.^{[ citation needed ]}

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.^{ [14] }

A Wiener process enjoys many symmetries 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 theorem.

The convergence of a random walk toward the Wiener process is controlled by the central limit theorem, 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 of total variance:

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's function 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 of the diffusion equation is:

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

- (valid only in 3D).

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

For 2D:^{ [15] }

For 1D:^{ [16] }

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.

If μ is nonzero, the random walk will vary about a linear trend. If v_{s} is the starting value of the random walk, the expected value after *n* steps will be v_{s} + *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, X_{i} from the inverse cumulative normal distribution with mean equal zero and σ of the original inverse cumulative normal distribution:

- Z = ,

but we have the distribution for the sum of two independent normally distributed random variables, Z = X + Y, is given by

- (μ
_{X}+ μ_{Y}, σ^{2}_{X}+ σ^{2}_{Y}) (see here).

In our case, μ_{X} = μ_{Y} = 0 and σ^{2}_{X} = σ^{2}_{Y} = σ^{2} yield

- (0, 2σ
^{2})

By induction, for *n* steps we have

- Z ~ (0,
*n*σ^{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 translation distance after *n* steps is

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 ± σ. Likewise, there is 50% probability that the translation distance after *n* steps will fall between ± 0.6745σ.

In disordered systems such as porous media and fractals may not be proportional to but to . The exponent is called the anomalous diffusion exponent and can be larger or smaller than 2.^{ [17] } Anomalous diffusion may also be expressed as σ_{r}^{2} ~ Dt^{α} where α is the anomaly parameter. Some diffusions in random environment are even proportional to a power of the logarithm of the time, see for example Sinai's walk or Brox diffusion.

The number of distinct sites visited by a single random walker has been studied extensively for square and cubic lattices and for fractals.^{ [18] }^{ [19] } This quantity is useful for the analysis of problems of trapping and kinetic reactions. It is also related to the vibrational density of states,^{ [20] }^{ [21] } diffusion reactions processes^{ [22] } and spread of populations in ecology.^{ [23] }^{ [24] } The generalization of this problem to the number of distinct sites visited by random walkers, , has recently been studied for d-dimensional Euclidean lattices.^{ [25] } The number of distinct sites visited by N walkers is not simply related to the number of distinct sites visited by each walker.

The information rate of a Gaussian random walk with respect to the squared error distance, i.e. its quadratic rate distortion function, is given parametrically by^{ [26] }

where . Therefore, it is impossible to encode using a binary code of less than bits and recover it with expected mean squared error less than . On the other hand, for any , there exists an large enough and a binary code of no more than distinct elements such that the expected mean squared error in recovering from this code is at most .

This section needs additional citations for verification .(February 2013) |

As mentioned the range of natural phenomena which have been subject to attempts at description by some flavour of random walks is considerable, in particular in physics^{ [27] }^{ [28] } and chemistry,^{ [29] } materials science,^{ [30] }^{ [31] } biology^{ [32] } and various other fields.^{ [33] }^{ [34] } The following are some specific applications of random walk:

- In financial economics, the "random walk hypothesis" is used to model shares prices and other factors.
^{ [35] }Empirical studies found some deviations from this theoretical model, especially in short term and long term correlations. See share prices. - In population genetics, random walk describes the statistical properties of genetic drift
- In physics, random walks are used as simplified models of physical Brownian motion and diffusion such as the random movement of molecules in liquids and gases. See for example diffusion-limited aggregation. Also in physics, random walks and some of the self interacting walks play a role in quantum field theory.
- In 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, random walk describes an ideal chain. It is the simplest model to study polymers.
^{ [36] } - In other fields of mathematics, random walk is used to calculate solutions to Laplace's equation, to estimate the harmonic measure, and for various constructions in analysis and combinatorics.
- In computer science, random walks are used to estimate the size of the Web.
^{ [37] } - In image segmentation, random walks are used to determine the labels (i.e., "object" or "background") to associate with each pixel.
^{ [38] }This algorithm is typically referred to as the random walker segmentation algorithm.

In all these cases ^{[ which? ]}, random walk is often substituted for Brownian motion ^{[ why? ]}.

- In brain research, random walks and reinforced random walks are used to model cascades of neuron firing in the brain.
- In vision science, ocular drift tends to behave like a random walk.
^{ [39] }According to some authors, fixational eye movements in general are also well described by a random walk.^{ [40] } - 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.
^{ [41] } - 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 or, for research of working conditions, a random worker in a given country.
^{[ citation needed ]}

- When this last approach is used in computer science it is known as Markov chain Monte Carlo or MCMC for short. Often, sampling from some complicated state space also allows one to get a probabilistic estimate of the space's size. The estimate of the permanent of a large matrix of zeros and ones was the first major problem tackled using this approach.
^{[ citation needed ]}

- When this last approach is used in computer science it is known as Markov chain Monte Carlo or MCMC for short. Often, sampling from some complicated state space also allows one to get a probabilistic estimate of the space's size. The estimate of the permanent of a large matrix of zeros and ones was the first major problem tackled using this approach.

- Random walks have also been used to sample massive online graphs such as social networking services.
- In wireless networking, a random walk is used to model node movement.
^{[ citation needed ]} - Motile bacteria engage in a biased random walk.
^{ [42] } - Random walks are used to model gambling.
^{[ citation needed ]} - In physics, random walks underlie the method of Fermi estimation.
^{[ citation needed ]} - On the web, the Twitter website uses random walks to make suggestions of whom to follow
^{ [43] } - 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.

A number of types of stochastic processes 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.

A random walk of length *k* on a possibly infinite graph *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*.

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,^{ [44] } 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.^{ [45] }

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, i.e. the city may contain tunnels and bridges. One way to prove this result is using the connection to electrical networks. Take a map of the city and place a one ohm resistor on every block. Now measure the "resistance between a point and infinity". In other words, choose some number *R* and take all the points in the electrical network with distance bigger than *R* from our point and wire them together. This is now a finite electrical network, and we may measure the resistance from our point to the wired points. Take *R* to infinity. The limit is called the *resistance between a point and infinity*. It turns out that the following is true (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, functional inequalities such as Sobolev and Poincaré inequalities and properties of solutions of Laplace's equation. A significant portion of this research was focused on Cayley graphs of finitely generated groups. In many cases these discrete results carry over to, or are derived from manifolds and Lie groups.

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^{ [46] } and last hitting times^{ [47] } 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 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, 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.^{ [48] } This random walk has much stronger localization properties.

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.
^{ [49] }

The self-avoiding walk of length *n* on is the random *n*-step path which starts at the origin, makes transitions only between adjacent sites in , 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,^{ [50] } while in higher dimension it grows beyond all bounds. This model has often been used in polymer physics (since the 1960s).

- The loop-erased random walk.
^{ [51] }^{ [52] } - The reinforced random walk.
^{ [53] } - The exploration process.
^{[ citation needed ]} - The multiagent random walk.
^{ [54] }

Long-range correlated time series are found in many biological, climatological and economic systems.

- Heartbeat records
^{ [55] } - Non-coding DNA sequences
^{ [56] } - Volatility time series of stocks
^{ [57] } - Temperature records around the globe
^{ [58] }

Random walk chosen to maximize entropy rate, has much stronger localization properties.

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.^{ [59] }^{ [60] }

**Brownian motion**, or **pedesis**, is the random motion of particles suspended in a medium.

A **statistical model** is a mathematical model that embodies a set of statistical assumptions concerning the generation of sample data. A statistical model represents, often in considerably idealized form, the data-generating process.

In probability theory, the **central limit theorem** (**CLT**) establishes that, in many situations, when independent random variables are added, their properly normalized sum tends toward a normal distribution even if the original variables themselves are not normally distributed. The theorem is a key concept in probability theory because it implies that probabilistic and statistical methods that work for normal distributions can be applicable to many problems involving other types of distributions. This theorem has seen many changes during the formal development of probability theory. Previous versions of the theorem date back to 1811, but in its modern general form, this fundamental result in probability theory was precisely stated as late as 1920, thereby serving as a bridge between classical and modern probability theory.

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 appear to vary in a random manner. Examples include the growth of a bacterial population, an electrical current fluctuating due to thermal noise, or the movement of a gas molecule. Stochastic processes have applications in many disciplines such as biology, chemistry, ecology, neuroscience, physics, image processing, signal processing, control theory, information theory, computer science, cryptography and telecommunications. Furthermore, seemingly random changes in financial markets have motivated the extensive use of stochastic processes in finance.

In mathematics, the **Wiener process** is a real valued continuous-time stochastic process named in honor of American mathematician Norbert Wiener for his investigations on the mathematical properties of the one-dimensional Brownian motion. It is often also called Brownian motion due to its historical connection with the physical process of the same name originally observed by Scottish botanist Robert Brown. It is one of the best known Lévy processes and occurs frequently in pure and applied mathematics, economics, quantitative finance, evolutionary biology, and physics.

The **Ising model**, , named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent magnetic dipole moments of atomic "spins" that can be in one of two states. The spins are arranged in a graph, usually a lattice, allowing each spin to interact with its neighbors. Neighboring spins that agree have a lower energy than those that disagree; the system tends to the lowest energy but heat disturbs this tendency, thus creating the possibility of different structural phases. The model allows the identification of phase transitions as a simplified model of reality. The two-dimensional square-lattice Ising model is one of the simplest statistical models to show a phase transition.

In probability and statistics, a **mixture distribution** is the probability distribution of a random variable that is derived from a collection of other random variables as follows: first, a random variable is selected by chance from the collection according to given probabilities of selection, and then the value of the selected random variable is realized. The underlying random variables may be random real numbers, or they may be random vectors, in which case the mixture distribution is a multivariate distribution.

In statistics, a **mixture model** is a probabilistic model for representing the presence of subpopulations within an overall population, without requiring that an observed data set should identify the sub-population to which an individual observation belongs. Formally a mixture model corresponds to the mixture distribution that represents the probability distribution of observations in the overall population. However, while problems associated with "mixture distributions" relate to deriving the properties of the overall population from those of the sub-populations, "mixture models" are used to make statistical inferences about the properties of the sub-populations given only observations on the pooled population, without sub-population identity information.

In probability theory, a **Lévy process**, named after the French mathematician Paul Lévy, is a stochastic process with independent, stationary increments: it represents the motion of a point whose successive displacements are random, in which displacements in pairwise disjoint time intervals are independent, and displacements in different time intervals of the same length have identical probability distributions. A Lévy process may thus be viewed as the continuous-time analog of a 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. See also *random walk* for more general treatment of this topic.

A **stochastic differential equation** (**SDE**) is a differential equation in which one or more of the terms is a stochastic process, resulting in a solution which is also a stochastic process. SDEs are used to model various phenomena such as unstable stock prices or physical systems subject to thermal fluctuations. Typically, SDEs contain a variable which represents random white noise calculated as the derivative of Brownian motion or the Wiener process. However, other types of random behaviour are possible, such as jump processes. Random differential equations are conjugate to stochastic differential equations.

In mathematics, the **Ornstein–Uhlenbeck process** is a stochastic process with applications in financial mathematics and the physical sciences. Its original application in physics was as a model for the velocity of a massive Brownian particle under the influence of friction. It is named after Leonard Ornstein and George Eugene Uhlenbeck.

The **contact process** is a stochastic process used to model population growth on the set of sites of a graph in which occupied sites become vacant at a constant rate, while vacant sites become occupied at a rate proportional to the number of occupied neighboring sites. Therefore, if we denote by the proportionality constant, each site remains occupied for a random time period which is exponentially distributed parameter 1 and places descendants at every vacant neighboring site at times of events of a Poisson process parameter during this period. All processes are independent of one another and of the random period of time sites remains occupied. The contact process can also be interpreted as a model for the spread of an infection by thinking of particles as a bacterium spreading over individuals that are positioned at the sites of , occupied sites correspond to infected individuals, whereas vacant correspond to healthy ones.

In mathematics, **Gaussian measure** is a Borel measure on finite-dimensional Euclidean space **R**^{n}, closely related to the normal distribution in statistics. There is also a generalization to infinite-dimensional spaces. Gaussian measures are named after the German mathematician Carl Friedrich Gauss. One reason why Gaussian measures are so ubiquitous in probability theory is the central limit theorem. Loosely speaking, it states that if a random variable *X* is obtained by summing a large number *N* of independent random variables of order 1, then *X* is of order and its law is approximately Gaussian.

In probability theory and statistical mechanics, the **Gaussian free field (GFF)** is a Gaussian random field, a central model of random surfaces. Sheffield (2007) gives a mathematical survey of the Gaussian free field.

In the theory of stochastic processes, the **filtering problem** is a mathematical model for a number of state estimation problems in signal processing and related fields. The general idea is to establish a "best estimate" for the true value of some system from an incomplete, potentially noisy set of observations on that system. The problem of optimal non-linear filtering was solved by Ruslan L. Stratonovich, see also Harold J. Kushner's work and Moshe Zakai's, who introduced a simplified dynamics for the unnormalized conditional law of the filter known as Zakai equation. The solution, however, is infinite-dimensional in the general case. Certain approximations and special cases are well understood: for example, the linear filters are optimal for Gaussian random variables, and are known as the Wiener filter and the Kalman-Bucy filter. More generally, as the solution is infinite dimensional, it requires finite dimensional approximations to be implemented in a computer with finite memory. A finite dimensional approximated nonlinear filter may be more based on heuristics, such as the Extended Kalman Filter or the Assumed Density Filters, or more methodologically oriented such as for example the Projection Filters, some sub-families of which are shown to coincide with the Assumed Density Filters.

**Harry Kesten** was an American mathematician best known for his work in probability, most notably on random walks on groups and graphs, random matrices, branching processes, and percolation theory.

**Diffusion maps** is a dimensionality reduction or feature extraction algorithm introduced by Coifman and Lafon which computes a family of embeddings of a data set into Euclidean space whose coordinates can be computed from the eigenvectors and eigenvalues of a diffusion operator on the data. The Euclidean distance between points in the embedded space is equal to the "diffusion distance" between probability distributions centered at those points. Different from linear dimensionality reduction methods such as principal component analysis (PCA), diffusion maps is part of the family of nonlinear dimensionality reduction methods which focus on discovering the underlying manifold that the data has been sampled from. By integrating local similarities at different scales, diffusion maps give a global description of the data-set. Compared with other methods, the diffusion map algorithm is robust to noise perturbation and computationally inexpensive.

In probability theory, **reflected Brownian motion** is a Wiener process in a space with reflecting boundaries.

**Maximal entropy random walk** (**MERW**) is a popular type of biased random walk on a graph, in which transition probabilities are chosen accordingly to the principle of maximum entropy, which says that the probability distribution which best represents the current state of knowledge is the one with largest entropy. While standard random walk chooses for every vertex uniform probability distribution among its outgoing edges, locally maximizing entropy rate, MERW maximizes it globally by assuming uniform probability distribution among all paths in a given graph.

- ↑ Wirth, E.; Szabó, G.; Czinkóczky, A. (8 June 2016). "Measure Landscape Diversity with Logical Scout Agents".
*International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences*. XLI-B2: 491–495. Bibcode:2016ISPAr49B2..491W. doi: 10.5194/isprs-archives-xli-b2-491-2016 . - ↑ Wirth E. (2015). Pi from agent border crossings by NetLogo package. Wolfram Library Archive
- ↑ Pearson, K. (1905). "The Problem of the Random Walk".
*Nature*.**72**(1865): 294. Bibcode:1905Natur..72..294P. doi:10.1038/072294b0. S2CID 4010776. - ↑ Pal, Révész (1990)
*Random walk in random and nonrandom environments*, World Scientific - ↑ Kohls, Moritz; Hernandez, Tanja (2016). "Expected Coverage of Random Walk Mobility Algorithm". arXiv: 1611.02861 . Bibcode:2016arXiv161102861K.Cite journal requires
`|journal=`

(help) - ↑ "Random Walk-1-Dimensional – from Wolfram MathWorld". Mathworld.wolfram.com. 26 April 2000. Retrieved 2 November 2016.
- ↑ Edward A. Codling et al, Random walk models in biology, Journal of the Royal Society Interface, 2008
- ↑ Kotani, M. and Sunada, T. (2003). "Spectral geometry of crystal lattices".
*Contemporary. Math*. Contemporary Mathematics.**338**: 271–305. doi:10.1090/conm/338/06077. ISBN 9780821833834.CS1 maint: multiple names: authors list (link) - ↑ Kotani, M. and Sunada, T. (2006). "Large deviation and the tangent cone at infinity of a crystal lattice".
*Math. Z*.**254**(4): 837–870. doi:10.1007/s00209-006-0951-9. S2CID 122531716.CS1 maint: multiple names: authors list (link) - ↑ "Pólya's Random Walk Constants". Mathworld.wolfram.com. Retrieved 2 November 2016.
- ↑ Durrett, Rick (2010).
*Probability: Theory and Examples*. Cambridge University Press. pp. 191. ISBN 9781139491136. - ↑ Pólya, George (1984).
*Probability; Combinatorics; Teaching and learning in mathematics*. Rota, Gian-Carlo, 1932-1999., Reynolds, M. C., Shortt, Rae Michael. Cambridge, Mass.: MIT Press. pp. 582–585. ISBN 0-262-16097-8. OCLC 10208449. - ↑ Erdős, P.; Taylor, S. J. (1960). "Some intersection properties of random walk paths".
*Acta Mathematica Academiae Scientiarum Hungaricae*.**11**(3–4): 231–248. doi:10.1007/BF02020942. ISSN 0001-5954. S2CID 14143214. - ↑ MacKenzie, D. (2000). "MATHEMATICS: Taking the Measure of the Wildest Dance on Earth".
*Science*.**290**(5498): 1883–4. doi:10.1126/science.290.5498.1883. PMID 17742050. S2CID 12829171. (Erratum: doi:10.1126/science.291.5504.597) - ↑ Chapter 2 DIFFUSION. dartmouth.edu.
- ↑ Diffusion equation for the random walk. physics.uakron.edu.
- ↑ D. Ben-Avraham and S. Havlin,
*Diffusion and Reactions in Fractals and Disordered Systems*, Cambridge University Press, 2000. - ↑ Weiss, George H.; Rubin, Robert J. (1982). "Random Walks: Theory and Selected Applications".
*Advances in Chemical Physics*.**52**. pp. 363–505. doi:10.1002/9780470142769.ch5. ISBN 9780470142769. - ↑ Blumen, A.; Klafter, J.; Zumofen, G. (1986). "Models for Reaction Dynamics in Glasses".
*Optical Spectroscopy of Glasses*. Physic and Chemistry of Materials with Low-Dimensional Structures.**1**. pp. 199–265. Bibcode:1986PCMLD...1..199B. doi:10.1007/978-94-009-4650-7_5. ISBN 978-94-010-8566-3. - ↑ Alexander, S.; Orbach, R. (1982). "Density of states on fractals : " fractons "".
*Journal de Physique Lettres*.**43**(17): 625–631. doi:10.1051/jphyslet:019820043017062500. S2CID 67757791. - ↑ Rammal, R.; Toulouse, G. (1983). "Random walks on fractal structures and percolation clusters".
*Journal de Physique Lettres*.**44**(1): 13–22. doi:10.1051/jphyslet:0198300440101300. - ↑ Smoluchowski, M.V. (1917). "Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen".
*Z. Phys. Chem.*(29): 129–168.,Rice, S.A. (1 March 1985).*Diffusion-Limited Reactions*. Comprehensive Chemical Kinetics.**25**. Elsevier. ISBN 978-0-444-42354-2 . Retrieved 13 August 2013. - ↑ Skellam, J. G. (1951). "Random Dispersal in Theoretical Populations".
*Biometrika*.**38**(1/2): 196–218. doi:10.2307/2332328. JSTOR 2332328. PMID 14848123. - ↑ Skellam, J. G. (1952). "Studies in Statistical Ecology: I. Spatial Pattern".
*Biometrika*.**39**(3/4): 346–362. doi:10.2307/2334030. JSTOR 2334030. - ↑ Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H. Eugene; Weiss, George H. (1992). "Territory covered by N diffusing particles".
*Nature*.**355**(6359): 423–426. Bibcode:1992Natur.355..423L. doi:10.1038/355423a0. S2CID 4284015.,Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H.; Weiss, George (1992). "Number of distinct sites visited by N random walkers".*Physical Review A*.**45**(10): 7128–7138. Bibcode:1992PhRvA..45.7128L. doi:10.1103/PhysRevA.45.7128. PMID 9906785. S2CID 6643160.; for insights regarding the problem of N random walkers, see Shlesinger, Michael F. (1992). "New paths for random walkers".*Nature*.**355**(6359): 396–397. Bibcode:1992Natur.355..396S. doi: 10.1038/355396a0 . S2CID 4367788. and the color artwork illustrating the article. - ↑ Berger, T. (1970). "Information rates of Wiener processes".
*IEEE Transactions on Information Theory*.**16**(2): 134–139. doi:10.1109/TIT.1970.1054423. - ↑ Risken H. (1984)
*The Fokker–Planck Equation*. Springer, Berlin. - ↑ De Gennes P. G. (1979)
*Scaling Concepts in Polymer Physics*. Cornell University Press, Ithaca and London. - ↑ Van Kampen N. G. (1992)
*Stochastic Processes in Physics and Chemistry*, revised and enlarged edition. North-Holland, Amsterdam. - ↑ Weiss, George H. (1994).
*Aspects and Applications of the Random Walk*. Random Materials and Processes. North-Holland Publishing Co., Amsterdam. ISBN 978-0-444-81606-1. MR 1280031. - ↑ Doi M. and Edwards S. F. (1986)
*The Theory of Polymer Dynamics*. Clarendon Press, Oxford - ↑ 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. - ↑ David A. Kodde and Hein Schreuder (1984), Forecasting Corporate Revenue and Profit: Time-Series Models versus Management and Analysts, Journal of Business Finance and Accounting, vol. 11, no 3, Autumn 1984
- ↑ Jones, R.A.L. (2004).
*Soft condensed matter*(Reprint. ed.). Oxford [u.a.]: Oxford Univ. Pr. pp. 77–78. ISBN 978-0-19-850589-1. - ↑ Bar-Yossef, Ziv; Gurevich, Maxim (2008). "Random sampling from a search engine's index".
*Journal of the ACM*. Association for Computing Machinery (ACM).**55**(5): 1–74. doi:10.1145/1411509.1411514. ISSN 0004-5411. - ↑ Grady, L (2006). "Random walks for image segmentation" (PDF).
*IEEE Transactions on Pattern Analysis and Machine Intelligence*.**28**(11): 1768–83. CiteSeerX 10.1.1.375.3389 . doi:10.1109/TPAMI.2006.233. PMID 17063682. S2CID 489789. - ↑ Rucci, M; Victor, J. D. (2015). "The unsteady eye: An information-processing stage, not a bug".
*Trends in Neurosciences*.**38**(4): 195–206. doi:10.1016/j.tins.2015.01.005. PMC 4385455 . PMID 25698649. - ↑ Engbert, R.; Mergenthaler, K.; Sinn, P.; Pikovsky, A. (2011). "An integrated model of fixational eye movements and microsaccades".
*Proceedings of the National Academy of Sciences*.**108**(39): E765-70. Bibcode:2011PNAS..108E.765E. doi:10.1073/pnas.1102730108. PMC 3182695 . PMID 21873243. - ↑ Nosofsky, R. M.; Palmeri, T. J. (1997). "An exemplar-based random walk model of speeded classification" (PDF).
*Psychological Review*.**104**(2): 266–300. doi:10.1037/0033-295x.104.2.266. PMID 9127583. Archived from the original (PDF) on 10 December 2004. - ↑ Codling, E. A; Plank, M. J; Benhamou, S. (6 August 2008). "Random walk models in biology".
*Journal of the Royal Society Interface*.**5**(25): 813–834. doi:10.1098/rsif.2008.0014. PMC 2504494 . PMID 18426776. - ↑ Gupta, Pankaj et al. WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web
- ↑ It is interesting to remark that in a general graph the meeting of two independent random walkers does not always reduces to the problem of a single random walk returning to its starting point.
- ↑ Krishnapur, Manjunath; Peres, Yuval (2004). "Recurrent Graphs where Two Independent Random Walks Collide Finitely Often".
*Electronic Communications in Probability*.**9**: 72–81. arXiv: math/0406487 . Bibcode:2004math......6487K. doi:10.1214/ECP.v9-1111. ISSN 1083-589X. S2CID 16584737. - ↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan (2017). "The distribution of first hitting times of randomwalks on Erdős–Rényi networks".
*Journal of Physics A: Mathematical and Theoretical*.**50**(11): 115001. arXiv: 1606.01560 . Bibcode:2017JPhA...50k5001T. doi:10.1088/1751-8121/aa5af3. S2CID 118850609. - ↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan (2016). "The distribution of path lengths of self avoiding walks on Erdős–Rényi networks".
*Journal of Physics A: Mathematical and Theoretical*.**49**(28): 285002. arXiv: 1603.06613 . Bibcode:2016JPhA...49B5002T. doi:10.1088/1751-8113/49/28/285002. S2CID 119182848. - ↑ Burda, Z.; Duda, J.; Luck, J. M.; Waclaw, B. (2009). "Localization of the Maximal Entropy Random Walk".
*Physical Review Letters*.**102**(16): 160602. arXiv: 0810.4113 . Bibcode:2009PhRvL.102p0602B. doi:10.1103/PhysRevLett.102.160602. PMID 19518691. S2CID 32134048. - ↑ Madras, Neal and Slade, Gordon (1996)
*The Self-Avoiding Walk*, Birkhäuser Boston. ISBN 0-8176-3891-1. - ↑ Hemmer, S.; Hemmer, P. C. (1984). "An average self-avoiding random walk on the square lattice lasts 71 steps".
*J. Chem. Phys*.**81**(1): 584–585. Bibcode:1984JChPh..81..584H. doi:10.1063/1.447349. - ↑ Lawler, Gregory (1996).
*Intersection of random walks*, Birkhäuser Boston. ISBN 0-8176-3892-X. - ↑ Lawler, Gregory
*Conformally Invariant Processes in the Plane*, book.ps. - ↑ Pemantle, Robin (2007). "A survey of random processes with reinforcement" (PDF).
*Probability Surveys*.**4**: 1–79. arXiv: math/0610076 . doi:10.1214/07-PS094. S2CID 11964062. - ↑ Alamgir, M and von Luxburg, U (2010). "Multi-agent random walks for local clustering on graphs",
*IEEE 10th International Conference on Data Mining (ICDM)*, pp. 18–27. - ↑ Peng, C.-K.; Mietus, J; Hausdorff, J. M.; Havlin, S; Stanley, H. E.; Goldberger, A. L. (1993). "Long-range anticorrelations and non-gaussian behavior of the heartbeat".
*Phys. Rev. Lett*.**70**(9): 1343–6. Bibcode:1993PhRvL..70.1343P. doi:10.1103/PhysRevLett.70.1343. PMID 10054352. - ↑ Peng, C. K.; Buldyrev, S. V.; Goldberger, A. L.; Havlin, S; Sciortino, F; Simons, M; Stanley, H. E. (1992). "Long-range correlations in nucleotide sequences".
*Nature*.**356**(6365): 168–70. Bibcode:1992Natur.356..168P. doi:10.1038/356168a0. PMID 1301010. S2CID 4334674. - ↑ Liu, Yanhui; Cizeau, Pierre; Meyer, Martin; Peng, C.-K.; Eugene Stanley, H. (1997). "Correlations in economic time series".
*Physica A*.**245**(3–4): 437. arXiv: cond-mat/9706021 . Bibcode:1997PhyA..245..437L. doi:10.1016/S0378-4371(97)00368-3. S2CID 14591968. - ↑ Koscielny-Bunde, Eva; Bunde, Armin; Havlin, Shlomo; Roman, H. Eduardo; Goldreich, Yair; Schellnhuber, Hans-Joachim (1998). "Indication of a universal persistence law governing atmospheric variability".
*Phys. Rev. Lett*.**81**(3): 729. Bibcode:1998PhRvL..81..729K. doi:10.1103/PhysRevLett.81.729. - ↑ Bovet, Pierre; Benhamou, Simon (1988). "Spatial analysis of animals' movements using a correlated random walk model".
*Journal of Theoretical Biology*.**131**(4): 419–433. doi:10.1016/S0022-5193(88)80038-9. - ↑ Kareiva, P.M.; Shigesada, N. (1983). "Analyzing insect movement as a correlated random walk".
*Oecologia*.**56**(2–3): 234–238. Bibcode:1983Oecol..56..234K. doi:10.1007/BF00379695. PMID 28310199. S2CID 20329045.

- Aldous, David; Fill, James Allen (2002).
*Reversible Markov Chains and Random Walks on Graphs*. Archived from the original on 27 February 2019. - Ben-Avraham D.; Havlin S.,
*Diffusion and Reactions in Fractals and Disordered Systems*, Cambridge University Press, 2000. - Doyle, Peter G.; Snell, J. Laurie (1984).
*Random Walks and Electric Networks*. Carus Mathematical Monographs.**22**. Mathematical Association of America. arXiv: math.PR/0001057 . ISBN 978-0-88385-024-4. MR 0920811. - Feller, William (1968),
*An Introduction to Probability Theory and its Applications*(Volume 1). ISBN 0-471-25708-7 - Hughes, Barry D. (1996),
*Random Walks and Random Environments*, Oxford University Press. ISBN 0-19-853789-1 - Norris, James (1998),
*Markov Chains*, Cambridge University Press. ISBN 0-521-63396-6 - 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. ISBN 978-981-4447-50-8 - Sunada, Toshikazu (2012).
*Topological Crystallography: With a View Towards Discrete Geometric Analysis*. Surveys and Tutorials in the Applied Mathematical Sciences.**6**. Springer. ISBN 978-4-431-54177-6. - 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. ISBN 0-521-55292-3

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.