Talk:Random walk

Probabilistic interpretation

Please, would you be so kind to give an example of a random walk under this heading, for example, the geometric distribution. It would especially be helpful if you could show how the probability distribution $P(N=n)=p(1-p)^{(n-1)}$ for $n=1,2,3,...$ could be derived in the framework of a random walk as well as the central moments and, if possible, the maximum likelihood estimator for $p$. — Preceding unsigned comment added by Ad van der Ven (talk • contribs) 15:27, 17 June 2011 (UTC)

Higher Dimensions

The article says: "Will the drunkard ever get back to his home from the bar? It turns out that he will" Wouldn't "Will the drunkard always get back to his home from the bar? It turns out that he will" be more accurate? For me "ever" implies any probabilty > 0 (which is trivially true) whereas "always" would more accurately describe "p = 1". --flatfish89 (talk) 17:46, 19 October 2008 (UTC)

As I understand it, with infinite time (as implied by "ever"), any probability > 0 would mean that the drunkard will get home - saying that he always gets home is redundant. --Aseld ^talk 15:48, 7 February 2009 (UTC)

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

Right; I've made this more precise by changing "Brownian motion" to "Wiener process" in that section. David-Sarah Hopwood (talk) 17:16, 12 February 2009 (UTC)

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)

Dolohov, please see Wikipedia:Manual of Style (mathematics) especially the section about writing style in mathematics articles. While it is pretty standard for the mathematics community, it is inappropriate and unnecessary in an encyclopedia. Use of the "royal we" should be avoided whenever possible. Cliff (talk) 06:02, 5 April 2011 (UTC)

Er... do you realize you replied to a comment more than 4 years old? I think it may be time to archive some things on this page. ~Amatulić (talk) 06:26, 5 April 2011 (UTC)

Of course I do. This is my attempt to revive discussion on this point. It makes no sense to create a new section to discuss a topic that still (after 4 years!) Has not been fixed. It's important to see old discussion on a topic. Cliff (talk) 15:57, 10 April 2011 (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)

Nobody's claiming that the probability of returning to the origin is zero. The claim is that in 3 or more dimensions, the probability is less than one. The flaw in your "take each dimension separately" argument is that, although the path will almost certainly cross the x-y plane infinitely often, there's no reason to suppose that any of those crossings will coincide with crossing the y-z plane and the z-x plane. 65.57.245.11 05:26, 10 September 2007 (UTC)

You're right, the crossing coincidence is not certain, just almost certain. However, I don't see why the chance of hitting an arbitrary bound with a 1D walk is anything but almost certain either, which is why I call into question the statement "A simple random walk on $\mathbb {Z}$ will cross every point an infinite number of times." 80.203.160.34 (talk) 14:09, 9 October 2015 (UTC)

I had the same difficulty understanding this so I had to read a book describing the proof. I ended up conceptualizing it as similar in nature to the issue of an escape velocity, although there is a force pulling the two objects together, they never meet. In the same way although there is always a certain non-zero probability that the random walk will return to the origin the probability does not sum to one even after considering an infinite sum in the same way that an infinitely long integral of the force over time applied to an object at it's escape velocity will only, manage to cancel out the momentum, not reverse it (in order to meet). So just think of the third dimension as the "probabilistic" escape velocity of a random walker. I think such an analogy works quite well. 71.147.50.115 (talk) 21:15, 25 March 2010 (UTC)

I just realized that the analogy works quite well in another regard. In three dimensions the inverse square law holds for forces. So the force at a distance 'd' is proportional to 1/d^2. Since $\int _{1}^{\infty }{\frac {1}{x^{2}}}\,dx=1$ is finite it only takes a finite amount of kinetic energy to achieve an escape velocity. Whereas if the forces applied only in two dimensions the force of gravity would be proportional to 1/d, and since $\int _{1}^{\infty }{\frac {1}{x}}\,dx=\infty$ is infinite it would take an infinite amount of kinetic energy to achieve an escape velocity (which is impossible, therefore the probability of returning is always one in less than or equal to two dimensions). 71.147.50.115 (talk) 21:59, 25 March 2010 (UTC)

Drunk Sailor

Rather than drunkard's walk, I remember the term "drunk sailor's walk" - or is this only used in German? —Preceding unsigned comment added by 84.136.218.223 (talk) 14:58, 27 September 2007 (UTC)

Some clarification on the a and b formula in the one dimensional case

Would someone please clarify the sentence leading up to the b/(a+b) formula. a and b are fixed positions. The current usage of "steps" could refer either to steps taken or a fixed number of steps from the origin. It would probably read better like this: "The expected number of steps until a one dimensional random walk goes up to position b or down to position -a is ab. The probability that the random walk will go up to position b before going down to position a is ..." —Preceding unsigned comment added by Speculator mike (talk • contribs) 21:45, 28 September 2007 (UTC)

