Talk:Random walk

RMS Distance (1D)

Actually, the average distance after n steps is of the order of ${\sqrt {n}}$ for practically any definition of average. So the original formulation was quite correct. I made some "compromise" with Miguel, but thinking about it, maybe this sentence can be just removed? What do you say?

You're probably right, except that the root-mean-square is *exactly* sqrt n. I wouldn't remove it, it is one of those intuitive statements that are useful to know. Note that I did not replace "average" by "root-mean-square", but rather supplemented the nontechnical statement with a technical one. — Miguel 18:17, 16 Jul 2004 (UTC)

Can someone show a proof that the rms is exactly sqrt n? This is not a Poisson distribution, it's a random walk - see e.g. http://mathworld.wolfram.com/RandomWalk1-Dimensional.html and i seem to have a simple proof that it's wrong:

The (absolute) distance x after n steps can be anywhere in the range from 0 to n inclusive. Taking the definition from root-mean-square, the only way that x_rms can equal sqrt n is if x_i = n for every i. This is clearly wrong, since x_i should range from 0 to n (with probabilities related to the binomial distribution). Therefore x_rms must be strictly less than sqrt n. QED.

So i've modified the rms statement. Please show that my proof is wrong and the sqrt n is right if you wish to reinstate the exactly claim. Boud 13:38, 29 Apr 2005 (UTC)

Your proof is wrong. The mean squared distance is n², not n, ,if x_i = n for every i, giving an RMS distance of n, not sqrt(n).

Sqrt(n) is indeed the correct RMS for a symmetrical random walk, and is always less than or equal to n. Jheald 17:05, 5 February 2007 (UTC)

I can't provide a correct proof (that's what I'm looking for), but I can show you that your proof is invalid. It was a simple oversight: when you sum over the values, you square them first. If every value is n, then the RMS is n, not sqrt n. Luqui 05:21, August 15, 2005 (UTC)

Surely the sqrt(2/pi) factor for the direct mean (as opposed to the rms) is only for the 1 dimensional walk (see the above referenced Mathworld 1-d walk article)? If so, this should definately be pointed out in this article. The proof that the rms is exactly sqrt(n) in 2d (and 3d) is easy to show...see the link in the Mathworld article to the 2d random walk. I have never seen a value for the 'direct' mean in the 2d walk...I assume it's probably next to impossible to calculate, hence why people only worry about the rms, but I assume it wouldn't be sqrt(2/pi). ScottRShannon 05:45, 5 October 2005 (UTC)

In 1 dimension, starting from 0, for n steps there are 2^n possible paths p each with some ending point E(p). The sum over p of (E(p))^2 is exactly n*2^n (easy proof by induction). The mean value of (E(p))^2 is therefore n and the rms is therefore sqrt(n).

