6.042/18.] Mathematics for Computer Science May12,2005 Srini devadas and Eric Lehman Lecture notes Special Topics 1 Streaks someone tapping the H and t keys in a what felt like a random way?0 Nas the table of H's and T's below generated by flipping a fair coin 100 times, or by HTTTHTHTTHTTHTHTHTHT TTTHHTHHTHTHTTHHATHT HHTHHTTTHHATHTTHHHHT THTTHATHTHTATHTTHTHH HTTHHHTHTHHHTHTHHHTH There is no way to be sure. However, this sequence has a distinctive feature that is com- mon in"random"human-generated sequences and unusual in truly random sequences namely, there is no long streak of H's or Ts. In fact, no symbol appears above more than four times in a row. How likely is that? If we flip a fair coin 100 times, what is the probability that we never get five heads in a row? 1.1 From a Probability Problem to a Counting Problem The sample space for this experiment is (H, r)o0; that is, the set of all length-100 se- quences of H's and Ts. If the coin tosses are fair and independent, then all 2 o such se- quences are equally likely. Therefore, we need only count the number of sequences with no streak of five heads; given that, the probability that a random length-100 sequence contains no such streak is: Pr(sequence has no HHHHH) t sequences with no HHHHH This is a common situation. We have reduced a probability problem to a counting problem. Unfortunatley, we have no hope of solving the counting problem by direct computation. No computer can consider all 2100 sequences of H's and T's, keeping track of how many lack a streak of five heads. But, on the bright side, there is a big bag of mathematical tricks for solving counting problems. In this case, we'll use a recurrence equation. The recurrence equation approach involves two steps6.042/18.062J Mathematics for Computer Science May 12, 2005 Srini Devadas and Eric Lehman Lecture Notes Special Topics 1 Streaks Was the table of H’s and T’s below generated by flipping a fair coin 100 times, or by someone tapping the H and T keys in a what felt like a random way? HTTTHTHTTHTTHTHTHTHT TTTHHTHHTHTHTTHHHTHT HHTHHTTTHHHTHTTHHHHT THTTHHTHTHTHTHTTHTHH HTTHHHTHTHHHTHTHHHTH There is no way to be sure. However, this sequence has a distinctive feature that is com￾mon in “random” human-generated sequences and unusual in truly random sequences: namely, there is no long streak of H’s or T’s. In fact, no symbol appears above more than four times in a row. How likely is that? If we flip a fair coin 100 times, what is the probability that we never get five heads in a row? 1.1 From a Probability Problem to a Counting Problem The sample space for this experiment is {H,T} 100; that is, the set of all length-100 se￾quences of H’s and T’s. If the coin tosses are fair and independent, then all 2 100 such se￾quences are equally likely. Therefore, we need only count the number of sequences with no streak of five heads; given that, the probability that a random length-100 sequence contains no such streak is: Pr (sequence has no HHHHH) = # sequences with no HHHHH 2 100 This is a common situation. We have reduced a probability problem to a counting problem. Unfortunatley, we have no hope of solving the counting problem by direct computation. No computer can consider all 2 100 sequences of H’s and T’s, keeping track of how many lack a streak of five heads. But, on the bright side, there is a big bag of mathematical tricks for solving counting problems. In this case, we’ll use a recurrence equation. The recurrence equation approach involves two steps: