# Bounds for number of coin toss switches

I toss $n$ biased coins and I want to count the number of times you get a H followed by a T or a T followed by a H. I call these switches. So for example if I get HHTTHTHHHT then I have $5$ switches in total. If the coin gives H with prob $p$ and $T$ with prob $1-p$ then how can you find an approximation to the probability of getting at least $k$ switches for large $n$? I would also be interested in a Chernoff style tail bound.

Adjacent switch occurrences are not independent however non adjacent ones appear to be. The probability of having a switch at position $i+1$ given that there is a switch at position $i$ is exactly $1/2$, irrespective of $p$.

The mean number of switches is $\mu= (n-1)2p(1-p)$ and the variance is $2pq(2n−3−2pq(3n−5))$ where $q=(1-p)$.

The exact probability was given at http://math.stackexchange.com/questions/258221/probability-distribution-of-number-of-switches.

-

For the total number of switches, the central limit theorem and the large deviation principle are established. The detailed analysis based on two related generating functions is motivated from an analytic argument by the author a few years ago to the following neat fact mentioned by Persi Diaconis (who has a non-analytic argument): For independent random variables $X_i$ with $P(X_i=1)=1/i=1-P(X_i=0)$, $i \ge 1$, one has $\sum_{i=1}^\infty X_iX_{i+1}=^d \hbox{Poisson}(1).$