BrainDen.com - Brain Teasers
• 0

More coin tosses

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

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

• 0

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.