TXT me

Probability Level 5

You flip a fair coin several times.

Find the expected value for the number of flips you'll need to make in order to see the pattern TXT, where T is tails, and X is either heads or tails.

If the expectation value can be expressed as $\frac ab$ , where $a$ and $b$ are coprime positive integers, find $a+b$ .

Clarification : You are looking for the pattern TTT or THT. That is, you will keep flipping until you see one of these two patterns, and then count the number of flips you made.

Other Expected Value Quizzes

Image credit : www.cointalk.com

The answer is 39.

2 solutions

Geoff Pilling
Jun 1, 2016

The expectation value is given by this set of linear equations:

$E = 1 + (1/2)*E_1 + (1/2)*E$
$E_1 = 1 + (1/2)*E_2 + (1/2)*E_3$
$E_2 = 1 + (1/2)*E_3$
$E_3 = 1 + (1/2)*E$

Where,

$E =$ Expectation value when you start flipping
$E_1 =$ Expectation value when your last flip is a tails (not preceded by another tails)
$E_2 =$ Expectation value once the last two coins are TT (but you haven't seen TXT yet)
$E_3 =$ Expectation value once the last two coins are TH (but you haven't seen TXT yet)

How are these equations derived? Well for the first one, if we are in state $E$ , we use up one flip (the " $1$ "), and we have a $\frac{1}{2}$ probability of ending up in state $E_1$ (if we flip tails) and $\frac{1}{2}$ probability of ending up in sate $E$ again (if we flip heads). The rest of the equations are derived similarly.

Solving for $E$ you get, $E = 34/5$ . $34+5 = \boxed{39}$

@Geoff Pilling Could you please explain how you got the first 4 linear equations.

Akshay Kaplesh - 4 years, 9 months ago

Yeah, I've added a small explanation to the solution. Does it make sense? Or should I add a bit more?

Geoff Pilling - 4 years, 9 months ago

@Geoff Pilling AHA! Got it. Thanks :)

Akshay Kaplesh - 4 years, 9 months ago

why cant we do like this? :( :( where am I wrong?

if expected value of coin flip for $TXT$ is $E$

then $E = \frac{E+1}{2} + \frac{E+3}{4} + \frac{3}{4}$ ........which gives us $E=8$ :( :(

Asif Hasan - 4 years, 5 months ago

How did you derive this equation?

Geoff Pilling - 4 years, 5 months ago

ohh wait!!

first we get $TXT$ in $3$ flips......then it is $\frac{1 * 3}{4}$

otherwise if we get $THH$ in first $3$ flips......then it will be $\frac{1* (E+3)}{8}$ .....

if we get $TTH$ in first $3$ flips......it's probability is $\frac{1}{8}$ ...on next flip we may get $TTHT$ or $TTHH$ .......then it should be $\frac{1}{8} * (\frac{1*(4+E)}{2} + \frac{1*4}{2}\ )$

and the other only case is we get $H$ on the first flip......then it is $\frac{1*(E+1)}{2}$

so we can write $E = \frac{E+1}{2} + \frac{3}{4} + \frac{1* (E+3)}{8}\ + \frac{1}{8} * (\frac{1*(4+E)}{2} + \frac{1*4}{2}\ )$

this gives us $E= \frac{34}{5}$ ......ohh ok!! - - - - i should have noticed....how dumb I am :( :( :(

Asif Hasan - 4 years, 5 months ago

I tried like this::

first we get $TXT$ in $3$ flips......then it is $\frac{1 * 3}{4}$

otherwise if we get $TXH$ in first $3$ flips......then it will be $\frac{1* (E+3)}{4}$ .....

and the other only case is we get $H$ on the first flip......then it is $\frac{1*(E+1)}{2}$

so we can write $E = \frac{E+1}{2} + \frac{E+3}{4} + \frac{3}{4}$

Asif Hasan - 4 years, 5 months ago

Let the expected value for the required number of flips be E.

There are three cases possible:

1) TXT, If we get this pattern at any step, we stop there.

2) TXH, If we get this pattern then we start flipping again to get the pattern in (1). Flipping after getting H is equivalent to flipping at beginning.

3) H, If we get this pattern then we start flipping again to get the pattern in (1). Flipping after getting H is equivalent to flipping at beginning.

Expected value = Value of the event * Probability of that event

Value of the event = No. of flips required in the event

Exp[1] = 3 * (1/2 * 1 * 1/2)

Exp[2] = (3+E) * (1/2 * 1 * 1/2)

Exp[3] = (1+E) * (1/2)

Thus E = (E+1)/2 + (E+3)/4 + 3/8 => E = 8

What is wrong here? I think answer should be (8+1 =) 9.

Kishan Kumar - 7 months, 2 weeks ago

This way of reasoning is entirely right. But you guys got the TTH case wrong. This case does not give E+3. From TTH, we get either TTHT (4) or TTHH (E+4), with 1/16 of probability for each. If we substitute this in, we get the same answer for both methods.

Zhang Naifu - 5 months, 2 weeks ago

@Geoff Pilling ur solution is not correct. When we calculate ur solution, we get 6 as a expected value, but the answer is 9

Tyler Miller - 1 year, 10 months ago

sorry meant 39

Tyler Miller - 1 year, 10 months ago

Abdelhamid Saadi
Jun 15, 2016

A Monte Carlo solution in Python

"TXT me"
from  random import choice
def roll():
    res = 3
    a,b,c = choice(["H","T"]), choice(["H","T"]), choice(["H","T"])
    while a + c != "TT":
        a,b,c = b,c, choice(["H","T"])
        res += 1
    return res

def recap(n):
    tot = 0
    for i in range(n):
        tot += roll()
    return tot/n


for n in range(21):
    print(recap(2**n))

Output

4.0
6.0
6.0
8.25
6.625
6.65625
6.234375
6.7421875
6.41796875
6.92578125
6.8232421875
6.55029296875
6.785888671875
6.8399658203125
6.80792236328125
6.81683349609375
6.8178253173828125
6.783042907714844
6.803562164306641
6.797967910766602
6.802909851074219

We are around $6.8 = \frac {34}{5}$

Ah, very nice! :)

Geoff Pilling - 5 years ago

TXT me

Image credit : www.cointalk.com

The answer is 39.

2 solutions

0 pending reports