Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Random Walks: the mathematics in 1 dimension

mit.edu

Post reply on HN
Print view View original

1–10 of 19 posts

Re: Random Walks: the mathematics in 1 dimension

#3

Post by Xcelerate »

One might ask the question: what is the probability that you will return to your starting position over the course of an infinite random walk? On a 1 dimensional or 2 dimensional lattice, that probability is 1. What's crazy though is that for a 3D lattice, the probability is not 1 — it's about 0.3405.

Re: Random Walks: the mathematics in 1 dimension

#4

Post by pash »

zodiac wrote: post #2

Isn't the expected distance (undirected) given by E[|d|], while sqrt(n) is the value of sqrt(E[d^2])?

They each measure the same thing, more or less, but it's easier to work analytically with squares than absolute values. Similarly, we tend to work with the variance rather than with expected absolute deviations, we calculate sums of squares rather than sums of absolute values, etc.

More fundamentally, root-mean-square is the norm induced by the expectation inner product in the space of random variables. Norms generalize the geometric notion of length, so intuitively RMS is an appropriate measure of the "stochastic distance" from the origin of a random walk after a set number of steps. RMS can likewise be used as an analogue for geometric length for other purposes in a stochastic context, e.g., in calculating the similarity dimension of fractal stochastic processes like Brownian motion.

Re: Random Walks: the mathematics in 1 dimension

#5

Post by iaw »

Xcelerate wrote: post #3

One might ask the question: what is the probability that you will return to your starting position over the course of an infinite random walk? On a 1 dimensional or 2 dimensional lattice, that probability is 1. What's crazy though is that for a 3D lattice, the probability is not 1 — it's about 0.3405.

Wow, do you have any proofs for this? I'm especially curious about the generalized n-dimensional case.

Re: Random Walks: the mathematics in 1 dimension

#6

Post by tristanj »

Xcelerate wrote: post #3

One might ask the question: what is the probability that you will return to your starting position over the course of an infinite random walk? On a 1 dimensional or 2 dimensional lattice, that probability is 1. What's crazy though is that for a 3D lattice, the probability is not 1 — it's about 0.3405.

I really love this proof. It's a great example of using maths to prove a counter-intuitive result. They way to prove it is rather clever, and made me appreciate what mathematicians do a lot more.

Shame I've never seen it shared online. I was actually hoping the submitted article was a proof of this, but you can't have everything in life.

Re: Random Walks: the mathematics in 1 dimension

#8

Post by hemmer »

iaw wrote: post #5
Xcelerate wrote: post #3

One might ask the question: what is the probability that you will return to your starting position over the course of an infinite random walk? On a 1 dimensional or 2 dimensional lattice, that probability is 1. What's crazy though is that for a 3D lattice, the probability is not 1 — it's about 0.3405.

Wow, do you have any proofs for this? I'm especially curious about the generalized n-dimensional case.

There is some more information and references here: http://mathworld.wolfram.com/PolyasRandomWalkConstants.html

Re: Random Walks: the mathematics in 1 dimension

#9

Post by sdoering »

hemmer wrote: post #8
iaw wrote: post #5

Earlier quoted context omitted.

Wow, do you have any proofs for this? I'm especially curious about the generalized n-dimensional case.

There is some more information and references here: http://mathworld.wolfram.com/PolyasRandomWalkConstants.html

Thanks a lot. Had to save this for further reference the moment I saw it.
Post reply on HN