Why Do Random Walks Get Lost in 3D?

In this video, we try to gain some intuition for why symmetric random walks are recurrent in 1 and 2D, but transient in 3D. This was proved by mathematician George Pólya in 1921.
Links for further reading:
Awesome demos of random walks by Russell Lyons (rdlyons.pages.iu.edu/rw/rw.html)
Analysis of high-dimensional random walks by Gregory Lawler, including expected escape time (www.math.uchicago.edu/~lawler/...)
Lecture on random walks by Andrej Košmrlj, including some physics and biology connections (www.princeton.edu/~akosmrlj/M...)
Special thanks to Ryan Adams, Elmira Amirloo, Alex Beatson, and Yair Shenfeld for feedback on this video.
Some of the animations in this video were created with 3Blue1Brown's manim library (github.com/3b1b/manim​).
Music: Trinkets by Vincent Rubinetti
Links:
KZbin: / ariseffai
Twitter: / ari_seff
Homepage: www.ariseff.com
If you'd like to help support the channel (completely optional), you can donate a cup of coffee via the following:
Venmo: venmo.com/ariseff
PayPal: www.paypal.me/ariseff

[@vi5hnupradeep]

This channel is so terribly underrated ! Good work man 💯

[@alexistorstenson]

super cool video! i'm watching this in the middle of the night after my math major friend told me about his research project involving random walks. been absolutely fascinated by the concept since i heard of it and this does a great job of breaking it down!

[@rinfrinkleko695]

What a great video! Thank you to share such a wonderful video that vividly explained the random walks. I was recently take research about graphs, you explaination about random walks really help me to understand it.

[@MrMareczek111]

Those videos are so high quality

[@pafloxyq]

nice one !!!...it feels so gr8 to see people using Manim to make such videos.

[@the_real_amir]

Thanks for making this video. Very well made

[@tedsheridan8725]

Great video. This is much more elegant and easier to follow than Mathamaniac's video.

[@bryanbischof4351]

I hadn’t previously thought of this result in concentration or measure! I think this is a good connection!

[@shamtradtam3769]

Pretty awesome explanation

[@user-tx2xg6ed3b]

Great video! 9:20 How does it follow from the fact that the expectation of the number of visits to the origin is infinite that the probability of returning to the origin is 1?

[@CBV0097]

Outstanding video!

[@farouku5334]

Hello! I’m a freshman at pton and I was wondering which class I may be able to take so I can learn more about the proofs? ORF 309 maybe?

[@ariseffai]

ORF 309 would be a great one to take. Good luck with your studies!

[@francois__]

Very cool!

[@rushikeshshinde2325]

Great Video!! I have been wondering about this question, Does walker will return if it is walking on a S^3 aka sphere with 3 dimensional surface?

[@andrewwang7528]

Yes, any path which returns to the origin in a walk in 2 dimensions also returns to the origin in a walk along a sphere as well as any other manifold isomorphic to Z^2

[@cubing7276]

@@andrewwang7528it's a sphere whose surface looks 3 dimensional

[@cubing7276]

not a 3 dimensional sphere

[@DC01]

Hey, nice video. I had a doubt at 9:25, as you mentioned the expected number of returns to the origin is infinite, but how does that tell us anything about the probability of returning to the origin?

[@ethanblackthorn3533]

awesome video

[@antares1694]

at 10:00, is it okay to multiply the two probabilities like that? The two events aren't independent as for every step along y, you don't take one along x. I'm sure the resulting series will still diverge, but there are others factors to account for.

[@drdca8263]

This was using the equivalence to two simultaneous 1d walkers, after applying a rotating and scaling

[@n8likesmath]

Quality video

[@superevilgoldfish]

13:05 isn't clear to me. Why do you say that the expected # of steps when you first reach distance r =r^2 ? Just before you said that regardless of dimensionality, the expected distance squared is n. So I thought that you would have expected # of steps when you first reach distance r =r^0.5 instead . I tried to follow you from a different path. If the walker is 'not drunk' and in dimension d, than to get to a distance r he needs to take r/sqrt(d) in each dimension(r^2=x^2+y^2+z^2 ->x,y,z=r/sqrt(3) , total # of steps n=3*r/sqrt(3)). So the number of steps he needs to take in total to get to r is d*r/sqrt(d) , which scales like sqrt(d) for a given r. You can see it diverges but I feel it's not as strong as your argument. I hope my question is clear, I would love to understand your last argument :)

