Getting at least $k$ heads in a row $l$ times over after at most $m$ flips.

Question

In the spirit of this question where we calculated the probability of at least once having gotten at least $k$ heads after $n$ coin tosses.

How would we go about calculating the probability of having gotten at least $k$ heads in a row $l$ times over after $m$ flips. What ideas or techniques can we utilize to make it easy to generalize this? I am more interested in description of the tools and techniques one can use than the actual answer.

Examples:

2 times 2 heads in a row

$HTH{\bf H}TTTH{\bf H} \leftarrow$ first time becomes true here.

2 times 3 heads in a row:

$HTHH{\bf H}THHTTHH{\bf H} \leftarrow$ first time becomes true here.

Answer 1

Let's take a look at a minimal example:

$$P = \frac 1 2\left[\begin{array}{ccc|ccc} 2&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&1&1&\color{red} 2&0&0\\\hline 0&0&0&\color{red} \uparrow&1&0\\ 0&0&0&0&0&1\\ 0&0&0&0&1&1 \end{array}\right]$$

1. Basic "building blocks" as in the answer here on the "diagonal" we can easily implement with Kronecker product with $\bf I$, the "storage states" are the 2s.
2. Now let but the upper leftmost block have storage state displaced 1 row to the block above.
3. This way each displacement will slow down (1 lower exponent than the previous part of the chain).

Any elegant way to avoid the displacement latency will be welcome!

Crazy checker (first time we get non-zero prob for 1 and 2 resp): $${\bf v} = \left[\begin{array}{cccccc}0&0&0&0&0&1\end{array}\right]^T$$ $${\bf P}^2{\bf v} = \left[\begin{array}{cccccc} 0&0&0&0.25&0.25&0.5\end{array}\right]^T\\{\bf P}^5{\bf v} = \left[\begin{array}{cccccc}0.0625&0.125&0.3125&0.09375&0.15625&0.25\end{array}\right]^T$$

The chance for 2 heads in a row is $1/4 = 0.25$ The chance for 4 heads in a row is $1/16 = 0.0625$

So assuming $H{\bf H}H{\bf H}$ counts as two heads in a row twice then the solution works!

We can also calculate the probability of not having any two H in a row in a string of 2 and 5 respectively, and if we do, we do indeed get the sum of the two last states: $$1-\frac 1 4\approx 0.25+0.5 = 0.75 \\ 1-\frac {19}{32} \approx 0.15625+0.25= 0.40625$$

The systematic construction of matrices for arbitrary $k,l,m$ should now be obvious.