Coin flipping problem

Question

Suppose that you are flipping a coin endless times. what's the expected round where you would get the same side $3$ consecutive times? I'm guessing it would take $7$ flips to see either HHH or TTT sequence. Because the expected flip to see a HH or TT is $6$ flips and plus the initial flip it would $7$.

Am I correct?

Answer 1

Another approach. Let $t_k$ be the expected number of tosses needed to see $k$ identical flips in a row. Clearly $t_1 = 1$; the first toss is always identical to itself.

We can create a recursion as follows. In order to get $k+1$ identical tosses in a row, we must first get $k$ identical tosses, which takes time $t_k$. On the next toss, with probability $\frac{1}{2}$, we achieve our goal of $k+1$ identical tosses; but also with probability $\frac{1}{2}$, we are back to the square one (we can use the toss that set us back as the first toss of the new attempt). Thus

$$ t_{k+1} = t_k + \frac{1}{2} \times 1 + \frac{1}{2} \times t_{k+1} $$

which can be simplified to obtain

$$ t_{k+1} = 2t_k+1 $$

This recurrence is easily solved with the boundary condition $t_1 = 1$ to yield

$$ t_k = 2^k-1 $$

and in particular, $t_3 = 2^3-1 = 7$.

Answer 2

Let $\psi(i, j)$ be the expected number of rounds to reach state $j$ from state $i$, where $i,j = \{0,1,2,3\}$.

$\psi(0,3) = 1+ \psi(1,3)$

$\psi(1,3) = 1+ \frac{1}{2}\psi(1,3)+\frac{1}{2}\psi(2,3)$

$\psi(2,3) = 1+\frac{1}{2}\psi(1,3)+\frac{1}{2}\psi(3,3)$

$\psi(3,3) = 0 $

Solve for $\psi(0,3)$. The answer is $7$.

Answer 3

Let $x_n$ be the probability that, after $n$ tosses, you still haven't gotten three in a row, and you currently have $1$ in a row - that is, you are are on your first toss or the previous two tosses were different. Let $y_n$ be the probability that you haven't yet gotten three in a row and you currently have the last two equal. Let $z_n$ be the odds that you've gotten three in a row at some point in the first $n$ tosses.

We are seeking: $$\begin{align}\sum_{n} n(z_n-z_{n-1}) &=\sum_{n}\sum_{j=1}^n (z_n-z_{n-1}) \\ &= \sum_{j=1}^\infty \sum_{n=j}^{\infty} (z_n-z_{n-1})\\ & = \sum_{j=1}^\infty (1-z_{j-1}) \\ &= 1+\sum_{j=1}^\infty (x_j+y_j)\end{align}$$

Markov Chain Approach

You see that:

$$\begin{pmatrix}x_{n+1}\\y_{n+1}\\z_{n+1}\end{pmatrix}= \begin{pmatrix}\frac{1}{2}&\frac{1}{2}&0\\ \frac{1}{2}&0&0\\ 0&\frac{1}{2}&1 \end{pmatrix}\begin{pmatrix}x_{n}\\y_{n}\\z_{n}\end{pmatrix}$$

The expected time to get three in a row is:

$$1+\sum_{n=1}^\infty (x_n+y_n) = 1+(1,1,0)\left(\sum_{n=1}^{\infty}A^{n-1}\right)(1,0,0)^T$$

Where $A$ is the above matrix.

The eigenvalues of $A$ are $1,\frac{1\pm\sqrt{5}}{4}$. So $x_n+y_n = a+b\left(\frac{1+\sqrt 5}{4}\right)^{n-1} + c\left(\frac{1-\sqrt 5}{4}\right)^{n-1}$ for some values $a,b,c$.

You know that $x_n+y_n\to 0$, so you know $a=0$.

We know that $x_1+y_1=1,x_2+y_2=1$.

So solve for $b,c$.

Then $$1+\sum_n (x_n+y_n) =1+\frac{b}{1-\frac{1+\sqrt{5}}4} + \frac{c}{1-\frac{1-\sqrt{5}}{4}} = 1+b(3+\sqrt{5}) + c(3-\sqrt{5})$$

The final step is to solve for $b,c$.

I'll skip the work, and tell you that $b=\frac{5+3\sqrt{5}}{10}$ and $c=\frac{5-3\sqrt{5}}{10}$.

Plugging this in, and we see the expected value is $7$.

---

** Generating function approach **

A similar approach, using generating functions, with less algebra, is to see that $y_{n+1}=\frac{1}{2}x_n$, and $x_{n+2}=\frac{1}{2}(x_{n+1}+y_{n+1})=\frac{1}{2}x_{n+1}+\frac{1}{4}x_n$.

So you have a linear recurrence for $x_n$.

Then $$\begin{align}f(z)&=\sum_{n=0}^{\infty}x_{n+1}z^n \\ &= 1+\frac{1}{2}z + \sum_{n=0}^{\infty}\left(\frac{1}{2}x_{n+2} +\frac{1}{4}x_{n+1}\right)z^{n+2}\\ &= 1+\frac{1}{2}z + \frac{1}{2}z(f(z)-1) + \frac{1}{4}z^2f(z)\end{align}$$

So we see that $$f(z)=\frac{1}{1-\frac{1}{2}z-\frac{1}{4}z^2}$$ and $f(1)=4$. But then, since $y_1=0$ and $y_{n+1}=\frac{1}{2}x_n$, we have $\sum y_n=\frac{1}{2}\sum x_n = 2$.

So $\sum (x_n+y_n)=6$ and the expected value is $7$.

Generalized:

For $k+1$ tosses in a row, let $x_{n,i}$ be the probability after $n$ tosses you have not seen $k+1$ identical results in a row, and you currently have seen $j$ identical tosses in a row. Then again, you have the expected value is:

$$1+\sum_{n=1}^{\infty} \sum_{i=1}^{k} x_{n,k}$$

You also have that $x_{n+j-1,j} = \frac{1}{2^{j-1}} x_{n,1}$ and $x_{n+1,1} = \frac{1}{2}\sum_j x_{n,j}$.

Altogether, this means that $x_{n+k,1}=\sum_{j=1}^{k} \frac{1}{2^j}x_{n+k-j,1}$.

Letting $f(z)=\sum_{n=0}^{\infty} x_{n+1,1}z^n$, we can show that:

$$f(z)(1-\frac{1}{2}z-\frac{1}{4}z^2-\cdots-\frac{1}{2^k}z^{k}) = 1$$

This is because the first $k+1$ coefficients of $f(z)$ coincide with the first $k+1$ coefficients of $\frac{1}{2}+\frac{1}{2}\frac{1}{1-z} = \frac{1}{2}\frac{2-z}{1-z}$ and the first $k+1$ coefficients of $2\frac{1-z}{2-z} =2-\frac{2}{2-z}$ coincides with $1-\frac{1}{2}z-\dots-\frac{1}{2^k}z^k $ so the first $k+1$ terms of the product is $1$, and the higher terms are zero by the recurrence.

So $f(1)=\sum x_{n,1} = 2^k$, and the expected value is then $2^{k+1}-1$.

Answer 4

Denote by $E_k$ $(0\leq k\leq 2)$ the expected number of additional throws when you have $k$ equal throws on the top of your stack. Then $$E_0=1+E_1,\qquad E_1=1+{1\over2} E_2+{1\over2} E_1,\qquad E_2=1+{1\over2} 0+{1\over2} E_1\ ,$$ with the solution $E_0={\bf 7}$, $E_1=6$, $E_2=4$. That's it.