How many coin flips would it take to have a 90% chance of flipping 3 heads in a row? If you were to flip a fair coin independently over and over, hoping to get 3 heads in a row, how many coin flips would it take for you to have a 90+% chance of having succeeded?
The way I've been thinking about this problem is as a Markov Chain with states: 0, 1, 2, and 3 heads in a row, where 3 is the absorptive state.

The transition matrix T is:
$$T=\begin{bmatrix}0.5&0.5&0&0\\0.5&0&0.5&0\\0.5&0&0&0.5\\0&0&0&1\end{bmatrix}$$
So roughly, what I'd like to be able to do is solve for n in the following equation  (let $k_1, k_2$, and $k_3$ be arbitrary constants):
$$\begin{bmatrix}1&0&0&0\end{bmatrix}*T^n =\begin{bmatrix}k_1&k_2&k_3&0.9\end{bmatrix}$$
Through trial and error on the calculator, I can figure out that [1 0 0 0]$*T^{30}\approx$ [0.050 0.027 0.014 0.908].
However, I'd like to be able to do this in a systematic way that could be applied to other Markov Chains, but I'm not sure how. Thanks for any help!
 A: What you're doing sounds pretty systematic to me. If $n$ is the number of states then it'll take you $O(n^3)$ time to do one matrix multiplication, so $O(\log(e)n^3)$ to compute a matrix power $T^e$. Thus binary searching over all powers up to $P$ to find the smallest power that works will cost $O(\log(P) \log(e) n^3)$ which is totally manageable for many Markov chains.
If you have some goals that are not fulfilled by this algorithm, you should explain what those goals are so you can get better answers. For example, if you need to answer this question for MCs with 100k+ states then you should specify that in the question or even ask a new question and specify there.
A: Let $C_n=$ number of sequences of $n$ tosses with at least $3$ consecutive heads.
We have $C_0=C_1=C_2=0$, and $C_3=1$.
For $n\ge4$, we have $C_n=2C_{n-1}+2^{n-4}-C_{n-4}$.
Explanation:
$2C_{n-1}=$ number of sequences of $n$ tosses with $3$ consecutive heads before last toss (last toss is either heads or tails).
$2^{n-4}-C_{n-4}=$ number of sequences of $n$ tosses with $3$ consecutive heads for the first time with the last toss (last $4$ results are $THHH$, and before that there were no $3$ consecutive heads).
We require $\dfrac{C_n}{2^n}\ge0.9$. Using excel, we find that $n_{\text{min}}=30$.
A: If you can find matrixes $P$ and $D$ such that $T=PDP^{-1}$, then by induction $T^n=PD^nP^{-1}$ (the base case $n=1$ is trivial, then if we have the induction hypothesis $T^{n-1}=PD^{n-1}P^{-1}$, it follows that $T^n = T(T^{n-1})=PDP^{-1}PD^{n-1}P^{-1}$, and that easily simplifies to $PD^nP^{-1}$). If $D$ is diagonal, i.e. all non-diagonal entries are zero, and diagonal entries are $\lambda_i$, then $D^n$ is easily calculated as having diagonal entries $\lambda_i^n$. $T$ and $D$ are similar, so they have the same eigenvalue spectrum, so the $\lambda_i$ are simply the eigenvalues of $T$. $P$ is given by the eigenvectors that correspond to each eigenvalue.
I found a calculator for diagonalizing matrices. Not all Markov chains can be diagonalized, so in some cases you have to use the Jordan Canonical Form.
In practice, though, it's often simpler to just calculate directly. You can calculate $T^{2^k}$ for integers $k$ until you get a value that's too large (just square the previous matrix to get the next one, i.e. $T^{2^{k+1}}=(T^{2^k})^2$), then do a binary search.
