BrainDen.com - Brain Teasers
• 0

# More coin tosses

Go to solution Solved by witzar,

## Question

You toss a fair coin repeatedly, hoping to see an odd number of T sandwiched between two H.

e.g. H T T H H T T T T H T H ... ( 12 tosses. )

On average, how many tosses does this take?

## Recommended Posts

• 0
• Solution

Let's consider the following states:

w = "still waiting for the first H"
e = "H followed by even number of T's"
o = "H followed by odd number of T's"
s = "odd number of T's sandwiched between two H"

We start in state w and when we get to the state s we are done.
We have the following transitions:
w->w (T), w->e (W)
e->e (H), e->o (T)
o->e (T), o->s (H)
with 0.5 probability each.

(It would be helpful to draw a diagram at this point.)

Let x|y denote the average number of transitions (tosses) needed to get from state y to state x.

e|w = 0.5*1 + 0.5*(1 + e|w) => e|w = 2.

Same thing with o|e:
o|e = 0.5*1 + 0.5*(1 + o|e) => o|e = 2.

Now the more difficult one:
s|o = 0.5*1 + 0.5*(1 + s|e) = 0.5*1 + 0.5*(1 + s|o + o|e) = 0.5*1 + 0.5*(1 + s|o + 2) => s|o = 4.

Finally:
s|w = s|o + o|e + e|w = 4 + 2 + 2 = 8.

So 8 tosses are needed on average.

Edited by witzar
##### Share on other sites
• 0

Here is a Java code I just wrote to confirm my calculations:

```package sandwichedht;

public class SandwichedHT {

enum State {
W, E, O, S;
private State onT, onH;

static {
W.onT = W; W.onH = E;
E.onT = O; E.onH = E;
O.onT = E; O.onH = S;
}

public State transition() {
return (Math.random() < 0.5) ? onH : onT;
}
}

int count() {
int i = 0;
for (State state = State.W; state != State.S; state = state.transition()) {
i++;
}
return i;
}

double avg(int tries) {
long totalCount = 0;
for (int i = 0; i<tries; i++) {
totalCount += count();
}
return ((double) totalCount)/tries;
}

public static void main(String[] args) {
int tries = 1000000;
double avg = new SandwichedHT().avg(tries);
System.out.println("tries=" + tries + " avg=" + avg);
}
}
```

It's results are pretty close to 8.

Edited by witzar
##### Share on other sites
• 0

And here is the straightforward approach:

```public class SandwichedHT {

boolean isSandwiched(String s) {
if (!s.endsWith("TH")) {
return false;
}
String s1 = s.substring(0, s.length() - 1);
int lastH = s1.lastIndexOf("H");
if (lastH == -1) {
return false;
}
return ((s1.length() - lastH) % 2 == 0);
}

int count() {
int i = 0;
String s = "";
do {
s += (Math.random() < 0.5) ? "H" : "T";
i++;
} while (!isSandwiched(s));
return i;
}

double avg(int tries) {
long totalCount = 0;
for (int i = 0; i<tries; i++) {
totalCount += count();
}
return ((double) totalCount)/tries;
}

public static void main(String[] args) {
int tries = 1000000;
double avg = new SandwichedHT().avg(tries);
System.out.println("tries=" + tries + " avg=" + avg);
}
}
```

It gives same results.

##### Share on other sites
• 0

I have to say your approach looks right, and no doubt the programs agree on the answer that follows from it.

I have two comments. One is it would be interesting to simulate the flips.

I haven't simulated it, as the computer than has my favorite programming language on it is being repaired.

The second comment is that I have a fairly clear analysis that gives a larger number of flips.

Simulation would probably verify one of our approaches.

##### Share on other sites
• 0

Between any 2 H, the probability of Ts being even or odd is equal.

The first H is expected to be seen in 2 tosses (probability 0.5 for T/H).

The expected number of Ts between Hs is:
0/2 + 1/4 + 2/8 + 3/16 + 4/32 + ... = 1

And a final toss for the last H.

Since the probability of Ts being even or odd is 0.5, multiply these tosses by 2
You get (2 + 1 + 1)*2 = 8 tosses

##### Share on other sites
• 0

I have two comments. One is it would be interesting to simulate the flips.

But this is exactly what my second program does. It simulates the flips.

##### Share on other sites
• 0

I made a decision graph that shows success or failure for four opening flip sequences:

1. T fail with p=1/2
2. HH fail with p=1/4
3. HTT fail with p=1/8
4. HTH succeed with p=1/8

This gives the answer immediately as 14, because in 8 representative trials

you will flip the coin 4 + 4 + 3 + 3 times with exactly one success.

##### Share on other sites
• 0

Ah, but of course my decision tree is incorrect.

My case 3 above was wrong. I need two steps to solve that tree.

(Step 1) H followed by (Step 2) odd T followed by H.

Step 2. Odd T followed by H. Three cases.

1. H fail with p=1/2
2. TT fail with p=1/4
3. HT succeed with p=1/4

Four trials, with 2+2+2 tosses, give one success.

Step 1, Precede this with H. Two cases.

1. T p=1/2 fail.
2. H p=1/2 succeeds after 6 more tosses

Two trials, with 1+1+6 tosses, give one success.

kudos to witzar (first solver) and DeGe for their clear thinking.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.