Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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 what is the probability of getting at least $k$ switches?

Update. joriki has given an exact answer. Is there a Chernoff type bound one can get to see if the number of switches is far from the mean? The mean number of switches is $\mu= (n-1)2p(1-p)$, I think.

share|cite|improve this question
Regarding the update - let $q=1-p$. The mean is $2(n-1)pq$, as you noticed, and the variance is $(n-1)2pq(1-2pq)+2(n-2)pq(1-4pq)=2pq(2n-3-2pq(3n-5))$. This might help get some heuristic. – Ofir Dec 14 '12 at 19:52
The Chernoff bound requires independence -- the occurrences of switches aren't independent, since successive potential switches share a common toss and the toss result is more likely to be the less likely result if a switch occurs than on average. You can use Ofir's calculation of the variance to apply Chebyshev's inequality, though. – joriki Dec 15 '12 at 20:54
up vote 3 down vote accepted

If there are $k$ switches, there are $k+1$ stretches of constant results. If $k+1=2l$, then $l$ of these are heads and $l$ are tails. There are anywhere from $l$ to $n-l$ heads in total, and likewise for tails. There are $\binom{j-1}{l-1}$ different ways of distributing $j$ heads or tails over $l$ stretches with each stretch containing at least one. We also need a factor of $2$ because we can start with either heads or tails. Thus the probability for an odd number $k=2l-1$ of switches is

$$ 2\sum_{j=l}^{n-l}\binom{j-1}{l-1}\binom{n-j-1}{l-1}p^j(1-p)^{n-j}\;, $$

where $l$ lies in the range $1\le l\le\lfloor n/2\rfloor$.

For an even number $k=2l$ of switches, there is one more stretch of the kind that we start out with, and the corresponding probability is

$$ \sum_{j=l}^{n-l-1}\binom{j-1}{l-1}\binom{n-j-1}l\left(p^j(1-p)^{n-j}+p^{n-j}(1-p)^j\right)\;, $$

where $l$ lies in the range $0\le l\le\lfloor(n-1)/2\rfloor$. For the probability of getting at least $m$ switches you just need to add these probablities for all $k\ge m$.

share|cite|improve this answer
Thanks. This seems hard to reason with though. Is there a Chernoff type bound one can apply here? – Anush Dec 14 '12 at 19:10

Let $f(n,k,p)$ be the probability that during $n$ tosses there are exactly $k$ switches, and that the last result is $H$ (where $p$ is the probability to get $H$). Then: $$f(n+1,k,p)=p(f(n,k,p)+f(n,k-1,1-p))$$ $$f(n,0,p)=p^n$$ By recursion one may compute $f(n,k,p)$ for relevant $n,k,p$. The desired value is $\sum_{i \ge k} f(n,i,p)+f(n,i,q)$. Generating functions may come in handy.

share|cite|improve this answer

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.