Probability of a sequence of events occurring at least once in n trials Consider an unfair coin flipped $n$ times. What is the probability of the following sequence occuring at least once? (for example)
H T T H
Probability of H is 75%, T is 25%. Events are independent.
My attempts:
My limited understanding tells me that the probability of it occurring in general is $0.75 * 0.25 * 0.25 * 0.75 = 0.035$
Then I have seen a general formula for probability of event occurring at least x times in n trials in this answer.
But what about for a sequence? I considered treating the sequence as a single event, and the trials be defined as a multiple of the sequence size. I.e. if the sequence is 4 events long, and there are 20 trials, then consider it looking for the sequence-event in 20/4 = 5 trials. But this would seem to preclude the possibility of the sequence starting anywhere, not just on multiples of 4.
Am I missing something?
 A: Denote by $p(n)$ the probability alluded to in the question, then by $q_0(n):=1-p(n)$ the a priori probability that we don't see $HTTH$ in $n\geq0$ trials, then by $q_1(n)$, $q_2(n)$, and $q_3(n)$ the probability that we don't see $HTTH$ in $n$ trials, given that we already have $H$, $HT$, resp., $HTT\>$ "on the stack". Combine the $q_i(n)$  to the column vector ${\bf q}(n):=\bigl(q_i(n)\bigr)_{0\leq i\leq 3}$. The equations
$$\eqalign{
q_0(n)&={3\over4}q_1(n-1)+{1\over4}q_0(n-1)\cr
q_1(n)&={3\over4}q_1(n-1)+{1\over4}q_2(n-1)\cr
q_2(n)&={3\over4}q_1(n-1)+{1\over4}q_3(n-1)\cr
q_3(n)&={1\over4}q_0(n-1)\cr}$$
can then be condensed to
$${\bf q}(n)=\left[\matrix{{1\over4}&{3\over4}&0&0\cr
0&{3\over4}&{1\over4}&0\cr
0&{3\over4}&0&{1\over4}\cr
{1\over4}&0&0&0\cr}\right]\>{\bf q}(n-1)\ ,\tag{1}$$
and we have the initial condition ${\bf q}(0)=(1,1,1,1)=:{\bf 1}$. Unfortunately the matrix $A$ appearing here has undesirable eigenvalues. Therefore we aim at a recursion for the probabilities in question. These are the numbers
$$p(n)=1-q_0(n)=1-\bigl(A^n{\bf 1}\bigr)_0\qquad(n\geq0)\ .$$
From the general theory of $(1)$ it follows that the sequence $n\mapsto q(n):=q_0(n)$ satisfies a recursion of the form
$$q(n)=c_1 q(n-1)+c_2 q(n-2)+c_3 q(n-3)+ c_4 q(n-4)\ .$$
I let Mathematica compute ${\bf q}(n)$ up to $n=7$ and then computed the $c_i$ by solving a linear system, using the obtained data. In this way I obtained
$$q(n)= q(n-1)-{3\over64} q(n-3)+{3\over256} q(n-4)\ .$$
It follows that the $p(n)=1-q(n)$ satisfy the recursion
$$p(n)=0\qquad(0\leq n\leq 3)\ ,$$ $$p(n)=p(n-1)-{3\over64}p(n-3)+{3\over256}p(n-4)+{9\over256}\qquad(n\geq4)\ .$$
One then obtains the following values:
$$\bigl(p(n)\bigr)_{n\geq0}=\left(0, 0, 0, 0, {9\over256}, {9\over128}, {27\over256}, {2277\over16384}, {11223\over65536}, 
{13257\over65536}, {243441\over1048576},\ldots\right)\ .$$
A: This can be solved by approaching it as a Markov process with one final state of “$HTTH$ has been seen.” The process remains in that final state after any subsequent result. Let the states be as follows. States $0$ through $3$ also assume “game not over” ($HTTH$ not yet seen). The numbers represent “steps towards success.”
S0. Initial state, or after a last flip of $T$ that didn’t follow $H$ or $HT$.
S1. The last flip was $H$, but this $H$ did not complete the $HTTH$.
S2. The last two flips were $HT$.
S3. The last three flips were $HTT$.
S4. The last four flips were $HTTH$.
The transition probabilities are easy to calculate. Each state except the final state $S_4$ transitions to some state (you have to think out which one) with probability $0.25$ and another state with probability $0.75$. For example, if the current state is $S_2$ (just saw $HT$) and you flip $T$, you reach state $S_3$. If you flip $H$, you go back to state $S_1$.
As $S_4$ is a steady/final state, $S_4$ transitions to $S_4$ with probability $1$.
The full transition matrix is
$P=\left(
\begin{array}{ccccc}
 \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 \\
 0 & \frac{3}{4} & \frac{1}{4} & 0 & 0 \\
 0 & \frac{3}{4} & 0 & \frac{1}{4} & 0 \\
 \frac{1}{4} & 0 & 0 & 0 & \frac{3}{4} \\
 0 & 0 & 0 & 0 & 1 \\
\end{array}
\right)$
The probability $p_{HTTH}(n)$ of ending up in state $S_4$ after exactly $n$ steps starting from state $S_0$ equals (this is a straightforward Markov process result) the $ij$-th entry of $P^n$.
I can’t find a closed form for $p_{HTTH}(n)$, but the first few values (calculated with Mathematica) are
$\frac{0}{4},\frac{0}{16},\frac{0}{64},\frac{9}{256},\frac{72}{1024},\frac{432}{4096},\frac{2277}{16384},\frac{11223}{65536},\frac{53028}{262144},\frac{243441}{1048576}$.
I’ve shown each $p_{HTTH}(n)$ as a fraction with denominator $4^n$, which seems to be what the denominator would be for a closed form. I can’t see a closed form, and the sequence of numerators doesn’t show up from an OEIS search. 
