I'm trying to solve the following problem:
Let's say I'm tossing a coin $N$ times. The coin is not fair, such that the probability for heads is $p_0$ and for tails is $1-p_0$.
What is the probability to have a streak of $M$ heads?
I would be most thankful if anyone can help me find a solution to this problem.
I could also use the solution for the case when the coin is fair, or for a streak of at least $M$, and not exactly $M$.
Thanks!
Best Answer
The survey: ENUMERATION OF STRINGS by A. M. Odlyzko, available at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.5995&rep=rep1&type=pdf
gives an answer for a fair coin, I think, for it gives the number of $n$ letters long words avoiding a given pattern, thus the probability that a streak longer than $M-1$ heads is avoided.
In the companion paper: String overlaps, pattern matching, and nontransitive games, L.J Guibas, A.M Odlyzko, http://dx.doi.org/10.1016/0097-3165(81)90005-4, the generating function for the probability in the biased case is given, in Section 3. This paper being cited 300 times according to Google Scholar, I guess that closed form expressions or at least precise asymptotics have been derived since the eighties, but digging the bibliography should provide some answers ...
I also found a recent book in which Ch. 2 is devoted to this question : @book{balakrishnan2011runs, title={Runs and scans with applications}, author={Balakrishnan, Narayanaswamy and Koutras, Markos V}, volume={764}, year={2011}, publisher={John Wiley \& Sons} }