Random Walk Simulation | Hacker News Reader

Random Walk Simulation

random-walk.fly.dev

26 pointsparthchopra27 comments

It's surprising that there have been few applications of random walks for random human walking:

https://en.wikipedia.org/wiki/Random_walk#Applications

Well... I made one... https://unli.xyz/walk/

    Doc: And in the future, we don't need horses. We have motorized carriages called automobiles.
    Jeb: If everybody's got one of these auto-whatsits, does anybody walk or run anymore?
    Doc: Of course we run. But for recreation. For fun.
    Jeb: Run for fun? What the hell kind of fun is that?

To be fair this isn't really a _random walk_ but it is a random walk

> few applications of random walks for random human walking

I've heard a hypothesis that an advantage of dubious fortune-telling techniques (entrails, tea leaves, etc.) for hunter-gatherer societies is that random choice of prey and direction each day keeps them from over-exploiting any given resource to extinction.

A weird flex Indian Rajas were said to have done is to release a horse and then follow it, offering to fight anyone they met upon the resulting (not so random) walk. https://en.wikipedia.org/wiki/Ashvamedha

I have read both ancient sword fighters and modern fencers advise to consciously plan an attack, but unconsciously trigger it: by letting noise from the environment decide the moment T=0, you're less likely to give your opponent any tells.

One might imagine that divination before battle would provide what the modern world calls a "mixed strategy" and could indeed by superior to pure strategies. (compare the SSBN; see also https://www.atlanticcouncil.org/in-depth-research-reports/is... )

On a more peaceful note, if you wish to choose between popular dinner spots, it may be best to make the selection at hazard: http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...

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.

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.

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.

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.

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!

Does not appear to work properly in Firefox.

It does work on Firefox on my side.

Same here. Firefox 123.0.1 on openSuse Tumbleweed.

My PhD was in an area where we often thought about diffusion of biological molecules, and my boss lent me "Random Walks in Biology", by Howard C Berg [1]. It is very readable and has just the right amount of maths.

Just mentioning in case you find it interesting. PDF copies are probably out there.

[1] https://www.amazon.co.uk/Random-Walks-Biology-Howard-Berg/dp...

This is beautiful! A button / service to easily export the rendered image for purchase such that I could wall mount it would be an easy way to monetize this. Something I'd gladly pay for. (yes, yes, I could print this myself but a service that printed this on nice paper and shipped it to me in sizes I couldn't recreate on my home printer is what I am getting at)

Hmm, somehow it does not work at all in Firefox Developer edition though. Thought I'm missing something at first.

I like how it looks! Would prefer 2 textboxes for the inputs rather than inputs/some stats about how many unique points it's visited before.

reminds me of the pipes animation in old microsoft screensavers!

Results look like a map for Spindizzy (my favorite 8bit game).

Reply on news.ycombinator.com