Sketch of inductive proof: Clear if n=0. Suppose true for some fixed n. In going from n to n+1, each summand x^2 is replaced by two summands (x-1)^2 + (x+1)^2 = 2x^2+ 2. The sum S of all 2^n terms therefore goes to 2S + 2*2^n. Since S = n*2^n by hypothesis, the new sum is n*2^(n+1) + 2^(n+1) = (n+1)*2^(n+1), as desired. — Preceding unsigned comment added by [[User:{{{1}}}|{{{1}}}]] ([[User talk:{{{1}}}#top|talk]] • [[Special:Contributions/{{{1}}}|contribs]])

A useful thing to note in the 1D case is that you must move on every step.

So the number of moves to the left m_L is simply n - m_R; and x = m_R - m_L = 2 m_R - n.

But m_R has a binomial distribution, with mean n p and variance n p q. So the mean square distance, <x²> is given by

<x²> = <(2 m_R - n)²>

= 4 <m_R²> - 4 <m_Rn> + <n²>

= 4 (<m_R>² + var(m_R)) - 4 <m_Rn> + n²

= 4 n²p² + 4 n p q - 4 n²p + n²

= 4 n p q + n²(2 p - 1)²

= 4 n p q + n²(p - q)² (ie: the square of the mean, plus the variance)

= n if p = q = 1/2.

-- Jheald 17:05, 5 February 2007 (UTC)

Stricto Sensu

Well, I didn't really see the point here. A graph is a graphic representation of something and there is no "strict sense" in which it has to be one way or the other. The time axis is just as important as the space axis. Could you please clarify? Gadykozma 05:17, 24 Jul 2004 (UTC)

Well, the walk takes place in space, so it is only "upwards" or "downwards". It gets difficult for beginners to grasp this if they only see the planar representation. But I may be overly cautios and punctillious. Pfortuny 10:14, 24 Jul 2004 (UTC)

Cities are Infinite?

I don't agree that cities are infinite. Maybe the word can be changed to indicate that cities are vast, but not infinite. "Imagine now a drunkard walking around in the city. The city is infinite and completely ordered, and at every corner he chooses one of the four possible routes (including the one he came from) with equal probability."

it doesn't say cities are infinite, it says "imagine a city [which is] infinite". This is is mathematics. --Taejo | Talk 15:31, 11 November 2005 (UTC)

clarification and consistency of figure

I just added a sentence at the end of the first paragraph of the relation to brownian motion section.

Basically the reason is that this article says:

"Brownian motion is the scaling limit of random walk in dimension 1."

Whereas the brownian motion article says:

"The term Brownian motion (in honor of the botanist Robert Brown) refers to either

1. The physical phenomenon that minute particles immersed in a fluid move about randomly; or

2. The mathematical models used to describe those random movements."

It's only 2. that is the scaling limit for a random walk. 1. is just a particular type of random movement (follwing the langevin equation).

Then I have another consistency problem, with the picture that shows "steps" of a brownian motion (it's in both articles). If a brownian motion has steps, then it's a random walk, it's not the scaling limit. If we are speaking of brownian motion as a scaling limit, then there can't be any discernable steps (i.e. the steps are infinitesimal).ThorinMuglindir 13:45, 27 October 2005 (UTC)

OK now I understand the picture... Well, the caption in the random walk article should be the same as in the brownian motion article. It is rather important to mention that each step is distributed according to a normal distribution, because that's what makes it "brownian motion" (the scaling limit of the random walk).ThorinMuglindir 14:32, 27 October 2005 (UTC)

error/precision in average distance

For a mere (uncorrelated) random walk, if the steps are constant and equal to 1 unit then for the distance from the starting point (net displacement): - the rms is equal to sqrt(n) in both 1 and 2 dimensions (the expected net squared displacement is equal to n) - the average distance asymptotes to sqrt(2n/pi) in 1 dimension but to sqrt(pi*n/4) in 2 dimensions (as consequences of the distribution of a khi law with 1 or 2 dof) - the expressions for correlated random walks are much more complex

simon.benhamou@cefe.cnrs.fr

Langton's Ant

Should Langton's Ant be mentioned (and linked to) as another example of a random walker, or is that diverting too far from the main point? 213.106.64.203 17:09, 20 January 2006 (UTC) Buckjack

There doesn't seem to be any randomness in Langton's ant.--GrafZahl 07:41, 21 January 2006 (UTC)

Non-encyclopedic POV

This article tells the reader to imagine things and asks rhetorical questions. This is not written from an encyclopedic POV, and these parts should be replaced or deleted. Steevven1 ^{(Talk) (Contribs) (Gallery)} 13:40, 5 February 2007 (UTC)

The language used here is fairly standard fare for a mathematics discussion. The "Imagine..." is setting up an analogy to the problem, and the question "Will the drunkard ever get back to his home from the bar?" then asked is not rhetorical, it is also analogy to the equivalent hypothesis, "A random walk from point A will eventually reach point B". While it may seem "non-encyclopedic" to someone who does not frequently read lay-discussions of mathematics, this is probably the clearest way to illustrate this concept. Dolohov 19:57, 12 March 2007 (UTC)

Reorganization

I added a picture and sorted the sections with the more elementary on top. This makes the article a bit non-rigorous (with examples and pictures before the definition) but should make for a better read I hope. Oleg Alexandrov (talk) 03:19, 18 April 2007 (UTC)

A random walk will always return to the origin regardless of the number of dimensions.

What is wrong with this explanation, assuming that "In a one dimensional random walk every point (including the origin) is crossed an infinite number of times in an infinite amount of time." is true?

In a one dimensional random walk every point (including the origin) is crossed an infinite number of times in an infinite amount of time. If we add a second dimension the line representing the point in the original 1 dimension will be crossed an infinite number of times. Since both dimensions are independent of each other there will be an infinite number of occurrences of both dimensions crossing the origin at the same time. This analogy can be extended to any number of dimensions where the third dimension will cross the plane, representing the original 2 dimensions, an infinite number of times.

From this I would conclude that a random walk will always return to the point of origin regardless of the number of dimensions if an infinite amount of time is allowed. In other words there always exists the chance that a random walk will take the shortest possible path to it's origin at any point in time and space. For example after n steps the random walker could be at coordinate (0,0,n) with probability $p=\left({1 \over 6}\right)^{n}$ thus there exists with equal probability that the random walker would take the shortest path to the origin from the farthest possible distance. How can their exist a chance that it would never(p=0) return to the origin if their always exists(p>0) a chance that it could return to the origin in any finite number of steps from any conceivable (Manhatten) distance from the origin. --ANONYMOUS COWARD0xC0DE 03:46, 2 June 2007 (UTC)

What mathematicans are usually concerned with is if the random walk visits a given point infinitely many times, not just one time. In particular, a simple symmetric random walk on the d-dimensional lattice doesn't visit any point infinitely often for dimension greater than two. The section on higher dimension needs this distinction to be brought up and clarified. Filam3nt 22:46, 3 June 2007 (UTC)

Lets generalize to 'd' dimensions travelling 'n' units straight out and back to the origin $p=\left({1 \over 2d}\right)^{2n}$. This means their exists a chance for a random walk to return to the origin once in any number of dimensions. Lets say k times: $p=\left(\left({1 \over 2d}\right)^{2n}\right)^{k}$ and $\lim _{k\rightarrow \infty }{\left(\left({1 \over 2d}\right)^{2n}\right)^{k}}=0$, but this also applies to the 2-D case so their must be something I am missing. In addition [1] never mentions a random walk returing to the origin an infinite number of times. --ANONYMOUS COWARD0xC0DE 03:46, 29 June 2007 (UTC)