Great Theoretical Ideas In Computer Science Steven Rudich Anupam Gupta Lecture 18 March 18 2004 CS 15 251 Spring 2004 Carnegie Mellon University Probability Theory Counting in Terms of Proportions A Probability Distribution Proportio n of MALES HEIGHT The Descendants Of Adam Adam was X inches tall He had two sons One was X 1 inches tall One was X 1 inches tall Each of his sons had two sons X X 1 X 1 X X 2 X 1 X 3 X 2 X 4 1 5 6 X 2 X 1 X 10 15 X 3 1 5 10 20 X 4 X 2 15 6 1 X 1 X 1 X X 2 X 1 X 3 X 2 X 4 1 5 6 X 2 X 1 X 10 15 X 3 1 5 10 20 X 4 X 2 15 6 1 1 1 X X 2 X 1 X 3 X 2 X 4 1 5 6 X 2 X 1 X 10 15 X 3 1 5 10 20 X 4 X 2 15 6 1 1 1 2 1 X 1 X 3 X 2 X 4 1 5 6 1 X 1 X 10 15 X 3 1 5 10 20 X 4 X 2 15 6 1 1 1 2 1 3 1 X 2 X 4 1 5 6 3 X 10 15 1 1 1 5 10 20 X 4 X 2 15 6 1 1 1 2 1 3 1 4 1 1 5 6 3 6 10 15 1 1 1 5 10 20 1 4 15 6 1 1 1 2 1 3 1 4 1 1 5 1 3 6 10 1 1 4 10 5 1 In nth generation there will be 2n males 6 6 15of n 1 15 20 different each with one heights h0 h1 hn hi X n 2i occurs with proportion Unbiased Binomial Distribution On n 1 Elements Let S be any set h0 h1 hn where each element hi has an associated probability Any such distribution is called an Unbiased Binomial Distribution or an Unbiased Bernoulli Distribution As the number of elements gets larger the shape of the unbiased binomial distribution converges to a Normal or Gaussian distribution Standard Deviation Mean Coin Flipping in Manhattan 1 4 6 4 1 At each step we flip a coin to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i Coin Flipping in Manhattan 1 4 6 4 1 At each step we flip a coin to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i Coin Flipping in Manhattan 1 4 6 4 1 At each step we flip a coin to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i Coin Flipping in Manhattan 1 4 6 4 1 At each step we flip a coin to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i Coin Flipping in Manhattan 1 4 6 4 1 At each step we flip a coin to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i Coin Flipping in Manhattan 1 4 6 4 1 2n different paths to level n each equally likely The probability of i heads occurring on the path we generate is n step Random Walk on a line 1 4 6 4 1 Start at the origin at each point flip an unbiased coin to decide whether to go right or left The probability that in n steps we take i steps to the right and n i to the left so we are at position 2i n is n step Random Walk on a line 1 4 6 4 1 Start at the origin at each point flip an unbiased coin to decide whether to go right or left The probability that in n steps we take i steps to the right and n i to the left so we are at position 2i n is n step Random Walk on a line 1 4 6 4 1 Start at the origin at each point flip an unbiased coin to decide whether to go right or left The probability that in n steps we take i steps to the right and n i to the left so we are at position 2i n is n step Random Walk on a line 1 4 6 4 1 Start at the origin at each point flip an unbiased coin to decide whether to go right or left The probability that in n steps we take i steps to the right and n i to the left so we are at position 2i n is n step Random Walk on a line 1 4 6 4 1 Start at the origin at each point flip an unbiased coin to decide whether to go right or left The probability that in n steps we take i steps to the right and n i to the left so we are at position 2i n is Probabilities and counting Say we want to count the number of X s with property Y One way to do it is to ask if we pick an X at random what is the probability it has property Y and then multiply by the number of X s Probability of X with property Y of X with property Y of X How many n bit strings have an even number of 1 s If you flip a coin n times what is the probability you get an even number of heads Then multiply by 2n Say prob was q after n 1 flips Then after n flips it is q 1 q Binomial distribution with bias p p 1 p 1 4 6 4 1 Start at the top At each step flip a coin with a bias p of heads to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i after n steps Binomial distribution with bias p p 1 p 1 4 6 4 1 Start at the top At each step flip a coin with a bias p of heads to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i after n steps Binomial distribution with bias p p 1 p p 1 p p 1 4 6 4 1 Start at the top At each step flip a coin with a bias p of heads to decide which way to go What is the probability of ending at the intersection of Avenue i and Street n i after n steps Binomial distribution with bias p p 1 p p 1 p p 1 4 6 4 1 Start at the top At each step flip a coin with …
View Full Document
Unlocking...