Great Theoretical Ideas In Computer Science Steven Rudich Anupam Gupta Lecture 20 March 24 2005 CS 15 251 Spring 2005 Carnegie Mellon University Probability Theory Counting in Terms of Proportions A Probability Distribution Proportio n of MALES 75 of the male population 50 of the male population 50 of the male population 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 Mean As the number of elements gets larger the shape of the unbiased binomial distribution converges to a Normal or Gaussian distribution 2m m t 2m m 2 m t e 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 Again a Normal or Gaussian distribution Let s look after n steps 50 of time p 2 n 3 Again a Normal or Gaussian distribution Let s look after n steps 68 of time p n Again a Normal or Gaussian distribution Let s look after n steps 95 of time p 2 n Again a Normal or Gaussian distribution Let s look after n steps 99 7 of time p 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 of X with prop P Probability of X 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 1 q of X with prop P total of Probability …
View Full Document
Unlocking...