More coin tosses

[bonanova]

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?

 

 

[witzar]

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.

Let's start with e|w:
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 August 30, 2014 by witzar

[bonanova]

Nice approach. Your answer is smaller than what I get.

[witzar]

Nice approach. Your answer is smaller than what I get.

 

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 August 31, 2014 by witzar

[witzar]

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.

[bonanova]

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.

[DeGe]

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

[witzar]

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.

[bonanova]

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.

[bonanova]

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.