I tried to derive this property... Ouch ! Could somebody give me little hints of derivation ? Sincerely yours, Damien. — Preceding unsigned comment added by Lamina-le-sédentaire (talk • contribs) 09:15, 12 October 2011 (UTC)

Clarification of the general definition

Does the "move distribution" for a generic random walk have to be independent of the current position? If so (or if not so) could this be specified somewhere in the introduction. If so then presumably the sample space has to follow certain symmetry conditions which depend on the "move distribution." For example you couldn't have a Gaussian random walk on the interval [0,1] because of the boundaries. —Preceding unsigned comment added by 129.31.244.53 (talk) 20:01, 16 October 2010 (UTC)

Redid intro and defition

I revised/expanded the intro somewhat and totally changed the definition. Hopefully the intro covers the topic more broadly. As for the definition, it formerly said:

“ The random walk is a path constructed according to the following rules:

• There is a starting point.
• The distance from one point in the path to the next is a constant.
• The direction from one point in the path to the next is chosen at random, and no direction is more probable than another.

”

This is far too narrow since RW's can be correlated, biased and have any step-length distribution. However, there is some inconsistency in the literature about definitions (for example: is a random walk a kind of Markov process? or are some Markov processes a limited form of a random walk?) and I do not presume that the definition/notation I provide is canonical. Best, Eliezg (talk) 19:57, 14 January 2008 (UTC)

The general case random walk

I found this article over the internet: http://qjmath.oxfordjournals.org/cgi/reprint/4/1/120.pdf . However, some amount of dollars must be paid in order to read it. Could someone please read this article? I think it would be useful for the improvement of this page. —Preceding unsigned comment added by Leoisiah (talk • contribs) 09:17, 13 February 2008 (UTC)

There does need to be some clarification of terminology etc., if the article is to be extended (or split) to deal with more general types of random walks. For example, Feller Vol 2 p 192, use ordinary random walk for the case where steps are of sizes -1,+1 only (with possibly unequal probabilities), but simple random walk for the same case on p213, simple binomial random walk on p393 and binomial random walk on p395, while Feller Vol 1 p363 uses generalized random walk for cases where steps may be of any integer size. In addition, Feller Vol 2 p190 uses general random walk for cases where the step size may have any (1-dimensional) distribution. In all cases the steps are independent across times. Melcombe (talk) 16:41, 11 June 2008 (UTC)

Indeed, there is no perfect consistency in the terminology in textbooks. But that's not a big deal. The article currently is ordered by increasing generality. There is some point to be made that for this particular subject the more general setup of simple random walks on graphs is a better starting point than the specific case of simple random walk on ${\mathbb {Z} }$. But I don't think that this is sufficiently compelling to warrant a rewrite. Oded (talk) 21:24, 15 June 2008 (UTC)

Formal Definition

The article could do with a mathematical definition somewhere, perhaps after the introduction? The descriptive definition is good, but it plunges into examples without a formal statement of what a random walk is. Wjastle (talk) 16:17, 16 August 2010 (UTC)

Even the Mathematica web site has a similar definition: http://mathworld.wolfram.com/RandomWalk.html

However, here's a mathematical one:

For the sum $S_{n}=x_{1}+x_{2}+x_{3}+\dots +x_{n}$, where $\{x\}_{k=1}^{\infty }$ is a sequence of independent discrete random variables, the sequence of sums $\{S\}_{n=1}^{\infty }$ is known as a random walk.

Paraphrased from http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter12.pdf

I'm not sure that such a definition adds any clarity to the article. I wouldn't object if someone adds it, though. ~Amatulić (talk) 17:36, 16 August 2010 (UTC)

Gaussian random walk - Is this really correct?

>For steps distributed according to any distribution with a finite variance (not necessarily just a normal distribution), the root mean squared expected translation distance after n steps is sigma x sqrt(n)

This doesn't seem right. Should it no be "any symmetric distribution" (3rd moment = 0)? —Preceding unsigned comment added by 156.109.18.2 (talk) 11:14, 24 August 2010 (UTC)

The statement is correct. The distance from the origin is the sum of a number of step. The variance of the distance is the sum of the variances of the step. The "root mean squared translation distance" is just the square root of the variance. A slightly odd terminology, which doesn't need the "expected" where it was. But there is no need to assume symmetry, just the existence of the variance of the distribution of steps. Melcombe (talk) 13:58, 24 August 2010 (UTC)

Thank you very much for your reply. I am not familiar with the term "root mean squared translation distance", but the formula seems to say it is sqrt(E(S_n^2)), where S_n is the position after n steps.

Could you clarify my mistake: if I step +1 with probability 1 then sigma is 0 and S_n=n so sqrt(E(S_n^2))=n, which does not seem to match the formula

