Citizendia
Your Ad Here

Example of eight random walks in one dimension starting at 0. The plot shows the current position on the line (vertical axis) versus the time steps (horizontal axis).
Example of eight random walks in one dimension starting at 0. The plot shows the current position on the line (vertical axis) versus the time steps (horizontal axis).

A random walk, sometimes denoted RW, is a mathematical formalization of a trajectory that consists of taking successive random steps. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Randomness is a lack of order Purpose, cause, or predictability The results of random walk analysis have been applied to computer science, physics, ecology, economics and a number of other fields as a fundamental model for random processes in time. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Physics (Greek Physis - φύσις in everyday terms is the Science of Matter and its motion. Ecology (from Greek grc οἶκος oikos, "house(hold" and grc -λογία -logia) is the scientific study of Economics is the social science that studies the production distribution, and consumption of goods and services. The Movement for Democracy in Liberia (MODEL was a rebel group in Liberia that became active in March 2003, launching attacks from Côte d'Ivoire. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler can all be modeled as random walks. In Chemistry, a molecule is defined as a sufficiently stable electrically neutral group of at least two Atoms in a definite arrangement held together by Foraging theory is a branch of Behavioral ecology that studies the foraging behavior of animals in response to the environment in which the animal lives Software for Fixed assets management and Stock control developed in 2004.

Specific cases or limits of random walks include the drunkard's walk and Lévy flight. A Lévy flight, named after the French mathematician Paul Pierre Lévy, is a type of Random walk in which the increments are distributed according to a " Random walks are related to the diffusion models and are a fundamental topic in discussions of Markov processes. Diffusion is the net movement of particles (typically molecules from an area of high concentration to an area of low concentration by uncoordinated random movement A Markov process, named after the Russian mathematician Andrey Markov, is a mathematical model for the random evolution of a memoryless system Several properties of random walks, including dispersal distributions, first-passage times and encounter rates, have been extensively studied.

Various different types of random walks are of interest. Often, random walks are assumed to be Markov, but other, more complicated walks are also of interest. A Markov process, named after the Russian mathematician Andrey Markov, is a mathematical model for the random evolution of a memoryless system Some random walks are on graphs, others on the line, in the plane, or in higher dimensions, while some random walks are on groups. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects Group theory is a mathematical discipline the part of Abstract algebra that studies the Algebraic structures known as groups. Random walks also vary with regards to the time parameter. Often, the walk is indexed by the natural numbers, as in X_0,X_1,X_2,\dots. However, some walks take their steps at random times, and in that case the position Xt is defined for t\ge 0.

Contents

One-dimensional random walk

A particularly elementary and concrete random walk is the random walk on the integers \mathbb Z, which starts at S0 = 0 and at each step moves by \pm1 with equal probability. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French To define this walk formally, take independent random variables Z_1,Z_2,\dots, each of which is 1 with probability 1 / 2 and − 1 with probability 1 / 2, and set S_n:=\sum_{j=1}^nZ_j. This sequence {Sn} is called the simple random walk on \mathbb Z.

This walk can be illustrated as follows. Say you flip a fair coin. If it lands on heads, you move one to the right on the number line. If it lands on tails, you move one to the left. So after five flips, you have the possibility of landing on 1, -1, 3, -3, 5, or -5. You can land on 1 by flipping three heads and two tails in any order. There are 10 possible ways of landing on 1. Similarly, there are 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 this example.

Five flips of a fair coin
Five flips of a fair coin

What can we say about the position Sn of the walk after n steps? Of course, it is random, so we cannot calculate it. But we may say quite a bit about its distribution. It is not hard to see that the expectation E(Sn) of Sn is zero. For example, this follows by the additivity property of expectation: E(S_n)=\sum_{j=1}^n E(Z_n)=0. A similar calculation, using the independence of the random variables Zn, shows that E(S_n^2)=n. This hints that E | Sn | , the expected translation distance after n steps, should be of the order of \sqrt{n}. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments In fact,

\lim_{n\to\infty} \frac{E|S_n|}{\sqrt n}= \sqrt{\frac 2{\pi}}.

Suppose we draw a line some distance from the origin of the walk. How many times will the random walk cross the line if permitted to continue walking forever? The following, perhaps surprising theorem is the answer: simple random walk on \mathbb Z will almost surely cross every point an infinite number of times. In Probability theory, one says that an event happens almost surely (a This result has many names: the level-crossing phenomenon, recurrence or the gambler's ruin. The reason for the last name is as follows: if you are a gambler with a finite amount of money playing a fair game against a bank with an infinite amount of money, you will surely lose. The amount of money you have will perform a random walk, and it will almost surely, at some time, reach 0 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 a\,b. The probability that this walk will hit b before -a steps is a \over a+b.

Some of the results mentioned above can be derived from properties of Pascal's triangle. \begin{matrix}&&&&&1\\&&&&1&&1\\&&&1&&2&&1\\&&1&&3&&3&&1\\&1&&4&&6&&4&&1\end{matrix The number of different walks of n steps where each step is + 1 or − 1 is clearly 2n. For the simple random walk, each of these walks are equally likely. In order for Sn to be equal to a number k it is necessary and sufficient that the number of + 1 in the walk exceeds those of − 1 by k. Thus, the number of walks which satisfy Sn = k is precisely the number of ways of choosing (n + k) / 2 elements from an n element set (for this to be non-zero, it is necessary that n + k be an even number), which is an entry in Pascal's triangle denoted by n \choose (n+k)/2. Therefore, the probability that Sn = k is equal to 2^{-n}{n\choose (n+k)/2}. 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 n. Definition The factorial function is formally defined by n!=\prod_{k=1}^n k In Mathematics, Stirling's approximation (or Stirling's formula) is an approximation for large Factorials It is named in honour of James Stirling

This relation with Pascal's triangle is easily demonstrated for small values of n. At zero turns, the only possibility will be to remain at zero. However, at one turn, you can move either to the left or the right of zero, meaning there is one chance of landing on -1 or one chance of landing on 1. At two turns, you examine the turns from before. If you had been at 1, you could move to 2 or back to zero. If you had been at -1, you could move to -2 or back to zero. So there is one chance of landing on -2, two chances of landing on zero, and one chance of landing on 2.

n -5 -4 -3 -2 -1 0 1 2 3 4 5
P[S0 = k] 1
2P[S1 = k] 1 1
22P[S2 = k] 1 2 1
23P[S3 = k] 1 3 3 1
24P[S4 = k] 1 4 6 4 1
25P[S5 = k] 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 walk on \mathbb Z. The central limit theorem (CLT states that the sum of a sufficiently large number of identically distributed independent Random variables each with finite In Probability theory,the law of the iterated logarithm is the name given to several theorems which describe the magnitude of the fluctuations of a Random walk.

Higher dimensions

Random walk in two dimensions.
Random walk in two dimensions.
Random walk in two dimensions with more, and smaller, steps. In the limit, for very small steps, one obtains the Brownian motion.
Random walk in two dimensions with more, and smaller, steps. In the limit, for very small steps, one obtains the Brownian motion. This article is about the physical phenomenon for the stochastic process see Wiener process.

Imagine now a drunkard walking randomly in a city. The city is realistically infinite and arranged in a square grid, and at every intersection, the drunkard chooses one of the four possible routes (including the one he came from) with equal probability. Formally, this is a random walk on the set of all points in the plane with integer coordinates. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics and its applications a coordinate system is a system for assigning an n - Tuple of Numbers or scalars to each point Will the drunkard ever get back to his home from the bar? It turns out that he will. This is the high dimensional equivalent of the level crossing problem discussed above. However, in dimensions 3 and above, this no longer holds. In other words, a drunk bird might forever wander the sky, never finding its nest. The formal terms to describe this phenomenon is that a random walk in dimensions 1 and 2 is recurrent, while in dimension 3 and above it is transient. This was proven by Pólya in 1921, and is discussed in a section of Markov Chains available online. George Pólya (b December 13, 1887 &ndash d September 7, 1985, in Hungarian Pólya György) was a Hungarian Year 1921 ( MCMXXI) was a Common year starting on Saturday (link will display full 1921 calendar of the Gregorian calendar

The trajectory of a random walk is the collection of sites it visited, considered as a set with disregard to when the walk arrived at the point. In one dimension, the trajectory is simply all points between the minimum height the walk achieved and the maximum (both are, on average, on the order of √n). In higher dimensions the set has interesting geometric properties. In fact, one gets a discrete fractal, that is a set which exhibits stochastic self-similarity on large scales, but on small scales one can observe "jugginess" resulting from the grid on which the walk is performed. A fractal is generally "a rough or fragmented geometric shape that can be split into parts each of which is (at least approximately a reduced-size copy of the whole" In Mathematics, a self-similar object is exactly or approximately similar to a part of itself (i The two books of Lawler referenced below are a good source on this topic.

Three random walks in three dimensions.
Three random walks in three dimensions.

Random walk on graphs

Assume now that our city is no longer a perfect square grid. When our drunkard reaches a certain junction he picks between the various available roads with equal probability. Thus, if the junction has seven exits the drunkard will go to each one with probability one seventh. This is a random walk on a graph. Will our drunkard reach his home? It turns out that under rather mild conditions, the answer is still yes. For example, if the lengths of all the blocks are between a and b (where a and b are any two finite positive numbers), then the drunkard will, almost surely, reach his home. Notice that we do not assume that the graph is planar, i. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden e. the city may contain tunnels and bridges. One way to prove this result is using the connection to electrical networks. An electrical network is an interconnection of Electrical elements such as Resistors Inductors Capacitors Transmission lines Voltage Take a map of the city and place a one ohm resistor on every block. The ohm (symbol Ω) is the SI unit of Electrical impedance or in the Direct current case Electrical resistance, Electrical resistance is a ratio of the degree to which an object opposes an Electric current through it measured in Ohms Its reciprocal quantity is Now measure the "resistance between a point and infinity". In other words, choose some number R and take all the points in the electrical network with distance bigger than R from our point and wire them together. This is now a finite electrical network and we may measure the resistance from our point to the wired points. Take R to infinity. The limit is called the resistance between a point and infinity. It turns out that the following is true (an elementary proof can be found in the book by Doyle and Snell):

Theorem: a graph is transient if and only if the resistance between a point and infinity is finite. It is not important which point is chosen if the graph is connected.

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

This characterization of recurrence and transience is very useful, and specifically it allows us to analyze the case of a city drawn in the plane with the distances bounded.

A random walk on a graph is a very special case of a Markov chain. In Mathematics, a Markov chain, named after Andrey Markov, is a Stochastic process with the Markov property. 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 in the other have a very simple connection between them (if the graph is regular, they are just equal). In Mathematics and Statistical mechanics, a Markov process is said to show detailed balance if the transition rates between each pair of states i In Graph theory, a regular graph is a graph where each vertex has the same number of neighbors i 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. The isoperimetric inequality is a geometric Inequality involving the square of the Circumference of a Closed curve in the plane and the In Mathematics, the isoperimetric dimension of a Manifold is a notion of dimension that tries to capture how the large-scale behavior of the manifold resembles Sobolev Sergei L'vovich (Russian Сергей Львович Соболев ( 6 October 1908 - 3 January 1989) was a Russian Jules Henri Poincaré ( 29 April 1854 &ndash 17 July 1912) (ˈʒyl ɑ̃ˈʁi pwɛ̃kaˈʁe was a French Mathematician In Mathematics, Laplace's equation is a Partial differential equation named after Pierre-Simon Laplace who first studied its properties A significant portion of this research was focused on Cayley graphs of finitely generated groups. In Mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph that encodes the structure of a Discrete group. A group ( G, • is a set G closed under a Binary operation • satisfying the following 3 Axioms: In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element For example, the proof of Dave Bayer and Persi Diaconis that 7 riffle shuffles are enough to mix a pack of cards (see more details under shuffle) is in effect a result about random walk on the group Sn, and the proof uses the group structure in an essential way. Dave Bayer is an American Mathematician. He is currently a Professor of Mathematics at Barnard College, Columbia University Persi Warren Diaconis (born January 31, 1945) is an American Mathematician and former professional magician Shuffling is a procedure used to randomize a deck of Playing cards to provide an element of chance in Card games Shuffling is often followed by a Shuffling is a procedure used to randomize a deck of Playing cards to provide an element of chance in Card games Shuffling is often followed by a In Mathematics, the symmetric group on a set X, denoted by S X or Sym( X) is the group whose underlying In many cases these discrete results carry over to, or are derived from Manifolds and Lie groups. A manifold is a mathematical space in which every point has a neighborhood which resembles Euclidean space, but in which the global structure may be In Mathematics, a Lie group (ˈliː sounds like "Lee" is a group which is also a Differentiable manifold, with the property that the group

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 graph itself is random, this topic is called "random walk in random environment" — see the book of Hughes.

Relation to Brownian motion

Simulated steps approximating Brownian motion in two dimensions.
Simulated steps approximating Brownian motion in two dimensions.

Brownian motion is the scaling limit of random walk in dimension 1. This article is about the physical phenomenon for the stochastic process see Wiener process. In Physics or Mathematics, the scaling limit is a term applied to the behaviour of a lattice model in the limit of the lattice spacing going to zero This means that if you take a random walk with very small steps you get an approximation to Brownian motion. To be more precise, if the step size is ε, one needs to take a walk of length L/ε² to approximate a Brownian motion of length L. As the step size tends to 0 (and the number of steps increased comparatively) random walk converges to Brownian motion 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, Brownian motion in several dimensions is the scaling limit of random walk in the same number of dimensions. Note that Brownian motion in the present article refers to the mathematical definition of the term, rather than the actual physical phenomenon of a minute particle diffusing in a fluid. This article is about the physical phenomenon for the stochastic process see Wiener process.

A random walk is a discrete fractal, but Brownian motion is a true fractal, and there is a connection between the two. A fractal is generally "a rough or fragmented geometric shape that can be split into parts each of which is (at least approximately a reduced-size copy of the whole" For example, take a random walk until it hits a circle of radius r times the step length. The average number of steps it performs is r². This fact is the discrete version of the fact that Brownian motion is a fractal of Hausdorff dimension 2 [1]. In Mathematics, the Hausdorff dimension (also known as the Hausdorff–Besicovitch dimension) is an extended non-negative Real number associated In two dimensions, the average number of points the same random walk has on the boundary of its trajectory is r4 / 3. This corresponds to the fact that the boundary of the trajectory of Brownian motion is a fractal of dimension 4/3, a fact predicted by Mandelbrot using simulations but proved only in 2000 (Science, 2000). Benoît B Mandelbrot (born 20 November 1924 is a French mathematician, best known as the father of fractal geometry. 2000 ( MM) was a Leap year that started on Saturday of the Common Era, in accordance with the Gregorian calendar.

Brownian motion enjoys many symmetries random walk does not. Symmetry generally conveys two primary meanings The first is an imprecise sense of harmonious or aesthetically-pleasing proportionality and balance such that it reflects beauty or For example, Brownian motion is invariant to rotations, but random walk is not, since the underlying grid is not (random walk is invariant to rotations by 90 degrees, but Brownian motion is invariant to rotations by, for example, 17 degrees too). This means that in many cases, problems on random walk are easier to solve by translating them to Brownian motion, 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 Brownian motion can be coupled, namely manifested on the same probability space in a dependent way that forces them to be quite close. This article is about the physical phenomenon for the stochastic process see Wiener process. In Mathematics, coupling is a proof technique that allows one to compare two unrelated variables by "forcing" them to be related in some way The simplest such coupling is the Skorokhod embedding, but other, more precise couplings exist as well.

The convergence of a random walk toward the Brownian motion is controlled by the central limit theorem. The central limit theorem (CLT states that the sum of a sufficiently large number of identically distributed independent Random variables each with finite For a particle in a known fixed position at t=0, the 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:

\sigma^2 = \frac{t}{\delta t}\,\epsilon^2, where t is the time elapsed since the start of the random walk, ε is the size of a step of the random walk, and δt is the time elapsed between two successive steps. In Probability theory, to say that two events are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other The normal distribution, also called the Gaussian distribution, is an important family of Continuous probability distributions applicable in many fields In Probability theory and Statistics, the variance of a Random variable, Probability distribution, or sample is one measure of

This corresponds to the Green function of the diffusion equation that controls the Brownian motion, which demonstrates that, after a large number of steps, the random walk converges toward a Brownian motion. The diffusion equation is a Partial differential equation which describes density fluctuations in a material undergoing Diffusion.

In 3D, the variance corresponding to the Green's function 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 Brownian motion toward which the random walk converges after a large number of steps:

D = \frac{\epsilon^2}{6 \delta t} (valid only in 3D)

Remark: 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. In Mathematics, Green's function is a type of function used to solve inhomogeneous Differential equations subject to boundary conditions The variance associated to each component Rx, Ry or Rz is only one third of this value (still in 3D).

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 difficult to analyze than the usual random walk — some notoriously so. For example

Applications

The following are the applications of random walk:

In all these cases, random walk is often substituted for Brownian motion.

Probabilistic interpretation

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,..., for some number \,0 < p < 1, \,P_{i,i+1}=p=1-P_{i,i-1}. In Mathematics, a Markov chain, named after Andrey Markov, is a Stochastic process with the Markov property. We can call it a random walk because we may think of it as being a model for an individual walking on a straight line who at each point of time either takes one step to the right with probability p or one step to the left with probability 1 − p.

A random walk is a simple stochastic process. A stochastic process, or sometimes random process, is the counterpart to a deterministic process (or Deterministic system) in Probability theory.

See also

References

  1. ^ Hence the drunkard's random walk would eventually cover all of the city streets (2 Euclidean dimensions) and he will eventually return home, whereas the bird taking a 'random walk' flight through the air (3 Euclidean dimensions) will not cover all space, and will not return to their starting point. Diffusion-limited aggregation (DLA is the process whereby particles undergoing a Random walk due to Brownian motion cluster together to form aggregates of such particles In Probability theory,the law of the iterated logarithm is the name given to several theorems which describe the magnitude of the fluctuations of a Random walk. In Probability theory, a martingale is a Stochastic process (i In Mathematics, a Markov chain, named after Andrey Markov, is a Stochastic process with the Markov property. Quantum random walks are a Mathematical model for Quantum mechanical systems that correspond to classical Random walks In Mathematics, the Wiener process is a continuous-time Stochastic process named in honor of Norbert Wiener.

Bibliography

Chapter 3 of this book contains a thorough discussion of random walks, including advanced results, using only elementary tools.

External links

Dictionary

random walk

-noun

  1. (mathematics) A stochastic path consisting of a series of sequential movements, the direction (and sometime length) of which is chosen at random
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic