# coin flips and markov chain

Consider the case of an infinite (or finite $n$) string of coin tosses, and let $q$ and $1-q$ be the probabilities that the coin comes up tails and heads, respectively. (For simplicity, we can take $q=\frac12$ so that the fraction of tails and heads are the same.)

Let $p$ be the probability that, if a given toss is tails, it will be followed by tails. (If $q = \frac12$, this is the same probability as for getting heads after heads, might as well be a different probability though.)

What is the probability of getting three or more tails consecutively out of $n$ flips (and alternatively out of infinite number of flips).

For example: $TTT-H-TTT-HH-TTTT\dots$

We can have half tails and half heads in total (when $q=\frac12$). $p$ does not affect the fraction of tails and heads in the limit, but affects how they are clustered. So when $p=1$ we have only 2 separate 'sections' such that one section is composed of only tails and the other runs of only heads. (ex: $TTTTT \dots HHHHH$). For $p=0$, it will be like $THTHTHTH\dots$

I am looking for:

1. The fraction of tails that are in sections of size three or more.
2. The expected size of sections with tails.

I'd be very thankful if you could help me with it!

## 1 Answer

To calculate the probability of getting 3 tails in a row in $n$ tosses, you could construct a Markov chain with the states $H$, $T_1$, $T_2$ and $T_3$, and the transition probabilities:

$$P(H \to H) = P(T_1 \to T_2) = P(T_2 \to T_3) = p$$ $$P(H \to T_1) = P(T_1 \to H) = P(T_2 \to H) = 1-p$$ $$P(T_3 \to T_3) = 1$$

Then calculate the probability of ending up at the absorbing state $T_3$ after $n-1$ steps, starting from state $H$ with probability $\frac12$ and from $T_1$ with probability $\frac12$ (to account for the first toss).

Edit: To answer your later questions, the length of consecutive sequences of tails is geometrically distributed with parameter $1-p$. Thus:

1. The probability that a randomly chosen section of tails has length $k$ is $p^{k-1}(1-p)$, and so the fraction of tails in sections of length $k$ is proportional to $kp^{k-1}(1-p)$ (see below for the actual probability). Thus, the fraction of tails in sections of $n$ or more is $$\frac{\sum_{k=n}^\infty kp^{k-1}(1-p)}{\sum_{k=1}^\infty kp^{k-1}(1-p)} = \frac{\sum_{k=n}^\infty kp^k}{\sum_{k=1}^\infty kp^k} = \frac{p^n(n-np+p)/(1-p)^2}{p/(1-p)^2} = p^{n-1}(n-np+p).$$

2. The expected length of a randomly chosen section of tails is $\dfrac{1}{1-p}$.

However, the fraction of tails in sections of $k$ tails is $kp^k\frac{(1-p)^2}{p}$, and so the expected length of the section a randomly chosen "tails" toss belongs to is in fact $$\sum_{k=1}^\infty k^2p^k\frac{(1-p)^2}{p} = \frac{p+1}{1-p} = \frac{2}{1-p}-1.$$