Bounds for number of coin toss switches

Question

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 https://math.stackexchange.com/questions/258221/probability-distribution-of-number-of-switches.

Answer 1

A "head" switch is a tail followed by a head, and a "tail'' switch is a head followed by a tail. Joint Laplace transform for the number of "head'' switches and "tail'' switches are given in the short note: On the Number of Switches in Unbiased Coin-tossing, http://www.math.udel.edu/~wli/papers/13-switches-sub.pdf

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). $

Answer 2

You can get a Chernoff style bound easily by considering the "even" and "odd" switches separately. The number of even (odd) switches is binomially distributed and you just use union bound and lose at most a factor of 2 in the bound.