You toss a fair coin 1000 times and take a step forward if the coin lands head and a step backward if it lands tail

Math Sep 09, 2020

You toss a fair coin 1000 times and take a step forward if the coin lands head and a step backward if it lands tail. Upper bound the probability that you end up ≥100 steps from your starting point (in either direction) using Chernoff bound (after the final simplification as in the slides).