most recent 30 from http://mathoverflow.net 2013-05-25T15:08:22Z http://mathoverflow.net/feeds/user/29968 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116452/bounds-for-number-of-coin-toss-switches Anush 2012-12-15T14:24:43Z 2013-01-25T18:04:07Z

<p>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. </p> <p>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$.</p> <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)$. </p> <p>The exact probability was given at <a href="http://math.stackexchange.com/questions/258221/probability-distribution-of-number-of-switches" rel="nofollow">http://math.stackexchange.com/questions/258221/probability-distribution-of-number-of-switches</a>.</p>

http://mathoverflow.net/questions/116452/bounds-for-number-of-coin-toss-switches/116486#116486 Anush 2012-12-16T09:09:58Z 2012-12-16T09:09:58Z

@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?