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