Q. 4.24

Question

Here is another way to obtain a set of recursive equations for determining $P_{n}$ , the probability that there is a string of $k$ consecutive heads in a sequence of $n$ flips of a fair coin that comes up heads with probability $p$ :

(a) Argue that for $k < n$ , there will be a string of $k$ consecutive heads if either

1. there is a string of $k$ consecutive heads within the first $n - 1$ flips, or

2. there is no string of $k$ consecutive heads within the first $n - k - 1$ flips, flip $n - k$ is a tail, and flips $n - k + 1, \dots, n$ are all heads.

(b) Using the preceding, relate $P_{n} t o P_{n - 1}$ . Starting with $P_{k} = p^{k}$ , the recursion can be used to obtain $P_{k + 1}$ , then $P_{k + 2}$ , and so on, up to $P_{n}$ .

Step-by-Step Solution

Verified

Answer

(a) 1 The probability for this case is $P_{n - 1}$ .

2 we have not obtained $k$ consecutive heads.

(b) $P_{n} = P_{n - 1} + (1 - p) \cdot (1 - P_{n - k - 1}) \cdot p^{k}$

1Step 1: Given information Part (a)

We found that there is another way to obtain a set of recursive equations for determining $P_{n}$ , the probability that there is a string of $k$ consecutive heads in a sequence of $n$ flips of a fair coin that comes up heads with probability $p$ .

2Step 2: Explanation Part (a)

Let's condition on what happens with the last $k$ flips. We have two options

There has been obtained $k$ consecutive Heads within first $n - 1$ flips. That means that we are not interested what happens in the last trial (the probability l), so the probability for this case is $P_{n - 1}$ .

Suppose that we have obtained $k$ consecutive Heads in the last $k$ flips. That means that in $n - k - 1$ st flip we had to have tail and that in the first $n - k - 1$ flips we have not obtained $k$ consecutive heads.