# Probability distribution of number of 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 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.

-
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

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

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

-