Great Theoretical Ideas In Computer Science John Lafferty Lecture 9 September 26 2006 CS 15 251 Fall 2006 Carnegie Mellon University Probability Theory Counting in Terms of Proportions A Probability Distribution Proportion of MALES 75 of the male population 50 of the male population HEIGHT 50 of the male population 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 1 X 10 15 X 2 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 1 X 10 15 X 2 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 1 X 10 15 X 2 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 X 1 X 10 15 1 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 1th In n each 1 3 6 1 4 1 5 n 1 10 10 generation there will be 2 males 6 6 15 of n 1 with one heights 15 20 different 5 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 a unbiased Binomial Distribution As the number of elements gets larger the shape of the unbiased binomial distribution converges to a Normal or Gaussian distribution Mean As the number of elements gets larger the shape of the unbiased binomial distribution converges to a Normal or Gaussian distribution 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 after n steps 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 after n steps 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 after n steps 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 after n steps 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 after n steps 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 Galton s Quincunx Machine Again a Normal or Gaussian distribution Let s look after n steps 50 of time 2 3 n Again a Normal or Gaussian distribution Let s look after n steps 68 of time n Again a Normal or Gaussian distribution Let s look after n steps 95 of time 2 n Again a Normal or Gaussian distribution Let s look after n steps 99 7 of time 3 n Probabilities and Counting are intimately related ideas Probabilities and counting Say we want to count the number of X s with property P One way to do it is to ask if we pick an X at random what is the probability it has property P and then multiply by the number of X s Probability of X of X with prop P with prop P total of X Probabilities and counting Say we want to count the number of X s with property P One way to do it is to ask if we pick an X at random what is the probability it has property P and then multiply by the number of X s Probability of X of X with prop P with prop P total 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 of 1 q P X with prop total of X …
View Full Document
Unlocking...