formulasearchengine - User contributions [en]

Main Page

2014-08-10T21:12:35Z

ChelseyBianco:

{{More footnotes|date=June 2009}}
[[Image:Random Walk example.svg|thumb|right|420px|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''' is a [[mathematical]] formalization of a path that consists of a succession of [[random]] steps. 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 [[random walk hypothesis|stock]] and the financial status of a [[gambler]] can all be ''modeled'' as random walks, although they may not be truly random in reality. The term ''random walk'' was first introduced by [[Karl Pearson]] in 1905.<ref>Pearson, K. (1905). ''The Problem of the Random Walk.'' [[Nature (journal)|Nature]]. '''72''', 294.</ref> Random walks have been used in many fields: [[ecology]], [[economics]], [[psychology]], [[computer science]], [[physics]], [[chemistry]], and [[biology]].<ref name=[1]>Van Kampen N. G., Stochastic Processes in Physics and Chemistry, revised and enlarged edition (North-Holland, Amsterdam) 1992.</ref><ref name=[2]>Redner S., A Guide to First-Passage Process (Cambridge University Press, Cambridge, UK) 2001.</ref><ref name=[3]>Goel N. W. and Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.</ref><ref name=[4]>Doi M. and Edwards S. F., The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986</ref><ref name=[4c]>De Gennes P. G., Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca and London) 1979.</ref><ref name=[5]>Risken H., The Fokker–Planck Equation (Springer, Berlin) 1984.</ref><ref name=[6]>Weiss G. H., Aspects and Applications of the Random Walk (North-Holland, Amsterdam) 1994.</ref><ref name=[7]>Cox D. R., Renewal Theory (Methuen, London) 1962.</ref> Random walks explain the observed behaviors of processes in these fields, and thus serve as a fundamental [[Statistical model|model]] for the recorded [[Stochastic process|stochastic activity]].

Various different types of random walks are of interest. Often, random walks are assumed to be [[Markov chain]]s or [[Markov process]]es, but other, more complicated walks are also of interest. Some random walks are on [[graph theory|graphs]], others on the line, in the plane, or in higher dimensions, while some random walks are on [[group theory|groups]]. Random walks also vary with regard to the time parameter. Often, the walk is in discrete time, and indexed by the natural numbers, as in <math>X_0,X_1,X_2,\dots</math>. However, some walks take their steps at random times, and in that case the position <math>X_t</math> is defined for the continuum of times <math>t\ge 0</math>. Specific cases or limits of random walks include the [[Lévy flight]]. Random walks are related to the [[diffusion]] models and are a fundamental topic in discussions of [[Markov process]]es. Several properties of random walks, including dispersal distributions, first-passage times and encounter rates, have been extensively studied.

==Lattice random walk==
{{Refimprove section|date=April 2011|reason=no sources in this entire section}}
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. In ''' simple symmetric random walk''' on a locally finite lattice, the probabilities of the location jumping to each one of its immediate neighbours are the same. The best studied example is of random walk on the ''d''-dimensional integer lattice (sometimes called the hypercubic lattice) <math>\mathbb Z^d</math>.<ref>Révész Pal, Random walk in random and non random environments, World Scientific, 1990</ref>

===One-dimensional random walk===
An elementary example of a random walk is the random walk on the [[integer]] number line, <math>\mathbb Z</math>, 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 1, −1, 3, −3, 5, or −5. With five flips, three heads and two tails, in any order, 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.

[[Image:Flips.svg|thumb|800px|center|All possible random walk outcomes after 5 flips of a fair coin]]
[[Image:random walk 2500.svg|right|thumb|280px|Random walk in two dimensions ([http://upload.wikimedia.org/wikipedia/commons/f/f3/Random_walk_2500_animated.svg animated version])]]
[[Image:random walk 25000 not animated.svg|right|thumb|280px|Random walk in two dimensions with 25 thousand steps ([http://upload.wikimedia.org/wikipedia/commons/c/cb/Random_walk_25000.svg animated version])]]
[[Image:Random walk 2000000.png|right|thumb|280px|Random walk in two dimensions with two million even smaller steps. This image was generated in such a way that points that are more frequently traversed are darker. In the limit, for very small steps, one obtains [[Brownian motion]].]]

To define this walk formally, take independent random variables <math>Z_1, Z_2,\dots</math>, where each variable is either 1 or −1, with a 50% probability for either value, and set <math>S_0 = 0\,\!</math> and <math>S_n =\sum_{j=1}^nZ_j.</math> The [[Series (mathematics)|series]] <math>\{S_n\}\,\!</math> is called the '''simple random walk on <math>\mathbb Z</math>'''. This series (the sum of the sequence of −1s and 1s) gives the distance walked, if each part of the walk is of length one.
The [[expected value|expectation]] <math>E(S_n)\,\!</math> of <math>S_n\,\!</math> 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:

:<math>E(S_n)=\sum_{j=1}^n E(Z_j)=0.</math>

A similar calculation, using the independence of the random variables and the fact that <math>E(Z_n^2)=1</math>, shows that:

:<math>E(S_n^2)=\sum_{j=1}^n E(Z_j^2)+ \sum_{i=1}^n \sum_{j=1}^n 2E(Z_j Z_i)=n.</math>

This hints that <math>E(|S_n|)\,\!</math>, the [[expected value|expected]] translation distance after ''n'' steps, should be [[Big O notation|of the order of]] <math>\sqrt n</math>. In fact,{{citation needed|date=April 2013}}

:<math>\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac 2{\pi}}.</math>

This result shows that diffusion is ineffective for mixing because of the way the square root behaves for large <math>N</math>.{{citation needed|date=April 2013}}

How many times will a random walk cross a boundary line if permitted to continue walking forever? A simple random walk on <math>\mathbb Z</math> 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 <math>a/(a+b)</math>, which can be derived from the fact that simple random walk is a [[martingale (probability theory)|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 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''. The number of walks which satisfy <math>S_n=k</math> is equally the number of ways of choosing (''n'' + ''k'')/2 elements from an ''n'' element set,{{citation needed|date=September 2013}} denoted <math>n \choose (n+k)/2</math>. For this to be non-zero, it is necessary that ''n'' + ''k'' be an even number. Therefore, the probability that <math>S_n=k</math> is equal to <math>2^{-n}{n\choose (n+k)/2}</math>. By representing entries of Pascal's triangle in terms of [[factorial]]s and using [[Stirling formula|Stirling's formula]], one can obtain good estimates for these probabilities for large values of <math>n</math>.

If the space is confined to <math>\mathbb Z</math>+ 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.


{| class="wikitable" style="text-align:center"
|-
! k
! style="width:2em" | −5
! style="width:2em" | −4
! style="width:2em" | −3
! style="width:2em" | −2
! style="width:2em" | −1
! style="width:2em" | 0
! style="width:2em" | 1
! style="width:2em" | 2
! style="width:2em" | 3
! style="width:2em" | 4
! style="width:2em" | 5
|-
| <math>P[S_0=k]</math>
|
|
|
|
|
| 1
|
|
|
|
|
|-
| <math>2P[S_1=k]</math>
|
|
|
|
| 1
|
| 1
|
|
|
|
|-
| <math>2^2P[S_2=k]</math>
|
|
|
| 1
|
| 2
|
| 1
|
|
|
|-
| <math>2^3P[S_3=k]</math>
|
|
| 1
|
| 3
|
| 3
|
| 1
|
|
|-
| <math>2^4P[S_4=k]</math>
|
| 1
|
| 4
|
| 6
|
| 4
|
| 1
|
|-
| <math>2^5P[S_5=k]</math>
| 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 <math>\mathbb Z</math>. 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<ref>{{cite journal |author= M. Kotani, [[Toshikazu Sunada|T. Sunada]] |year= 2003 |title= Spectral geometry of crystal lattices |journal= Contemporary. Math.|volume= 338 |pages= 271–305 }}</ref>
.<ref>{{cite journal |author= M. Kotani, [[Toshikazu Sunada|T. Sunada]] |year= 2006 |title= Large deviation and the tangent cone at infinity of a crystal lattice |journal= Math. Z. |volume= 254 |pages= 837–870 }}</ref>

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

===Higher dimensions===
[[Image:Walk3d 0.png|right|thumb|280px|Three random walks in three dimensions]]
Imagine now a drunkard walking randomly in an idealized city. The city is effectively 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 (mathematics)|plane]] with [[integer]] [[Coordinate system|coordinates]].

Will the drunkard ever get back to his home from the bar? This is the 2-dimensional equivalent of the level crossing problem discussed above. It turns out that he [[almost surely]] will 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%.<ref>[http://mathworld.wolfram.com/PolyasRandomWalkConstants.html Pólya's Random Walk Constants]</ref>

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 "jaggedness" resulting from the grid on which the walk is performed. The two books of Lawler referenced below are a good source on this topic.

===Relation to Wiener process===

[[Image:Brownian hierarchical.png|thumb|right|196px|Simulated steps approximating a Wiener process in two dimensions]]

A [[Wiener process]] is a stochastic process with similar behaviour 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 [[map-territory relation|confusion of a model with the phenomenon being modeled]].)

A Wiener process is the [[scaling limit]] of random walk in dimension 1.{{citation needed|date=April 2012}} 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 process walk of length ''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|date=April 2012}} This fact is the ''discrete version'' of the fact that a Wiener process walk is a fractal of [[Hausdorff dimension]] 2.{{citation needed|date=April 2012}}

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 [[Benoît Mandelbrot|Mandelbrot]] using simulations but proved only in 2000
by [[Greg Lawler|Lawler]], [[Oded Schramm|Schramm]] and [[Wendelin Werner|Werner]].<ref>Dana Mackenzie, ''[http://www.sciencemag.org/content/290/5498/1883.full Taking the Measure of the Wildest Dance on Earth]'', Science, Vol. 290, no. 5498, pp. 1883–1884.</ref>

A Wiener process enjoys many [[symmetry|symmetries]] random walk does not. For example, a Wiener process walk 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 Wiener processes are 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 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 [[Coupling (probability)|''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 other, more precise couplings exist as well.

The convergence of a random walk toward the Wiener process is controlled by the [[central limit theorem]]. For a particle in a known fixed position at ''t'' = 0, the theorem tells us that after a large number of [[statistical independence|independent]] steps in the random walk, the walker's position is distributed according to a [[normal distribution]] of total [[variance]]:

:<math>\sigma^2 = \frac{t}{\delta t}\,\varepsilon^2,</math>

where ''t'' is the time elapsed since the start of the random walk, <math>\varepsilon</math> is the size of a step of the random walk, and <math>\delta t</math> is the time elapsed between two successive steps.

This corresponds to the [[Green's function|Green function]] of the [[diffusion equation]] that controls the Wiener process, which demonstrates 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:

:<math>\sigma^2 = 6\,D\,t</math>

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:

:<math>D = \frac{\varepsilon^2}{6 \delta t}</math> (valid only in 3D)

Remark: the two expressions of the variance above correspond to the distribution associated to the vector <math>\vec R</math> that links the two ends of the random walk, in 3D. The variance associated to each component <math>R_x</math>, <math>R_y</math> or <math>R_z</math> is only one third of this value (still in 3D).

==Gaussian random walk==
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 <math>\Phi^{-1}(z,\mu,\sigma)</math> where 0 ≤ ''z'' ≤ 1 is a uniformly distributed random number, and μ and σ are the mean and standard deviations of the normal distribution, respectively.

If μ is nonzero, the random walk will vary about a linear trend. If vs is the starting value of the random walk, the expected value after ''n'' steps will be vs + ''n''μ.

For the special case where μ is equal to zero, after ''n'' steps, the translation distance's probability distribution is given by ''N''(0, ''n''σ2), where ''N''() is the notation for the normal distribution, ''n'' is the number of steps, and σ is from the inverse cumulative normal distribution as given above.

Proof: The Gaussian random walk can be thought of as the sum of a series of independent and identically distributed random variables, Xi from the inverse cumulative normal distribution with mean equal zero and σ of the original inverse cumulative normal distribution:
: Z = <math>\sum_{i=0}^n {X_i}</math>,

but we have the distribution for the sum of two independent normally distributed random variables, Z = X + Y, is given by
: ''N''(μX + μY, σ2X + σ2Y) [[Sum of normally distributed random variables|(see here)]].
In our case, μX = μY = 0 and σ2X = σ2Y = σ2 yield
: ''N''(0, 2σ2)
By induction, for ''n'' steps we have
: Z ~ ''N''(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
:<math>\sqrt{E|S_n^2|} = \sigma \sqrt{n}.</math>

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 ± σ<math>\sqrt{n}</math>. Likewise, there is 50% probability that the translation distance after ''n'' steps will fall between ± 0.6745σ<math>\sqrt{n}</math>.

===Anomalous diffusion===

In disordered systems such as porous media and fractals <math>\sigma^2</math> may not be proportional to <math>t</math> but to <math>t^{2 / d_w}</math>. The exponent <math>d_w</math> is called the [[anomalous diffusion]] exponent and can be larger or smaller than 2.<ref>D. Ben-Avraham and S. Havlin, ''[http://havlin.biu.ac.il/Shlomo%20Havlin%20books_d_r.php Diffusion and Reactions in Fractals and Disordered Systems]'', Cambridge University Press, 2000.</ref> [[Anomalous diffusion]] may also be expressed as σr2 ~ Dtα where α is the anomaly parameter.

===Number of Distinct Sites===
The number of distinct sites visited by a single random
walker <math>S(t)</math> has been studied extensively for square and
cubic lattices and for fractals
<ref name="WeissRubin1982">{{cite journal|last1=Weiss|first1=George H.|last2=Rubin|first2=Robert J.|title=Random Walks: Theory and Selected Applications|volume=52|year=1982|pages=363–505|issn=19344791|doi=10.1002/9780470142769.ch5}}</ref>
.<ref name="BlumenKlafter1986">{{cite journal|last1=Blumen|first1=A.|last2=Klafter|first2=J.|last3=Zumofen|first3=G.|title=Models for Reaction Dynamics in Glasses|volume=1|year=1986|pages=199–265|issn=0924-459X|doi=10.1007/978-94-009-4650-7_5|bibcode = 1986PCMLD...1..199B }}</ref> This quantity is useful
for the analysis of problems of trapping and kinetic reactions.
It is also related to the vibrational density of states
<ref name="AlexanderOrbach1982">{{cite journal|last1=Alexander|first1=S.|last2=Orbach|first2=R.|title=Density of states on fractals : " fractons "|journal=Journal de Physique Lettres|volume=43|issue=17|year=1982|pages=625–631|issn=0302-072X|doi=10.1051/jphyslet:019820043017062500}}</ref>
,<ref name="RammalToulouse1983">{{cite journal|last1=Rammal|first1=R.|last2=Toulouse|first2=G.|title=Random walks on fractal structures and percolation clusters|journal=Journal de Physique Lettres|volume=44|issue=1|year=1983|pages=13–22|issn=0302-072X|doi=10.1051/jphyslet:0198300440101300}}</ref> diffusion reactions processes
<ref>{{cite journal|last=Smoluchowski|first=M.V.|journal=Z. Phys. Chem | number=29| pages=129–168|year=1917|title=Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen}},{{cite book|last=Rice|first=S.A.|title=Diffusion-Limited Reactions|url=http://books.google.com/books?id=sWiyspAjelsC&pg=PP2|accessdate=13 August 2013|series=Comprehensive Chemical Kinetics|volume=25|date=1 March 1985|publisher=Elsevier|isbn=0-444-42354-0}}</ref>
and spread of populations in ecology.<ref name="Skellam1951">{{cite journal|last1=Skellam|first1=J. G.|title=Random Dispersal in Theoretical Populations|journal=Biometrika|volume=38|issue=1/2|year=1951|pages=196|issn=00063444|doi=10.2307/2332328}},{{cite journal|last1=Skellam|first1=J. G.|title=Studies in Statistical Ecology: I. Spatial Pattern|journal=Biometrika|volume=39|issue=3/4|year=1952|pages=346|issn=00063444|doi=10.2307/2334030}}</ref>
The generalization of this problem to the number of
distinct sites visited by <math>N</math> random walkers, <math>S_N(t)</math>, has recently
been studied for d-dimensional Euclidean lattices.<ref name="LarraldeTrunfio1992">{{cite journal|last1=Larralde|first1=Hernan|last2=Trunfio|first2=Paul|last3=Havlin|first3=Shlomo|last4=Stanley|first4=H. Eugene|last5=Weiss|first5=George H.|title=Territory covered by N diffusing particles|journal=Nature|volume=355|issue=6359|year=1992|pages=423–426|issn=0028-0836|doi=10.1038/355423a0|bibcode = 1992Natur.355..423L }},{{cite journal|last1=Larralde|first1=Hernan|last2=Trunfio|first2=Paul|last3=Havlin|first3=Shlomo|last4=Stanley|first4=H.|last5=Weiss|first5=George|title=Number of distinct sites visited by N random walkers|journal=Physical Review A|volume=45|issue=10|year=1992|pages=7128–7138|issn=1050-2947|doi=10.1103/PhysRevA.45.7128|bibcode = 1992PhRvA..45.7128L }}; for insights regarding the problem of N random walkers, see {{cite journal|last1=Shlesinger|first1=Michael F.|title=New paths for random walkers|journal=Nature|volume=355|issue=6359|year=1992|pages=396–397|issn=0028-0836|doi=10.1038/355396a0|bibcode = 1992Natur.355..396S }} and the color artwork illustrating the article.</ref> The number of distinct sites visited by N walkers
is not simply related to the number of distinct sites visited
by each walker.

==Applications==
{{Refimprove section|date=February 2013}}
[[File:Antony Gormley Quantum Cloud 2000.jpg|thumb|[[Antony Gormley]]'s ''[[Quantum Cloud]]'' sculpture in [[London]] was designed by a computer using a random walk algorithm.]]
The following are some applications of random walk:
*In [[economics]], the "[[Random Walk Hypothesis|random walk hypothesis]]" is used to model shares prices and other factors. Empirical studies found some deviations from this theoretical model, especially in short term and long term correlations. See [[share price]]s.
*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]] [[Motion (physics)|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 [[theoretical biology|mathematical ecology]], random walks are used to describe individual animal movements, to empirically support processes of [[diffusion|biodiffusion]], and occasionally to model [[population dynamics]].
*In [[polymer physics]], random walk describes an [[ideal chain]]. It is the simplest model to study [[polymers]].
*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 [[Mathematical analysis|analysis]] and [[combinatorics]].
* In [[computer science]], random walks are used to estimate the size of the [[www|Web]]. In the [http://www2006.org/ World Wide Web conference-2006], bar-yossef et al. published their findings and algorithms for the same.
* In [[Segmentation (image processing)|image segmentation]], random walks are used to determine the labels (i.e., "object" or "background") to associate with each pixel.<ref>Leo Grady (2006): [http://www.cns.bu.edu/~lgrady/grady2006random.pdf "Random Walks for Image Segmentation"], ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', pp. 1768–1783, Vol. 28, No. 11</ref> This algorithm is typically referred to as the [[random walker (computer vision)|random walker]] segmentation algorithm.
In all these cases, random walk is often substituted for Brownian motion.
*In [[human brain|brain research]], random walks and reinforced random walks are used to model cascades of neuron firing in the brain.
*In vision science, [[fixational eye movement]]s are well described by a random walk.<ref>Ralf Engbert, Konstantin Mergenthaler, Petra Sinn, and Arkady Pikovsk: [http://www.pnas.org/content/early/2011/08/17/1102730108.full.pdf "An integrated model of ﬁxational eye movements and microsaccades"]</ref>
*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.<ref>[http://web.archive.org/web/20041210231937/http://oz.ss.uci.edu/237/readings/EBRW_nosofsky_1997.pdf Nosofsky, 1997]</ref>
*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|date=April 2012}}
:*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 (mathematics)|matrix]] of zeros and ones was the first major problem tackled using this approach.{{citation needed|date=April 2012}}
*Random walks have also been used to [[Sampling (statistics)|sample]] massive online graphs such as [[online social network]]s.
*In [[wireless networking]], a random walk is used to model node movement.{{citation needed|date=April 2012}}
*[[bacterial motility|Motile bacteria]] engage in a [[biased random walk (biochemistry)|biased random walk]].{{citation needed|date=April 2012}}
*Random walks are used to model [[gambling]].{{citation needed|date=April 2012}}
*In physics, random walks underlie the method of [[Fermi estimation]].{{citation needed|date=April 2012}}
*On the web, the Twitter website uses Random walks to make suggestions of who to follow <ref name="twitterwtf">Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter], Proceedings of the 22nd international conference on World Wide Web</ref>

==Variants of random walks==

A number of types of [[stochastic process]]es have been considered that are similar to the pure random walks but where the simple structure is allowed to be more generalized. The ''pure'' structure can be characterized by the steps being defined by [[independent and identically distributed random variables]].

===Random walk on graphs===

A random walk of length ''k'' on a possibly infinite [[Graph (mathematics)|graph]] ''G'' with a root ''0'' is a stochastic process with random variables <math>X_1,X_2,\dots,X_k</math> such that <math>X_1=0</math> and
<math> {X_{i+1}} </math> is a vertex chosen uniformly at random from the neighbors of <math>X_i</math>.
Then the number <math>p_{v,w,k}(G)</math> 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'', <math>p_{0,0,2k}</math> is the probability that a <math>2k</math>-step random walk returns to ''0''.

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 graph|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 (unit)|ohm]] [[electrical resistance|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 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]]. 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 graph|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 [[isoperimetry|isoperimetric inequalities]], see more [[Isoperimetric dimension#Consequences of isoperimetry|here]], functional inequalities such as [[Sobolev inequality|Sobolev]] and [[Poincaré inequality|Poincaré]] inequalities and properties of solutions of [[Laplace's equation]]. A significant portion of this research was focused on [[Cayley graph]]s of [[Glossary of group theory|finitely generated]] [[Group (mathematics)|groups]]. For example, the proof of [[Dave Bayer]] and [[Persi Diaconis]] that 7 [[shuffle|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 [[symmetric group|''Sn'']], and the proof uses the group structure in an essential way. In many cases these discrete results carry over to, or are derived from [[manifold]]s and [[Lie group]]s.

A good reference for random walk on graphs is the online book by [http://stat-www.berkeley.edu/users/aldous/RWG/book.html Aldous and Fill]. For groups see the book of Woess.
If the transition kernel <math>p(x,y)</math> is itself random (based on an environment <math>\omega</math>) then the random walk is called a "random walk in random environment". When the law of the random walk includes the randomness of <math>\omega</math>, the law is called the annealed law; on the other hand, if <math>\omega</math> is seen as fixed, the law is called a quenched law. See the book of Hughes 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 [http://arxiv.org/abs/0810.4113 maximal entropy random walk (MERW)] we want all paths to be equally probable, or in other words: for each two vertexes, each path of given length is equally probable. This random walk has much stronger localization properties.

===Self-interacting random walks===
There are a number of interesting models of random paths in which each step depends on the past in a complicated manner. All are more complex for solving analytically than the usual random walk; still, the behavior of any model of a random walker is obtainable using computers. Examples include:
* The [[self-avoiding walk]] (Madras and Slade 1996).<ref>Neal Madras and Gordon Slade (1996), ''The Self-Avoiding Walk'', Birkhäuser Boston. ISBN 0-8176-3891-1.</ref>
The self-avoiding walk of length n on Z^d is the random n-step path which starts at the origin, makes transitions only between adjacent sites in Z^d, never revisits 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,<ref>{{citation|author=S. Hemmer and P. C. Hemmer|title=An average self-avoiding random walk on the square lattice lasts 71 steps|journal=J. Chem. Phys.| volume=81| pages=584| year=1984| doi=10.1063/1.447349|bibcode = 1984JChPh..81..584H }}</ref> 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]] (Gregory Lawler).<ref>Gregory Lawler (1996). ''Intersection of random walks'', Birkhäuser Boston. ISBN 0-8176-3892-X.</ref><ref>Gregory Lawler, ''Conformally Invariant Processes in the Plane'', [http://www.math.cornell.edu/~lawler/book.ps book.ps].</ref>
* The [[reinforced random walk]] (Robin Pemantle 2007).<ref>Robin Pemantle (2007), [http://www.emis.de/journals/PS/images/getdoc9b04.pdf?id=432&article=94&mode=pdf A survey of random processes with reinforcement]''.</ref>
* The [[exploration process]].{{citation needed|date=April 2012}}
* The [[multiagent random walk]].<ref>Alamgir, M and von Luxburg, U (2010). [http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/AlamgirLuxburg2010_%5b0%5d.pdf "Multi-agent random walks for local clustering on graphs"], ''IEEE 10th International Conference on Data Mining (ICDM)'', 2010, pp. 18-27.</ref>


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

* Heartbeat records<ref>{{cite journal |author= C.-K. Peng, J. Mietus, J. M. Hausdorff, [[Shlomo Havlin|S. Havlin]], H. E. Stanley, A. L. Goldberger |year= 1993 |title= Long-range anticorrelations and non-gaussian behavior of the heartbeat |journal= Phys. Rev. Lett. |volume= 70 |pages= 1343–6 |url= http://havlin.biu.ac.il/Publications.php?keyword=Long-range+anticorrelations+and+non-gaussian+behavior+of+the+heartbeat&year=*&match=all |doi= 10.1103/PhysRevLett.70.1343 |pmid= 10054352 |issue= 9|bibcode = 1993PhRvL..70.1343P }}</ref>
* Non-coding DNA sequences<ref>{{cite journal |author= C.-K. Peng, S. V. Buldyrev, A. L. Goldberger, [[Shlomo Havlin|S. Havlin]], F. Sciortino, M. Simons, [[H. Eugene Stanley|H. E. Stanley]] |year= 1992 |title= Long-range correlations in nucleotide sequences| doi = 10.1038/356168a0 |journal= Nature |volume= 356 |pages= 168–70 |url= http://havlin.biu.ac.il/Publications.php?keyword=Long-range+correlations+in+nucleotide+sequences&year=*&match=all |issue= 6365 |pmid=1301010|bibcode = 1992Natur.356..168P }}</ref>
* Volatility time series of stocks<ref>{{cite journal |author= Y. Liu, P. Cizeau, M. Meyer, C.-K. Peng, [[H. Eugene Stanley|H. E. Stanley]]|year= 1997 |title= Correlations in economic time series |journal= Physica A|volume= 245 |pages= 437 |doi= 10.1016/S0378-4371(97)00368-3 |issue= 3–4 }}</ref>
* Temperature records around the globe<ref>{{cite journal |author= E. Koscielny-Bunde, A. Bunde, S. Havlin, H. E. Roman, Y. Goldreich, H.-J. Schellenhuber |year= 1998|title= Indication of a universal persistence law governing atmospheric variability |journal= Phys. Rev. Lett. |volume= 81 |pages= 729 |url= http://havlin.biu.ac.il/Publications.php?keyword=Indication+of+a+universal+persistence+law+governing+atmospheric+variability&year=*&match=all |doi= 10.1103/PhysRevLett.81.729 |issue= 3 |bibcode=1998PhRvL..81..729K}}</ref>

==See also==
* [[Branching random walk]]
* [[Brownian motion]]
* [[Law of the iterated logarithm]]
* [[Lévy flight]]
* [[Lévy flight foraging hypothesis]]
* [[Loop-erased random walk]]
* [[Self-avoiding walk]]

==References==
{{Reflist}}

===Bibliography===
*Pal Révész (2013), ''Random walk in random and non-random environments (Third Edition)'', World Scientific Pub Co. ISBN 978-981-4447-50-8
*David Aldous and Jim Fill, ''Reversible Markov Chains and Random Walks on Graphs'', http://stat-www.berkeley.edu/users/aldous/RWG/book.html
*{{Cite book | last1=Doyle | first1=Peter G. | last2=Snell | first2=J. Laurie | title=Random walks and electric networks | arxiv=math.PR/0001057 | publisher=[[Mathematical Association of America]] | series=Carus Mathematical Monographs | isbn=978-0-88385-024-4 | mr=920811 | year=1984 | volume=22 | postscript={{inconsistent citations}}}}
*[[William Feller]] (1968), ''An Introduction to Probability Theory and its Applications'' (Volume 1). ISBN 0-471-25708-7
:Chapter 3 of this book contains a thorough discussion of random walks, including advanced results, using only elementary tools.
*Barry D. Hughes (1996), ''Random walks and random environments'', Oxford University Press. ISBN 0-19-853789-1
*James Norris (1998), ''Markov Chains'', Cambridge University Press. ISBN 0-521-63396-6
* Pólya (1921), [http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0084&DMDID=DMDLOG_0016&L=1 "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz"], ''[[Mathematische Annalen]]'', 84(1-2):149–160, March 1921.
*Wolfgang Woess (2000), ''Random walks on infinite graphs and groups'', Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3
*Mackenzie, Dana, [http://www.sciencemag.org/cgi/content/full/sci;290/5498/1883 "Taking the Measure of the Wildest Dance on Earth"], Science, Vol. 290, 8 December 2000.
*G. Weiss ''Aspects and Applications of the Random Walk'', North-Holland, 1994.
*D. Ben-Avraham and [[Shlomo Havlin|S. Havlin]], ''[http://havlin.biu.ac.il/Shlomo%20Havlin%20books_d_r.php Diffusion and Reactions in Fractals and Disordered Systems]'', Cambridge University Press, 2000.
*"Numb3rs Blog." Department of Mathematics. 29 April 2006. Northeastern University. 12 December 2007 http://www.atsweb.neu.edu/math/cp/blog/?id=137&month=04&year=2006&date=2006-04-29.

==External links==
* [http://mathworld.wolfram.com/PolyasRandomWalkConstants.html Pólya's Random Walk Constants]
* [http://vlab.infotech.monash.edu.au/simulations/swarms/random-walk/ Random walk in Java Applet]

{{Stochastic processes}}
{{Use dmy dates|date=September 2010}}

{{DEFAULTSORT:Random Walk}}
[[Category:Concepts in physics]]
[[Category:Stochastic processes]]
[[Category:Variants of random walks]]

Main Page

2014-08-10T17:53:47Z

ChelseyBianco:

In [[statistics]], the '''Pearson product-moment correlation coefficient''' (sometimes referred to as the '''PPMCC''' or '''PCC''',<ref>"The human disease network", Albert Barabasi et al., Plos.org</ref> or '''Pearson's ''r''''', and is typically denoted by ''r'') is a measure of the [[correlation]] (linear dependence) between two variables ''X'' and ''Y'', giving a value between +1 and −1 inclusive. It is widely used in the sciences as a measure of the strength of linear dependence between two variables. It was developed by [[Karl Pearson]] from a similar but slightly different idea introduced by [[Francis Galton]] in the 1880s.<ref name="thirteenways">J. L. Rodgers and W. A. Nicewander. [http://www.jstor.org/stable/2685263 Thirteen ways to look at the correlation coefficient]. The American Statistician, 42(1):59–66, February 1988.</ref><ref>{{Cite journal| doi = 10.1214/ss/1177012580| last = Stigler | first = Stephen M. | title = Francis Galton's Account of the Invention of Correlation | journal = Statistical Science | volume=4 | issue=2 | pages = 73–79 | year = 1989 | jstor=2245329}}</ref>

[[Image:Correlation examples2.svg|thumb|400px|right|Several sets of (''x'', ''y'') points, with the correlation coefficient of ''x'' and ''y'' for each set. Note that the correlation reflects the non-linearity and direction of a linear relationship (top row), but not the slope of that relationship (middle), nor many aspects of nonlinear relationships (bottom). N.B.: the figure in the center has a slope of 0 but in that case the correlation coefficient is undefined because the variance of ''Y'' is zero.]]

==Definition==
Pearson's correlation coefficient between two variables is defined as the [[covariance]] of the two variables divided by the product of their [[standard deviations]]. The form of the definition involves a "product moment", that is, the mean (the first moment about the origin) of the product of the mean-adjusted random variables; hence the modifier ''product-moment'' in the name.

===For a population===
Pearson's correlation coefficient when applied to a population is commonly represented by the Greek letter ''ρ'' (rho) and may be referred to as the ''population correlation coefficient'' or the ''population Pearson correlation coefficient''. The formula for ''ρ'' is:

:<math> \rho_{X,Y}={\mathrm{cov}(X,Y) \over \sigma_X \sigma_Y} ={E[(X-\mu_X)(Y-\mu_Y)] \over \sigma_X\sigma_Y} </math>

===For a sample===
Pearson's correlation coefficient when applied to a sample is commonly represented by the letter ''r'' and may be referred to as the ''sample correlation coefficient'' or the ''sample Pearson correlation coefficient''. We can obtain a formula for ''r'' by substituting estimates of the covariances and variances based on a [[statistical sample|sample]] into the formula above. That formula for ''r'' is:

:<math>r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}}</math>

An equivalent expression gives the correlation coefficient as the mean of the products of the [[standard score]]s. Based on a [[Statistical sample|sample]] of paired data (''X''''i'', ''Y''''i''), the sample Pearson correlation coefficient is

:<math>r = \frac{1}{n-1} \sum ^n _{i=1} \left( \frac{X_i - \bar{X}}{s_X} \right) \left( \frac{Y_i - \bar{Y}}{s_Y} \right)</math>

where

:<math>\frac{X_i - \bar{X}}{s_X}, \bar{X}, \text{ and } s_X</math>

are the [[standard score]], sample [[mean]], and sample [[standard deviation]], respectively.

==Mathematical properties==
The absolute value of both the sample and population Pearson correlation coefficients are less than or equal to 1. Correlations equal to 1 or -1 correspond to data points lying exactly on a line (in the case of the sample correlation), or to a bivariate distribution entirely supported on a line (in the case of the population correlation). The Pearson correlation coefficient is symmetric: ''corr''(''X'',''Y'') = ''corr''(''Y'',''X'').

A key mathematical property of the Pearson correlation coefficient is that it is [[invariant estimator|invariant]] (up to a sign) to separate changes in location and scale in the two variables. That is, we may transform ''X'' to ''a'' + ''bX'' and transform ''Y'' to ''c'' + ''dY'', where ''a'', ''b'', ''c'', and ''d'' are constants, without changing the correlation coefficient (this fact holds for both the population and sample Pearson correlation coefficients). Note that more general linear transformations do change the correlation: see [[#Removing correlation|a later section]] for an application of this.

The Pearson correlation can be expressed in terms of uncentered moments. Since ''μ''''X'' = E(''X''), ''σ''''X''2 = E[(''X'' − E(''X''))2] = E(''X''2) − E2(''X'') and
likewise for ''Y'', and since

: <math>E[(X-E(X))(Y-E(Y))]=E(XY)-E(X)E(Y),\,</math>

the correlation can also be written as

:<math>\rho_{X,Y}=\frac{E(XY)-E(X)E(Y)}{\sqrt{E(X^2)-(E(X))^2}~\sqrt{E(Y^2)- (E(Y))^2}}.</math>

Alternative formulae for the ''sample'' Pearson correlation coefficient are also available:

:<math>
r_{xy}=\frac{\sum x_iy_i-n \bar{x} \bar{y}}{(n-1) s_x s_y}=\frac{n\sum x_iy_i-\sum x_i\sum y_i}
{\sqrt{n\sum x_i^2-(\sum x_i)^2}~\sqrt{n\sum y_i^2-(\sum y_i)^2}}.
</math>

The above formula suggests a convenient single-pass algorithm for calculating sample correlations, but, depending on the numbers involved, it can sometimes be [[numerical stability|numerically unstable]].

==Interpretation==
The correlation coefficient ranges from −1 to 1. A value of 1 implies that a linear equation describes the relationship between ''X'' and ''Y'' perfectly, with all data points lying on a [[line (mathematics)|line]] for which ''Y'' increases as ''X'' increases. A value of −1 implies that all data points lie on a line for which ''Y'' decreases as ''X'' increases. A value of 0 implies that there is no linear correlation between the variables.

More generally, note that (''X''''i'' − ''X'')(''Y''''i'' − ''Y'') is positive if and only if ''X''''i'' and ''Y''''i'' lie on the same side of their respective means. Thus the correlation coefficient is positive if ''X''''i'' and ''Y''''i'' tend to be simultaneously greater than, or simultaneously less than, their respective means. The correlation coefficient is negative if ''X''''i'' and ''Y''''i'' tend to lie on opposite sides of their respective means.

===Geometric interpretation===
[[File:Regression lines.png|thumb|upright=1.5|Regression lines for y=gx(x) [red] and x=gy(y) [blue]]]

For uncentered data, the correlation coefficient corresponds with the cosine of the angle <math>\varphi</math> between both possible [[regression line]]s y=gx(x) and x=gy(y).

For centered data (i.e., data which have been shifted by the sample mean so as to have an average of zero), the correlation coefficient can also be viewed as the [[cosine]] of the [[angle]] <math>\ \theta</math> between the two [[Vector (geometry)|vectors]] of samples drawn from the two random variables (see below).

Both the uncentered (non-Pearson-compliant) and centered correlation coefficients can be determined for a dataset. As an example, suppose five countries are found to have gross national products of 1, 2, 3, 5, and 8 billion dollars, respectively. Suppose these same five countries (in the same order) are found to have 11%, 12%, 13%, 15%, and 18% poverty. Then let '''x''' and '''y''' be ordered 5-element vectors containing the above data: '''x''' = (1, 2, 3, 5, 8) and '''y''' = (0.11, 0.12, 0.13, 0.15, 0.18).

By the usual procedure for finding the angle <math>\ \theta</math> between two vectors (see [[dot product]]), the ''uncentered'' correlation coefficient is:


:<math> \cos \theta = \frac { \bold{x} \cdot \bold{y} } { \left\| \bold{x} \right\| \left\| \bold{y} \right\| } = \frac { 2.93 } { \sqrt { 103 } \sqrt { 0.0983 } } = 0.920814711. </math>

Note that the above data were deliberately chosen to be perfectly correlated: ''y'' = 0.10 + 0.01 ''x''. The Pearson correlation coefficient must therefore be exactly one. Centering the data (shifting '''x''' by E('''x''') = 3.8 and '''y''' by E('''y''') = 0.138) yields '''x''' = (−2.8, −1.8, −0.8, 1.2, 4.2) and '''y''' = (−0.028, −0.018, −0.008, 0.012, 0.042), from which


:<math> \cos \theta = \frac { \bold{x} \cdot \bold{y} } { \left\| \bold{x} \right\| \left\| \bold{y} \right\| } = \frac { 0.308 } { \sqrt { 30.8 } \sqrt { 0.00308 } } = 1 = \rho_{xy}, </math>

as expected.

===Interpretation of the size of a correlation===
{|class="wikitable" align="right"
|-
! Correlation !! Negative !! Positive
|-
| None || −0.09 to 0.0 || 0.0 to 0.09
|-
| Small || −0.3 to −0.1 || 0.1 to 0.3
|-
| Medium || −0.5 to −0.3 || 0.3 to 0.5
|-
|Strong || −1.0 to −0.5|| 0.5 to 1.0
|}

Several authors<ref name="Buda">A. Buda and A.Jarynowski (2010) ''Life-time of correlations and its applications vol.1'', Wydawnictwo Niezalezne: 5–21, December 2010, ISBN 978-83-915272-9-0</ref><ref name="Cohen88"/> have offered guidelines for the interpretation of a correlation coefficient. However, all such criteria are in some ways arbitrary and should not be observed too strictly.<ref name="Cohen88">Cohen, J. (1988). ''Statistical power analysis for the behavioral sciences'' (2nd ed.)</ref> The interpretation of a correlation coefficient depends on the context and purposes. A correlation of 0.9 may be very low if one is verifying a physical law using high-quality instruments, but may be regarded as very high in the social sciences where there may be a greater contribution from complicating factors.

===Pearson’s distance===
A distance metric for two variables X and Y known as ''Pearson's distance'' can be defined from their correlation coefficient as<ref>Fulekar (Ed.), M.H. (2009) ''Bioinformatics: Applications in Life and Environmental Sciences'', Springer (pp. 110) ISBN 1-4020-8879-5</ref>
:<math>d_{X,Y}=1-\rho_{X,Y}.</math>
Considering that the Pearson correlation coefficient falls between [-1, 1], the Pearson distance lies in [0, 2].

==Inference==
[[Image:correlation significance.svg|300px|right|thumb|A graph showing the minimum value of Pearson's correlation coefficient that is significantly different from zero at the 0.05 level, for a given sample size.]]Statistical inference based on Pearson's correlation coefficient often focuses on one of the following two aims:
* One aim is to test the [[null hypothesis]] that the true correlation coefficient ''ρ'' is equal to 0, based on the value of the sample correlation coefficient ''r''.
* The other aim is to construct a [[confidence interval]] around ''r'' that has a given probability of containing ''ρ''.
We discuss methods of achieving one or both of these aims below.

===Use a permutation test===
[[Resampling (statistics)#Permutation tests|Permutation tests]] provide a direct approach to performing hypothesis tests and constructing confidence intervals. A permutation test for Pearson's correlation coefficient involves the following two steps:
* (i) using the original paired data (''x''''i'', ''y''''i''), randomly redefine the pairs to create a new data set (''x''''i'', ''y''''i′''), where the ''i′'' are a permutation of the set {1,...,''n''}. The permutation ''i′'' is selected randomly, with equal probabilities placed on all ''n''! possible permutations. This is equivalent to drawing the ''i′'' randomly "without replacement" from the set {1,..., ''n''}. A closely related and equally justified ([[Bootstrapping (statistics)|bootstrapping]]) approach is to separately draw the ''i'' and the ''i′'' "with replacement" from {1,..., ''n''};
* (ii) Construct a correlation coefficient ''r'' from the randomized data.
To perform the permutation test, repeat (i) and (ii) a large number of times. The [[p-value]] for the permutation test is the proportion of the ''r'' values generated in step (ii) that are larger than the Pearson correlation coefficient that was calculated from the original data. Here "larger" can mean either that the value is larger in magnitude, or larger in signed value, depending on whether a [[two-tailed test|two-sided]] or [[two-tailed test|one-sided]] test is desired.

===Use a bootstrap===
The [[bootstrapping (statistics)|bootstrap]] can be used to construct confidence intervals for Pearson's correlation coefficient. In the "non-parametric" bootstrap, ''n'' pairs (''x''''i'', ''y''''i'') are resampled "with replacement" from the observed set of ''n'' pairs, and the correlation coefficient ''r'' is calculated based on the resampled data. This process is repeated a large number of times, and the empirical distribution of the resampled ''r'' values are used to approximate the [[sampling distribution]] of the statistic. A 95% [[confidence interval]] for ''ρ'' can be defined as the interval spanning from the 2.5''th'' to the 97.5''th'' [[percentile]] of the resampled ''r'' values.

===Testing using Student's t-distribution===
For pairs from an uncorrelated [[bivariate normal distribution]], the [[sampling distribution]] of Pearson's correlation coefficient follows [[Student's t-distribution]] with degrees of freedom ''n'' − 2. Specifically, if the underlying variables have a bivariate normal distribution, the variable

:<math>t = r\sqrt{\frac{n-2}{1 - r^2}}</math>

has a Student's t-distribution in the null case (zero correlation).<ref>Rahman, N.A. (1968) ''A Course in Theoretical Statistics'', Charles Griffin and Company, 1968</ref> This also holds approximately even if the observed values are non-normal, provided sample sizes are not very small.<ref>Kendall, M.G., Stuart, A. (1973) ''The Advanced Theory of Statistics, Volume 2: Inference and Relationship'', Griffin. ISBN 0-85264-215-6 (Section 31.19)</ref><ref>For deviation on small sample sizes, see for example http://www.neustats.com/neu-da-documentation/whats-that-pearson-p-value-in-the-tables/</ref> For determining the critical values for ''r'' the inverse of this transformation is also needed:

:<math>r = \frac{t}{\sqrt{n - 2 + t^2}}.</math>

Alternatively, large sample approaches can be used.

Early work on the distribution of the sample correlation coefficient was carried out by [[R. A. Fisher]]<ref>{{Cite journal
| last = Fisher | first = R.A.
| authorlink = R. A. Fisher
| title = Frequency distribution of the values of the correlation coefficient in samples from an indefinitely large population
| journal = [[Biometrika]]
| volume = 10
| issue = 4
| pages = 507–521
| year = 1915
| doi = 10.1093/biomet/10.4.507
}}</ref><ref>{{Cite journal
| last = Fisher | first = R.A.
| authorlink = R. A. Fisher
| title = On the probable error of a coefficient of correlation deduced from a small sample
| journal = [[Metron (journal)|Metron]]
| year = 1921
| volume = 1
| issue = 4
| pages = 3–32
| url = http://hdl.handle.net/2440/15169
| accessdate = 2009-03-25
| format = [[PDF]]
}}</ref>
and A. K. Gayen.<ref>{{Cite journal
| first = A.K. | last = Gayen
| title = The frequency distribution of the product moment correlation coefficient in random samples of any size draw from non-normal universes
| journal = [[Biometrika]]
| year = 1951
| volume = 38
| pages = 219–247
| doi = 10.1093/biomet/38.1-2.219
}}</ref>
Another early paper<ref>Soper, H.E., Young, A.W., Cave, B.M., Lee, A., Pearson, K. (1917). "On the distribution of the correlation coefficient in small samples. Appendix II to the papers of "Student" and R. A. Fisher. A co-operative study", ''[[Biometrika]]'', 11, 328-413. {{doi|10.1093/biomet/11.4.328}}</ref> provides graphs and tables for general values of ''ρ'', for small sample sizes, and discusses computational approaches.

===Use the exact distribution===
For data that follows a [[bivariate normal distribution]], the exact density function for the sample correlation of a normal bivariate is<ref>Kenney, J. F. and Keeping, E. S., ''Mathematics of Statistics'', Pt. 2, 2nd ed. Princeton, NJ: Van Nostrand, 1951.</ref><ref>[http://mathworld.wolfram.com/CorrelationCoefficientBivariateNormalDistribution.html Correlation Coefficient - Bivariate Normal Distribution]</ref>

:<math>f\left(r\right) = \frac{\left(n - 2\right)\, \mathbf{\Gamma}\left(n - 1\right) \left(1 - \rho^2\right)^{\frac{n - 1}{2}} \left(1 - r^2\right)^{\frac{n - 4}{2}}}{\sqrt{2\pi}\, \mathbf{\Gamma}\left(n - \frac{1}{2}\right) \left(1 - \rho r\right)^{n - \frac{3}{2}}} \,\mathbf{_2F_1}\left(\frac{1}{2}, \frac{1}{2}; \frac{2n - 1}{2}; \frac{\rho r + 1}{2}\right)</math>

where <math>\mathbf{\Gamma}</math> is the [[gamma function]], <math>\,\mathbf{_2F_1}(a,b;c;z)</math> is the [[hypergeometric function|Gaussian hypergeometric function]]. In the special case when <math>\,\rho = 0</math>, the density can be written as:

:<math>f\left(r\right) = \frac{\left(1 - r^2\right)^{\frac{n - 4}{2}}}{\mathbf{B}\left(\frac{1}{2}, \frac{n - 2}{2}\right)},</math>

where <math>\mathbf{B}</math> is the [[beta function]], which is one way of writing the density of a Student's t-distribution, as above.

Note that{{citation needed|date=April 2012}} <math>E\left(r\right) = \rho - \frac{\rho \left(1 - \rho^2\right)}{2 \left(n - 1\right)} + \cdots </math>, therefore ''r'' is a biased estimator of <math>\,\rho</math>. An approximately unbiased estimator can be obtained by solving the equation <math>r = E\left(r\right) = \rho - \frac{\rho \left(1 - \rho^2\right)}{2 \left(n - 1\right)}</math> for <math>\,\rho</math>. However, the solution, <math>\breve{\rho} = r \left[1 + \frac{1 - r^2}{2\left(n - 1\right)}\right]</math>,{{citation needed|date=April 2012}} is suboptimal.{{citation needed|date=April 2012}} An approximately unbiased estimator,{{citation needed|date=April 2012}} with minimum variance for large values of ''n'', with a bias of order <math>\frac{1}{n - 1}</math>, can be obtained by maximizing <math>\log{f\left(r\right)}</math>, i.e. <math>\hat{\rho} = r \left[1 - \frac{1 - r^2}{2\left(n - 1\right)}\right]</math>.{{citation needed|date=April 2012}}

===Use the Fisher transformation===
In practice, [[confidence intervals]] and [[hypothesis test]]s relating to ρ are usually carried out using the [[Fisher transformation]]:

: <math>F(r) = {1 \over 2}\ln{1 + r \over 1 - r} = \operatorname{artanh}(r).</math>

If ''F''(''r'') is the Fisher transformation of ''r'', and ''n'' is the sample size, then ''F''(''r'') approximately follows a [[normal distribution]] with

:<math>\text{mean} = F(\rho) = \operatorname{artanh}(\rho)</math>    and standard error    <math>\text{SE} = \frac{1}{\sqrt{n - 3}}.</math>

Thus, a [[standard score|z-score]] is

:<math>z = \frac{x - \text{mean}}{\text{SE}} = [F(r) - F(\rho_0)]\sqrt{n - 3}</math>

under the [[null hypothesis]] of that <math>\rho = \rho_0</math>, given the assumption that the sample pairs are [[independent and identically distributed]] and follow a [[bivariate normal distribution]]. Thus an approximate [[p-value]] can be obtained from a normal probability table. For example, if ''z'' = 2.2 is observed and a two-sided p-value is desired to test the null hypothesis that <math>\rho = 0</math>, the p-value is 2·Φ(−2.2) = 0.028, where Φ is the standard normal [[cumulative distribution function]].

To obtain a confidence interval for ρ, we first compute a confidence interval for ''F''(''<math>\rho</math>''):
 
 
:<math>100(1 - \alpha)%\text{CI}: \operatorname{artanh}(\rho) \in [\operatorname{artanh}(r) \pm z_{\alpha/2}SE]</math>
 
The inverse Fisher transformation bring the interval back to the correlation scale.
 
 
:<math>100(1 - \alpha)%\text{CI}: \rho \in [\operatorname{tanh}(\operatorname{artanh}(r) - z_{\alpha/2}SE), \operatorname{tanh}(\operatorname{artanh}(r) + z_{\alpha/2}SE)]</math>
 
For example, suppose we observe ''r'' = 0.3 with a sample size of ''n''=50, and we wish to obtain a 95% confidence interval for ρ. The transformed value is artanh(''r'') = 0.30952, so the confidence interval on the transformed scale is 0.30952 ± 1.96/√47, or (0.023624, 0.595415). Converting back to the correlation scale yields (0.024, 0.534).

==Pearson's correlation and least squares regression analysis==
The square of the sample correlation coefficient, which is also known as the [[coefficient of determination]], estimates the fraction of the variance in ''Y'' that is explained by ''X'' in a [[simple linear regression]]. As a starting point, the total variation in the ''Y''''i'' around their average value can be decomposed as follows

:<math>
\sum_i (Y_i - \bar{Y})^2 = \sum_i (Y_i-\hat{Y}_i)^2 + \sum_i (\hat{Y}_i-\bar{Y})^2,
</math>

where the <math>\hat{Y}_i</math> are the fitted values from the regression analysis. This can be rearranged to give

:<math>
1 = \frac{\sum_i (Y_i-\hat{Y}_i)^2}{\sum_i (Y_i - \bar{Y})^2} + \frac{\sum_i (\hat{Y}_i-\bar{Y})^2}{\sum_i (Y_i - \bar{Y})^2}.
</math>

The two summands above are the fraction of variance in ''Y'' that is explained by ''X'' (right) and that is unexplained by ''X'' (left).

Next, we apply a property of least square regression models, that the sample covariance between <math>\hat{Y}_i</math> and <math>Y_i-\hat{Y}_i</math> is zero. Thus, the sample correlation coefficient between the observed and fitted response values in the regression can be written

<math>
\begin{align}
r(Y,\hat{Y}) &= \frac{\sum_i(Y_i-\bar{Y})(\hat{Y}_i-\bar{Y})}{\sqrt{\sum_i(Y_i-\bar{Y})^2\cdot \sum_i(\hat{Y}_i-\bar{Y})^2}}\\
&= \frac{\sum_i(Y_i-\hat{Y}_i+\hat{Y}_i-\bar{Y})(\hat{Y}_i-\bar{Y})}{\sqrt{\sum_i(Y_i-\bar{Y})^2\cdot \sum_i(\hat{Y}_i-\bar{Y})^2}}\\
&= \frac{ \sum_i [(Y_i-\hat{Y}_i)(\hat{Y}_i-\bar{Y}) +(\hat{Y}_i-\bar{Y})^2 ]}{\sqrt{\sum_i(Y_i-\bar{Y})^2\cdot \sum_i(\hat{Y}_i-\bar{Y})^2}}\\
&= \frac{ \sum_i (\hat{Y}_i-\bar{Y})^2 }{\sqrt{\sum_i(Y_i-\bar{Y})^2\cdot \sum_i(\hat{Y}_i-\bar{Y})^2}}\\

&= \sqrt{\frac{\sum_i(\hat{Y}_i-\bar{Y})^2}{\sum_i(Y_i-\bar{Y})^2}}.
\end{align}
</math>

Thus

:<math>
r(Y,\hat{Y})^2 = \frac{\sum_i(\hat{Y}_i-\bar{Y})^2}{\sum_i(Y_i-\bar{Y})^2}
</math>

is the proportion of variance in ''Y'' explained by a linear function of ''X''.

==Sensitivity to the data distribution==
===Existence===
The population Pearson correlation coefficient is defined in terms of [[moment (mathematics)|moments]], and therefore exists for any bivariate [[probability distribution]] for which the [[statistical population|population]] [[covariance]] is defined and the [[marginal distribution|marginal]] [[population variance]]s are defined and are non-zero. Some probability distributions such as the [[Cauchy distribution]] have undefined variance and hence ρ is not defined if ''X'' or ''Y'' follows such a distribution. In some practical applications, such as those involving data suspected to follow a [[heavy-tailed distribution]], this is an important consideration. However, the existence of the correlation coefficient is usually not a concern; for instance, if the range of the distribution is bounded, ρ is always defined.

===Large sample properties===
In the case of the bivariate [[normal distribution]] the population Pearson correlation coefficient characterizes the joint distribution as long as the marginal means and variances are known. For most other bivariate distributions this is not true. Nevertheless, the correlation coefficient is highly informative about the degree of linear dependence between two random quantities regardless of whether their joint distribution is normal.<ref name="thirteenways"/>
The sample correlation coefficient is the [[maximum likelihood estimate]] of the population correlation coefficient for bivariate normal data, and is [[asymptotic distribution|asymptotically]] [[bias of an estimator|unbiased]] and [[efficiency (statistics)|efficient]], which roughly means that it is impossible to construct a more accurate estimate than the sample correlation coefficient if the data are normal and the sample size is moderate or large. For non-normal populations, the sample correlation coefficient remains approximately unbiased, but may not be efficient. The sample correlation coefficient is a [[consistent estimator]] of the population correlation coefficient as long as the sample means, variances, and covariance are consistent (which is guaranteed when the [[law of large numbers]] can be applied).

===Robustness===
Like many commonly used statistics, the sample statistic ''r'' is not [[robust statistics|robust]],<ref name="wilcox">{{Cite book| title=Introduction to robust estimation and hypothesis testing | last = Wilcox | first = Rand R. | publisher= Academic Press | year=2005}}</ref> so its value can be misleading if [[outlier]]s are present.<ref>{{Cite journal| title= Robust Estimation and Outlier Detection with Correlation Coefficients | last= Devlin | first = Susan J | coauthors = Gnanadesikan, R; Kettenring J.R. | journal= Biometrika | volume= 62 | issue= 3 |year=1975 | pages=531–545 | doi= 10.1093/biomet/62.3.531 | jstor=2335508}}</ref><ref>{{Cite book| title=Robust Statistics | last = Huber | first = Peter. J.| publisher= Wiley | year=2004}}{{Page needed|date=September 2010}}</ref> Specifically, the PMCC is neither distributionally robust,{{Citation needed|date=November 2009}} nor outlier resistant<ref name="wilcox"/> (see [[Robust statistics#Definition]]). Inspection of the [[scatterplot]] between ''X'' and ''Y'' will typically reveal a situation where lack of robustness might be an issue, and in such cases it may be advisable to use a robust measure of association. Note however that while most robust estimators of association measure [[statistical dependence]] in some way, they are generally not interpretable on the same scale as the Pearson correlation coefficient.

Statistical inference for Pearson's correlation coefficient is sensitive to the data distribution. Exact tests, and asymptotic tests based on the [[Fisher transformation]] can be applied if the data are approximately normally distributed, but may be misleading otherwise. In some situations, the [[bootstrapping (statistics)|bootstrap]] can be applied to construct confidence intervals, and [[resampling (statistics)|permutation tests]] can be applied to carry out hypothesis tests. These [[non-parametric statistics|non-parametric]] approaches may give more meaningful results in some situations where bivariate normality does not hold. However the standard versions of these approaches rely on [[exchangeable random variables|exchangeability]] of the data, meaning that there is no ordering or grouping of the data pairs being analyzed that might affect the behavior of the correlation estimate.

A stratified analysis is one way to either accommodate a lack of bivariate normality, or to isolate the correlation resulting from one factor while controlling for another. If ''W'' represents cluster membership or another factor that it is desirable to control, we can stratify the data based on the value of ''W'', then calculate a correlation coefficient within each stratum. The stratum-level estimates can then be combined to estimate the overall correlation while controlling for ''W''.<ref>Katz., Mitchell H. (2006) ''Multivariable Analysis - A Practical Guide for Clinicians''. 2nd Edition. Cambridge University Press. ISBN 978-0-521-54985-1. ISBN 0-521-54985-X {{DOI|10.2277/052154985X}}</ref>

==Calculating a weighted correlation==
Suppose observations to be correlated have differing degrees of importance that can be expressed with a weight vector ''w''. To calculate the correlation between vectors ''x'' and ''y'' with the weight vector ''w'' (all of length ''n''),<ref>http://sci.tech-archive.net/Archive/sci.stat.math/2006-02/msg00171.html</ref><ref>[http://www.mathworks.com/matlabcentral/fileexchange/20846 A MATLAB Toolbox for computing Weighted Correlation Coefficients]</ref>

* Weighted mean:

:: <math>\operatorname{m}(x; w) = {\sum_i w_i x_i \over \sum_i w_i}.</math>

* Weighted covariance
:: <math>\operatorname{cov}(x,y;w) = {\sum_i w_i (x_i - \operatorname{m}(x; w)) (y_i - \operatorname{m}(y; w)) \over \sum_i w_i }.</math>

* Weighted correlation
:: <math>\operatorname{corr}(x,y;w) = {\operatorname{cov}(x,y;w) \over \sqrt{\operatorname{cov}(x,x;w) \operatorname{cov}(y,y;w)}}.</math>

==Removing correlation==
It is always possible to remove the correlation between random variables with a linear transformation, even if the relationship between the variables is nonlinear. A presentation of this result for population distributions is given by Cox & Hinkley.<ref>Cox, D.R., Hinkley, D.V. (1974) ''Theoretical Statistics'', Chapman & Hall (Appendix 3) ISBN 0-412-12420-3</ref>

A corresponding result exists for sample correlations, in which the sample correlation is reduced to zero. Suppose a vector of ''n'' random variables is sampled ''m'' times. Let ''X'' be a matrix where <math>X_{i,j}</math> is the ''j''th variable of sample ''i''. Let <math>Z_{m,m}</math> be an ''m'' by ''m'' square matrix with every element 1. Then ''D'' is the data transformed so every random variable has zero mean, and ''T'' is the data transformed so all variables have zero mean and zero correlation with all other variables - the moment matrix of ''T'' will be the identity matrix. This has to be further divided by the standard deviation to get unit variance. The transformed variables will be uncorrelated, even though they may not be [[Statistical independence|independent]].

:<math>D = X -\frac{1}{m} Z_{m,m} X</math>



:<math>T = D (D^T D)^{-\frac{1}{2}}</math>

where an exponent of -1/2 represents the [[matrix square root]] of the [[matrix inverse|inverse]] of a matrix. The covariance matrix of ''T'' will be the identity matrix. If a new data sample ''x'' is a row vector of ''n'' elements, then the same transform can be applied to ''x'' to get the transformed vectors ''d'' and ''t'':

:<math>d = x - \frac{1}{m} Z_{1,m} X</math>



:<math>t = d (D^T D)^{-\frac{1}{2}}</math>
This decorrelation is related to [[Principal Components Analysis]] for multivariate data.

==Reflective correlation==
The reflective correlation is a variant of Pearson's correlation in which the data are not centered around their mean values.{{Citation needed|date=January 2011}} The population reflective correlation is

:<math>
\text{Corr}_r(X,Y) = \frac{E[XY]}{\sqrt{EX^2\cdot EY^2}}.
</math>

The reflective correlation is symmetric, but it is not invariant under translation:

:<math>
\text{Corr}_r(X, Y) = \text{Corr}_r(Y, X) = \text{Corr}_r(X, bY) \neq \text{Corr}_r(X, a + b Y), \quad a \neq 0, b > 0.
</math>

The sample reflective correlation is

:<math>
rr_{xy} = \frac{\sum x_i y_i}{\sqrt{(\sum x_i^2)(\sum y_i^2)}}.
</math>

The weighted version of the sample reflective correlation is

:<math>
rr_{xy, w} = \frac{\sum w_i x_i y_i}{\sqrt{(\sum w_i x_i^2)(\sum w_i y_i^2)}}.
</math>

==Scaled correlation==
{{Main|Scaled correlation}}

Scaled correlation is a variant of Pearson's correlation in which the range of the data is restricted intentionally and in a controlled manner to reveal correlations between fast components in time series.<ref name = "Nikolicetal">Nikolić D, Muresan RC, Feng W, Singer W (2012) Scaled correlation analysis: a better way to compute a cross-correlogram. ''European Journal of Neuroscience'', pp. 1–21, {{doi|10.1111/j.1460-9568.2011.07987.x}} http://www.danko-nikolic.com/wp-content/uploads/2012/03/Scaled-correlation-analysis.pdf</ref> Scaled correlation is defined as average correlation across short segments of data.

Let <math>K</math> be the number of segments that can fit into the total length of the signal <math>T</math> for a given scale <math>s</math>:

:<math>K = \operatorname{round}\left(\frac{T}{s}\right).</math>

The scaled correlation across the entire signals <math>\bar{r}_s</math> is then computed as

:<math>\bar{r}_s = \frac{1}{K} \sum\limits_{k=1}^K r_k,</math>

where <math>r_k</math> is Pearson's coefficient of correlation for segment <math>k</math>.

By choosing the parameter <math>s</math>, the range of values is reduced and the correlations on long time scale are filtered out, only the correlations on short time scales being revealed. Thus, the contributions of slow components are removed and those of fast components are retained.

==See also==
{{Portal|Statistics}}
{{Wikiversity|Linear correlation}}
* [[Correlation and dependence]]
* [[Spearman's rank correlation coefficient]]
* [[Association (statistics)]]
* [[Disattenuation]]
* [[Maximal information coefficient]]
* [[Normally distributed and uncorrelated does not imply independent]]

==References==
{{Reflist}}

{{Statistics}}
{{Use dmy dates|date=September 2010}}

{{DEFAULTSORT:Pearson Product-Moment Correlation Coefficient}}
[[Category:Covariance and correlation]]
[[Category:Parametric statistics]]
[[Category:Statistical ratios]]

[[ca:Coeficient de correlació de Pearson]]
[[de:Korrelationskoeffizient]]
[[et:Lineaarne korrelatsioonikordaja]]
[[es:Coeficiente de correlación de Pearson]]
[[eu:Korrelazio-koefiziente]]
[[it:Indice di correlazione di Pearson]]
[[he:מתאם פירסון]]
[[nl:Correlatiecoëfficiënt]]
[[ja:相関係数]]
[[no:Pearsons produkt-moment korrelasjonskoeffisient]]
[[pl:Współczynnik korelacji Pearsona]]
[[pt:Coeficiente de correlação de Pearson]]
[[ru:Корреляция#Линейный коэффициент корреляции]]
[[sk:Bravaisov-Pearsonov korelačný koeficient]]
[[sl:Pearsonov koeficient korelacije]]
[[zh:皮尔逊积矩相关系数]]

Main Page

2014-08-10T14:18:42Z

ChelseyBianco:

{{refimprove|date=August 2012}}
'''Maze generation [[algorithm]]s''' are automated methods for the creation of [[maze]]s.

[[Image:Prim Maze.svg|right|frame|This maze generated by modified version of [[Prim's algorithm]], below.]]

== Graph theory based methods ==

[[File:Graph_based_maze_animation.gif|thumb|Animation of Graph theory based method]]

A maze can be generated by starting with a predetermined arrangement of cells (most commonly a rectangular grid but other arrangements are possible) with wall sites between them. This predetermined arrangement can be considered as a [[connected graph]] with the edges representing possible wall sites and the nodes representing cells. The purpose of the maze generation algorithm can then be considered to be making a subgraph where it is challenging to find a route between two particular nodes.

If the subgraph is not [[connected graph|connected]], then there are regions of the graph that are wasted because they do not contribute to the search space. If the graph contains loops, then there may be multiple paths between the chosen nodes. Because of this, maze generation is often approached as generating a random [[spanning tree (mathematics)|spanning tree]]. Loops which can confound naive maze solvers may be introduced by adding random edges to the result during the course of the algorithm.

The animation shows the maze generation steps for a
graph that is not on a rectangular grid.
First, the computer creates a random [[planar graph]] G
shown in blue, and its [[Dual_graph|dual]] F
shown in yellow. Second, computer traverses F using a chosen
algorithm, such as a depth-first search, coloring the path red.
During the traversal, whenever a red edge crosses over a blue edge,
the blue edge is removed.
Finally, when all vertices of F have been visited, F is erased
and two edges from G, one for the entrance and one for the exit, are removed. 

=== Depth-first search ===
[[File:Depth-First_Search_Animation.ogv|thumb|right|Animation of generator's thinking process using Depth-First Search]]

This algorithm is a randomized version of the [[depth-first search]] algorithm. Frequently implemented with a stack, this approach is one of the simplest ways to generate a maze using a computer. Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell. This approach guarantees that the maze space is completely visited.

As stated, the algorithm is very simple and does not produce over-complex mazes. More specific refinements to the algorithm can help to generate mazes that are harder to solve.

# Start at a particular cell and call it the "exit."
# Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
## If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then [[recursion|recur]] with that neighbor as the current cell.

As given above this algorithm involves deep recursion which may cause stack overflow issues on some computer architectures. The algorithm can be rearranged into a loop by storing backtracking information in the maze itself. This also provides a quick way to display a solution, by starting at any given point and backtracking to the exit.

[[File:Horizontally_Influenced_Depth-First_Search_Generated_Maze.png|thumb|right|Horizontal Influence]]

Mazes generated with a depth-first search have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before backtracking. Also mazes will typically be relatively easy to find the way to the square that was first picked at the beginning of the algorithm, since most paths lead to or from there, but it is hard to find the way out.{{Why|date=October 2014}}

To add difficulty and a fun factor to depth-first search generated mazes, you can influence the likelihood of which neighbor you should visit, instead of it being completely random. By making it more likely to visit neighbors to your sides, you can have a more horizontal maze generation. Experimenting with directional "influence" in certain places could lead to creating fun designs, such as a checkerboard pattern, an X, and more.

==== Recursive backtracker ====
The depth-first search algorithm of maze generation is frequently implemented using [[backtracking]]:

# Make the initial cell the current cell and mark it as visited
# While there are unvisited cells
## If the current cell has any neighbours which have not been visited
### Choose randomly one of the unvisited neighbours
### Push the current cell to the stack
### Remove the wall between the current cell and the chosen cell
### Make the chosen cell the current cell and mark it as visited
## Else if stack is not empty
### Pop a cell from the stack
### Make it the current cell
## Else
### Pick a random unvisited cell, make it the current cell and mark it as visited

=== Randomized Kruskal's algorithm ===
[[File:KruskalGeneratedMaze.webm|thumb|An animation of generating a 30 by 20 maze using Kruskal's algorithm.]]
This algorithm is a randomized version of [[Kruskal's algorithm]].

# Create a list of all walls, and create a set for each cell, each containing just that one cell.
# For each wall, in some random order:
## If the cells divided by this wall belong to distinct sets:
### Remove the current wall.
### Join the sets of the formerly divided cells.

There are several data structures that can be used to model the sets of cells. An efficient implementation using a [[disjoint-set data structure]] can perform each union and find operation on two sets in nearly constant [[amortized time]] (specifically, <math>O(\alpha(V))</math> time; <math>\alpha(x) < 5</math> for any plausible value of <math>x</math>), so the running time of this algorithm is essentially proportional to the number of walls available to the maze.

It matters little whether the list of walls is initially randomized or if a wall is randomly chosen from a nonrandom list, either way is just as easy to code.

Because the effect of this algorithm is to produce a minimal spanning tree from a graph with equally weighted edges, it tends to produce regular patterns which are fairly easy to solve.

=== Randomized Prim's algorithm ===
[[File:MAZE 30x20 Prim.ogv|thumb|upright=1.6|An animation of generating a 30 by 20 maze using Prim's algorithm.]]
This algorithm is a randomized version of [[Prim's algorithm]].

# Start with a grid full of walls.
# Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
# While there are walls in the list:
## Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:
### Make the wall a passage and mark the cell on the opposite side as part of the maze.
### Add the neighboring walls of the cell to the wall list.
## Remove the wall from the list.

Like the depth-first algorithm, it will usually be relatively easy to find the way to the starting cell, but hard to find the way anywhere else.

Note that simply running classical Prim's on a graph with random weights would create mazes stylistically identical to Kruskal's, because they are both minimal spanning tree algorithms. Instead, this algorithm introduces stylistic variation because the edges closer to the starting point have a lower effective weight.

==== Modified version ====
Although the classical Prim's algorithm keeps a list of edges, for maze generation we could instead maintain a list of adjacent cells. If the randomly chosen cell has multiple edges that connect it to the existing maze, select one of these edges at random. This will tend to branch slightly more than the edge-based version above.

==Recursive division method==
{| class="wikitable" align="right"
|+ '''Illustration of Recursive Division'''
|-
! width="110px" | ''original chamber''
! width="110px" | ''division by two walls''
! width="110px" | ''holes in walls''
! width="110px" | ''continue subdividing...''
! width="110px" | ''completed''
|-
| align="center" | [[Image:Chamber.png|101px]]
| align="center" | [[Image:Chamber division.png|101px]]
| align="center" | [[Image:Chamber divided.png|101px]]
| align="center" | [[Image:Chamber subdivision.png|101px]]
| align="center" | [[Image:Chamber finished.png|101px]]
|}

Mazes can be created with ''recursive division'', an algorithm which works as follows: Begin with the maze's space with no walls. Call this a chamber. Divide the chamber with a randomly positioned wall (or multiple walls) where each wall contains a randomly positioned passage opening within it. Then recursively repeat the process on the subchambers until all chambers are minimum sized. This method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid.

For example, in a rectangular maze, build at random points two walls that are perpendicular to each other. These two walls divide the large chamber into four smaller chambers separated by four walls. Choose three of the four walls at random, and open a one cell-wide hole at a random point in each of the three. Continue in this manner recursively, until every chamber has a width of one cell in either of the two directions.
 

== Simple algorithms ==
[[File:Prim Maze 3D.svg|right|thumb|300px|3D version of Prim's algorithm. Vertical layers are labeled 1 through 4 from bottom to top. Stairs up are indicated with "/"; stairs down with "\", and stairs up-and-down with "x". Source code is included with the image description.]]
Other algorithms exist that require only enough memory to store one line of a 2D maze or one plane of a 3D maze. They prevent loops by storing which cells in the current line are connected through cells in the previous lines, and never remove walls between any two cells already connected.

Most maze generation algorithms require maintaining relationships between cells within it, to ensure the end result will be solvable. Valid simply connected mazes can however be generated by focusing on each cell independently. A binary tree maze is a standard orthogonal maze where each cell always has a passage leading up or leading left, but never both. To create a binary tree maze, for each cell flip a coin to decide whether to add a passage leading up or left. Always pick the same direction for cells on the boundary, and the end result will be a valid simply connected maze that looks like a [[binary tree]], with the upper left corner its root.

A related form of flipping a coin for each cell is to create an image using a random mix of forward slash and backslash characters. This doesn't generate a valid simply connected maze, but rather a selection of closed loops and unicursal passages. (The manual for the [[Commodore 64]] presents a BASIC program using this algorithm, but using [[PETSCII]] diagonal line graphic characters instead for a smoother graphic appearance.)

== Cellular automaton algorithms ==
Certain types of [[cellular automata]] can be used to generate mazes.<ref name=ca>{{cite web|url=http://www.conwaylife.com/wiki/index.php?title=Maze|title=Maze - LifeWiki |author=[http://www.conwaylife.com/wiki/index.php?title=User:Nathaniel Nathaniel Johnston] ''et al'' |date=21 August 2010 |publisher=LifeWiki |accessdate=1 March 2011}}</ref> Two well-known such cellular automata, Maze and Mazectric, have rulestrings B3/S12345 and B3/S1234.<ref name=ca /> In the former, this means that cells survive from one generation to the next if they have at least one and at most five [[Moore neighbourhood|neighbours]]. In the latter, this means that cells survive if they have one to four neighbours. If a cell has exactly three neighbours, it is born. It is similar to [[Conway's Game of Life]] in that patterns that do not have a living cell adjacent to 1, 4, or 5 other living cells in any generation will behave identically to it.<ref name=ca /> However, for large patterns, it behaves very differently.<ref name=ca />

For a random starting pattern, these maze-generating cellular automata will evolve into complex mazes with well-defined walls outlining corridors. Mazecetric, which has the rule B3/S1234 has a tendency to generate longer and straighter corridors compared with Maze, with the rule B3/S12345.<ref name=ca /> Since these cellular automaton rules are [[deterministic]], each maze generated is uniquely determined by its random starting pattern. This is a significant drawback since the mazes tend to be relatively predictable.

Like some of the graph-theory based methods described above, these cellular automata typically generate mazes from a single starting pattern; hence it will usually be relatively easy to find the way to the starting cell, but harder to find the way anywhere else.

==Python code example{{clarify|reason=Which algorithm does this code implement??|date=October 2014}}==
<source lang="python">
import numpy
from numpy.random import random_integers as rand
import matplotlib.pyplot as pyplot

def maze(width=81, height=51, complexity=.75, density=.75):
# Only odd shapes
shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)
# Adjust complexity and density relative to maze size
complexity = int(complexity * (5 * (shape[0] + shape[1])))
density = int(density * (shape[0] // 2 * shape[1] // 2))
# Build actual maze
Z = numpy.zeros(shape, dtype=bool)
# Fill borders
Z[0, :] = Z[-1, :] = 1
Z[:, 0] = Z[:, -1] = 1
# Make aisles
for i in range(density):
x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2
Z[y, x] = 1
for j in range(complexity):
neighbours = []
if x > 1: neighbours.append((y, x - 2))
if x < shape[1] - 2: neighbours.append((y, x + 2))
if y > 1: neighbours.append((y - 2, x))
if y < shape[0] - 2: neighbours.append((y + 2, x))
if len(neighbours):
y_,x_ = neighbours[rand(0, len(neighbours) - 1)]
if Z[y_, x_] == 0:
Z[y_, x_] = 1
Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1
x, y = x_, y_
return Z

pyplot.figure(figsize=(10, 5))
pyplot.imshow(maze(80, 40), cmap=pyplot.cm.binary, interpolation='nearest')
pyplot.xticks([]), pyplot.yticks([])
pyplot.show()
</source>

==See also==
* [[Maze solving algorithm]]

==References==
{{reflist}}

==External links==
* [http://www.jamisbuck.org/presentations/rubyconf2011/index.html Jamis Buck: HTML 5 Presentation with Demos of Maze generation Algorithms]
* [http://www.astrolog.org/labyrnth/algrithm.htm#perfect Think Labyrinth: Maze algorithms] (details on these and other maze generation algorithms)
* [http://www.martinfoltin.sk/mazes Maze Generation ] - Master's Thesis (Java Applet enabling users to have a maze created using various algorithms and human solving of mazes)
* [http://rosettacode.org/wiki/Maze Collection of maze generation code] in different languages in Rosetta Code
* [http://totologic.blogspot.com/2013/04/maze-generation-in-3d.html Maze generation and navigation in 3D]
* [http://totologic.blogspot.com/2014/09/triangulated-circular-maze-generation.html Triangulated circular maze generation] with Daedalus Lib

[[Category:Mazes]]
[[Category:Algorithms]]
[[Category:Random graphs]]
[[Category:Articles with example Python code]]