Branch: : Aeronautical EngineeringSend Friend Request
Suppose you flip a fair coin n times. What is the longest streak of consecutive heads that you expect to see? The answer is Θ(lg n), as the following analysis shows.
We first prove that the expected length of the longest streak of heads is O(lg n). The probability that each coin flip is a head is 1/2. Let Aik be the event that a streak of heads of length at least k begins with the ith coin flip or, more precisely, the event that the k consecutive coin flips i, i 1, ..., i k - 1 yield only heads, where 1 ≤ k ≤ n and 1 ≤ i ≤ n -k 1. Since coin flips are mutually independent, for any given event Aik, the probability that all k flips are heads is
- Heaps in Design and analysis of algorithms free notes
- Analysis of quicksort in Design and analysis of algorithms free notes
- Overview of Recurrences in Design and analysis of algorithms free notes
- Probabilistic analysis and further uses of indicator random variables in Design and analysis of algorithms free notes
- Analysis of insertion sort in Design and analysis of algorithms free pdf notes