Another coin problem: a super-fair coin making patterns?

Question

Here's the follow-up I promised to:

http://answers.yahoo.com/question/index;_ylt=AjUPi5vJAy_o_BTk83ybJdHsy6IX;_ylv=3?qid=20080825193804AAlxo3x

You'll want to refer to an old question of mine:

http://answers.yahoo.com/question/index;_ylt=Ah9xLVlW4zrnQiN1iRGUS0nsy6IX;_ylv=3?qid=20080204061908AAh0f3Y

http://tech.groups.yahoo.com/group/mathforfun/message/13182

Basically, we have a coin which, given that we've tossed it n times and gotten X heads, the probability for heads in the next toss is 1-X/n (and p=1/2 in the first toss).

It's been shown that, for n tosses, X has a distribution that follows

Pr(X=x) = E(n-1,x-1)/(n-1)!

for n>=2, x=1, 2, ..., n-1 and is zero otherwise. Here E(n, k) is an Eulerian number:

http://en.wikipedia.org/wiki/Eulerian_numbers

However, that may not be too useful here, as I care about sequences.

In sync with the previous few coin questions here, I want to know this: If we flip the coin until the combination THT or TTH shows up, which sequence is more likely to be the end of our coin flipping?

Answer 1

While everyone thinks of a theoretical approach, let me just give the results of a monte carlo simulation of this.

Over 100,000 trials, I'm getting on average that THT ends the sequence 52500, while TTH ends it 47500. The ratio is approximately 1.11.

*EDIT*

I'm surprised no one else is answering. I'm really interested to know if an analytical solution exists for this problem.

*EDIT*

No I rounded those values. Of course with monte carlo simulations, you'll never get exactly the same answer twice. At least with mine, the best you can do is average over numerous trials. But to 2 decimal places, the ratio is roughly 1.11. If we take that as 10/9, then that gives P(THT) = 10/19 and P(TTH) = 9/19. But it's hard to say for sure those are exact values. I doubt it.

Here are some results I got. Based on 1,000,000 trials, I'm getting that THT ends the sequence 525,245 times.

So let p = prob that THT ends the sequence.

We may say that

p^ = 0.525245

p ~ N(p^, p^q^/n)

A 95% confidence interval for p would be

0.525245 ± 9.788x10^(-4)

or (0.524266, 0.526224).

0.5 is over 50 standard deviations away from 0.525245.

So I think it is safe to conclude that THT definitely has a higher probability of ending the sequence than TTH.