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

[@mathemaniac]

Second channel video: kzbin.info/www/bejne/gZ-6fGqujtqsZpI 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.

[@mathemaniac]

Right, thanks for pointing it out!

[@BeaDSM]

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.

[@Anon282828]

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

[@Mad_mathematician224]

@@mathemaniac can you tell best book to learn complex analysis??

[@alanmai3773]

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

[@valtersanches3124]

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.

[@DiamondSane]

I had same for long and short scales of numbers. This was a pleasure to get the question closed.

[@Prisal1]

omg

[@wilesmith]

should have stayed

[@CloudPhase]

@@wilesmith Please reread this comment

[@TaigiTWeseDiplomat--Formosan]

0。0

[@mr_zmt7152]

Good to know my dad will fome back one day 😅

[@at7388]

It's just a matter of time.

[@aloysiuskurnia7643]

but your dad remembers where has he been, though :

[@Periwinkleaccount]

Unfortunately, he is not random.

[@pluto8404]

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.

[@hantiop]

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.

[@kylebowles9820]

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!

[@mathemaniac]

Thank you!

[@pianissimo7121]

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

[@vkvk7113]

Damn must be even harder to return home for drunk 4-dimensional birds

[@futnick4917]

who knows how calabi yau spaces would find their way home 😅

[@Flourish38]

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!” :/

[@hannahnelson4569]

I agree. This video was... strange.

[@sirhenryvonvandings]

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)

[@mmeister8582]

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

[@ptorq]

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.

[@svennyhenny]

Not everyone is meant to be an online educator/presenter. I don't believe this person is one of them

[@David-mu1eh]

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!

[@mathemaniac]

Yes, many people have pointed it out - I probably should have said "almost guaranteed", as in "almost surely".

[@benjamingoldstein14]

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.

[@chrisc6468]

@@benjamingoldstein14 it is possible; actually, it's just as likely as any other infinite random walk.

[@benjamingoldstein14]

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

[@dele1763]

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

[@andrewhubbard4043]

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.

[@agfd5659]

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

[@midas01tw]

@@agfd5659 aside from the mathimatical proof, why wouldnt just being able to go in a straight line forever make the probability >0%

[@midas01tw]

@@agfd5659 oh wait i get it now, he worded it badly

[@FerdEdits]

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

[@7uub1]

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

[@99Megaluca99]

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.

[@vrojak7636]

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!

[@crossiqu]

Probably e ;-)

[@deinauge7894]

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

[@vkvk7113]

All I know is it must be real tough to get home if you're a 4-dimensional drunk bird

[@samueldeandrade8535]

​@@vkvk7113 because 4-dimensional booze must hit as hard as LSD. Right? Yeah, man. Yeah, science.

[@benburdick9834]

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!

[@taopaille-paille4992]

Computations of probability often involves combinatorics

[@benburdick9834]

@@taopaille-paille4992 I know that, but I've only ever seen the linear algebra approach to Markov chains.

[@taopaille-paille4992]

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

[@jmcsquared18]

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.

[@Gus-AI-World]

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!

[@aaronhalloway7237]

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.

[@x0cx102]

Ok dummy have you figured it out yet? Lol

[@aaronhalloway7237]

@@x0cx102 Ain't nobody got time for that! Besides, I'm a dummy.

[@calebu2]

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.

[@johnchessant3012]

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?

[@mathemaniac]

Yes, that trick also works. If there is a short explanation on the connection, I would have said it in the video, though.

[@lyrimetacurl0]

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.

[@AbelShields]

Hey, can you elaborate a little more please? I don't quite follow

[@caiqueportolira]

​@@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^

[@AbelShields]

@@caiqueportolira that was very insightful, thank you

[@QuantumHistorian]

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

[@mathemaniac]

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.

[@MrNionys]

@@mathemaniac you couldve also used a double sum for i=0...n, j=0...(n-i)

[@AndreasChrisWilhelmer]

