| Part of a series onstatistics |
| Probability theory |
|---|
 |
Inmathematics, arandom walk, sometimes known as adrunkard's walk, is astochastic process that describes a path that consists of a succession ofrandom steps on somemathematical space.
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 equalprobability. Other examples include the path traced by amolecule as it travels in a liquid or a gas (seeBrownian motion), the search path of aforaging animal, or the price of a fluctuatingstock and the financial status of agambler. Random walks have applications toengineering and many scientific fields includingecology,psychology,computer science,physics,chemistry,biology,economics, andsociology. The termrandom walk was first introduced byKarl Pearson in 1905.[1]
Realizations of random walks can be obtained byMonte Carlo simulation.[2]
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 asimple random walk, the location can only jump to neighboring sites of the lattice, forming alattice path. In asimple 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 thed-dimensional integer lattice (sometimes called the hypercubic lattice).[3]
If the state space is limited to finite dimensions, the random walk model is called asimple 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.[4]
An elementary example of a random walk is the random walk on theinteger 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 Theseries is called thesimple 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.Theexpectation 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, theexpected translation distance aftern steps, should beof the order of. In fact,[5]
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 will cross every point an infinite number of times. This result has many names: thelevel-crossing phenomenon,recurrence or thegambler's ruin. The reason for the last name is as follows: a gambler with a finite amount of money will eventually lose when playinga 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.
Ifa andb are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hitsb or −a isab. The probability that this walk will hitb before −a is, which can be derived from the fact that simple random walk is amartingale. And these expectations and hitting probabilities can be computed in in the general one-dimensional random walk Markov chain.
Some of the results mentioned above can be derived from properties ofPascal's triangle. The number of different walks ofn steps where each step is +1 or −1 is 2n. For the simple random walk, each of these walks is equally likely. In order forSn to be equal to a numberk it is necessary and sufficient that the number of +1 in the walk exceeds those of −1 byk. It follows +1 must appear (n + k)/2 times amongn steps of a walk, hence the number of walks which satisfy equals the number of ways of choosing (n + k)/2 elements from ann element set,[6] denoted. For this to have meaning, it is necessary thatn + k be an even number, which impliesn andk are either both even or both odd. Therefore, the probability that is equal to. By representing entries of Pascal's triangle in terms offactorials and usingStirling's formula, one can obtain good estimates for these probabilities for large values of.
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 ofn. 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 |
Thecentral limit theorem and thelaw of the iterated logarithm describe important aspects of the behavior of simple random walks on. In particular, the former entails that asn increases, the probabilities (proportional to the numbers in each row) approach anormal distribution.
To be precise, knowing that,and usingStirling's formula one has
Fixing the scaling, for fixed, and using the expansion when vanishes, it follows
taking the limit (and observing that corresponds to the spacing of the scaling grid) one finds the gaussian density. Indeed, for a absolutely continuous random variable with density it holds, with corresponding to an infinitesimal spacing.
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.[7][8]
A one-dimensionalrandom walk can also be looked at as aMarkov chain whose state space is given by the integers For some numberp satisfying, the transition probabilities (the probabilityPi,j of moving from statei to statej) are given by
The heterogeneous random walk draws in each time step a random number that determines the local jumping probabilities and then a random number that determines the actual jump direction. The main question is the probability of staying in each of the various sites after jumps, and in the limit of this probability when is very large.
In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discretefractal, that is, a set which exhibits stochasticself-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 towhen 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 theplane withintegercoordinates.
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 1921George Pólya proved that the personalmost 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%.[9] The mathematicianShizuo 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".[10]
The probability of recurrence is in general, which can be derived bygenerating functions[11] or Poisson process.[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?"[13] 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.[14]
The asymptotic function for a two-dimensional random walk as the number of steps increases is given by aRayleigh distribution. The probability distribution is a function of the radius from the origin and the step length is constant for each step. Here, the step length is assumed to be 1, N is the total number of steps and r is the radius from the origin.[15]
AWiener process is a stochastic process with similar behavior toBrownian motion, the physical phenomenon of a minute particle diffusing in a fluid. (Sometimes theWiener process is called "Brownian motion", although this is strictly speaking a confusion of a model with the phenomenon being modeled.)
A Wiener process is thescaling limit 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 lengthL/ε2 to approximate a Wiener length ofL. 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, ifB is the space of all paths of lengthL with the maximum topology, and ifM is the space of measure overB with the norm topology, then the convergence is in the spaceM. 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 radiusr times the step length. The average number of steps it performs isr2.[citation needed] This fact is thediscrete version of the fact that a Wiener process walk is a fractal ofHausdorff dimension 2.[citation needed]
In two dimensions, the average number of points the same random walk has on theboundary of its trajectory isr4/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 byMandelbrot using simulations but proved only in 2000byLawler,Schramm andWerner.[16]
A Wiener process enjoys manysymmetries 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 andWiener process can becoupled, namely manifested on the same probability space in a dependent way that forces them to be quite close. The simplest such coupling is theSkorokhod embedding, but there exist more precise couplings, such asKomlós–Major–Tusnády approximation theorem.
The convergence of a random walk toward the Wiener process is controlled by thecentral limit theorem, and byDonsker's theorem. For a particle in a known fixed position att = 0, the central limit theorem tells us that after a large number ofindependent steps in the random walk, the walker's position is distributed according to anormal distribution of totalvariance:
wheret 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 theGreen's function of thediffusion 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 theGreen'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).
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:[17]
For 1D:[18]
A random walk having a step size that varies according to anormal distribution is used as a model for real-world time series data such as financial markets.
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 vs is the starting value of the random walk, the expected value aftern steps will be vs +nμ.
For the special case where μ is equal to zero, aftern steps, the translation distance's probability distribution is given byN(0,nσ2), whereN() 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:
but we have the distribution for the sum of two independent normally distributed random variables,Z =X +Y, is given by(see here).
In our case,μX = μY = 0 andσ2X = σ2Y = σ2 yieldBy induction, forn steps we haveFor steps distributed according to any distribution with zero mean and a finite variance (not necessarily just a normal distribution), theroot mean square translation distance aftern steps is (seeBienaymé's identity)
But for the Gaussian random walk, this is just the standard deviation of the translation distance's distribution aftern 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 aftern steps will fall between. Likewise, there is 50% probability that the translation distance aftern steps will fall between.
The number of distinct sites visited by a single random walker has been studied extensively for square and cubic lattices and for fractals.[19][20] This quantity is useful for the analysis of problems of trapping and kinetic reactions. It is also related to the vibrational density of states,[21][22] diffusion reactions processes[23]and spread of populations in ecology.[24][25]
Theinformation rate of a Gaussian random walk with respect to the squared error distance, i.e. its quadraticrate distortion function, is given parametrically by[26]where. Therefore, it is impossible to encode using abinary code of less thanbits and recover it with expected mean squared error less than. On the other hand, for any, there exists an large enough and abinary code of no more than distinct elements such that the expected mean squared error in recovering from this code is at most.
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(February 2013) (Learn how and when to remove this message) |
As mentioned, the range of natural phenomena which have been subject to attempts at description by some flavour of random walks is considerable. This is particularly the case in the fields of physics,[27][28]chemistry,[29]materials science,[30][31] and biology.[32][33][34]
The following are some specific applications of random walks:
A number of types ofstochastic processes have been considered that are similar to the pure random walks but where the simple structure is allowed to be more generalized. Thepure structure can be characterized by the steps being defined byindependent and identically distributed random variables. Random walks can take place on a variety of spaces, such asgraphs, the integers, the real line, the plane or higher-dimensional vector spaces, oncurved surfaces or higher-dimensionalRiemannian manifolds, and ongroups. It is also possible to define random walks which take their steps at random times, and in that case, the positionX
t has to be defined for all timest ∈ [0, +∞). Specific cases or limits of random walks include theLévy flight anddiffusion models such asBrownian motion.
A random walk of lengthk on a possibly infinitegraphG with a root0 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 lengthk starting atv ends atw.In particular, ifG is a graph with root0, is the probability that a-step random walk returns to0.
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,[45] 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.[46]
An example of a case where the person will reach his home almost surely is when the lengths of all the blocks are betweena andb (wherea andb are any two finite positive numbers). Notice that we do not assume that the graph isplanar, i.e. the city may contain tunnels and bridges. One way to prove this result is using the connection toelectrical networks. Take a map of the city and place a oneohmresistor on every block. Now measure the "resistance between a point and infinity". In other words, choose some numberR and take all the points in the electrical network with distance bigger thanR 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. TakeR to infinity. The limit is called theresistance 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 oftransience 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 aMarkov chain. Unlike a general Markov chain, random walk on a graph enjoys a property calledtime symmetry orreversibility. Roughly speaking, this property, also called the principle ofdetailed 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 isregular, 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 toisoperimetric inequalities, see morehere, functional inequalities such asSobolev andPoincaré inequalities and properties of solutions ofLaplace's equation. A significant portion of this research was focused onCayley graphs offinitely generated groups. In many cases these discrete results carry over to, or are derived frommanifolds andLie groups.
In the context ofrandom graphs, particularly that of theErdős–Rényi model, analytical results to some properties of random walkers have been obtained. These include the distribution of first[47] and last hitting times[48] 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 byAldous 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.[49] 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 of lengthn on is the randomn-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,[51] while in higher dimension it grows beyond all bounds.This model has often been used inpolymer physics (since the 1960s).
Random walk chosen to maximizeentropy rate, has much stronger localization properties.
Random walks where the direction of movement at one time iscorrelated with the direction of movement at the next time. It is used to model animal movements.[56][57]
