Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a coin that, when tossed, produces heads with probability $p \geq 0.5$ and tails with probability $1-p$.

I start a coin-tossing experiment. Whenever I get more than one tail in a row, I discard the second tail and toss again, so that my results look like one long chain of heads with the occasional tail sprinkled in. In the long run, does the overall percentage of heads converge to 100%? How long does my result list have to be to guarantee at least $x$% heads? What if I only discard the last toss if I get more than $k$ tails in a row?

(This question comes from thinking about the caching function of my streaming music library. Please excuse a first-year undergrad's background knowledge; if this has been done a million times before I would appreciate a link to the general subject)

share|improve this question

1 Answer 1

The resulting output is a Markov chain on the state space $\{h,t\}$ with transitions $p(t,h)=1$, $p(t,t)=0$, $p(h,h)=p$ and $p(h,t)=1-p$. The overall percentage of heads converges to the stationary measure of $h$. The stationary distribution $\pi$ solves $\pi(t)=p(t,t)\pi(t)+p(h,t)\pi(h)$, that is, $\pi(t)=(1-p)\pi(h)$.

Hence $\pi(h)=\dfrac1{2-p}$ and, in particular, $\pi(h)\ne1$ for every $p\ne1$.

If the strategy is to discard the last toss if one gets more than $k$ tails in a row, the resulting output is a Markov chain with memory $k$, or equivalently, a Markov chain on the state space $\{h,t\}^k$, and the same technique applies.

An alternative is to consider the length of the run of consecutive tails ending at $n$. This is again a Markov chain, this time on the state space $\{0,1,\ldots,k\}$. The transitions are $p(i,i+1)=1-p$ and $p(i,0)=p$ for every $i\leqslant k-1$, and $p(k,0)=1$. The stationary distribution $\pi_k$ solves the system $\pi_k(0)=p\pi_k(0)+\cdots+p\pi_k(k-1)+\pi_k(k)$ and $\pi_k(i)=(1-p)\pi_k(i-1)$ for $1\leqslant i\leqslant k$. Hence $\pi_k(i)=(1-p)^i\pi_k(0)$ for every state $i$, and $\pi_k(0)\cdot\sum\limits_{i=0}^k(1-p)^i=1$.

Finally, for each $k\geqslant1$, the overall percentage of heads converges to $\pi_k(0)=\dfrac{p}{1-(1-p)^{k+1}}.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.