14:14 "The ONLY difference is that the transition probabilities are all 1/6 and there is one more pair of directions to consider." Hmmm.. I don't believe that is true. Imagine drawing a diagonal path from the top left to the bottom right theough each of the squares of your square grid. In doing so you increase the number of paths of each node to 6, but remain in the 2D case. So having an additional pair of directions and a probability of 1/6 does not appear to be the relevant factor here. There is still a difference to the 3D case of course, as this variant is - for the lack of a better term - "more strongly interconnected". Aka we can now reach neighbors on paths of even as well as odd lengths. I honestly haven't played through that construct further than that as of yet, but that part of the explanation presented here seems unsatisfactory to me. Afterall that version of a 2D grid would yield a scenario where a random walk would also not return if probability 1/6 was the relevant property here. It would surprise me if that was the case.

[@gutzimmumdo4910]

very clear and ordered, exelent work.

[@PunmasterSTP]

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!

[@FiniteSimpleFox]

16:00 There's a nice combinatorial argument to replace these calculations; choose n of 2n steps and colour them red. Now choose another n and colour them green for a total of 2n choose n possibilities. If a step is red and blue it becomes up, if it's red and not blue it becomes right, if it's blue but not red then it's left, if it's neither than it becomes down. You can verify that there is therefore a bijection between the number of colourings and the number of paths of length 2n, so it's going to be (2n choose n)^2

[@SendyTheEndless]

I've always wanted to learn about this. I guess it's something I can Markov my bucket list.

[@vkvk7113]

"A drunk man will find his way home, but a drunk bird may get lost forever." 🤣🤣🤣 This is gonna be my new quote

[@goodplacetostop2973]

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.

[@mathemaniac]

What other problems work in 2D and not in higher dimensions though? I only know this one and the Stein's paradox one.

[@Michallote]

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

[@angeldude101]

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

[@txv1085]

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

[@txominvs8962]

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

[@tanchienhao]

It’s finally out!! Great video!!!

[@ddystopia8091]

Take the point of video and left it as an exercise for reader. Genius

[@Kushiren]

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.

[@dumonu]

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.

[@lukevideckis2260]

So there's a difference between probability 1 of something happening, and a guarantee of that thing happening?

[@mathemaniac]

Right, I could probably say "almost guaranteed" to be rigorous, in the sense of "almost surely".

[@tahmidt]

I had the same thought and I'm surprised that this wasn't addressed, because I thought this would be a very common objection.

[@pyropulseIXXI]

There is more than one way to return to the origin

[@frentz7]

Yes you are right. It was an error in the introduction to the video.

[@jamesedward9306]

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.

[@taopaille-paille4992]

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

[@DevinDTV]

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

[@uwezimmermann5427]

Manim is great isn't it? But it is also a big time-killer... But around 15:00 when you do the sum for the 3D-case don't you sum too many j's? If your sum of i reaches n then there are no choices left for any steps in the other two directions, yet your j-sum also appears to go all the way so that you at the top of the sum have already spent 2n of your n steps, leaving -n steps for the third direction. Fewer terms in the summation would of course mean that your total probability becomes even smaller...

[@ribal3269]

I started studying Markov chains not so long ago and this video cleared the fog over ALOT of concepts. Great video!!!

[@mathemaniac]

Great to hear!

[@Mad_mathematician224]

@@mathemaniac hello

[@Aquillyne]

Hello from a fellow Cantabrigian! Congrats on 100K.

[@strikeemblem2886]

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.

[@mathemaniac]

Ah that's interesting.

[@PierreLeroy76620]

Thank you for the video ! It great to come back on a subject I had issue (convergent series).

[@BigDBrian]

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.

[@hohuynhquocchuong4925]

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

[@gilthekid4421]

watching this on the bus home from the bar right now. glad to know I’ll get there

[@pokepress]

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.

[@mathemaniac]

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.

[@livedandletdie]

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

[@nathangamble125]

It's not that it's ever not possible to return, but that it's possible to not return.

[@sniperfox47]

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

[@Cowtymsmiesznego]

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