[@ariseffai]

Hmm, I think there's a simple mistake in your reasoning. After n steps, for any n, the expected squared distance is n. So after r^2 steps, the expected squared distance is r^2. Now, I'll leave you with this question: after r^2 steps, what is the expected distance (non-squared)? :)

[@user-tx2xg6ed3b]

@@ariseffai it is not so clear for me too... Could you explain this in details?

[@rmschindler144]

I wonder if there are different species of ‘random’.

[@hellogoodbye4894]

What is the probability of returning in 4D?

[@ariseffai]

mathworld.wolfram.com/PolyasRandomWalkConstants.html lists the probabilities for the first 8 dimensions.

[@navyatayi6956]

For the 1-D case, P(Sn=0) is proportional to 1/under root(n) Now, if n tends to infinity wouldn't the probability become 0? but when we calculate it through the indicator variable we get the probability as 1 So I am confused about this. It would be of great help if you could clarify this doubt since I am stuck trying to understand this. Thank you for this amazing video!

[@drdca8263]

P(S_{2n}=0) tends to zero as n tends to infinity, but P(there exists an n>0 such that S_{2n}=0) is 1. E[1_{S_{2n}=0}] is proportional to 1/sqrt(n) , But/therefore the sum over all positive natural numbers n of E[1_{S_{2n}=0}] is infinite, and so expected number of times origin is visited, is infinite. And so probability that it will eventually is 1.

[@Niglnws]

It is like as you increase number of coin flips, the probabilities tend to 0. When you flip a coin you have 50% to get 50% heads. But for 1000 flips, you have a very small probability value to get 50% heads. I bet i can get 2 heads out of 4 experiments but i wont bet that i can get 500 heads out of 1000 experiments. Although the expected value is 500. Here the probability to return after exactly like 1000 steps to 0 is somehow small. But to return after 2 steps is more probable (we are still in the area). Because higher steps means higher variance (we may reach +1000, it is probable). But that doesnt mean we didnt path the origin during our trip. During the 1000 steps we are more likely to have passed thr origin many times. But to say that at exactly the 1000 step we are at the origin is not likely. Consider the graph of the 1d random walk where the y axis is the distance you reached and the x axis is the time or number of step. You will fluctuate around the zero and you will cross the x axis many times but the amplitude of fluctuations is probable to be higher as we go further in time or steps. As we flip the coin more, the difference between heads and tails may increase largely. At n=1 one head and 0 tail the difference is 1. As n increase, you may have 600 tail and 400 head, we are away from the zero by distance 200. But during the 1000 steps we may have crossed the zero many times where we have equal heads and tails. It is logical as we go more we may cross the x axis more.

[@Niglnws]

I understand it almost well. But i am not good at infinities mathematics and about how some infinities are greater than others. But i believe that if 3d walk given infinite steps greater than the infinity of the 2d walk, i t will return at least once with a probability reaching 1. Before i watched the video and saw hoe you simulate the 2d walk as 2 of the 1d. I thought of something similar which is the plane of x,y and that plane go into and out of the screen or paper as the z axis with probabilities 0.5. If in the 2d walk or the xy plane we return infinite number of times, and Also the z direction as a 1d walk return to 0 infinite number of times, then they probably meet infinite number of times but here with infnity less than infinity in 2d. So i compensate the 3d by giving it a very large infinity to guarantee that the infinity of xy meet the infinity in case of 1d (z axis walk). 😶

[@tianjiaowang4969]

Why is three simultaneous 1D walks has 8 outcomes at each steps? I thought it was 6

[@sagebauer1077]

left or right, up or down, forward or backwards. in three simultaneous 1d walks, you could have 8 combinations (left&up&backward for example). but in a 3d walk you only have one of those 6 options, not a combination

[@tianjiaowang4969]

@@sagebauer1077 Thank you, that's helpful

[@kfurgie999]

I assume this is related to why space has 3 spatial dimensions

[@thisisnotmyrealname628]

woo thats cool