MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 3 down vote accepted

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,

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

share|cite|improve this answer

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.

share|cite|improve this answer
@OriGurel-Gurevich Chernoff will give me an upper bound on the probability of being some distance from the mean. Is it also possible to get a similar lower bound on the probability? – Anush Dec 16 '12 at 9:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.