2
$\begingroup$

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.

  • 0
    The Cherno$f$f 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.2012-12-15

2 Answers 2

3

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

  • 0
    Thanks. This seems hard to reason with though. Is there a Chernoff type bound one can apply here?2012-12-14
1

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.