Random walk

Random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology.

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.

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.

By representing entries of Pascal's triangle in terms of factorials and using Stirling's formula, one can obtain good estimates for these probabilities for large values of

This relation with Pascal's triangle is demonstrated for small values of n. At zero turns, the only possibility will be to remain at zero.

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.

In fact, one gets a discrete fractal, that is, a set which exhibits stochastic self-similarity on large scales.

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.

[12] 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?

[14] The asymptotic function for a two-dimensional random walk as the number of steps increases is given by a Rayleigh distribution.

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

For example, take a random walk until it hits a circle of radius r times the step length.

[citation needed] In two dimensions, the average number of points the same random walk has on the boundary of its trajectory is r4/3.

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.

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.

It is also related to the vibrational density of states,[21][22] diffusion reactions processes[23] and spread of populations in ecology.

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 physics[27][28] and chemistry,[29] materials science,[30][31] and biology.

The pure structure can be characterized by the steps being defined by independent and identically distributed random variables.

Specific cases or limits of random walks include the Lévy flight and diffusion models such as Brownian motion.

Building on the analogy from the earlier section on higher dimensions, assume now that our city is no longer a perfect square grid.

[46] 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).

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.

In other words, in a transient system, one only needs to overcome a finite resistance to get to infinity from any point.

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.

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

A significant portion of this research was focused on Cayley graphs of finitely generated groups.

There are a number of interesting models of random paths in which each step depends on the past in a complicated manner.

is the random n-step path which starts at the origin, makes transitions only between adjacent sites in