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