18.6 - Random walks on a line - Local search algorithms - [dsa 2] - By tim roughgarden

Understanding why Papadimitrious's randomized local search algorithm for two set works requires understanding some basic properties of random walks on the non-negative integers. It's a very fun classic topic. In this video I'll provide the relevant background. In this video, we're going to focus on a simple randomized process. We're not going to discuss in this video how this connects to Papadimitriou's algorithm. But in the next video, we will, trust me. The setup is as follows. Perhaps you just took a super difficult exam. Maybe it was in algorithm class, for example. You stagger out of the exam room and you're just in a complete daze. You have no idea where you are or were your going. You just stumble along. At each time step, you take a step to the left with 50% probability. Where a step to the right with 50% probability, you have no idea where you're going. We measure your position in terms of the number of steps you've taken from a dead end at the end of the street, which we call position 0. So by randomly walking left or right at each time step, your position either goes up by 1 or it goes down by one. Each has a 50 50 chance of happening. So one exception is if you found your way to position 0. Again that's a dead end, there's no way to go left. So with 100% probability, you stagger back to the right. You go back to position one at the next time step. We assume that your exam room is located at this position 0 at the dead end. In other words, at time 0 you're at position 0. There's a lot of interesting questions you can ask about random walks on the non-negative integers. Here's the one we're going to be interested in. Imagine your dorm room is n steps away from the exam room, that is, your dorm room is at position [INAUDIBLE] n. Now if you had your wits about you, you could go from your exam room to your dorm room in n steps. You just zip right down the line. But you don't have your wits about you. You're in this post-exam daze, staggering around. So doing your random walk, on average how many steps does it take you before you make it home? To position N. To illustrate a sample trajectory, imagine that your dorm room was only three steps away. That's spot 3. So in time 1, we know that for sure, you move from position 0 to position 1. And now maybe you get lucky and you stumble a step to the right, in the next time step, so you're at position 2. You're only one step away from home. But now, unfortunately, you stagger backward, back to position one. Maybe now you lurch forward back to position two again and this time your momentum carries you forward on home to position 3. That was a trajectory in which it took you 5 steps to get home to your dorm room at position three. You can imagine a trajectory which is faster if you just zipped straight there. There, you can certainly also imagine trajectories which are slower if you stumbled back left a couple times more before making it all the way to the right to position three. So let's state this statistic precisely and check in with your intuition about how it grows as a function of n. So, for a non-negative integer, n, I'm going to use T sub n to denote the number of steps this random walk takes before it reaches, for the first time, position n. So, T sub n is a random variable in the sense that it's value depends on exactly which steps you took on the results of your random coin flips. On the other hand, once you unveil the answers to all of the random coin flips whether you go left Left to right, at each time step you can compute T, just like we did in the sample trajectory on the last slide.So the non-trivial question I want you to think about on this quiz is, how does the expected value of T saban/g grow as a function of the position And that you're waiting to reach. I'm not expecting to devise a proof to the asnswer, indeed that's what we're going to be doing for most of the rest of this video. Just asking you to take your best guess. And so the correct answer is B, theta n^2. Depending on how much facility you have with discrete probability, you may or may not have been able to do a back-of-the-envelope calculation that would suggest this should be the answer. So for example, if you take some Bernoulli random variables and do some calculations with their standard deviation, you might expect the answer to be theta(n^2). In fact what's even cooler and what we're going to prove is it's not just theta(n^2), the expected value of The variant random variable T sub N is exactly N squared for every non-negative integer N. For the most part in these courses, I've endeavored to give you proofs which on the one hand aren't too long, I know you're a busy person and I don't want to waste your time, but also on the other hand teach you something. So I hope you'll forgive me if it's not clear what this proof teaches you. This is just going to be the slicked-up [INAUDIBLE] proof from the book that the expected value of T sub n, number of steps needed to reach the position n on a random walk is exactly m squared. The really nice idea behind this slick proof is to solve a more general problem. So we're going to calculate the expected number of steps, not just to get from position 0 to position n on a random walk. But more generally from every intermediate position I to the position N on a random walk. The reason this is a good idea, this gives us N+1 different statistics we're trying to calculate. And it's easy to relate the values of these differents things we're trying to calculate. From these relationships we'll be able to solve for all of them simultaneously. So, let's have some notation to make this precise for a non-negative integer i, by Z sub i, I mean the number of random walk steps that you take if I start you at i until you reach position n for the first time. Notice by the definitions, Z sub zero is exactly the same thing as t sub n. The number of steps you need to reach n starting from 0. So, are there any Zi's whose expectations are easy to compute? Well, sure, if we took i=n, what is z sub n. That's the, number of steps, on average, you need to get from n to n, for the first time. Well that's going to be zero. For the other values of i, we're not going to solve for the expected value of z sub i explicitly just yet. Rather, we're going to relate the expectations of different zi's to each other. To see how this works lets start with i equals zero that is Z0 the random variable that we really care about. Now we don't know what the expected value of Z0 is that's is we're trying to compute but we do know that every walk starting at 0 and you get n begins with the step from 0 to 1 and then is followed by. A walk from 1 to N. Therefore, the expected length of one of these walks is just 1, that's for that first hop to get from 0 to 1 plus the expected value of a random walk from position 1 to N. That's a quantity also known as the expected value of Z sub 1. So that's kind of exciting, how we were able to avoid explicitly computing the expected value of z sub 0, instead relating it to the expectation of a different random variable z sub 1. But if you think about it we can play exactly the same game with the intermediate values of pi as well. We can relate the expected value of z sub i to the expected values of z sub i-1 and z sub i+1. To make this fully precise, I'm going to bust out the definition of conditional expectation. If you want to review it, you can go back to part 1, we need a conditional probability to analyze, [UNKNOWN] contraction algorithm or you can just look it up on Wikipedia or whatever. If you are not feeling in the mood to recall what conditional expectation is, actually think the computations them about to do or sufficiently intuitive, you will find them eminently plausible even without the former justification. So what's the expected value of Z sub i, the average number of steps you need to hit n for the first time if I start you out at position i. Well, let's just condition on what happened in the first step. There are only 2 possibilities. 50% probability you go left to i-1. The rest of what happens is a random walk from i-1 and you just count the steps till you get the end for the first time. The other 50% of the time where you go right and the rest of the process is just a random walk starting from i+1 and you count the steps till you get the end for the first time. If you want to be totally formal about it, you would just expand that the expected value of z sub i conditioning on the first step, so you'll have the probability when you go left times the Conditional expectation of Z sub I given that you go left in the first step and a similar term for when you go right. As we discussed, we know the probability that you go left is exactly 1/2. The probability that you go right is exactly 1/2. The conditional expected value of your random walk, given that you went left first, well that's just 1. That's the step you took to get to I-1, plus the expected length of a random walk to N from I-1. Similarly, if you're lucky enough to go right, then the expected random walk is just 1, that's for the step to go right, plus the expected value of the rest of the random walk, also known as the expected value of Z sub (i+1). Once the dust clears, we discover that the expected value of Z sub i, the average number of steps from position i, is just 1. Plus the average of the expectations of Z sub I minus 1, and Z sub I plus 1. If we multiply both sides of this equality by 2 and rearrange, we get that the difference between the expected values of Z sub I and Z sub I plus 1 is equal to 2 more than the difference between the expected values of Z sub I minus 1 and Z sub I. So what's going to interpretation of this equation? Well first let's just notice that the expected value of z sub i, of that number is definitely decreasing as you take i bigger and bigger. As you start closer and closer to your destination n, certainly the number of steps you need is going down. So without reason both sides of this equation are going to be positive. Write the expected value of Z sub i is going to be bigger than z sub i+1. You don't need as many steps if you start further to the right at i+1. This equation is saying more, its saying, consider a consecutive pair of conceivable starting point. Clearly you have an advantage by starting one position closer. This equation is saying that as you slide this pair of consecutive starting points closer to the destination the advantage gets amplified. So, so however much savings you got by starting 1 position closer at 1 instead of I-1, you get that same advantage plus two more if you get to start at I+1 relative to starting at I. So why was it useful to relate all of these various expectations to each other? Well now that we have this big systems of constraints, we can solve simultaneously for what all of these expectations have to be. In particular, one expectation we really care about, e of z naught. So to see how we do this, let's just write down what the difference is between success and expectations have to be. So the first thing we know and this is one of our edge cases, is that whatever the expected value of Z not is it has to be one more than the expected value of Z1. That is the difference between these two expectations equals 1. We concluded the previous slide by noting that if you slide a pair of consecutive positions, one position further toward the destination n, then the advantage you get by starting one position closer goes up by two. So, if your advantage is one, by starting at z1 instead of z9 Then your advantage is going to be three by starting at Z two instead of Z one. That is, the expected value of Z one minus the expected number of steps from two is going to be equal to three. So we can just apply that equation over and over again. We bump up the indices by one, and the difference between the expectation gets bumped up by two. So at the end of the day, relative to our very first equation we've bumped up both indexes by n-1, so we've bumped up the right hand side by 2n-2, so we have that the expected value of zn-1 minus the expected value of zn=2n-1. Massive cancellation is often the sign you're on the right track so that's what we're going to see here. So all of the expected values for z1 throught zn-1 appears once positively, once negatively so they all are going to drop out. And actually gets even better than that, the expected value of z sub n. That's just 0. Remember that would be how longer random walk takes to get from end to end, also known as 0. So if we add up all these equations we magically get exactly what he heard about in left hand side the expected value of z0 of a walks turning at 0 and the n that's also known as T sub n, the expectation we're trying to analyse. So what is the right hand side sum 1 easy way to think about it is just to group the first row with the last row the second row with the second to the last row and so on. For example of n is equal to 100 we're going to group 1 with 199, 3 with 197, 5 with 195, and so on. So each of these groupings is going to gives us 2N, and if N is even there's going to be N/2 of these pairs, giving us a total of N^2. If N is odd, the story is the same you just get N-1/2 groups of size 2N, plus the median group is going to have the value of N. Again, you get N^2. So that completes this very pretty if some what inscrutable proof that the expected number of steps you need before you reach n for the first time is exactly n squared. In the analysis of Papadimitriou's algorithm we're not actually going to use this claim about the expectation rather we're going to use an easy corollary which gives an upper bound of the probablility that. This exceeds its expectation by more than a factor of 2. Specifically, we're going to use the fact that the probability that a random walk needs strictly more than 2*n^2 steps tor each position n for the first time is no more than 50%. This is a special case of a simple but useful inequality known as Markov's Inequality. In proof let's denote by p the probability of interest, the probability that the random variable Tn is strictly bigger than 2n^. Essentially the reason the corollary is true is that if the probability that Tn was bigger than 2n^ was strictly bigger than 1/2, well then the expectation would have to be bigger than n squared, but it's not it's eqauls to n squared, we just computed it. So a little more formally, let's start from the expected value of t sub n. Now we know this is n^2, we just computed it, but let's also write out the definition of this expected value. So that's just a sum over the values that tn might take on, let's go ahead and just use all, all negative integers k from 0 to infinity, and then it's k times the probability that t sub n takes on the value k. I'm going to break this sum into two parts. The parts where k takes on a value that's at most 2n^2, and then the parts of the sum where k takes on a value bigger than 2n^2. So now let me just do some very crude lower bounds of this right-hand side. This first sum, well, whatever it is, it's going to be non-negative. Because ks are non negative and probabilities are non negative. And the second sum, again I'm feeling very generous, let's just lower bound k in the sum by 2n^2, it's always going to be bigger than that. After the dust clears the first sum has disappeared that's what we're just lower-bounding by 0. In the second sum we're lowering K by 2n squared at that point. We can take the 2n squared outside the sum and at that point the sum is merely the total probability masked on which Tn takes on a value strictly bigger than 2n^2+1. By definition we are calling this probability of P. This is the probability of interest. And rearranging we do see that, in fact, P has to be at most one-half [INAUDIBLE] So that completes the claim of the corollary. It's really just a simple consequence of the hard work which was proving that the expected value of this random log was n^2. We'll plug this corollary into the analyisis of Papademetriou's algorithm next.