[@32zim32]

Always watching this video when can not sleep. Thank you a lot

[@patrickshepherd1341]

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.

[@irrelevant_noob]

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

[@NightmareCourtPictures]

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,

[@mathemaniac]

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!

[@NightmareCourtPictures]

@@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,

[@DeclanMBrennan]

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.

[@mathemaniac]

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.

[@deinauge7894]

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.

[@lunalumafly]

"here is a very clever general trick" ad immediately starts

[@FireyDeath4]

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

[@mathemaniac]

Possible, but with probability 0.

[@FireyDeath4]

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

[@matthewrosborough2705]

I... am not convinced. like at all. ive watched this through twice but idk. im not doubting your math, im not doubting the process. heck im not even gona say you are wrong. just that this does not convince me. i think its the " no matter where the drunk man started, it is mathematically guaranteed that he will return home " bit. given an infinite walk in presumably an infinite grid to walk on. it is easy to think of many random walk outputs that would never actually get back to the home. and that for each given number of steps there is no actual guarantee that the drunk man would actually make it home and that the same goes for the 3d fly. on the other hand if given an infinite grid and an infinite number of moves, it should absolutely be possible for the bird to return to center. but you say that there is a non zero chance that it gets lost forever (which again should be possible in both 2d and 3d) . i feel like imagined walks that dont fit the general statement never properly gets addressed out side of the math. idk im just a dumb uni drop out i dont know shit, no idea why this popped up on my feed but the vid itself is decent. keep up the good work and congratz on 100k

[@QuantenMagier]

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.

[@lt4376]

Huh?

[@psionicoculus6093]

It's just a thought experiment dude

[@QuantenMagier]

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

[@PKPTY]

Good point!

[@ninjashuriken]

Prove that a bird cannot leave the atmosphere

[@J7Handle]

There are an infinite number of infinite paths that never return to the origin, though. They may be an infinitesimal part of the probability space, but infinitesimal is not the same as zero. Also, 1/n is very slow at diverging, so that drunk man is going to take until the heat death of the universe to guarantee at least one return.

[@teckyify]

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

[@DavyCDiamondback]

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

[@kelvinliu-huang5955]

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 🙃

[@jordanjohn01]

i’ve never seen a more confusing video

[@mohammaddashtpeyma8369]

As a professional mathematician, I should say I love your insightful contents

[@jorenaldo]

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?

[@Xdd2912]

@@jorenaldo because a state is either recurrent or transient, and the probability of doing that is 0.

[@jorenaldo]

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

[@isqwerblya]

there are infinity ways to NOT return in 2d - so return is NOT guaranteed

[@BariScienceLab]

I'm doing a project right now on modeling heat distribution using random walks and this was PERFECT timing!

[@su2spinors]

Lol this Bari science lab channel is a scam.

[@siquod]

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

[@popularmisconception1]

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.

[@deinauge7894]

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)

[@popularmisconception1]

@@deinauge7894 thank you

[@Spectacurl]

First video, instant subscribe

[@SlowerCuber]

This is brilliant!

[@rango_gaming]

I have a 100% percent chance of driving straight to my house when I’m looking for my home while drunk

[@RogerGarrett]

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?

[@mathemaniac]

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.

[@einmensch6694]

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

[@sohomsaumeep5682]

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.

[@RogerGarrett]

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

[@RogerGarrett]

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

[@yash1152]

6:09 i don't know why the sound started suddenly feeling sooo similar to "Junferno" - anyone else felt same?

[@walterkipferl6729]

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.

[@mathemaniac]

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.

[@LovroPlaninšek]

