What are the odds that a run of one H or T (i.e., THT or HTH) will occur in n flips of a fair coin?

References:
    John P. Robinson, Transition Count and Syndrome are Uncorrelated, IEEE
    Transactions on Information Theory, Jan 1988.

First we define a function or enumerator P(n,k) as the number of length
"n" sequences that generate "k" successes.  For example,

     P(4,1)= 4  (HHTH, HTHH, TTHT, and THTT are 4 possible length 4 sequences).

I derived two generating functions g(x) and h(x) in order to enumerate
P(n,k), they are compactly represented by the following matrix
polynomial.


            _    _      _     _           _   _
           | g(x) |    | 1   1 | (n-3)   |  4  |
           |      | =  |       |         |     | 
           | h(x) |    | 1   x |         |2+2x |    
           |_    _|    |_     _|         |_   _|

The above is expressed as matrix generating function.  It can be shown
that P(n,k) is the coefficient of the x^k in the polynomial
(g(x)+h(x)).

For example, if n=4 we get (g(x)+h(x)) from the matrix generating
function as (10+4x+2x^2).  Clearly, P(4,1) (coefficient of x) is 4 and
P(4,2)=2 ( There are two such sequences THTH, and HTHT).

We can show that

   mean(k) = (n-2)/4 and sd= square_root(5n-12)/4

We need to generate "n" samples. This can be done by using sequences of length
(n+2).  Then our new statistics would be

   mean = n/4

   sd = square_root(5n-2)/4

Similar approach can be followed for higher dimensional cases.