0:00

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.

Â