Random walks in 2D and 3D are fundamentally different (Markov chains approach)
HTML-код
- Опубликовано: 4 июн 2024
- Second channel video: • Explicit calculation: ...
100k Q&A Google form: forms.gle/BCspH33sCRc75RwcA
"A drunk man will find his way home, but a drunk bird may get lost forever." What is this sentence about?
In 2D, the random walk is "recurrent", i.e. you are guaranteed to go back to where you started; but in 3D, the random walk is "transient", the opposite of "recurrent". In fact, for the 2D case, that also means that you are guaranteed to go to ALL places in the world (the only constraint is, of course, time). [Think about why.]
Markov chains are also an important tool in modelling the real world, and so I feel like this is a good excuse for bringing it up.
At the end, I also compare this phenomenon to Stein's paradox - in both cases, there is a cutoff between 2 and 3 dimensions, and they have similar intuitive explanation - is that a coincidence?
Video chapters:
00:00 Introduction
00:59 Chapter 1: Markov chains
03:20 Chapter 2: Recurrence and transience
10:08 Chapter 3: Back to random walks
Further reading:
Larry Brown’s paper: stat.wharton.upenn.edu/~lbrown...
Using electric circuits to prove recurrence / trasience: math.dartmouth.edu/~pw/math10...
More complicated, but more general proof: sites.math.washington.edu/~mo...
Actual probability for 3D random walk to come back: mathworld.wolfram.com/PolyasR...
Other than commenting on the video, you are very welcome to fill in a Google form linked below, which helps me make better videos by catering for your math levels:
forms.gle/QJ29hocF9uQAyZyH6
If you want to know more interesting Mathematics, stay tuned for the next video!
SUBSCRIBE and see you in the next video!
If you are wondering how I made all these videos, even though it is stylistically similar to 3Blue1Brown, I don't use his animation engine Manim, but I will probably reveal how I did it in a potential subscriber milestone, so do subscribe!
Social media:
Facebook: / mathemaniacyt
Instagram: / _mathemaniac_
Twitter: / mathemaniacyt
Patreon: / mathemaniac (support if you want to and can afford to!)
Merch: mathemaniac.myspreadshop.co.uk
Ko-fi: ko-fi.com/mathemaniac [for one-time support]
For my contact email, check my About page on a PC.
See you next time!
Second channel video: ruclips.net/video/KnWK7xYuy00/видео.html
Please watch it because I spent an unjustified amount of effort into that video (it was originally meant to be on the main channel).
Of course, please submit your questions here: forms.gle/BCspH33sCRc75RwcA
Also, I have moved to a room literally next to a highway (?), and so I'm sorry for the constant traffic in the background. I have tried almost everything I can to damp it down, but it still shows up in the audio.
Right, thanks for pointing it out!
Does this hold for a hexagonal grid? It would give six options for each step like with the 3D case, but you could return on odd steps too.
@@BeaDSM "we leave this as an exercise for the reader" ;-)
The 'inside / outside' argument hold for 2d hex grids, so I would say yes. I don't see how you could return on an odd step with hex grids (moving vertex to vertex along edges). You could in a triangular grid though (but in that config you can't return on even steps).
@@mathemaniac can you tell best book to learn complex analysis??
In this video it is mentioned that P(V>=k) = P(V>=1)^k, but I think it should be P(V=k) = P(V=1)^k.
These two are different, can anyone confirm?
(My English is not good, so I used a translator.)
Good to know my dad will fome back one day 😅
It's just a matter of time.
but your dad remembers where has he been, though :
Unfortunately, he is not random.
well if he went to get cigarettes, the smoke will cause a paradox as the smoke will not reutrn home, and if the smoke doesnt return home, your dad cant be home.
Sorry that your dad might be not just walking on a 2D surface, but also flying up and down, ending up with motions in a 3D space.
Seven years ago I got a golden medal in my country's math olympics. There were several events before the ceremony, and one of them was a talk from a famous mathematician about this exact topic. He told us about a story about the random walk in 1 and 2 dimensions, and that it's different in the 3rd. Right when he was about to explain the reason the drunken bird may never get back to his nest, a staff member called me and my friends out of the auditorium and we never got to know the ending. I was so frustrated and disappointed. I tried searching it on Google but back then every result I found was way too complex for me to understand. Today, seven years later, you finally answered the question.
I am so grateful for this video and for the algorithm having recommended it to me. It's such a specific and niche thing but I was a curious kid and it has bothered me so much for so long. I thought I'd regret leaving that lecture for the rest of my life. Thank you.
I had same for long and short scales of numbers. This was a pleasure to get the question closed.
omg
should have stayed
@@wilesmith Please reread this comment
0。0
I loved it when you kinda pause, and when you asked "wait why do we care again?" after setting up the foundation to answer the question. Made the end feel more rewarding, nice!
Thank you!
I agree, if this was a class i would be annoyed because everyone should be paying attention. But it's RUclips and it's much more relaxing to be reminded why we are doing what we are doing.
Damn must be even harder to return home for drunk 4-dimensional birds
The way this video is structured is… odd. I feel like I’m constantly being told “all we have to do is this!” And then you present a very slight manipulation that clearly doesn’t actually solve the hard part of the problem, and then after the simple manipulations run out, I’m told “but this is too complicated for this video. Sorry!” :/
I agree. This video was... strange.
I feel like this didnt even explain why the 2nd dimension random walk is forcibly recurrent, with my understanding there is still the possibility that the drunken man never returns, as the 2d space still is infinite. it may be less probable for the bird to return, as it has an additional dimension, but i dont get why it should be imposssible for the man to never return (in an infinite space, not talking about a planets surface or smthn)
@@sirhenryvonvandings there is an explanation though. She proved that with probability 1 you will go back to the origin infinitely many times (events with probability 0 may still happen btw). I agree that there was a lack of insight as to why this is, except for the bit at the end.
I agree; every time he said recurrent or transient I was silently screaming "but you're still just ASSERTING that it's recurrent/transient in the 2D/3D case; you haven't PROVED a damn thing!" And then we get half a second of some combinatorial expression and we're told "this scales as the harmonic series and this scales as less than that (somehow)" still with no proof. If something is too complicated to show in a video, maybe don't make a video purporting to show it. Just a thought.
Not everyone is meant to be an online educator/presenter. I don't believe this person is one of them
I'd bet you are aware, but you are mixing up "something is guaranteed" and "something has probability 1". It is possible for a random walk to go in one direction forever (of course, therefore never returning). This walk has just probability 0 (just as any other specific walk). Cool video!
Yes, many people have pointed it out - I probably should have said "almost guaranteed", as in "almost surely".
I don’t know if “it is possible for a random walk to go in a single direction forever” is precisely correct. It is true that there is non-zero probability that a random walk can go in a single direction for any finite number of steps.
@@benjamingoldstein14 it is possible; actually, it's just as likely as any other infinite random walk.
@@chrisc6468 I am just uneasy thinking about a random walk continuing “forever” - it’s weird thinking about “the set of infinite random walks” rather than a limit converging almost surely.
@@benjamingoldstein14 That’s the question, I think infinity is purely a mathematical conception, and perhaps it may not exist in reality. In the same way a mathematically defined sphere is super rare in nature, infinity is also probably rare or non-existent. Theoretically, given the mathematical model/scenario described in the video, it’s possible for a path to continue in one direction forever, but in reality there are limits.
So if the cutoff is somewhere between 2 and 3, can we calculate it exactly? That would require non-integer dimensions, I don't know if that would make any sense for this problem, but I remember dealing with these when learning about fractals.
My money is on e for the cutoff!
Probably e ;-)
sorry for you... since the series in the end is ~1/n^(d/2) the cutoff seems to be exactly at d=2, where the expected number of returns diverges logarithmically. 1/n^k converges for k>1
All I know is it must be real tough to get home if you're a 4-dimensional drunk bird
@@vkvk7113 because 4-dimensional booze must hit as hard as LSD. Right? Yeah, man. Yeah, science.
One thing that I think would be useful in understanding this video is a short discussion of the distinction between 'certain' (no game can exist which fails the property) and 'almost certain' (the property occurs in games with probability 1). You frequently say a property is 'guaranteed' (which sounds like the former), when a random walk in a straight line (possible; probability 0) does not exhibit the property.
@@fairy8141 he was not stating things precisely. What he meant is that in 2D, there is 0% probability that you will never return to the origin, but in 3D the probability that you will never return to the origin is > 0. In other words, in 1D and 2D it is _almost certain_ that you will return to the origin, but in 3D there is a non zero probability that you will not return to the origin. He was confusing 100% probability with certainty - those are two different concepts.
@@agfd5659 aside from the mathimatical proof, why wouldnt just being able to go in a straight line forever make the probability >0%
@@agfd5659 oh wait i get it now, he worded it badly
@@agfd5659 I’m still trying to wrap my head around the 2d origin being recurrent. There are an infinite amount of paths that don’t cross the origin and either go off in a straight line for infinity, or loop inside a box for infinity. So if there is both an infinite amount of paths that either return or don’t, how does that make it almost certain? The 3d space also has an infinite amount of paths for either scenario. You could pair all 2d paths with a corresponding 3d path meaning both have the same amount of paths that return and don’t return. To clarify, you wouldn’t run out of 2d paths before 3d paths if you were coupling them because they are both infinite. So what’s the difference here I feel like I’m missing something. And how does a mathematical proof quantify “almost” in almost certain?
@@FerdEdits Not all infinities are created equal:) If you throw a dart randomly anywhere on the line of real numbers, there are an infinite number of whole numbers you could land on, yet the probability - quite intuitively imho - is zero, and you will instead land on an irrational number with probability one, because they are just so much more numerous. That doesn't mean that it's theoretically impossible to land on a whole number, it's just practically impossible, in the sense of probability (the whole situation being highly theoretical of course).
I understand the expected value computation and the reasoning that that gives a 2D walk a probability of 1 to return to the origin. The difficulty I'm having is with the assertion that that guarantees a return. After all, I can trivially construct a valid random walk which does not return to the origin: consider the walk which always chooses to move to the right. Even though this has a 0 probability to occur, there are infinitely many such walks which do not return. All possible random walks in general each have a 0 probability of occurring (considering the case of infinitely long random walks) and yet one of them must occur. I therefore think that declaring that a random walk is guaranteed to return to the origin is too strong an assertion even with the probability 1 because "guaranteed" seems to imply that all possible random walks return to the origin, which is easily disproven by my counterexample.
So there's a difference between probability 1 of something happening, and a guarantee of that thing happening?
Right, I could probably say "almost guaranteed" to be rigorous, in the sense of "almost surely".
I had the same thought and I'm surprised that this wasn't addressed, because I thought this would be a very common objection.
There is more than one way to return to the origin
Yes you are right. It was an error in the introduction to the video.
A neat trick for the 2D case: tilt the grid by 45°, now the x and y directions are uncoupled and the probability of returning home in n steps is just the square of the same probability in the 1D case, so it's [(2n,n)/4^n]^2. Unfortunately this trick doesn't work in 3D.
Is there a short explanation for how this problem is related to Stein's paradox?
Yes, that trick also works. If there is a short explanation on the connection, I would have said it in the video, though.
I made a simple program to do a 3D random walk and pressed go, it returned home in 800 or so steps. Considering there's a 2/3 chance of "greater than infinity" I find this amazing. I only tried it once anyway.
Hey, can you elaborate a little more please? I don't quite follow
@@AbelShields Consider the places where you can end up after 2 steps: (0, 0), (0, 2), (2, 0), (1, 1)... etc (mirror those points on the X and Y axis to the rest)
After being rotated 45d: (0, 0), (sqrt(2), sqrt(2)), (0, sqrt(2)), (sqrt(2), 0)... etc
Reescaling by sqrt(2): (0, 0), (1, 1), (0, 1), (1, 0)... etc
After the transformation the X and Y coordinates are not correlated anymore, you can move on the X coordinate without limiting your move on the Y coordinate.
Imagine the geometric figure that those points form: at first it was a rhombus, and when you tilt this rhombus by 45d it becomes a square, in this square the X and Y coordinates have no relationship with one another at all.
So the chance of returning to the origin in 2D is the chance of returning to the origin on the X coordinate and on the Y coordinate at the same time => P(2D) = P(1D)^2
Did it help? ^u^
@@caiqueportolira that was very insightful, thank you
Pretty sure there's a mistake in the sum at 14:51? The way it currently is, you're allowing i=j=n, which means you're taking the factorial of negative numbers, which I'm pretty sure is not what you want here. Instead, you should be summing j from 0 to n-i on the "inside" and then i from 0 to n on the "outside".
Right, I should probably just say i + j ranging from 0 to n, or even more ambiguously, sum over possible i's and j's.
@@mathemaniac you couldve also used a double sum for i=0...n, j=0...(n-i)
This makes me want to sleep
I don't get it
And anyway, that doesn't make any sense. Assuming for every step there is a possibility that you will take one that doesn't return to the origin (which is always the case), I would say that returning isn't even guaranteed in 1D. It's always possible in every dimension, but I don't see how it could possibly be a necessity above 0D
Possible, but with probability 0.
@@mathemaniac Okay, but it's like, in 0-2D it's apparently a certainty. Yeah, I heard a statistician say that given infinite time, there's a probability of 1 a random traveller will return to any given origin in 1D. I guess that mathematically makes sense, but in 2D, I feel like it's just way more possible to just go near an origin and keep missing it, since you can move around it and get to any side. In 3D, it seems like if you apply the idea you got for 2D and get to a spot where XY is the same, you'd be at a different Z, but if you apply the reasoning for 1D as well, you should surely eventually get back to the origin based on probability, but, uh...yeah
**sigh** you clearly have some idea about limits that I don't really (-_-) I know I watched the video but it's just been one of those days
Here have a cookie for listening to me say silly stuff :P
Perhaps I'm naïve, but I was not expecting combinatorics to show up in a Markov chain video. Always love the surprises that these videos bring, keep up the great work!
Computations of probability often involves combinatorics
@@taopaille-paille4992 I know that, but I've only ever seen the linear algebra approach to Markov chains.
@@benburdick9834 this use of combinatorics in the video is pretty. Proving the convergences of the series might be a bit "ugly". Probably using Stirling formula or things like this. Overall a nice problem. Probability theory is always a nice math topic to study
I appreciate you bringing me back to my math grad school days. This stuff is so much fun, it makes me want to get back to doing random nonsense and just seeing what I can stumble upon. We need more professional academics posting content like this. It's believe it's possible to entertain an audience even with complex, nuanced topics like this. Good teaching makes that possible.
I started studying Markov chains not so long ago and this video cleared the fog over ALOT of concepts. Great video!!!
Great to hear!
@@mathemaniac hello
As a professional mathematician, I should say I love your insightful contents
as a non mathematician I got lost at around 5:10 , why are we guaranteed to get back again and again? why can't we just go up and left to infinity and never come back?
@@jorenaldo because a state is either recurrent or transient, and the probability of doing that is 0.
@@nguyennguyenkhac2759 but why is it 0? Why are all sequences guaranteed to have a pair of opposite directions everytime?
I have a big question! I just started the video, so perhaps there is an answer in here somewhere, but I'm gonna go ahead and ask anyway.
Many problems seem like they change fundamentally when some parameter changes from 2 to 3. Here is the list I've compiled so far (it's small):
- this problem
- 2SAT is solvable in polynomial time, 3SAT is np-complete
- the critical probability in percolation theory is provable on a 2d grid, but possibly not analytically solvable in a 3d grid
- Newton's 3 body problem
- Newton's Method fractals are very plain when the degree of the polynomial is 2, but they get complex when the polynomial is degree 3
What is up with the 2 --> 3 divide? What other problems exhibit this? I don't know where to start looking.
Further bit of trivia to potentially add to the list: n! = n for 1 and 2, but n! >> n for n>2. :-)
Since you did a video on Green's functions: The Green's fct for the Laplacian on Rd is radially growing for d=1 and d=2, and decaying for d>=3.
Ah that's interesting.
I wish I had this video when I had my Markov's chain class :) Nice visualisation.
A thing I think that could be a nice addition, would be example of usage of Markov chains, say in engineering for example. Although I understand this channel is mostly math, real world example sometime helps grounding the interest.
Really enjoyed the link to the MLE at the end as well.
Good job :)
Great video, nicely done. Also congrats for this 100K milestone.
This cutoff between 2 and at least 3 dimensions is funny. There are « many » (define many) problems that work in 2D but not in higher dimensions.
What other problems work in 2D and not in higher dimensions though? I only know this one and the Stein's paradox one.
@@mathemaniac Hmmm I am not sure but it could be one of those things that were only missing a useful mathematical tool or framework. Rotations used to perplex me in 2D because it was needed to introduce a 3D vector and use the cross product. Seemed off why would rotations not work in 2D by themselves? Then i was introduced to geometric algebra and it stopped being confusing
@@Michallote Speaking of rotations in Geometric Algebra, 2D is a rather unique case since there is only 1 plane to rotate in, so every vector you want to rotate is within that plane and hence you can use 1-sided rotations. In 3D and above, you need to account for vectors that don't lie within the desired plane, and the way to handle that is with 2-sided rotations. (1D doesn't have _any_ rotations.) 2-sided rotations still work in 2D though, so they're still preferred in GA because they're more general. (Also deriving rotation-by-double-reflection for quaternions without any GA notation is rather satisfying if you ask me. Reflecting quaternions isn't nearly as widely known, but they work with the exact same formula as in GA.)
@@mathemaniac Chaos theory: dynamical systems can only exhibit chaotic behavior in 3D or above, so there is none in 1D or 2D. (see Peixoto's theorem and also Poincaré-Bendixson theorem)
@@mathemaniac in Chaos theory, continous dynamical systems can only exhibit Chaotic behavior in 3D or above, so there are no Strange Attractors in 1D or 2D (see Poincare-Bendixson theorem and also Peixoto's theorem)
at every step of this explanation, i found myself wondering how what you're saying relates to the original point
it might have been better to explain it in completely reverse order from how you did
A bird will return home because it is only flying limited height over a 2D Manifold because of Atmosphere. If you want a true non-return random walk in 3D you should have chosen a Spaceship with a random path like the Spaceships lost in Hyperspace in Babylon 5.
Huh?
It's just a thought experiment dude
@@lt4376 What I mean to say is a bird can not do a true random 3d walk because if it flies to high there will be no atmosphere, so it is limited in the height dimension and therefore will return.
Good point!
Prove that a bird cannot leave the atmosphere
Answer to 4:25
If the origin is recurrent, so is every other lattice point (simmetry).
Starting from a given point, there will be a positive probability to get to the origin in some number of moves.
Even if this does not happen, you have probability 1 to eventually come back to the starting point and try again, because the starting point is recurrent. You get to try again infinite times, granting probability 1 of getting to the origin.
Leaving up the proof to the viewers, wow.
I don't get it though, like even for the 1D case the probability is 1 (or infinitesimally close to 1) but there still is a non-zero probability, that they don't reach the starting point again. Since there is a non-zero chance they have more steps to the right (or to the left if that was their first step) at any given point, than in.the other direction. Highly unlikely, but possible.
So how is it guaranteed in the 2D case?
I could echo so much of the praise heaped on by other comments, but I don't want to bore anyone reading this comment with redundancy. I'll just say that this video and the one before it blew my mind, and I can't tell you how glad I am that I came across your channel. Congrats on the 100k subs, and let's go for a million!
Can we think about this continuously in terms of diffusion? If an initial point distribution of some substance at the origin diffuses isotropically in d dimensions, it will at time t have a Gaussian distribution with standard deviation proportional to the square root of t. The density at the origin decays then like the normalization factor in front of the exponential, which is inversely proportional to the standard deviation raised to the power of d. Taken together, the density at the origin evolves proportional to t^(-d/2), and it is proportional to the probability of a single molecule of the substance having made a closed loop random walk (because that's what diffusion is on the molecular level). The integral of that from epsilon>0 to infinity diverges for d
my eyes poped wide open from the beginning to the end. This is the first time I know this. Now I happily can not get to sleep thinking about this!
I've always wanted to learn about this. I guess it's something I can Markov my bucket list.
What's always confused me about random walks is that it seems to be significantly determined by where the walk starts. Suppose you start a random walk, A, at some arbitrary point. After some arbitrary number of moves it will (likely) be at some OTHER random point. Now start ANOTHER random walk B at that current location of A. Both A and B continue on their random walks. A will tend to "hover" around its starting point and B will tend to "hover" around IT's starting point. But for each step along the way of A and B it's next step is totally random. It has no memory of what path it had taken to get where it currently is, how many steps it had previously taken, or where it was when it took its first step. Indeed, if someone had first looked at A and B right at the point in time when B had started it's trek, with A being at the exact same point, that person would expect both A and B to "hover" around that same point, and be pretty surprised when A goes off and "hovers" around a different point. How would that observer account for A hovering around a different point? Each step is random, isn't it, totally independent of any prior steps, right?
Being recurrent does not mean the random walk will 'hover" around the starting point. In fact, the random walk in 2D will visit every single point on the lattice, with probability 1.
"Hovering" has to be interpreted in relation to the time you observe the random walk at. In 1-d, the standard deviation of the random walk grows with c*sqrt(t) (c is some constant) if t is the time, which basically means that if you observe a random walk at point A at time 0, it will "usually" end up somewhere between A-c*sqrt(t) and A+c*sqrt(t) at time t.
That means, you do "hover" around a point, but only if you consider finite time. In the far away future, the point A WILL become "basically irrelevant", which in a way leads to every point being reached with probability 1.
Let's say you have two random walks A and B, from stating points A and B respectively. Let's assume that at one point, both walks meet at point C. An observer is then introduced: She cannot tell which point is to hover around which starting point.
Actually, the two points will not hover around either A or B depending on their starting position at all. That each of them met at C, will have different probabilities to start with, depending on C's distance with A and B respectively. There, it account for the 'hovering' of the points. After coming to point C, they will not be biased, but before that the very probability of coming to C was different.
Hope it answers your question.
@@sohomsaumeep5682 Sorry, but I don't see how any of the responses explains the issue., No matter where the object is, by definition it is totally random, i.e. equal probabilities, that it will move in any particular direction. The move is not in any way dependent upon any prior moves. But in the long run, from that time forward, it will make approximately the same number of left, right, forward, and backward moves, with left-rights canceling out one another and forward-backwards cancelling out one another, with the overall effect of "hovering" around that point. And the same logic applies to every other position it ever happens to occupy.
@@sohomsaumeep5682 They do NOT have "different probabilities to start with". The very definition of a random walk is that, at each and every position the probability of going left or right or forward or backward is exactly the same, 25% probability for each. It does not matter at all how they arrived at a particular point. And those moves, over time all add up to basically no movement at all. All the left moves are cancelled out by the right moves, all the forward moves are canceled out by the backward moves. The object "hovers" around the point. The paradox is that the object hovers around every single position it ever happens to visit, which it clearly cannot do.
What is the fractional (fractal?) dimension > 2 and < 3, for which random walk is still recurrent?
"A drunk man will find his way home, but a drunk bird may get lost forever." 🤣🤣🤣
This is gonna be my new quote
This is very interesting result, but I'm thinking if the generalization to 2d vs 3d works here, maybe it is limited by the fact that you used square lattice and von neumann neighborhood. Consider moore neighborhood instead of von-neuman, i.e. let's allow diagonal moves. Then you basically play this game as 3 separate 1d random walks. I suppose if 2d random walk is supposed to get back to original point, 1d is even more, and it all boils down to question, if/how many times they return to the original point in the same time.
Another possibility is hexagonal 2d lattice, where all the moves have a probability of 1/6, just like in 3d, but the difference is that two diagonal moves with probability of (1/6)^2 can do the same as one straight move, and there are also infinitely many longer paths, so you don't have this simple to-and-fro arrow pairs that cancel each other out, you have to do some infinite series sums or something.
And the third thing is how does this work in continuous space with gaussian probabilities?
And what about fractal dimensioned spaces? Where is the breaking point? At which fractal dimension?
I'd like to see the analysis, I cannot do it on my own now.
The first part isn't too hard: As you said, allowing diagonal moves results in independent walks. And the probability of returning at each step is just the d-th power of the 1-dimensional case. Let 2n be the ste number (as in the video) then P(n)~1/sqrt(n) in one dimension. Thus is is ~1/n^(d/2) in d dimensions. You could put in fractional values for d (whatever this walk should look like)... The cutoff between convergence and divergence is exactly at d=2, where the divergence is only logarithmic.
Other grid types don't change anything about this cutoff. But it will change the specific probabilities.
A continious random walk with gaussian moves is probably the easiest of all. The resulting probability after n moves is the convolution of n single walks, which is just a gaussian again, with variance multiplied by n.
Now define what you mean by "returning home". Maybe a sphere around the origin. Again, the height of the central peak of the gaussian decreases as ~1/sqrt(n). For d dimensions just multiply d gaussians ... so the result is again P(n) ~ 1/n^(d/2). (It's only exact in an infinitesimal range at the origin, but valid as the limit for large n in any macroscopic range)
@@deinauge7894 thank you
The square grid eliminating odd returns seems to be the result of a square having an even number of sides. How would using a triangular grid affect things? Moving from discrete to continuous would also be fun to explore where at each step an angle is chosen at random.
It will not really affect the final result that the resulting random walk is still recurrent. But it would be more difficult to write down the exact formula.
In fact, we can think about the Wiener process (the continuous version of the random walk) as a limit of random walk, and as you might imagine, the Wiener process is recurrent in 2D, and transient in 3D.
But returning home in the Wiener walk is defined differently, as you never come back to exactly 0.
When you chose random angles - except when you chose from "good" sets like (0, 90°, 180°, 270°) or (0,120°,240°) you will be able to reach infinitely many points in any finite range. And thus you will never hit the origin exactly on point.
So this kind of looks to only works for grids without diagonal movement or graphs with max node connections 4?
The flaw with this, is that it supposes the property that the state-space is infinite.
In a finite state-space...you can imagine a 3x3 and a 3x3x3 grid, all states will reoccur with some non-zero probability (interestingly, some more than others), and in some of those cases, there is a strong probability that both will return after it has reached equilibrium as the boundary probabilities aren't the same (less degrees of freedom at the boundary, so more probability pointing towards a dynamic equilibrium state meaning a higher likely-hood to return to the origin)
In reference to the saying, both the bird and the man *will* find their way home. The bird will just take longer time because the state-space is exponentially larger. Consider even that Earth is a finite system and it also has a boundary: The bird can't wander off into space, space being the boundary, and so is compelled to stay on Earth, and after some finite time will return to it's home.
It's well known that 2d and 3d are not fundamentally different but in fact equivalent and isomorphic (holographic principle) so this shouldn't come as a surprise, that what's wrong is the underlying axioms that try to define the logic of the problem.
Cool video though, title is can just seem a bit misleading! Upon reading some comments...it seems like a few people pointed this out.
Cheers,
2D and 3D are fundamentally different, topologically, and yes, this works on an infinite 2D and 3D space.
In fact, for a finite state space, every state is recurrent! It's not just nonzero return probability, but 1!
@@mathemaniac At infinity, you could also prove that the drunk man never left home, because you could subdivide the grid over and over again instead of extending it outward. The video inadvertently proving that the man could also be just a 0D point that never left the origin.
Dimension being scale invariant here is a proof of its isomorphism, not that the dimensions are fundamentally different.
Cheers,
Take the point of video and left it as an exercise for reader. Genius
Sorry, was there something I missed? I accept that with higher dimensions, the probability of occupying a specific point on a given step diminishes, but the way the problem is stated seems to imply that in 3+ dimensions, it is possible to have a situation where the traveler cannot make it to the specified point, which is not true given the movement rules. Given a sufficient number of available steps, there is a possibility of reaching a point that many (or fewer) spaces away regardless of the number of dimensions involved.
I'm really not sure what you mean here - essentially in 3+ dimensions, yes, there is a possibility of never coming back to the origin. There are way too many paths that will never return to the origin that makes it a positive probability.
@@mathemaniac In 1 dimensions, and 2 dimensions, sure given infinite space probability is 1. Given 3, the probability is near 0 given infinite space.
For 4 dimensions it's 0 given infinite space. But still 1 given finite space. But even so, eventually as we approaches some n+ dimensions, even given finite space the probability will reach 0. Now that n is a finite and rather small number. Because the sphere of inner space will be reduced to the origin itself. When the hypersphere that contains the space in which the probability is 1 or greater, has a radius less than 1. I believe it's 7d. But yeah... Maths is not intuitive at all. Specially as soon as infinity is mixed in, and even worse, as soon as statisticians touch anything with their filthy hands, and put that P(x) symbol, anywhere, one should instantly leave, because when something is statistically unlikely in finite time, to the point of not happening at all ever, and as the terms grow larger the probability goes to 0, and as soon as that magic threshold known as infinity is reached, P(x)=1... as the likelihood of returning to the origin in 2n steps is about 0, Well it's for n=1 only 33% chance of returning. And it quickly diminishes, as there's 5/27 chance of returning for n=2 that's roughly 18.5%.
It's not that it's ever not possible to return, but that it's possible to not return.
@@nathangamble125 I've watched this a few times now and I still don't get how that's any different between 2d and 3d... In 2d the chance of a single step to the right is 1/4. The chance of two steps right is 1/16. The chance of n rights in a row is 1/(4^n) so the chance of traveling right an infinite number of cases is 1/∞ (infinetismal) which is non-zero... This is similarly the chance of *any* path of a given sequence length...
What supposedly changes in 3 dimensions? Sure it's a smaller degree of infinetismal at any given length but taken an infinite length it's still an infinite number of infinetismal likely options, with many of them never returning...
@@sniperfox47 Here's my attempt at a justification - why does the series 1 + 1/2 + 1/3 + ... diverge to infinity, while the series 1 + 1/2 + 1/4 + 1/8 + ... converges to 2? It's a question of how fast the sum grows relative to how "fast" it slows down. In the harmonic series case, the numbers aren't becoming smaller and smaller fast enough, and the sum eventually "consumes" all integers. However, in the geometric series case you will never get the sum to 2, as the numbers are becoming smaller "faster" than the sum is growing.
I would try to "visualize" the 2d vs 3d random walk through a similar concept. As the number of steps gets higher and higher, and more and more points are visited with a positive probability, the random walk is "covering" the space faster than the space is "expanding". But in a 3d infinite space, because there are more possibilities, the space "expands" faster than the random walk can "cover all of it". That would be the interpretation of the "3d" infinite sum in the video converging instead of diverging to infinity - the terms (which correspond to P(returned in n steps)) aren't growing fast enough.
How would this work in a saddle-shaped hyperbolic space, where there's more room than in 2d but less than in 3d? Is there a cutoff point in how strongly hyperbolic it is where it flips from recurrent to transient? How would something like that be measured?
I was commenting to myself on how well this explanation matched the one I was taught by Dr. Norris. So I laughed out loud when you announced you were a Cambridge mathmo.
Great job with the video.
I believe the reason it doesn't matter you start at the origin is the property of Markov chains about "forgetting" how you got somewhere. Since a path from the origin could get to any given point, and is guaranteed to return to the origin regardless of how you got there, you could also have started at said point.
Just because the relatively of start and endpoint. 2 point have just 1 degree of freedom, mean 1 fix 1 free.
I was math undergraduate but never stepped into the depth of serious math problem probably due to lack of clarity in teaching.I like your teaching style,made things so much clearer
Is it possible for transition probabilities for a markov chain be dependent on which point in the lattice we are ?
Yes.
watching this on the bus home from the bar right now. glad to know I’ll get there
This is brilliant!
If we assume 2d plane as surface of a 3d object such as sphere etc.
Why not if we also assume a 3d as also an object like inside the sphere or a cube?
Please explain this.
Thankyou
Thank you for the video ! It great to come back on a subject I had issue (convergent series).
So no jetpacks for drunk people, please. We need to sign this into law now, before someone gets lost!
Lol
Clearly explained, though I would need to watch multiple times to really grasp everything. I feel that illustrating the example for a one-dimension case would have helped me understand more. I suspect that the math involved would've been almost trivial(?) and therefore have given me a stronger foundation to understand the 2 and 3 dimension cases.
Actually the 1-dimensional case is very similar to the 2-dimensional case in terms of the level of math involved, and it is not that much easier really... but you can think about it now - the 2n-th step return probability for the 1 dimensional case is exactly the square root of that of the 2-dimensional case!
Thanks :)
What about if when changing direction you are allowed to turn at angles less than 90 degrees? Would your random walk in 2d still be recurrent, or would it be transient, or would it depend on how likely turning at any given angle is?
As long as you move on a grid, the result stays the same. If you move with strange angles such that the points you can reach (in priciple) are arbitrarily close to each other, than there is no guarantee to get back to the exact starting point.
But if you define your home to be a finite sphere around the origin, then you have Probability of 1 to get home again...
Always watching this video when can not sleep. Thank you a lot
Random motion has no mean displacement. Therefore, the probability density must be represented by a point, line, or sphere. Thus every destination will be reached regardless of dimension (eventually). It only matters about what “order” of infinite you are considering.
I'm doing a project right now on modeling heat distribution using random walks and this was PERFECT timing!
Lol this Bari science lab channel is a scam.
At what (fractal) dimension does the sum go from recurrent to transient. My gut feeling would guess at the natural log (2.718...) dimensions, but this is way beyond my ability to calculate.
1:16 hey how did you get the yellow dots to turn black when I don't look at them?
regarding recurrency => starting point is ignorable.
The probability of returning to the origin is 100%. Thus, the conditional probability of (getting home) given (first you go to place xy) is, by Bayes rule, probability of getting home and first going to xy divided by probability of going to xy. Since getting home has probability 1, getting home is independent from every other event.
So, Bayes rule simplifies to probability of (getting home) given (first you go to place xy) being probability of going to xy divided by probability of going to xy. It is thus 1.
By the markov property, you cannot distinguish (starting at 00 and going to xy) from (starting at xy). So, the choice of starting point is not important.
That was a bit different to what I had in mind, but it still works. The implicit assumption in your argument is that there is a positive probability of going from the origin to place xy, otherwise you can't even use conditional probability in the first place.
Maybe I'm misunderstanding, but how can it be truly guaranteed to return to the start in the 2d case? Surely there is an infinitely tiny but non zero possibility that every single random choice for the entire infinite walk has it going, say, to the left? I get that the math proves it must return, but intuitively it seems wrong.
Infinitely tiny => 0
Possible, with probability is 0.
The question is posed at the 4:20 mark. I think it requires a finite induction argument.
If there is a location neighboring the starting point that is between the starting point and the goal, then he will definitely visit that location. Then bootstrap, with this new location as a starting point. Your argument is similar to the probability that WEST never comes up on a four sided die, or 6 on a regular die. Probability = 0 means impossible. Tough question.
There is probably a better argument, along the lines of every point is recurrent, and every point will be revisited.
I wonder if there is a phase shift at a fractal dimension d (not an integer) where random walks never return if > d and always return if < d. Maybe there a fractal with altered initial seed to goes between dimensions 2 and 3 which could help get some grasp on this.
Hello mathemaniac, can you please produce another video showing Gaussian random walks in 1D, 2D and 3D in continuous steps by manipulating the pdf of the normal distribution. This one was mainly focused on discreteness.
error in first 60 seconds. NO, lol, it's not "mathematically guaranteed" that a two-dimensional random walk returns to the starting point. Rather, it's *probabilistically* going to happen, as the technical term, "almost surely." In other words, there are in fact infinitely many paths that never come back to the start -- but in terms of probability, they sum up to zero when compared to (weighted properly, in) the entire sample space of all paths.
I have addressed this in other comments already.
@@mathemaniac oh that's great! Did you fix the video?
@@frentz7 No, RUclips does not allow me to. You can't edit a RUclips video once it's out.
@@mathemaniac aren't there very limited editing tools that can edit a video even after releasing it?
Has an outward spiral not a non zero probability in both cases and hence has in both cases a non zero chance to never return? 🤔
I was thinking this, (also, two steps one direction, then moving in a 1x1 square). I think with any fixed path, the probability actually approaches zero for infinite steps
2D has a 0% chance. But 0% != never in whenever there are infinitely large/many things involved. There's even a technical math term: it's called "almost never". It's very unintuitive 🙃
Can anyone please explain how we got the equation for the no. of return paths? I am confused. Thank you
Brilliant and highly entertaining video. I must admit though, very counterintuitive to me. It seemed to me that the three D case would also always return to the origin. I'm sure I'll be revisiting this video again and again to try to determine where I've gone wrong in my logic. Well done. Two thumbs up.
You have more space to get lost in the 3D case
You accidentally linked the wrong video for the extra bit, both in the description and in the pinned comment (you self-linked the video in this channel)
Right thank you for pointing it out!
This is just to guarantee, that the return probability to this channel is 1
How did you know my intention????
I finally understand (sort of not really) a bit now.
At first I was thinking of it as-
At any point, with each direction being assigned a number on a die like 1 2 3 4 5 6, no matter where you are in 3d there is always a chance that you can roll with a non zero probability back to the orgin.
I realize now that when you do that you are multiplying probabilities again and again, and in 3d the amount the probability rises as you approach infinite (or area's large enough being "outer"), it diminishes leaving a non zero probability that you can get lost forever even with infinite steps.
I might be silly, because now i went from thinking " this is wierd shouldnt you always return to the orgin with infinite steps? " to " why doesnt 2d get lost like 3d? ".
I guess I am silly with a 100% probability.
The way I guess the solution is 2D has 4 directions to go in, while 3D has 6 directions to go in. So 3D has more paths getting lost.
The only problem is quantifying that amount.
This is exactly where I'm stuck. I get that we're trying to prove whether it *guaranteed* the bird returns or not, not if it's possible that it returns.. However, given an infinite number of steps, don't we have to prove that a return is impossible in order to prove that it isn't guaranteed? Because any non-zero chance of return should be guaranteed if attempted over infinite steps, right? Saying that reaching any specific coordinate is guaranteed should also mean that every single coordinate will be reached at some point, right? If you tell me that this isn't the case because the probability of any specific path approaches zero, then fair enough. But is that not also the case in 2d? Sure, it approaches zero faster in 3d, but they should both approach 0 nonetheless.
To simplify, I'm imagining a 1D number line where you start at 0 and are attempting to return to 0. Say there's a 50/50 chance of you going left or right in a single step. A return home seems incredibly likely. There is always a chance you could take right steps for a very long time, but given infinite steps you will always eventually go left. Any particular series of lefts and rights is just as likely as any other, so there is a non-zero chance that the path you get is one that returns you home. The odds of any specific path approaches zero, but to say that makes any single path impossible just doesn't make sense to me. Either every path is equally possible, or they are all impossible because the path is infinite and will never reach an end. This logic applies to 2d and 3d, and I'm struggling to understand where I'm going wrong.
Imagine a 2D number line where every step you take has a 1/6 probability of going left and a 5/6 probability of going right. (1/6 chosen somewhat arbitrarily, I just want something lower than 50%, but 1/6 looks similar to the 3D problem) Are you telling me that a return isn't guaranteed then? More of our steps will go to the right than the left, and I suppose that if you let that run infinitely then it is likely to go to the right forever. But there is still a non-zero chance of a very long string of left turns far into the path that returns you to the origin. And if there is a chance, there is a guarantee, due to the infinite nature of the question. Even if you take it to extremes, where left has a 1/1000 probability and right as a 999/1000 probability, a return is still possible.
Am I just wrong in my assumption that a non--zero chance is equal to a guarantee when you continue to infinity? Is that base assumption flawed? Either a probability of 1/infinity is 0 or it is just incomprehensibly small. If you tell me that we proved it is 0 in 3d, I don't understand why it's not zero in 2d or 3d. I generally understand the math that proved it to be the case, but my monkey brain can't comprehend why it's actually the case. It feels like one of those slight of hand equations where someone proves that 2=1 by sneakily hiding a division by zero.
(just to be clear, I don't think this video is any sort of slight of hand. I 100% believe I am making some leap in my logic, but I just feel like I can't find it no matter where I look. I'm sure there's an explanation out there that isn't just pure mathematical proofs.)
Great video, algebraic combinatorics deserves so much love
Very interesting. I have a question though: Are you allowed to do this rearranging of terms in the sum at 5:44? On the one hand, infinite sums are not allowed to be rearranged, on the other hand, this is a sum with no negative values. Does that mean that in this case this is allowed?
yes. it's only problematic when the sum of the positive terms (or negative terms) diverge, as in the alternating harmonic series.
I get the logic when you are restricted to steps on a lattice, but isn't there a missing step that demonstrates that this is equivalent to when you can make a unit step r in a theta ranging from (0, 2pi], which is what a more realistic random walk would be for 2D
The even more realistic process is when you have a variable step size and do this continuously. That's called the Weiner process, and is just the limit of a normal random walk when step size tends to 0.
@@mathemaniac Thanks for the response. Yeah, I restricted the step size because I wasn't sure about the generalization up to that point.
Edit: oh no, you have sent me down an interesting rabbit hole with the Weiner process when I need to be prepping for an interview haha
@@mathemaniac I read that for some step size distribution, 2D random walk can be transient?
@@sophiophile What are you interviewing for? Good luck!
For the two lines of reasoning you mention at 4:25, the first thing is that for any given point along a closed path, the Markov property means you could get the exact same path with the exact same probability if it had started at that point. Secondly, any given point should have at least one path that goes through it.
Thank you!
The theorem tells you that the probability that we loop back is 1, not that there are particular loops that are guaranteed to appear.
I would fix this argument as follows:
We are guaranteed to return once and so we are guaranteed to return infinitely many times (Markov property).
Each of those times there is a positive probability 'p' that we take any specific loop. We choose a loop that contains the point that we want it to go through.
Now for the walk to not go through the point we must have a (1-p) probability event happen infinitely many times. So we hit the point with probability 1.
@@farissaadat4437 The theorem states that no matter where the loop starts, it will reach 'home' - even if it does NOT start at 'home.' 'Home' can be any point in the space, not necessarily the starting point. Thus, the theorem DOES state that the random walk will eventually visit every point in the space, how ever many loops it takes.
@@johnathanmonsen6567
you can't pick 'the loop' and then apply the theorem. the theorem gives you your loop and then you have to hope that it passes through your point. I'm worried that you are doing things the wrong way around as is very common in Probability Theory.
also, what do you mean by you can choose any point to be 'home'? as soon as you specify a walk then your origin is fixed.
@@farissaadat4437 As in, the man in the analogy does not start at 'home.' His starting position can be any position relative to 'home,' and I'm pretty sure that does hold that it means 'home' can be any position relative to the starting position.
I don't quite get it. If you start at (0,0) and just walk in a down-right pattern forever - e.g.
(0, 0)
(1, 0)
(1,-1)
(2,-1)
(2,-2)
.
.
.
You will never return to the origin. Isn't there a chance - no matter how unlikely, that this sequence is randomly chosen?
This is a valid path, but with probability 0, because your path is very specific.
Man, I could even follow most of the reasoning! Great video!
Beautiful, good job
What if on a 2d plane the drunk man just walks in one direction forever
Each time he walks it’s just as likely for every direction, so it’s entirely possible, no matter how unlikely, that he just goes in a straight line forever, meaning he never returns home
That probability is zero
@@caiqueportolira it not any less likely than any other combination of moves though
How you make video which software you are using anyone can help me?
It’s finally out!! Great video!!!
Every time you animated that exact same 2d walk it got more and more annoying
But in the "real" world without the mesh you have infinite transitions to other states (because there are infinite directions in the 2d plane where you can go) each with an infinitely small probability. Is the sum that gives you E(V) still infinite in this case?
i dont get the no calculation, inner outer explanation. Isnt there also more space in the outer region in 2d? is there just that much more space in 3d that you never come back? but theres little enough infinite space in 2d?
Awesome sir! Thanks!
There's something I don't understand. If there is a possible route back to the origin, then I can only assume that there's a non zero chance to get back to the origin. Given an infinite amount of time, there should be no reason that why you wouldn't reach the origin. I see no reason why the third dimension changes this. I understand why the chance will approach zero given a finite amount of time, but with an infinite amount of time, it should eventually reach the origin. The chance should be low, however any chance above zero with enough time will eventually happen. Is there something I'm missing?
The path is possible, just with probability 0.
@@mathemaniac so like how the probability of hitting any single point on a dart board is zero, despite the fact that you will definitely hit one?
very clear and ordered, exelent work.
Is it impossible to go only one step left one right and do that infinitely in 2D space, that would not bring us to the starting point instead it would take us infinitely far away?
Is it impossible to move only in 2 dimensions in 3D space, that would bring us to the origin if we did not go only one step left another right and so on and on?
For the big equation at 15:00 :
Shouldn't it be two nested sums, with i going from 0 to n, and j going from i to n?
As it is stated (at least the way i read it), both can range from 0 to n, which leads to the z-direction having as low as -n steps, which makes no sense
Did anyone else notice the optical illusion at 1:15 when the yellow points appear? some seem to have a smaller black dot in the center but it's not really there.
Is it known which value converges the second series to?
You can deduce it from the return probability, which has been calculated here: mathworld.wolfram.com/PolyasRandomWalkConstants.html (also linked in the description)
I think in the 3D case j should only go up to n-i right? Otherwise, we would have a negative amount of steps up and down.
What number dimension specifically between 2 and 3 is the transition?
Well, what do you mean by a random walk in fractional dimensions? I don't have the answer to that.
Most of my math knowledge come from youtube videos so please excuse me if this is a stupid question; is this all assuming an infinite grid/area/whatever I should call the array of nodes? Intuitively it seems like with infinite area the 2d random walker is just significantly more likely to return to the origin. I guess I don't understand how its possible that the extra dimension makes it possible to never return, because it seems like thats entirely dependent on the confines within which you're working. Hopefully someone can understand what I'm asking and help because I have tried to google this and ended up more confused than before.
Can't get enough of this
What about random walks on other lattice types, like triangular or hexagonal?
I don't quite understand: is it only because of the increase in possible states that it becomes less likely for one to come back to its original position? If yes, then even in 2D, but with a different grid, it would be equivalent to a 3D grid with 6 directions to move. For e.g we can define a 2D grid with 6 directions (instead of 4) which is equal to the directions that are allowed in 3D, so in both cases the probabilities for directions is 1/6. Hence, it would be as likely as in the 3D case that one would not be able to come back to its original position?
Some questions to expand the topic:
Is the coordinate system being based on a square grid arbitrary? How would the results vary if the path followed along a 2D grid of tessellating triangles or hexagons (where each point has 6 or 3 path options instead of 4) instead?
Also, I wonder if the difference in results between 2D space and 3D space is due to the fact that the path remains a 1-dimensional in both cases. If we have a 2D path in 3D space (e.g. a 1-unit wide ribbon), would that change the result for a path in 3D space?
I would like to hear any answers!
square is not arbitrary because in 2d you have 4 directions to go in.
10,000 points for a finding a valid mathematical reason to print 'poo' on the screen a bunch of times
Can't you only interchange the order of summation for an infinite sum like you do at 6:16 if the sum is already convergent? Unless I'm mistaken, that would make this argument tautological.
This also implies that you will always find your keys if you lose them, but not if you put them away.
What in the enchanted table was that 1971 paper you scrolled through near the end of the vid? I've never seen any paper as long as that, that too filled with maths. How is any viewer capable of reading through all that, that in itself looked like a 6 month long achievement.
The whole point of the video: Each point in R2 is recurrent. Author won't tell us why but asks us to comment in an attempt to guess why. WOW.
Ok dummy have you figured it out yet? Lol
@@x0cx102 Ain't nobody got time for that! Besides, I'm a dummy.
At 10:00 for the expectation shouldn't the p_00^(k) be multiplied with k?
It is only a Yes/No question, so the variable can only take the value 0 and 1.
You can intuit some of what you said that leads to Brown's paper, and it would be interesting to know more about it, though I don't think I would understand the notations used.
Wait, how do you mathematically approach if the 2d surface has something like a rail system that you could let you be at and under the ground level?
The size (cardinality) of the sum of two planes is equal to one plane (a typical proof in real analysis), so there's no difference in this case