Also, when you say "root mean squared translation distance" is just the square root of the variance, do you mean the variance of S_n? Again this does not appear to match the formula unless E(S_n) = 0?

Thanks

OK, for that formula a zero mean is required for the step size, and I have put that in. (A zero mean is not the same as symmetry.) I guess some more general formulae could be put in to cover the more general case, but the obvious way to do it would not match in well with the rest of the article. Melcombe (talk) 16:59, 24 August 2010 (UTC)

I originally wrote that section. Thanks for fixing it up. ~Amatulić (talk) 17:09, 24 August 2010 (UTC)

Thanks for the reply. I think this formula is interesting because it says that when the mean is 0 you can expect stay reasonably close to the starting point (within sqrt(n)) no matter what the distribution. In the general case you can be all over the place so the corresponding formula would probably not say very much —Preceding unsigned comment added by 156.109.18.2 (talk) 17:39, 24 August 2010 (UTC)

But, in the more general case, you will be within a smallish distance (within sqrt(n)) of a known location (that depends on the mean step size) that drifts away from zero at a fixed rate, which is actually quite simple. Melcombe (talk) 08:46, 31 August 2010 (UTC)

Clarification of the general definition

Does the "move distribution" for a generic random walk have to be independent of the current position? If so (or if not so) could this be specified somewhere in the introduction. If so then presumably the sample space has to follow certain symmetry conditions which depend on the "move distribution." For example you couldn't have a Gaussian random walk on the interval [0,1] because of the boundaries. 129.31.244.53 (talk) 20:02, 16 October 2010 (UTC)

Bounded random walk

I don't see anything about bounded random walks here. That seems a shame. A walk on a finite graph is finite, OK, but what about the continuous case? e.g. random walk in a space with one boundary (e.g. position can't go below zero). --mcld (talk) 15:32, 19 February 2011 (UTC)

How does this passage square with the transience in 3d ???

The section Random walk on graphs begins as follows:

"Assume now that our city is no longer a perfect square grid. When our drunkard reaches a certain junction he picks between the various available roads with equal probability. Thus, if the junction has seven exits the drunkard will go to each one with probability one seventh. This is a random walk on a graph. Will our drunkard reach his home? It turns out that under rather mild conditions, the answer is still yes. For example, if the lengths of all the blocks are between a and b (where a and b are any two finite positive numbers), then the drunkard will, almost surely, reach his home. Notice that we do not assume that the graph is planar, i.e. the city may contain tunnels and bridges."

Can someone please explain how this is consistent with the fact that the symmetric random walk in 3D (i.e., on the 1-skeleton of the cubical tiling) is known to be transient?

Certainly all "blocks" have equal lengths. The statement "Notice that we do not assume that the graph is planar" seems to allow a grid like this 3D one. What properties of the graph are assumed???

If this is not what is intended here, perhaps the above-quoted statement could be modified to make clear just why such grids as the 3D one (and for that matter all the corresponding nD ones, n ≥ 3) do not qualify. Thanks.Daqu (talk) 23:50, 5 March 2011 (UTC)

This section is extremely confusing and could really do with some rewriting. Or decent citations. I'm really interested in this subject and frustrated that all the sources I can find are hopelessly impenetrable; Someone should really fix this section up! 152.179.216.94 (talk) 15:25, 17 April 2014 (UTC)

I want to submit a couple of Random Walk .gif's

I created an account so I could submit my Random Walk animated gifs but now it tells me I must be Autoconfirmed. Can I just give these to someone to put on the page? I think they're perfect ... small and actually a Random Walk, unlike the Brownian motion simulated by Random Walk video. — Preceding unsigned comment added by DrDInfinity (talk • contribs) 00:59, 2 July 2011 (UTC)

Video not working

I saw Firefox 13.0.1 cannot play the video, it previews, but when I click play, nothing happens. Now3d (talk) 12:22, 6 July 2012 (UTC)

Random walks on graphs

The current section about random walk on graphs is in my opinion terribly written, being vague and unstructured even though the contents are mostly fine. I have written a new version (you can see it at User:Jean Raimbault/sandbox/Random walk; I think the contents are OK for now but I'll probably edit it a bit for readability before moving it to mainspace) with which I would like to replace the current one. On the other hand the material is perhaps a bit technical for a "entry-level" page such as this one and it may be preferable to create a new page for this content, rewriting the material on the main page to be much more lightweight. I personally favour the latter option, in fact I would probably put a large part of the current content in separate pages (in particular the stuff on Pólya's walk feels too massive) and try to make this page more accessible (this seems like a rather long-term project so I cannot claim I'll be able to do a substantial part of this myself). Opinions and comments? jraimbau (talk) 16:46, 30 August 2016 (UTC)