I don't understand this video at all. The way the problem is set, my first thought was "Well, in 2 dimension, 3 dimensions, or even 18 dimensions, an infinite random walk should go through each and every one of the infinite points an infinite number of times. That's what infinity means, after all, _there's no last step."_ This video and the 2nd channel one are trying to answer the very specific question of "does adding up the probabilities of each step landing on the home converge or diverge?" I think that's indeed a good approach to turn the problem into something actually defined and written down. I watched the 2nd channel video, but really struggled to follow along. In the end, it still didn't make sense, how can an infinite walk go over a specific point a finite number of times?? I went back to that original infinite series of steps and if I'm getting it right, in both 2D and 3D, odd steps have no chance of landing on 00, but the even steps get increasingly less likely to land on 00 the further out you get, just never reaching 0. So still, how is it any different in 3D? Also, the 'no calculation' explanation doesn't make sense, in this outer region there is just a smaller chance of getting back, but that doesn't matter with infinite steps as long as there is a non-zero chance. But if that's the case, a 2D walk would be no different. Ok my main 'practical' argument I want disproven: You can think of a 3D random walk as a 2D walk happening at the same time as a 1D walk perpendicular to the 2D one (so in the third dimension). As a step gets taken in one of the two walks, one doesn't get taken in the other and vice versa. Whenever both the 2D and the 1D walks are at the home simultaneously, we take that as our imaginary 3D walk being on the home. So this video proves a 2D walk has recurrence, a 1D walk being no different. So we have an infinite number of times either walk was on the home, so we can assume an infinite number of times they were on the home simultaneously as well. As a last minute idea, maybe 2D and 1D don't have recurrence either I might be missing something, but after watching the video again I'm still stumped.

[@tristanc6967]

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.

[@mathemaniac]

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!

[@tristanc6967]

Thanks :)

[@oDrashiao]

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

[@billob1305]

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

[@SirNobleIZH]

Awesome video, never thought that Grian would be traching me math

[@shawnmikeska4867]

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.

[@torydavis10]

10,000 points for a finding a valid mathematical reason to print 'poo' on the screen a bunch of times

[@carterrazink5518]

I studied this for my bachelor’s thesis this last fall - great to watch a much more elegant illustration 👍

[@Known_as_The_Ghost]

I guess I'm dumb, because I don't understand. Aren't both scenarios a non-zero percent chance they never return home? What if 2d guy literally just kept walking in a straight line forever?

[@kelvinliu-huang5955]

2D has a 0% chance. But 0% != never, whenever there are infinitely large/many things involved. There's even a technical math term: it's called "almost never". It's very unintuitive 🙃

[@Known_as_The_Ghost]

@@kelvinliu-huang5955 I'm not sure what you're implying.

[@kelvinliu-huang5955]

Something can be possible and yet have a 0% chance. The mathematical term for this is "almost never". Here's an example: randomly cut off a piece of string from a spool. Now measure how long it is. What's the probability that it's exactly 5.3000... inches long? What's the probability it's exactly 5.3100... inches long? How about 5.299444...? The answer to all of those questions is 0% because you'll always be off by some decimal places For more examples check out the Wikipedia article "Almost surely" under "Illustrative examples"

[@johnathanmonsen6567]

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.

[@ippishio]

Thank you!

[@farissaadat4437]

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.

[@johnathanmonsen6567]

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

[@farissaadat4437]

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

[@johnathanmonsen6567]

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

[@greyskullmcbeef4901]

Where is the commenter who explains it in 2 sentences? This video just goes on and on into infinity

[@LineOfThy]

impossible

[@LucaBl]

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?

[@brajki6364]

I don't think it is. At least in a finite amount of time. I am not sure about an infinite amount of time though.

[@raamav.4837]

Thanks

[@FE2E00]

Feels like clickbait lol. You just asserted that ALL 2d random walks are "recurrrent" and I keep waiting for the proof to be presented. Does this sort of motivated reasoning pass for expertise at whatever school you mentioned?

[@pizzamidhead2183]

are you dumb?

[@justinpyle3415]

someone correct my logic here. if each change of state has foegotten its previous states, and this creates an infinite number of state changes, and if the number of times the state changes is always infinite, and if there is any probability at all of returning to origin in 3 dimensions, shouldnt the expected number of returns also be infinite for 3 dimensions?

[@bennettpalmer1741]

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.

[@mathemaniac]

