probability question related to pattern in coin tossing If I toss a fair coin $n$ times, calculate the probability that no pattern HHTHTHH occurs.
 A: Construct a deterministic finite automaton which detects the regular expression $.*(HHTHTHH).*$ such that the sole accepting state $A$ always transitions to a state $B$, which always transitions to itself. The starting state is $S$.
This is basically a directed graph and we can find the transition matrix $P$, each row of which gives the probabilities of getting from one state (i.e. vertex) corresponding to that row, to the next states (one vertex corresponding to each column).
You basically need the entries corresponding to starting state $S$ and ending state $A$, from each of $P, P^2,  P^3, \dots , P^n$ and add them up to get the probability that the pattern $HHTHTHH$ occurs (or more simply the $(S,B)$ entry of $P^{n+1}$ will do). Subtract that from $1$ and you are done.
The $(S,A)$ entry of $P^k$ gives the probability that we find the pattern exactly at the end of $k$ tosses, and no tosses before that.
A: I don't know about exact solution, but numeric approximation is $P(n)=1-e^{-\frac{n}{125}}$.

Matlab\Octave Code
function test_script_1()
x=7:30:600;
y=tsh([],5000,7:30:600);
er=@(p)sum(((p(1)+p(2)*exp(p(3)*x/500))-y).^2);
an=fminsearch(er,[0,0,0]);
anr=round(an);
disp(anr);
plot(x,y,x,anr(1)+anr(2)*exp(anr(3)*x));
legend('calculated','1-e^{-x/125}',4)
end
function result=tsh(a,b,n)
% HHTHTHH (H -> 1 , T -> 0)
if isempty(a)
    a=logical([1 1 0 1 0 1 1]);
end
if isempty(b)
    b=1000;
end
if isempty(n)
    n=100;
end
if any(size(n)>1)
    result=zeros(size(n));
    for pa=1:length(n)
        result(pa)=test_script_1(a,b,n(pa));        
    end
    return
end
la=length(a);
t=false(1,b);
for i=1:b
    v=raspr(0,1,n);
    for j=1:n
        if all(a==v(j:j+la-1))
            t(i)=true;
            break
        end
    end
end
result=nnz(t)/b;
end
function resu=raspr(a1,b1,s)
resu=round((b1-a1+1)*rand(1,s)+a1-0.5);
end

Somebody know why is that?
