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.