Average number of heads in filtered coin toss

Question

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)

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