Probability Theory: Counting in Terms of Proportions A Probability DistributionThe Descendants Of AdamUnbiased Binomial Distribution On n+1 Elements.As the number of elements gets larger, the shape of the unbiased binomial distribution converges to a Normal (or Gaussian) diAs the number of elements gets larger, the shape of the unbiased binomial distribution converges to a Normal (or Gaussian) diGalton’s Quincunx MachineAgain, a Normal or Gaussian distribution! Let’s look after n stepsAgain, a Normal or Gaussian distribution! Let’s look after n stepsAgain, a Normal or Gaussian distribution! Let’s look after n stepsAgain, a Normal or Gaussian distribution! Let’s look after n stepsProbabilities and countingProbabilities and countingHow many n-bit strings have an even number of 1’s?How many n-trit strings have even number of 0’s?Some puzzlesActually, 6 and 7 are equally likelyAnother viewSo, sometimes, probabilities can be counter-intuitiveLanguage Of ProbabilityFinite Probability DistributionFinite Probability DistributionSample spaceProbabilityProbability DistributionEventsEventsEventsUniform DistributionUniform DistributionUniform DistributionUsing the LanguageUsing the Language: visuallyUsing the LanguagePictureUsing the LanguageMore Language Of ProbabilityAnother way to calculate Birthday probability Pr(no collision)Independence!Independence!Independence!Monty Hall problemMonty Hall problemwhy was this tricky?Probability Theory:Counting in Terms of Proportions Great Theoretical Ideas In Computer ScienceJohn Lafferty CS 15-251 Fall 2006Lecture 9 September 26 2006 Carnegie Mellon UniversityA Probability DistributionHEIGHTProportion of MALES50% of the male population75% of the male population50% of the male populationThe Descendants Of AdamAdam was X inches tall.He had two sonsOne was X+1 inches tallOne was X-1 inches tallEach of his sons had two sons …XX-1X+111X-2X+2XX-3X+3X-1 X+1X-4X+4X-2X+2X156655101015201X-1X+111X-2X+2XX-3X+3X-1 X+1X-4X+4X-2X+2X1566551010152011111X-2X+2XX-3X+3X-1 X+1X-4X+4X-2X+2X1566551010152011111112X-3X+3X-1 X+1X-4X+4X-2X+2X1566551010152011111112113 3X-4X+4X-2X+2X1566551010152011111112113 3114461566551010152011111112113 31144615665510101520In nthgeneration, there will be 2nmales, each with one of n+1 different heights: h0< h1< . . .< hn.hi= (X – n + 2i) occurs with proportionUnbiased Binomial Distribution On n+1 Elements.Let S be any set {h0, h1, …, hn} where each element hihas an associated probabilityAny 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.MeanAs the number of elements gets larger, the shape of the unbiased binomial distribution converges to a Normal(or Gaussian) distribution.11446Coin Flipping in ManhattanAt each step, we flip a coin to decide which way to go.Avenue i and Street (n-i) after n steps?What is the probability of ending at the intersection of11446Coin Flipping in ManhattanAt each step, we flip a coin to decide which way to go.Avenue i and Street (n-i) after n steps?What is the probability of ending at the intersection ofCoin Flipping in ManhattanAt each step, we flip a coin to decide which way to go.Avenue i and Street (n-i) after n steps?What is the probability of ending at the intersection of11446Coin Flipping in ManhattanAt each step, we flip a coin to decide which way to go.Avenue i and Street (n-i) after n steps?What is the probability of ending at the intersection of11446Coin Flipping in ManhattanAt each step, we flip a coin to decide which way to go.Avenue i and Street (n-i) after n steps?What is the probability of ending at the intersection of11446Coin Flipping in Manhattan2ndifferent paths to level n, each equally likely. The probability of i heads occurring on the path we generate is:11446n-step Random Walk on a lineStart 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: 11446n-step Random Walk on a lineStart 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: 11446n-step Random Walk on a lineStart 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: 11446n-step Random Walk on a lineStart 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: 11446n-step Random Walk on a lineStart 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: 11446Galton’s Quincunx MachineAgain, a Normal or Gaussian distribution!Let’s look after n steps23√n50% oftimeAgain, a Normal or Gaussian distribution!Let’s look after n steps68% oftime√nAgain, a Normal or Gaussian distribution!Let’s look after n steps95% oftime2√nAgain, a Normal or Gaussian distribution!Let’s look after n steps99.7% oftime3√nProbabilities and Countingare intimately related ideas…Probabilities and countingSay 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)(total # of X)Probability of X with prop. P =Probabilities and countingSay 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)(total # of X)Probability of X with prop. P =×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 X)Probability of X with prop. P =×11446Binomial distribution with bias p Start at the top. At each step,
View Full Document