Binomial Distribution

Math for CS · Axiom Academy

Counting successes in repeated trials The binomial distribution answers a fundamental question: if you repeat an experiment n times, each with success probability p , how many successes do you get? Each trial has exactly two outcomes (success/failure) Same probability p for every trial : the number of ways to choose which k trials are successes p^k : probability those k trials all succeed (1-p)^ n-k : probability the remaining n - k trials all fail Parameters: (number of trials), (success probability) Run a Monte Carlo algorithm n times, each succeeding with probability p . The number of successes is Binomial (n,p) . Want at least one success? . Insert n keys into a table of size m using uniform hashing. Keys landing in a specific slot follow Binomial (n, 1/m) . Expected chain length = n/m (the load factor). A communication channel flips each bit independently with probability p . Errors in n bits follow Binomial (n,p) . Error-correcting codes are designed to handle the likely range of errors. If n is large and p is small (with moderate): Binomial counts successes in n independent trials Requires: fixed n , independent trials, constant p , binary outcome Approximated by Normal (large n ) or Poisson (large n , small p ) Fundamental for analyzing randomized algorithms and networks Axiom Academy | Probability for Computer Science

This is the written version of the interactive lesson above. See the full Math for CS course.