English 字幕

← 18-22 Distance To Satisfying Assignment



Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. So another way that we can understand this is that we start out with a random assignment
  2. that has a distance of n/2 to the satisfying assignment
  3. Again, assuming that assignment exists.
  4. So, by distance, I mean the number of variables we need to flip.
  5. We can expect this to be about n/2 as we just found out.
  6. Each time this algorithm here goes through the loop, there's two things that can happen
  7. The first thing is that we move closer to the satisfying assignment
  8. and by closer, I mean that we gained one more variable
  9. that is set to the same as it would be in the satisfying assignment.
  10. So basically, making a step forward happens with probability one-third
  11. but of course as we also just found out, we can also make a step backward
  12. and kind of flip the wrong variable and the probability for doing that is at most two-thirds.
  13. Let's show worse case analysis here so we will erase this one here
  14. and say in a worse case, we make a step forward with probability exactly one-third
  15. and we make a step backward with probability exactly two-thirds.
  16. And how often do we make this step? Well, the loop here is executed 3n*.
  17. So what happens is the following, we start off here with our random assignment and then 3n*
  18. We either move forward with probability one-third or we move backward with probability two-thirds.
  19. And then the next time assume that we are lucky, we have move forward,
  20. we again move forward with probability one-third and backwards with probability two-thirds
  21. and this goes on and on and on and on until we either reach the satisfying assignment
  22. or which is much more likely, we don't reach the satisfying assignment.
  23. We might even get farther away from it.
  24. Actually, chances are pretty good that we are.
  25. Now, the nasty thing here of course is that we move forward
  26. with the lower probability than moving backward.
  27. So, the probability of coming from a random assignment to the satisfying assignment
  28. by running the algorithm once actually doesn't seem too good
  29. and the exact probability analysis here is somewhat complicated
  30. especially if you haven't had an intermediate course in statistics yet,
  31. but what we can try to do even if the statistic analysis is may be a bit complicated
  32. is at least do a simulation.
  33. So, run a program to do simulation for me.
  34. Assuming you start at a distance one half from a satisfying assignment
  35. What's the probability of making n/2 steps in the right direction
  36. if the probability of making a step in the right direction is one-third
  37. and the probability of making a step in the wrong direction is two-thirds
  38. and you try 3n* and then run this for different values of n and here's what I got.
  39. Now, of course, when you run such a simulation yourself, you might get a little bit different results,
  40. but you will be more or less in the same range, I hope.
  41. Here are the results that I got.
  42. For n equals 10, you end up at 2.8% probability of making n/2 steps in the right direction.
  43. For n equals 20, it's 0.084% and you can see that it rather quickly decreases.
  44. Now, my question to you here, does the probability decrease
  45. as a function of n again logarithmically with n, linearly with n, or exponentially with n.