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!
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} }
This problem is trickier than it looks.
Essentially you're doing a string matching problem. So one approach is to build a finite state automaton to recognise what you're interested in. In this case you want to recognise M heads with either an end of the sequence or a tail at each end. You now want to find the probability of ending in an accept state. This is now an elementary Markov chain problem. This formulation generalises straightforwardly to many related questions like finding the probability of exactly one streak, at least one streak, streaks of at least a given size and so on.
If you're interested in the behaviour as $N \to \infty$ for various $M$ and $p$ (possibly depending on $N$), then concentration results can give some information.
The basic tool is Azuma's inequality. Let $X$ be the number of streaks of length $M$ (that is, $M$ consecutive flips all of which come up heads—so longer streaks count multiple times). Changing any one flip changes $X$ by at most $M$, so $$ \mathbb{P}(|X - \mathbb{E}(X)| \geq t) \leq 2e^{-t^2/2M^2N}. $$ Now $\mathbb{E}(X) = (N-M+1)p^M$, so $X$ is concentrated around its mean (and in particular, is unlikely to be zero) provided that $M\sqrt N$ is small compared to $(N-M+1)p^M$.
See The Longest Run of Heads by Mark F. Schilling which gives a recursive formula for $\Pr (R_N\le M)$, whereas you are looking for $\Pr (R_N\le M) -\Pr (R_N\le M-1)$.
