## The coin tossing problem

Submitted by plusadmin on January 1, 1998January 1998

Imagine an infinite sequence of coin tosses, and suppose you win a penny every time there is a sequence of *k* heads in a row followed by a tail (in other words, at every occurrence of the sequence HHH...HT of *k* heads followed by a tail). If *k* is large then you will not win pennies very often, but you will certainly win some sooner or later.

How many pennies are you likely to win in the first *n* tosses of the coin?