Infinitely tiny => 0 Possible, with probability is 0.

[@troyseffrood2972]

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.

[@troyseffrood2972]

There is probably a better argument, along the lines of every point is recurrent, and every point will be revisited.

[@skrd37]

"i am lost, how to get back to my house?" get drunk and do random walk

[@frentz7]

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.

[@mathemaniac]

I have addressed this in other comments already.

[@frentz7]

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

[@mathemaniac]

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

[@vibaj16]

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

[@usptact]

Man, I could even follow most of the reasoning! Great video!

[@nilsp9426]

So no jetpacks for drunk people, please. We need to sign this into law now, before someone gets lost!

[@WinterNox]

Lol

[@zhuolovesmath7483]

If there is a point with nonzero probability of not returning to the origin, then one can simply walk to that point, and derive a contradiction

[@sophiophile]

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

[@mathemaniac]

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.

[@sophiophile]

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

[@mbrusyda9437]

@@mathemaniac I read that for some step size distribution, 2D random walk can be transient?

[@benjamingoldstein14]

@@sophiophile What are you interviewing for? Good luck!

[@dewaard3301]

This also implies that you will always find your keys if you lose them, but not if you put them away.

[@sapphire--9375]

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.

[@xXJ4FARGAMERXx]

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.

[@Turruc]

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

[@daggerball]

Recurrence only means that probability approaches 1 when number of steps approaches infinity. It doesn't guarantee anything strictly speaking. e.g. there is always a chance that we only will go in one direction. Infinitely small, yet non-zero chance.

[@uriaviad9617]

This is incorrect. The chance is 0. It's just that "possible" outcomes can have probability of 0. Infinitely small,yet non-zero isn't even defined in standard mathematics (it can be defined but usually mathematical theories don't use these definitions)

[@daggerball]

if you have a sequence where a_n equals (number of paths of length n not visiting origin) over (total number of paths of length n), then with n approaching infinity a_n will approach zero, yet it will not equal zero for any finite n. That precisely means that probability is non-zero. The "infinitely small" part doesn't even matter here. For "Infinite case" where you effectively operate on limits of probabilities rather than probabilities thmselves, the probability of visiting the origin is precisely 1. But even this doesn't guarantee that you will ever return to the origin, because the lower bound of the number of steps it will take in such case is precisely infinite. Or rather there is no lower bound at all.

[@daggerball]

Also, there is a neat trick one can use. Infinite random walk can be represented as uniformely distributed numbers in the range [0...1) written in the base four (or six in 3D). Each number represent one possible path, where n-th digit (dₙ) after the comma сorresponds with the direction of the n-th step. E.g. 0.01230123... means that we are going in square. In that case condition of visiting the origin can be formulated as such: for given number ∃ N > 0 : Sum[n=1..N]( e^(2πjdₙ/b) ) = 0 (where b - base). In order to proof that visiting the origin is not guaranteed we just need to pick a number where that condition is not satisfied, the most trivial of which is zero: ∀n: dₙ = 0 => Sum[n=1..N]( e^0 ) = N > 0 The neat part of this mapping is that it helps to understand that in models with infinite states probabilities usually loose some of their meaning. p = 0 does not always mean 'impossible' and p = 1 does not always mean 'guaranteed'. we learn that when we learn about probability density and its purpose, but suddenly forget when it comes to some fancy Markov chains.

[@uriaviad9617]

@@daggerball I know all of this and it doesn't contradict what I was saying. The probability is 0 and not "infinitely small yet none 0". Also the important thing is that there are uncountably many states. With countably many states any possible state will have positive probability.

[@daggerball]

That's right. But those are slightly different kind of probabilities, one cannot rely on judging whether something is guaranteed or not. That's also why I used word 'chance'. It's the same as saying that 1/x = 0, because we are talking about infinite x. There is a reason why we explicitly use limits for that. The ability to measure infinity is a powerful tool, but should be used with caution, since it can confuse infimum with minimum. It would be grate if something like 'effective probability' was used instead. Most importantly, it just bothers me when intuition is sacrificed in favor of catchy phrase. Intuition tells us that returning is not guaranteed, and it's true in this case.

[@t0lgi019]

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)

