Random walks in 2D and 3D are fundamentally different (Markov chains approach) 

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.)

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.

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

Thank you!

I agree, if this was a class i would be annoyed because everyone should be paying attention. But it's RU-vid and it's much more relaxing to be reminded why we are doing what we are doing.

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

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.

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.

@@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).

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)

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

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

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

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.

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)

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.

@@Xdd2912 but why is it 0? Why are all sequences guaranteed to have a pair of opposite directions everytime?

You have more space to get lost in the 3D case

Great to hear!

@@mathemaniac hello

Ah that's interesting.

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,

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

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.

Further bit of trivia to potentially add to the list: n! = n for 1 and 2, but n! >> n for n>2. :-)

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.

Just because the relatively of start and endpoint. 2 point have just 1 degree of freedom, mean 1 fix 1 free.

This is a valid path, but with probability 0, because your path is very specific.

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

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 🙃

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.

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 :)

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.

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.

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????

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?

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.

impossible

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.)

Lol

I have addressed this in other comments already.

@@mathemaniac oh that's great! Did you fix the video?

@@frentz7 No, RU-vid does not allow me to. You can't edit a RU-vid video once it's out.

@@mathemaniac aren't there very limited editing tools that can edit a video even after releasing it?

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!

Lol this Bari science lab channel is a scam.

Yes.

That probability is zero

@@caiqueportolira it not any less likely than any other combination of moves though

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

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...

I think the cut off is likely 2D itself or very close.