Hacker News Reader

Comment by parthchopra | Hacker News Reader

Found this interesting random walk simulation. I thought random walks tended to stay close to the initial state, regardless of the number of steps/step size, but this simulation ends up making some pretty cool random walk art.

View on HN

An interesting fact: a 1D random walk will almost always return to the origin (as in, given an infinite number of runs, only finitely many will not return to the origin), wheras a 2D random walk will almost never return to the origin (of an infinite number of runs, only finitely many will return to the origin). Of course, this is directly saying much about the average distance from the origin, which slowly increases with steps as mentioned by others.

The expected distance is something like constant*sqet(N)*L where N is the number of steps and L in the lenght of each step.

Random walks have plenty of counter-intuitive properties when it comes to returning to the origin.

- The average distance from the origin increases as time goes on.

- But the average coordinate any given step ends up on is and remains the origin for the duration of the walk.

More weirdly, though I don't know if this is true in two dimensions (ah, a sibling comment states it only holds in one dimension -- thanks!)

- As time goes on, a single random walk will take longer and longer to return to the origin.

- But a single random walk still returns to the origin infinitely often!

You might be thinking of the bounded case? I think maybe a 1d random walk bounded on one side will tend to stay near to the origin.

> I thought random walks tended to stay close to the initial state...

Can you remember from where you got that impression?

If randomness is evenly distributed in a random walk, it tends to stay close to the starting point.

Edit: Plot of steps Timestamp: 34:49

https://ocw.mit.edu/courses/6-0002-introduction-to-computati...

It'll gradually creep away*, proportionally to sqrt(t).

Got a timestamp in that video that says differently?

* in the absence of (restoring) forces, it's unwise to rely on things staying where you left them, as that'd be betting against entropy. Lagniappe: https://www.youtube.com/watch?v=i6rVHr6OwjI

EDIT: even more apropos: https://www.youtube.com/watch?v=ObvxPSQNMGc

Think of it this way: if randomness is evenly distributed, the steps to the left and right will balance out, just as the steps up and down will. This balance tends to keep the random walk close to its starting point.

Except they don't balance.

(if they do balance, your walk is not very random. https://en.wikipedia.org/wiki/Cyril_Burt#Scientific_miscondu... was caught faking data because his residuals were improbably small)

Exercise: how many strings of length N with the alphabet {R,L} are there where #R = #L?

Exercise: as above, but for #R = #L + k

See also Haldane, "The Faking of Genetical Results" pp8-10 in https://archim.org.uk/eureka/archive/Eureka-6.pdf

They can balance but still be random -- that's the essence of drawing without replacement, or the hypergeometric distribution.

What you probably mean is that they are no longer independent.

You're right. (I'd count enforcement of "without replacement" as a force; at least for classical walks it'd require some kind of Maxwell daemon?)

I guess what I want to get at: a Galton board is easily understood by elementary school students (and probably constructible by those in the upper grades), and it doesn't take much time playing with one to notice that all the balls don't wind up with their paths balanced out, in the middle column.

(even the normal distribution is misleading, because centrality is a 1D phenomenon; given enough dimensions observing the exact average becomes exceedingly unlikely)

If you take the same Galton board and focud on the paths taken by all balls that ended up in a particular bin you get the hypergeometric distribution for the steps they have taken. So the draws without replacement lurk in the Galton board too.

It does, in other words, not require a demon, only a restricted viewing angle.

TIL!

> Page unintentionally left blank. —CS

Skämtar du med mig?

Another way to think about it: the more steps, the more likely it is you get a run which is imbalanced for long enough to make it some given distance from the origin.

That balance will only tend to keep the average coordinate near the starting point. But the variance/std dev will increase without bound.

Although you are correct, the goal of the comment was to illustrate why random walks would gravitate towards their starting point.

Reply on news.ycombinator.com