[@mathemaniac]

Right thank you for pointing it out!

[@tekkenatoryt9686]

This is just to guarantee, that the return probability to this channel is 1

[@mathemaniac]

How did you know my intention????

[@reversefulfillment9189]

Always markov your trail so you can find your way home, when you're going to get drunk.

[@PKPTY]

Beautiful, good job

[@alexczarnomski1116]

Great video, algebraic combinatorics deserves so much love

[@SourceCod33]

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

[@caiqueportolira]

That probability is zero

[@SourceCod33]

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

[@remi_starfall]

I'm a bit confused on the conceptual side of things here. Suppose you have a single infinite series of moves in a random walk on a 2d plane. As others have pointed out, the probability of walking to the left an infinite number of times approaches 0, but is still possible. Now suppose you have an infinite series containing every infinite series of moves in a random walk on a 2d plane. In this case, the probability of an infinite number of returns is 1, as logically at least one infinite series of moves would comprise moving left and right an infinite number of times. Applying this to a 3d plane, with a single infinite series, there is a probability of walking left an infinite number of times that approaches 0, but is still possible. Once again, with an infinite series containing every infinite series of moves, the probability of an infinite number of returns is 1, as logically at least one infinite series of moves would comprise moving left and right an infinite number of times. With all that being said, what is the fundamental difference between the 2d case and the 3d case? In the introduction you say that the 2d case is "mathematically guaranteed" to return while the 3d case has a "non-zero chance" that there will be no returns. As I said above, if you only take one infinite series of moves, both instances have a probability of never returning, and if you take an infinite series containing all infinite series of moves, both instances are guaranteed to return an infinite number of times. Why is the 2d case guaranteed while the 3d case is not? What do you even mean by that statement? Any clarification would be appreciated because the concept of a fundamental division between 1d/2d walks and 3d+ walks is intriguing to me, and I want to understand the video.

[@mathemaniac]

The path going off in 1 direction is a valid path, but the probability is 0. In the 3D case, there are way more places that you can go so you wander off rather than going back in the origin.

[@chiefcloudyeye0489]

@@mathemaniac Given an infinite number of tries, wouldn't any valid path have a nonzero probability?

[@Hailfire08]

Proof: 1) You can reach any other state with non-zero probability 2) We can expand the probability of returning to the origin in terms of sums over previous states 3) As the probability of returning is 1, every element in the sums can only be the probability of reaching that state, since any less and it wouldn't sum to one. Thus the probability of returning from a possible state is 1 C) As all states have non-zero probability, they are all possible, thus they all have probability 1 to return to the origin

[@__8120]

Every time you animated that exact same 2d walk it got more and more annoying

[@AndrewBrownK]

Maybe I’ll understand this video when I get home and clear my hangover

[@blacklistnr1]

@2:50 I find it more intuitive when explanations say what does happen, rather than what doesn't. E.g. instead of saying about forgetting previous nodes, say you only consider neighbouring nodes. Then, if you want, clarify that history doesn't matter.

[@adelmakram5641]

So, how to calculate the probability of return in 3D? The expected number of times the random walker will go to the origin is finite. But the probability of this event = the expected number of times/n, where n is infinity many times of trials, so the prob must be 0. But we know the probability is not zero so what is the formula for calculating the probability of return?

[@Lucien86]

From the perspective of working on self-complete systems. This is another example of something we see as the number of dimensions in a system increases - that as degrees of freedom increase traditional rules of geometry begin to break down. Angles are the perfect example of this where in 2 dimensions angles form a neat self complete system but in three they do not. In four dimensions we can only imagine this gets a lot worse. - Things like random walks are exactly the same for the same reason.

[@TheDoh007]

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

[@myrandomfood7659]

Can anyone please explain how we got the equation for the no. of return paths? I am confused. Thank you

[@TaohRihze]

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.