Probability

Question 1

Chernoff Bound

Answer 1

The likelihood of being at least some distance away from the middle decreases exponentially on distance

Question 2

Markov Inequality

Answer 2

The probability something is beyond a bound*expected value must be smaller than 1/bound

Question 3

Drunkard’s Walk on 2SAT

Answer 3

You can flip bits randomly in a 2SAT solution and mimic drunkards walk - do this 100n^2 times and you have at least a 10% chance of landing past distance n from the origin

Question 4

Lower and Upper Bound Probabilities for Drunkard’s Walk

Answer 4

If you walked n steps, the probability you’re within 10sqrt(n) from the origin is at least 99%.

If you walked n steps, the probability that you’re at least sqrt(n)/10 steps from the origin is at least 10%

If you walked 100n^2 steps, I can guarantee with at least 99% certainty that you are within 100n steps of the start

If you walked 100n^2 steps, I can guarantee with at least 10% certainty that you are at least n away from the start