
タイトル：
1822 Distance To Satisfying Assignment

概説：

So another way that we can understand this is that we start out with a random assignment

that has a distance of n/2 to the satisfying assignment

Again, assuming that assignment exists.

So, by distance, I mean the number of variables we need to flip.

We can expect this to be about n/2 as we just found out.

Each time this algorithm here goes through the loop, there's two things that can happen

The first thing is that we move closer to the satisfying assignment

and by closer, I mean that we gained one more variable

that is set to the same as it would be in the satisfying assignment.

So basically, making a step forward happens with probability onethird

but of course as we also just found out, we can also make a step backward

and kind of flip the wrong variable and the probability for doing that is at most twothirds.

Let's show worse case analysis here so we will erase this one here

and say in a worse case, we make a step forward with probability exactly onethird

and we make a step backward with probability exactly twothirds.

And how often do we make this step? Well, the loop here is executed 3n*.

So what happens is the following, we start off here with our random assignment and then 3n*

We either move forward with probability onethird or we move backward with probability twothirds.

And then the next time assume that we are lucky, we have move forward,

we again move forward with probability onethird and backwards with probability twothirds

and this goes on and on and on and on until we either reach the satisfying assignment

or which is much more likely, we don't reach the satisfying assignment.

We might even get farther away from it.

Actually, chances are pretty good that we are.

Now, the nasty thing here of course is that we move forward

with the lower probability than moving backward.

So, the probability of coming from a random assignment to the satisfying assignment

by running the algorithm once actually doesn't seem too good

and the exact probability analysis here is somewhat complicated

especially if you haven't had an intermediate course in statistics yet,

but what we can try to do even if the statistic analysis is may be a bit complicated

is at least do a simulation.

So, run a program to do simulation for me.

Assuming you start at a distance one half from a satisfying assignment

What's the probability of making n/2 steps in the right direction

if the probability of making a step in the right direction is onethird

and the probability of making a step in the wrong direction is twothirds

and you try 3n* and then run this for different values of n and here's what I got.

Now, of course, when you run such a simulation yourself, you might get a little bit different results,

but you will be more or less in the same range, I hope.

Here are the results that I got.

For n equals 10, you end up at 2.8% probability of making n/2 steps in the right direction.

For n equals 20, it's 0.084% and you can see that it rather quickly decreases.

Now, my question to you here, does the probability decrease

as a function of n again logarithmically with n, linearly with n, or exponentially with n.