Homework answers / question archive / 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

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

Share With

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).