Fdtxjr

A fair coin is tossed until the coin lands "tails-tails" (i.e. a tails followed by a tails) for the first time. Let $X$ counts the number of tosses required. Find the probability of the event $X=n.$ What will be the expectation of $X$?

I think this problem has to be solved by recursion but I find difficulty to solve this. Any suggestions regarding this will be highly appreciated.

Thank you very much for your valuable time.

EDIT $:$ If got "tails-tails" for the first time in $n$ steps. Then the first two steps will be either $HH$ or $HT$ or $TH.$ If the first two tosses will yield either $HH$ or $TH$ then we follow the previous step. If it yields $HT$ in the first two steps then the next two steps will be either $HH$ or $HT$ and we go on like that.

We know that $Bbb E(X) = Bbb E(X mid A) Bbb P(A) + Bbb E(X mid A^c) Bbb P(A^c).$
So in this case we can write $Bbb E(X) = Bbb E(X mid H) Bbb P(H) + Bbb E(X mid T) Bbb P (T).$

Now $$Bbb E(X mid H) = Bbb E(X) + 1, Bbb P(H) = frac 1 2.$$ What is $Bbb E(X mid T)$? $$Bbb E(X mid T) = Bbb E((X mid T) mid TH) Bbb P (TH mid T) + Bbb E((X mid T) mid TT) Bbb P(TT mid T).$$ Now $$Bbb E((X mid T) mid TH) = 1 + Bbb E(X mid H) = 2 + Bbb E(X).$$ and $$Bbb E((X mid T) mid TT) = 2.$$ Also $$Bbb P(TH mid T) = Bbb P(TT mid T) = frac 1 2.$$ So we get $$Bbb E (X mid T) = frac 1 2 Bbb E(X) + 2.$$ Putting all these together we get $Bbb E(X) = 6.$

Where have I done mistake? Would you please check it?

Hints:

Let $g_n$ be the number of sequences of length $n$ made up of $H$ and $T$ (heads and tails) that contain no two consecutive tails. Then the sequence you want is such a sequence (but of length $n - 2$) followed by $TT$. Assume you know the value of $g_n$ in general. In terms of $g_n - 3$, what is the desired probability?

Now, to compute $g_n$, consider how we can obtain a such a sequence of length $n$ from a similar sequence of smaller length. Suppose you're given a sequence of length $n - 1$ that contains no $TT$ (two consecutive tails). Then definitely we can add an $H$ to the end of this sequence to get a valid sequence of length $n$? How many such sequences are there (in terms of the unknown $g_k$)? Does this not count all valid sequences ending in $H$?

So that leaves valid sequences of length $n$ ending in $T$. How shall we get such a sequence? Well, if the last term is $T$, then certainly the term before that must be $H$ (for otherwise we would have $TT$ at the end). So what we want is a valid sequence of length $n - 1$ that ends in $H$. How many such sequences are there (again in terms of the unknown $g_k$)?

Adding the above two should give a recurrence relation for $g_n$. The base cases are $g_0 = ???$ and $g_1 = ???$.

You can also easily convert this into a recurrence relation for the desired probability itself.

Full Solution:

The recurrence relation for $g_n$, the number of $H$-$T$ sequences of length $n$ that contain no $TT$ (consecutive tails)$ is

$$g_n = g_n - 1 + g_n - 2; g_0 = 1, g_1 = 2.$$

A sequence of length $n$ that ends in $TT$ and has no two consecutive tails before that is of the form $G_n-3HTT$, where $G_n-3$ is a sequence of length $n - 3$ with no consecutive tails. The probability of a sequence of $n$ tosses ending in $TT$ at the last two tosses for the first time is therefore
beginalign*
p_n & = dfracg_n-32^n\
& = dfracg_n-4 + g_n-52^n\
& = dfrac p_n-1 2 + dfrac p_n-2 4
endalign*
with base cases $p_2 = dfrac 1 4$, $p_3 = dfrac 1 8$.

Then the expected number of tosses is $sumlimits_n = 2^infty n, p_n$. To compute this using the recurrence relation that we already have for $p_n$,

beginalign*
n p_n &= dfrac n 2 p_n - 1 + dfrac n 4 p_n - 2 \
&= dfrac 1 2 (n - 1) p_n - 1 + dfrac 1 2 p_n-1 + dfrac1 4 (n - 2)p_n - 2 + dfrac 2 4 p_n-2
endalign*

Now, we sum this up from $n = 4$ to $infty$. Note that $sum p_n = 1$. Thus,

beginalign*
mathbb E[X] - 3 p_3 - 2 p_2 &= dfrac 1 2 (mathbb E[X] - 2 p_2) + dfrac 1 2 (1 - p_2) + dfrac 1 4 mathbb E[X] + dfrac 1 2 implies\
mathbb E[X] &= 6.
endalign*

Let $h(n)$ denote the number of sequences of length $n$ that end with $H$ and don't contain $TT$. Since $h(n) = h(n-1)+h(n-2)$ and the base cases of $h(n)$ are $h(1) = 1$ and $h(2) = 2$, this is the Fibonacci sequence, $$h(n) = frac(frac1+sqrt52)^n+1-(frac1-sqrt52)^n+1sqrt5$$
On another track,
$$Bbb P(X = n) = frach(n-2)2^n$$. Plugging the explicit formula of $h(n)$ into the above probability and simplifying finds that $$Bbb P(X = n) = frac(frac1+sqrt54)^n-1-(frac1-sqrt54)^n-12sqrt5$$ Using two infinite arithmetico-geometric sums, the expected value is found to be 6. Note: the expected value could also be found by Ned's method in an earlier comment of $E = frac12*(E+1)+frac14*(E+2)+frac14*2$. Solving for $E$ finds that $E = 6$.