The Long Run Behavior of Random Walks - Omer Tamuz - 1/16/2019

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments

I thought this was very good, especially the balance between exact mathematical statements and easier-for-a-general-audience statements.

👍︎︎ 5 👤︎︎ u/theadamabrams 📅︎︎ Jan 31 2019 🗫︎ replies
Captions
presented by Caltech good evening thank you for coming through the rain I am John Ron Rosenthal the chair of the division of humanities and Social Sciences it's a pleasure and an honor to introduce the speaker for tonight's Ernest C watson lecture series professor omerta Meuse professor Tammuz received a bachelor's degree in computer science and physics from tel aviv university and then a PhD in mathematics from the whitesman institute in 2013 after his synced up after a stint as a postdoc at MIT in Microsoft Research he joined Caltech in 2015 and is now assistant professor of economics and mathematics as his very brief history suggests momemtum OU's embodies the interdisciplinary interaction that makes Caltech scholars unique we are not just one thing the best of us build paths between fields and use these paths to solve important problems Professor Tim OU's enjoys traveling through the disciplines but unlike the Proms he's going to talk about tonight his progress is entirely non-random it is instead something quite extraordinary motion of confidence and relaxed intensity relax but see because it seems that oh mayor always has time for other student in his office another hallway conversation with a colleague or graduate student intense because in fact those students are in his office solve proving theorems and discussing heart problems intends also because one day as we're walking to lunch he said to me did you know that the optimal random audit rule follows the golden ratio what could I say but raise my eyebrow in suspicion by the time lunch was over I was convinced and I now visit his office every one point six weeks with some randomness added I also recall that when he was giving his job market talk about optimal diffusion of information along a network he spent most of the time explaining to us the ideas that the network cannot be locally too sparse or too dense and why that was the case too sparse information information does not flow enough to dense and individuals will start to conform too much then as an aside he kind of squinted and Medard we had to build some new math to solve this one that leaves confident when American mousse came he said he wanted to do math and social science and he was not sure we would let him do so I told him yes you can and as you will see tonight yes he does tonight only I will speak over the long run behavior random walks please join me in welcoming my colleague and friend omerta moon I thank you very much thank you John LaRon I want to thank the the officers who teach a communication for helping prepare this and thank you all for coming in this in this rain okay so I'm gonna talk about random walks and this is a talk about math mostly I'm gonna try to keep the calculations and the numbers to them I know there'll be a few here and there but if if if they scare you then just tune them out and skip a minute and you won't miss anything you can join right later for those of you who happen to be mathematicians or experts in this field some of the things I'm gonna say a bit loose so you know forgive me for any inaccuracy some of the terms I made up especially for this talk so I hope to disappoint everybody cool okay so what is a random walk there are a few different types of random walks and we're gonna start with the simplest one which is a simple random walk on the integers so the integers are represented by these dots this is say 0 1 2 and then minus 1 minus 2 and we have some person or particle or something that starts say at zero and we have a clock the ticks and every tick of the clock this person is going to move either left or right with probability 1/2 so it's very important for me that we really understand so I want to give a little demonstration I need a heavier deck of cards I'm not gonna be a magic trick but I'm gonna shuffle them so things are random and I'm gonna need a volunteer from the audience maybe you come rat rat random random boy that I've never seen before what's your name I'm yeah okay stand right here so what I'm going to do is shuffle the deck and I'm gonna draw cards from the deck one by one and if it comes out black I'll say right and if it comes out red I'll say left and whenever I tell you right left just move one cone left or right got it okay okay so let's let's do a random walk by a random child right left right no that was wrong go back left right left right left right left Wow right right left left left right okay so that's how it goes thank you you can go [Music] okay so this is the basic idea is very very simple we have a random process in this case it was drawing card you can imagine that I tossed a coin or maybe I used a computer to this and I have some object in this case a person that moves right and left each time with probability 1/2 but people in math study this well that's a good question why they say they think it's interesting they think it's beautiful that's usually the motivation of mathematicians but this is actually an important model in science so this thing could be a boy jumping left and right it could be a particle that's being hit by other particles which sometimes move it to the right sometimes move it to the left that's called Brownian motion it could be the price of a stock that goes up and down randomly over time so understanding what happens with this very simple model does have implications to how we understand all sorts of real physical financial biological and other processes ok um so let's let's try and see what happens with this random walk what I have on this graph here is what happens after two ticks so we started out in the middle after one tick with probability 1/2 of was that one in probability 1/2 at minus one after two ticks either I came back to zero or I went to 2 or 2 minus 2 and it turns out that with probability 1/2 I end up back where I started and with probability 1/4 I'm at minus 2 and probability 1/4 I'm into this is what this is what it looks like after 20 ticks of the clock so now you see that it's somehow spread out there's still decent probability of being at zero about one point about 17% and then it drops off and even though 20 ticks have passed the probability of actually being at say minus 20 is very very small to be at minus 20 after 20 ticks I would have had to go left every single time would have had to pass 20 heads one after another that that doesn't have that chance of one in a million actually let's look at what it looks like after a hundred ticks so now the probability of being back at zero where I start is about 10% then it tapers off sort of gently and you can see that say around minus 10 and 10 most likely I'm somewhere between minus 10 and 10 and then it kind of drops off very quickly the probability of being beyond 30 is again very very small it's about should be about less than 1 in 10,000 or something something of that order of magnitude so even though I've taken a hundred steps I've most likely gone only about a distance 10 from where I started and this shape is something that appears very frequently in probability and also in many physical processes called the bell curve or a Gaussian or normal distribution and indeed if we look at what happens at time T after T ticks of this clock it's going to look more and more like a perfectly smooth beautiful bell curve the width of this bell curve is going to be about the square root of time of the time so at time 100 like we saw here most of the most likely I'm between minus 10 and 10 the width of this bell curve at time 100 is about 10 in fact with about probability 70% or 68% I'll be within square root T of 0 of where I started so at time 10 I'll be between minus antenna time 10,000 I'll be within the square root of 10,000 which is a hundred so within a hundred we're started at time 1 million I'll be within a thousand of where I started so a thousand is much much less than 1 million I've taken a million steps but most likely I have not drifted off more than a thousand locations from where I started and in fact so that the rate at which I escape at which I leave this place where I started is much much slower than if I was just walking straight okay so I'm gonna mention a few of the people who pioneered and made major contributions to this field first person mention is George poison now GERD mathematician is born in 1887 he was a professor in Switzerland from while then he moved to Stanford in the 40s and he has the following question what is the probability that the random walk will eventually return to the origin returned to where it started so when we had the random boy to the random walk I think right in the beginning he went right and then immediately back left and came back to where he started okay but you could have imagined that just by chance he would have taken I don't know three steps to the right and then went to the left and maybe one and maybe eventually maybe it's possible that he would never come back to where he started this is the question to Polly asked what is the probability that the random walk on the integers never comes back to the origin or what is the probability that eventually it comes it comes back to the ordinary so we want to know what happens after a long long time do we necessarily come back or do we not necessarily come back and with some probability drift off so there's their names for these things we call a random walk recurrent if it returns to where it started with probability 1 if with 100% probability it returns to where it started and we're gonna call it transient if this probability is less than 1 the probability is it's never going to be a 0 chance to return to where I started if I started here there is a decent chance that I go right and then go back left to where I started but maybe there is some chance that I never come back in which case I would call the random walk transient if I necessarily come back it's recurrent now recurrent random walk so random walk that comes back will then again come back and again and again because once I've come back to where I started I just start afresh and keep on walking again so if before I had to come back the second time I again have to come back and then the third time and so on so a recurrent and amok will come back again and again and again a transient random walk may come back a few times but eventually it would leave and never come back so Paulie asked which kind of random walk is this simple random walk on the integers recurrent or transient okay so it's a bit of a big crowd to take to ask you what you think but you should ask yourself what do you think do you think that this particle that's being pushed around by particles will eventually come back to where it started or is it gonna drift off here's another sort of economic application imagine that I'm gambling at a coin toss and when I guess correctly I get a dollar and when I guess incorrectly I lose a dollar so now I can look at my bank balance and it goes up by one each time with probability one half it goes down by one each time with probability one half exactly this random walk and if my bank balance starts at zero I can ask doesn't necessarily always going to come back to zero or is it possible that it goes up and never comes back down to the paulius theorem and Polly's name has a few parts and I'll explain the other parts too but the first part of Polly is there is that the simple random walk on the integers is recurrent so this random walk always comes back to where it started I'm gonna try to explain why this is true so the proof of why this is true is a bit technical you have to know some fairly advanced math or you have to know the state-of-the-art math of 1921 which is which is quite advanced but I'll try to give some intuition for for why it's true enough hopefully it'll tell us something it turns out this is related to Zeno's paradox so let me remind you what Zeno's paradox is or one of you knows paradoxes imagine that I have a runner who runs across a field and at the first tick of the clock the runner crosses half the field the second tick one-fourth of the field then 1/8 1/16 1 over 32 and so on so each time the runner runs a half of what she ran the previous tick of the clock and it turns out that the runner will never reach the end of the field the way to see that is to is to notice that the length of the field is 1 and what the runner is doing they're always having the distance left to run so if I want to walk across the stage first tick of the clock I walk halfway cross the second tick I walk half of what's left I'm not gonna reach the end the third tick I walk half of what's left now so again I'm not gonna reach the end and then half of what's left and so on so this is what this runner is doing they're never gonna reach the end if you sum up all these numbers to infinity they do reach the end okay in some sense at time infinity they get they reach one which is just another way of saying they're going to get arbitrarily close to one to the end of the field over time I don't want to get into a philosophical discussion of of Zeno's paradox I want to notice another thing imagine a different runner and this Runner is going to go through one half of the field at time one then 1/3 then 1/4 then one-fifth and so on it turned out that this runner will reach the end of the field in fact 1/2 plus 1/3 plus 1/4 is already more than 1 so after three ticks of the clock this runner you're gonna cross to the end of the field the more interesting thing is that no matter what the length of the field is imagine that this is counting 1/2 the length of a football field so I'm going to do 1/2 the length of a football field the time one and then 1/3 or football feel the time 2 and so on the question is how far am I going to go if I give myself enough time the answer is there's no limit to how far I'm gonna go if this is what I'm doing so I'm going less and less every time but somehow still given enough time I'll go any distance given enough time across enough you know get to the moon from here so the sum of all these numbers doesn't have a limit to write that the sum is infinity so the runner will reach the end but in fact give it enough time she'll go through any distance so some of these infinite sums of numbers are bounded or finite you never cross some line other sums like this one cross every line eventually even though the numbers are getting smaller and smaller and smaller okay so what does this have to do with our random walk let's try to understand what is the probability of coming back to zero at a particular time T so let's remember what happened at time 100 at time 100 I was most likely between minus 10 and 10 so you can imagine that more or less might the probability of when I am is spread more or less equally over 10 different locations so in each one it's going to be more or less 1 over 10 in fact the probability of being back at 0 is very close to 1 over 10 more generally it turns out that at time T the probability of being back at returning to where I started is about 1 over the square root of T so at time 100 the probability back is about 1 over 10 time 10,000 it's about 1 over 100 at time 1 million it's about 1 over a thousand what Paulie approved is the following he realized that if you take a sum of these return probabilities I'm gonna sum the probability that I come back at time 1 and the probability that I come back at time 2 and so on I'm gonna sum all these numbers if this sum is infinite if there's no bound to the sum then the random walk is recurrent somehow if this sum is infinite then these numbers are big so I have a high chance of returning if these numbers are small in the sense that their sum is finite then the random walk is transient and it turns out that if I sum the return probabilities for this random walk which is 1 over root T 1 over root 2 plus 1 over root 3 plus 1 root 4 and so on so this is an exercise that our freshmen will do here this sum is infinite which means that the random walk is recurrent ok so let's move it up a notch and let's go to two dimensions so what I'm gonna do here I didn't prepare two dimensional array of cones but I'm gonna again start somewhere on this on this grid say here and then at each tick of the clock I'm gonna draw a card and depending on which suit it's from one of the four suits I'm gonna move either left or right or forwards or backwards and then draw another one and again you've either left or right or forwards or backwards now you can ask the same question do I eventually come back to where I started okay so somehow there's a lot a lot more places to go here on a line I'm very constrained to be on the line so maybe it somehow makes sense that I keep on coming back but in this two-dimensional grid I can go this way in that way and maybe sort of come back but just miss it and go around it and go in some other direction it's not clear what happens here but it turns out that the same sort of reasoning that we saw before I'm can be used to solve this question and what we have to do we have to calculate the probability of coming back then sum them all and see if the sum is finite or infinite what is it going to look like at time T so let's look at time 1 million what is the probability that that I'm at each particular point on this grid it turns out that this time it actually looks like a bell not just like a slice of a bell but an actual bell so it's again a bell curve and it has width square root T so it turns out that in this two-dimensional random walk again I'm most likely not to have gone distance more than more than the square root of T of where I started now the number of points within a circle square root T of where I started is the square root of T squared which is T so here the probability to be back at time 1 over T at time is one over T the probability to be back at time 100 is about 1 over 100 instead of 1 over 10 that it was before it's much lower than it was before a time 1 million the probability to be back is 1 over a million but if I sum all these probabilities this sum is still infinite which means that again I'm going to come back again and again to the origin this is again recurrent random walk so when I have a two dimensional Walker they're gonna return to where they started for sure with probability 1 they come back to where they started so what would be the next question that we want to three them so what are we gonna do in 3 dimensions this would be very hard to demonstrate here but you can imagine a bird maybe I should have brought it a drone and and the drone is either gonna go left or right or forwards or backwards or it's going to go up or it's gonna go down each with probability 1/6 because I have 6 different options of where to go now so because I don't have a drone I have a YouTube video and this is the simulation on a computer that somebody did they're sort of zooming out and rotating it as it's developing so you can see it from all directions but this is what it looks like this point is doing exactly what I described it's moving up down left right forwards backwards each with probability 1/6 and now we can again ask what is the probability that we come back to where we started so this time again you should ask yourself what your intuition tells you if you've managed to develop one by now but somehow it seems very easy to miss this point that we started at there are a lot of different places that I can be in 3 dimensions I think we probably started somewhere ok I don't know what exactly we started to maybe up here but so here's what happens in three dimensions it turns out again that I'm not going to go more than the square root of T away from where I started so the distance that this particle went is again much much smaller than the amount of time it spent walking it's doing one move in each time period but because it's now going in a straight line but going randomly at time T it's only going to go square root T away from where it started so that that holds in every dimension but now there are a lot more places within square root e of where I started at time 1 million square root T is 1,000 and at distance 1000 of where I started they're about a million points it's gonna be the squared of T cubed and that's the probability of coming back it's 1 over the square root of T cubed this when I sum up these probabilities this sum turns out to be finite ok so something very interesting happens here this random walk is transient it may come back to where it started maybe this bird goes up and down just comes back right away maybe goes up down left right right left down up and comes back to where it started but eventually it's gonna go away and not come back again and this happens in the transition between two dimensions and three dimensions so this random walk is transient and this this is what is usually called paulius theorem tells you that it dimensions 1 & 2 3 & & Walken's recurrent and dimensions 3 & actually higher the random walk is is transient and and this has actual implications for example some biological processes when they happen on a membrane they behave differently than when they happen in 3 mentions in their say in the inside of her of a cell because there's this random walk element involved okay let's look at a different random walk so I'm gonna go back to to one dimension but this time I'm not just going to go with probability 1/2 and 1/2 left and right I'm going to go left with probability 1/3 and right with probability 2/3 so imagine maybe I'm still pulling out these cards but I only go left when it's a face card and I go right with all the other cards I think that should give me more or less 2/3 1/3 so I'm much more likely to go right then left and over time this will accumulate so if we look here this is what happens at time maybe time 50 I don't I'm 50 öre time 100 but I started at 0 this is my probability of being at each particular location at this time and you can see that the probability of being back at 0 is already very very small and most likely to have drifted to the right yeah so this should be at time 50 I've most likely have drifted to the right and and I'm over here so it's still gonna look like a bell curve but instead of being centered at zero and giving a lot of probability to being back at zero it's going to be centered more and more to the right the center is gonna be at about T over 3 so at time T I will more or less have gone T over 3 to the right 1/3 so I'm still not going as fast as if I was just going to the right I'm only going at 1/3 to speed but the probability to be back is now very very small and this random walk is transient again I might come back maybe I'll go to the left and then to the right and left left and right right and come back but eventually I'm guaranteed to leave and not come back again so this is another example of a transient walk in one dimension the simple random walk in one dimension keeps on coming back ok so we we've looked at 1 2 in 3 dimensions and you can do this in 4 & 5 dimensions whatever that means and actually anything above 3 the same way in this traffic so the next thing that people did were try to think about random walks not in any particular dimension but in completely different geometries this is gonna be non Euclidean geometry so what does that what does that mean here's an example this is called the well imagine that now I'm these locations are where I'm allowed to be and what I'm going to do is I'm going to do a random walk between these locations I'm going to move along these lines that connect these locations randomly this picture and this picture actually are the same geometry here you can see it you can see the symmetry very nice this geometry or this graph as they're called it's called the three regular tree tree because I guess if you look at it like this it it actually looks like a tree three regular because each location each point is connected to exactly three other points and one important feature of this graph which differentiates it from this the grids we've seen so far the two dimensional the three dimensions is that there are no loops if I go somewhere the only way I can return to where I started is through the same path I can't go this way and come back through another path when I do it random walk on the two-dimensional grid I can I can leave a point one way and come back from a very different direction here if I leave this point and go up if I ever come back I have to come back from this location I cannot this is not connected to this I can't loop around here's the four regular tree so now it's exactly the same except each location has four different neighboring locations and again there are no loops and you can draw many many certs or graphs like this this is just a taste of the possible geometries or graphs where you can you can do random walks it's there's a whole universe of these things and it's very very interesting to study different proper these things so let's be a bit more concrete what I mean by a random walk here so this is again the three regular tree imagine that there's another line coming out here connected to two more vertices so I'm going to start from one of them say the origin is here and at each tick of the clock I'm going to move with probability 1/3 to each one of the three neighboring locations I'm gonna do this again and again and again let's ask the same question do I keep on coming back to where I started or do I leave and never come back and it turns out that this random walk is transient so it leaves and never comes back it's not a recurrent random walk that comes back again and again and again and the way to see this is to connect it to this random walk with a drift that I talked about before so before I was walking on the integers going left with probability 1/3 and right with probability 2/3 and we saw that that was transient eventually I don't go and I leave and don't come back what's going on here is that when I'm at a given point we can let's divide this into levels so everything that's on the same line is going to be in the same level what happens when I'm at a certain level I have probability 1/3 of going here probability 1/3 of going here probability 1/3 of going here so our probability 2/3 of going up and 1/3 of going down so if we only look at what happens to my height it's exactly like this random walk on the integers with adrift it has an upward drift so my height is gonna eventually not go back to being 0 so I won't come back to this point where I started this is a transient random walk and you can see it here also if I start from here you could if I if I say go up I have probability 3/4 of going further away from where it started and only probability 1/4 of coming back so again I'm gonna tend to drift away and eventually I won't come back so here's another question that people have asked does the random walk return to all directions so now I want to know not whether the random walk returns to where it started but does it return to all directions so what do I mean by that imagine that we have this random boy doing the random walk imagine in two dimensions so there's this two-dimensional grid and I just stand where he started and I let him do his walk but my hand points to where he is so maybe he starts over there and then goes there and my hand points to where he is and the question is am I going to point in all directions again and again and again or am I eventually going to server sort of fixate and not change the direction will I eventually not go back to pointing there and in two dimensions the up the answer is very simple I'm gonna point in all directions again and again because the random walk is recurrent so the walker comes back to our started and goes off and each time they're gonna go off they're going to go off in a different direction so I'm going to point in all directions again and again and again one interesting question is what happens in three dimensions in three dimensions the random walk is transient eventually it leaves and never comes back so this drone or bird that's doing the random walk maybe I'll come back but eventually and what it won't come back it'll be very very far and stay very very far it'll go further and further out so when my hand is pointing at where it is it's gonna be a very small speck in the sky that's still only moving one step left right up or down so my hand is only going to move very very little and now it's not clear whether I'm gonna it's gonna go again again and again to all directions so it turns out that this was solved and there's a theorem called Ashok a Denis theorem and it turns out that in any dimension the random walk will visit all dimensions again and again so even though this random walk becomes in three dimensions it becomes very very far if I'm pointing there over time if I give it enough time I'll end up pointing there and there in any possible direction again and again and again and I'm gonna call random walks that have this property directionally recurrent so the direction is returned they come back to all directions again and again again and the ship headed near the knee theorem is named after two friends gentleman says that in any dimension the random walk is directionally recurrent it'll visit all directions again and again so let me tell you a little bit about the history of this show Kaden Ethier and for that I have to tell you about David Blackwell so David Baca was born in Illinois in 1919 he went to her vanish Champaign it was sort of a child prodigy he went there when he was 16 or 17 he graduated at 19 he got a PhD at 22 in math he later did research in maths statistics economics he was very prolific and had a lot of them great contributions to many fields and his first job after the PhD was a postdoctoral fellow at the Institute for Advanced Study at Princeton so the Institute for Advanced Study was already there very prestigious place that Einstein there's one founding members in Hanoi Minh was an important mathematician and Blackwell actually had a chance to talk to phenomena and worked with him it's it's not it's in the town of Princeton and it's not part of the University but they have a lot of joined um I guess crowd OH collaboration and people from the Institute for Advanced Study often went to take courses in Princeton the Institute didn't have it its own courses now David Blackwell unlike other people in his position was not allowed to go to Princeton to take courses which is why he left and the reason he wasn't allowed to do that is because he was black so in Princeton in 41 there were no black students the first undergrads graduated later okay during the 18th century there was one or two after the Civil War the first PhD graduates from Princeton who were African American it's only in the late 50s so Blackwell left he got a position at Howard University which is this historical black University he was there for 12 years he applied to Berkeley when he went to Howard but again he was denied due to racial concerns they weren't really trying to hide it they thought his work was it was good enough but in 59 he was given a position in UC Berkeley it was the first tenured african-american there and in 65 he was the first african-american in the American Academy of Sciences so somehow to some extent at least he was accepted eventually but it was a long and arduous work despite all this he's he has great contributions across many fields every colonist knows his name as well as people in probability in other fields of math and statistics so it turns out that black will prove - okay Denis theorem a few years the force of K and in E but still the names okay Denis theorem is how how this goes but maybe should be called Blackwell's theorem and it's the same theorem just a few years earlier that it visit that these random walks are our direction be recurrent so this term directionally recurrent as a term I made up so I apologize to any experts in the audience who are wondering what what I'm talking about so what happens to random walk on this regular tree well remember that it's transient eventually it leaves the point where it started and never comes back let's look at it here or maybe here I start here and eventually I leave and don't come back imagine that I leave and go up the last time that I leave and don't come back well if I left going up and I never come back to this point I have to spend the rest of the random walk somewhere up here I can never go to this branch of the tree because I left this point and I'm not coming back if I was going to get to this retic because there are no loops I can't loop around and come to this branch so once I've left I'm stuck in this branch forever so I might leave and come back and leave and come back but eventually they leave and don't come back so if you have a person standing here in the middle and pointing at the random Walker they're not going to point in all directions again and again eventually they're gonna point say upwards or maybe this way or maybe that way each with probability 1/3 so there's a random direction that this random walk converges to but actually it does the direction does get fixated from some point on and doesn't change so this random walk is not Direction the currents are actually transient and there's a big question which is for which kind of of geometries or which kind of graphs like this I've only shown you these very few examples is the random walk directionally recurrent if I show you a picture like that of the geometry can you tell me what the random walk will do there and this is a difficult problem we we've made some progress on this so this is together with to Caltech grad students who extremely bright and another collaborator of ours yet you're hardly lose at ben-gurion University in Israel and we've understood this for a certain class of geometries in some sense I don't want to get into the technical details that are called groups so some of these graphs that come from something called groups whatever that means we now understand better this question for them so this this is uh this is some recent progress that's been made so the last thing I want to tell you is about a connection to economics it's a bit of a tenuous connection but I'll tell you anyway so so here's a little riddle imagine that I have a person standing at each node here I also have a person standing in each node here and they have to agree on on a money exchanging scheme each one of them has to choose one of the people who's next to them so in this case one of the three people who are next to me in this case one of the four people who are next to me and give them $1 the question is can we do this in such a way that everybody becomes richer by $1 so I give $1 but I get $2 and that's true for everyone this sounds very paradoxical how is it possible that everybody takes $1 out of their pocket gives it to somebody and suddenly everybody is $1 richer than before so this turns out to be impossible to do here there's absolutely no way to do this it's a nice little argument for why that's true but here it is it is possible so how can I do this here how do we how do we make how we decide who gives money to whom so that everybody becomes $1 richer right so what we're gonna do is we're gonna give the dollar down each person has two people above them and one person below them and each person is just gonna give the dollar to the person below them and get two dollars from the person above them okay it's called a Ponzi scheme but it actually works here because this graph doesn't end so there isn't the layer of fools at the end who are left without their dollar but here there's no way to do a Ponzi scheme like this so there's something really different about this geometry in this in geometry even though here we also have infinitely many people there are no Ponzi schemes here here there are Ponzi schemes and this turns out to be related to this question of directional recurrence of the random walk so this is related to a lot of work done by Hillel Furstenberg who was born in 35 in Berlin they they fled Germany in 39 to the sea the US he studied at Princeton then he was a professor in the University of Minnesota in ventually he moved to the Hebrew University and in Jerusalem he also happens to be the academic advisor of the academic advisor of the academic advisor of my advisor and what he showed I guess this is also related to results by by other people is that graphs in which wealth creation in which these Ponzi schemes can exist I directionally transient so when I have a graph like this one imagine that here we have this point in the center and everybody just sends one dollar towards the center so this person is going to send a dollar here and this person will send a dollar here this person will send a dollar here and so on so here everybody comes three dollars or two dollars richer so graphs like this where you have these Ponzi schemes the random walks on them are directionally transient they don't come back to all the erections again and again okay so this there is this mathematical connection between these two seemingly unrelated okay thank you very much [Applause] you
Info
Channel: caltech
Views: 4,313
Rating: 4.7872338 out of 5
Keywords: Caltech, science, technology, research
Id: b8LMlCPRjPE
Channel Id: undefined
Length: 43min 47sec (2627 seconds)
Published: Tue Jan 22 2019
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.