Question

We keep tossing a fair coin n = 106 million times, write down the outcomes: it gives a Heads-and-Tails-sequence of length n. We call an integer i special, if the i, i + 1, i + 2, i + 3, . . . , i + 18-th elements of the sequence are all Heads. That is, we have a block of 19 consecutive Heads starting with the i-th element of the sequence. Let X denote the number of special integers i. What is the expected value of X? I also want the numerical value.

Answer 1

Let be the indicator random variable that takes the value 1 if the ith coin is the first coin in a sequence of 19 consecutive heads.

For any sequence of length 19, the starting coin can be from toss ,

such that is between and

Thus the number of such sequences is

                                                               

The expected number of such sequences is

                                                               

                                                                                       by linearity of expectation

Now the expectation for to be a sequence of k heads is

                                                            

(since each toss is independent, expectations can be multiplied and expectation of each coin turning a head is 1/2)

Thus

The expected number of such sequences is

                                                               

                                                               

                                                               

Now substitute n = 106 million

we get the expected number of such sequences is