Let's say we flip a coin $N=100$ times and get "HTHTHTHHHTHHHHTTHTT...HHT". What is the probability that se letter combination "HHHHH" occurs at least once in this string of $100$ letters? If not a precise formula then the best approximation for $N \to \infty$. I find it to be approximately:
$$1-\text{BinomPdf}(N/2,\,(1/2)^5,\,0) \, .$$
There are some useful approximations given in related questions here and here. However, in the case of a string of heads it is possible to obtain an exact answer quite easily using Markov chains.
Exact probability via Markov chain: Consider a discrete sequence of coin tosses $\{ x_n | n \in \mathbb{N} \}$. For a given value of $n$, let $\mathscr{W}$ be the event that five consecutive heads have occurred in the finite chain, and let $\mathscr{H}_k$ be the event that the last $k$ coin tosses were heads (and the one before that was not a head). We use these events to give the following partition of six possible states of interest:
$$\begin{matrix} \text{State 0} & & & \bar{\mathscr{W}} \cap \mathscr{H_0}, \\[6pt] \text{State 1} & & & \bar{\mathscr{W}} \cap \mathscr{H_1}, \\[6pt] \text{State 2} & & & \bar{\mathscr{W}} \cap \mathscr{H_2}, \\[6pt] \text{State 3} & & & \bar{\mathscr{W}} \cap \mathscr{H_3}, \\[6pt] \text{State 4} & & & \bar{\mathscr{W}} \cap \mathscr{H_4}, \\[6pt] \text{State 5} & & & \mathscr{W}. \quad \quad \text{ } \text{ } \\[6pt] \end{matrix}$$
Now, assume that the sequence of coin-tosses is exchangeable and let $\theta$ be the probability of a head on a single toss. Your process can be represented as a discrete-time Markov chains that begins in $\text{State 0}$ at $n=0$ and transitions according to the probability matrix:
$$\mathbf{P} = \begin{bmatrix} 1-\theta & \theta & 0 & 0 & 0 & 0 \\[6pt] 1-\theta & 0 & \theta & 0 & 0 & 0 \\[6pt] 1-\theta & 0 & 0 & \theta & 0 & 0 \\[6pt] 1-\theta & 0 & 0 & 0 & \theta & 0 \\[6pt] 1-\theta & 0 & 0 & 0 & 0 & \theta \\[6pt] 0 & 0 & 0 & 0 & 0 & 1 \\[6pt] \end{bmatrix}.$$
The last state is an absorbing state which represents the case where the chain has produced a run of five consecutive heads. For a given value of $n$ the probability of a run of five consecutive heads in the chain is $\mathbb{P}(\mathscr{W} | n) = \{ \mathbf{P}^n \}_{0,5}$. (This probability is zero for all $n <5$ as expected.)
Programming this in R: You can program this as a function in R using the code below. This code has been vectorised to generate an array of powers of the transition matrix for a finite sequence of coin tosses. It also allows you to put in a probability of a single head, so it is not restricted to the case of a fair coin.
#Create function to give n-step transition matrix for n = 1...N
#t is the probability of a head
#N is the last value of n
PROB <- function(N, t) { P <- matrix(c(1-t, t, 0, 0, 0, 0,
1-t, 0, t, 0, 0, 0,
1-t, 0, 0, t, 0, 0,
1-t, 0, 0, 0, t, 0,
1-t, 0, 0, 0, 0, t,
0, 0, 0, 0, 0, 1),
nrow = 6, ncol = 6,
byrow = TRUE);
PPP <- array(0, dim = c(6,6,N));
PPP[,,1] <- P;
for (n in 2:N) { PPP[,,n] <- PPP[,,n-1] %*% P; }
PPP }
#Calculate probability for N = 100 for fair coin
N <- 100;
t <- 0.5;
PROB(N,t)[1,6,N];
[1] 0.8101096
As you can see from this calculation, the probability of getting a string of five consecutive heads in $n=100$ tosses of a fair coin is $0.810196$ (i.e., it will happen a little over one-fifth of the time). This calculation was extremely rapid using the above vectorised code for the Markov chain.
Showing the probability as a function of $n$: It is quite simple and fast to calculate this probability for any given $n$ and so we can easily generate a series of probabilities and show the probability of the event of interest as $n$ increases. The following R code and resulting plot show the probability increasing as we increase the number of coin tosses. We also plot a red dashed line showing the approximation function suggested by Martijn Weterings in the comment below. This shows that the approximation is reasonably close to the true probability curve.
library(ggplot2);
#Create approximation function
APPROX <- rep(0,N);
for (n in 1:N) APPROX[n] <- 1 - (1-t^5/(1+t+t^2+t^3+t^4))^n;
#Create data frame of probabilities up to N
N <- 300;
PPP <- PROB(N,t)[1,6,];
DF <- data.frame(n = 1:N, Probability = PPP, Approx = APPROX);
#Plot probability as a function of n
FIGURE <- ggplot(data = DF, aes(x = n, y = Probability)) +
geom_line(size = 1) +
geom_line(aes(y = Approx, colour = 'red'), size = 1, linetype = 'dashed') +
theme(legend.position="none") +
ggtitle("Probability of Five Consecutive Heads (Fair Coin)") +
xlab("Number of Tosses") + ylab("Probability");
FIGURE;
Just for fun:
substr_prob <- function(flips, string, iter, seed) {
out <- sapply(1:iter, function(zzz) {
result <- paste(sample(c("H", "T"), flips, TRUE), collapse = "")
grepl(string, result, fixed = TRUE)
})
return(mean(out))
}
> substr_prob(flips = 100, string = "HHHHH", iter = 10000, seed = 1839)
[1] 0.8084
Technically slow due to using strings and whatnot, but it still takes under a second to run and is user friendly.
