I'm wondering if there is a nice solution for this problem. As stated, I flip a coin $n$ times, and want the probability of a run of 3 (or more) heads appearing within it. For example, if I toss a coin 9 times, an example that would include a run of 3 heads is TTHHHTHTH, as is THTHHHHHT, but TTHHTHTTH is not.
Generalisations to runs of $m$ (or more) heads also welcome!
On
The time $T_{m+1}$ needed to get a run of $m+1$ heads is $$T_{m+1}=T_m+1$$ with probability $p_H=\frac12$ and $$T_{m+1}=T_m+1+T'_{m+1}$$ with probability $p_T=1-p_H=\frac12$, where $T'_{m+1}$ is distributed like $T_{m+1}$ and independent of $T_m$.
Thus, the generating functions $g_m(s)=E(s^{T_m})$ are such that
$$g_{m+1}(s)=\frac12s(g_m(s)+g_m(s)g_{m+1}(s))\tag{$\ast$}$$
From there, the solution is standard. First, $(\ast)$ can be rewritten as $$g_{m+1}(s)=\frac{sg_m(s)}{2-sg_m(s)}$$ hence $$\frac1{g_{m+1}(s)}-\frac{s}{2-s}=\frac2s\left(\frac1{g_m(s)}-\frac{s}{2-s}\right)$$ that is, using $g_0(s)=1$,$$\frac1{g_m(s)}=\left(\frac2s\right)^m\left(1-\frac{s}{2-s}\right)+\frac{s}{2-s}$$ from which every $g_m(s)$ follows as
$$g_m(s)=\frac{s^m(2-s)}{2^{m+1}(1-s)+s^{m+1}}$$
For example, for $m=1$, $$g_1(s)=\frac{s^2}{2-s}$$ that is, $T_1$ is a shifted geometric random variable. More generally, recall that each function $g_m$ fully encodes the distribution of $T_m$ since, by definition, $$g_m(s)=\sum_{k=0}^\infty P(T_m=k)s^k$$ thus, expanding $g_m(s)$ as a power series yields every $P(T_m=k)$. If one is interested to observe a run of length $m$ during the $k$ first draws, one would simply compute $$P(T_m\leqslant k)$$
On
If you toss a coin $n$ times, there are $2^n$ possible outcomes, each of which has probability $1/2^n$ of occurring.
The number of favorable outcomes is found by subtracting those outcomes in which three consecutive heads do not occur from the total number of outcomes.
Let $a_n$ be the number of sequences of length $n$ which do not contain three consecutive heads. Since it is not possible for three consecutive heads to occur until the coin has been tossed three times, $a_1 = 2$ and $a_2 = 4$. Since the only outcome in which three consecutive heads occurs when the coin is tossed three times is HHH, $a_3 = 2^3 - 1 = 7$.
We write a recurrence relation for the number of sequences of length $n$ that do not contain three consecutive heads. We condition based on the most recent occurrence of tails. The most recent occurrence of tails must occur in one of the last three positions, otherwise we would have three consecutive heads.
Hence, the number of sequences of length $n$ that do not contain three consecutive heads satisfy the recurrence relation $$a_n = a_{n - 1} + a_{n - 2} + a_{n - 3}, n \geq 4$$ Thus, the number of sequences of length $n$ that do not contain three consecutive heads is given by the recursion \begin{align*} a_1 & = 2\\ a_2 & = 4\\ a_3 & = 7\\ a_n & = a_{n - 1} + a_{n - 2} + a_{n - 3}, n \geq 4 \end{align*} This is oeisA000073.
The desired probability is then $$\Pr(\text{contains run of three consecutive heads}) = \frac{2^n - a_n}{2^n} = 1 - \frac{a_n}{2^n}$$
Let $H_m$ be the event that the $m$th toss is heads. Then 3 heads is $$A_m := H_m \cap H_{m+1} \cap H_{m+2}$$
where $m = 1$ to $n-2$. Thus, by inclusion-exclusion, a probability of a run of 3 heads is
$$P(\bigcup_{k=1}^{n-2} \bigcap_{i=0}^2 H_{k+i}) = P(\bigcup_{k=1}^{n-2} A_k)$$
$$ = \sum_{i=1}^{n-2} P(A_i) - \sum_{1 \le i < j \le n-2} P(A_i \cap A_j) + \sum_{1 \le i < j < k \le n-2} P(A_i \cap A_j \cap A_k)$$
Now, $P(A_i \cap A_j \cap A_k) = 0$ unless $i+2=j+1=k$ in which case we have $P(A_i \cap A_j \cap A_k) = P(H_k)$
Similarly, $P(A_i \cap A_j) = 0$ unless $i+1=j$ or $i+2=j$ in which cases we respectively have $P(A_i \cap A_j) = P(H_j \cap H_{j+1})$ and $P(A_i \cap A_j) = P(H_j)$