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 http://math.stackexchange.com/questions/258221/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 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.

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. The complication is that switch occurrences are not independent. In fact it appears that 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 http://math.stackexchange.com/questions/258221/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 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 http://math.stackexchange.com/questions/258221/probability-distribution-of-number-of-switches.