• The Amara On Demand team is looking for native speakers of German, Japanese, Korean, Italian, Hindi and Dutch to help with special paid projects
Apply here 非表示にする

## ← 18-22 Distance To Satisfying Assignment

• 1 フォロワー
• 45 Lines

### 埋め込みコードを取得する x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=6QhSaF9koxg" data-team="udacity"></div> ``` 1言語

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.