math puzzle

[Solomon]

its a bit like asking if Heads Tails Heads is more likely than Heads Heads Tails.

The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

[Mnemonic]

The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

Please explain.

[Solomon]

The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

Please explain.

If I did, I'd essentially be giving away the solution to the original question which I'm surprised no one has gotten so far. Regardless, writing a simulation program should be simple enough if you don't believe what I claim.

[hyperpape]

Attempted answer. Of course we have previously established that I'm bad at probability...

After 3 flips, the two are obviously equal.

The trick is that starting with the fourth flip, some of the patterns that give you HTH are "blocked" by the HHT patterns.

Consider the fourth flip:

(1) HHH 1/2 chance of finishing HHT
(4) HTT
(5) THH 1/2 chance of finishing HHT
(6) THT 1/2 chance of finishing HTH
(7) TTH
(8) TTT

Missing from the list are
(2) HHT
(3) HTH
because you stop after three flips for these two.

I'm not sure how deeply related they are, but this reminds of an even more counterintuitive problem: http://mathoverflow.net/questions/17960 ... -want-boys with answers at http://mathoverflow.net/questions/17960 ... -want-boys. I don't pretend to understand even a fraction of that--the only part that made sense was to consider what happens if the country is just one family.

Edit: You actually have to show that the advantage HHT has after the fourth flip will persist. It seems obvious, but I don't have a good argument for it.

P.S. Oh, the question was about Starcraft. It's PvT, PvT, PvZ is more likely?

[jts]

The average # of flips until the pattern 'Heads Tails Heads' appears is not the same as the average # of flips until 'Heads Heads Tails' appears.

Please explain.

@mnemonic

Isn't it fairly obvious? If on average a coin comes up heads 50% of the time, then after it comes up heads on one flip, it needs to come up heads less than fifty percent of time on subsequent flips in order for the asserted probability to hold true. If you doubt me, flip a coin five or six times to test this.

Consider the sequences HTH and HTT. Obviously the conditional probability of getting H or T after having gotten the first two entries in the sequence (HT) is the same. So given a certain probability of getting HT, getting HTH and HTT on the next flip are equally likely. But after failing to get HTT, by definition you have an H in the third sequence, so you have a .25 chance of having HTT within two flips. But if you fail to get HTH, then you have a zero percent chance of getting HTH within two flips, and only a .125 chance of having HTT within three flips.

[perceval]

Isn't it fairly obvious? If on average a coin comes up heads 50% of the time, then after it comes up heads on one flip, it needs to come up heads less than fifty percent of time on subsequent flips in order for the asserted probability to hold true. If you doubt me, flip a coin five or six times to test this.

that's NOT true ... but That was a joke right ? Beware you might plant some weird idea on ppl mind, probas are tricky enough as they are

[Mnemonic]

@ percival
I think we both read the question wrong. I (and probably you too) interpreted the question as; Flip a coin 3 times, which sequence is more likely: HHT or HTH. They are obviously the same with each being 1/8. This is because each coin flip is a separate event and the result is not influenced by previous flips. You can easily draw a decision tree and then you just have to walk along one of the branches and multiply the probabilities.

But the question was: I play a large number of games (10000+) which sequence is likely to appear first and how often will it appear. This kind of math is more advanced than the first one because it depends on the previous results. If the first two flips are HH then you have 50% to hit HHT but 0% to hit HTH

[perceval]

@ percival
I think we both read the question wrong. I (and probably you too) interpreted the question as; Flip a coin 3 times, which sequence is more likely: HHT or HTH. They are obviously the same with each being 1/8. This is because each coin flip is a separate event and the result is not influenced by previous flips. You can easily draw a decision tree and then you just have to walk along one of the branches and multiply the probabilities.

But the question was: I play a large number of games (10000+) which sequence is likely to appear first and how often will it appear. This kind of math is more advanced than the first one because it depends on the previous results. If the first two flips are HH then you have 50% to hit HHT but 0% to hit HTH

i agree with that but my "that's NOT true" was to jts first comment: saying that if you got 1 H first you have less than 1/2 prob to have H next to "maintain the balance" but i think that was a joke . Or i didnt understand the statement
Hyperpape explanation is the right one (IMHO) even if it still hurts my common sense so much that i want to find a flaw.

i'll come up with my own Proba anecdote:

There was a probability teacher who would ask his class, onthe first day, to generate a random string of H and T in two ways:
Th
The one whose mother last name started with an L or before should flip a coin 200 times, the other should just make out a sequence from the top of their heads.
the "mother last name" thing is choosen so that the professor doesnt know which student used which way (but still some students will have to).

Then the professor would guess which one was simulated and which wasnt at a glance wit ha very high sucess rate. How did he do that ?

.. i don t remember where i heard that story hope it wasnt on that board....

He would look for a string of 5 H in a row, which is highly likely to happen in a 200 H or T random seq, but a human would never produce it while trying to be pseudo random
Edit: proba is much closer to 1 with 5 H in a row than 6

[perceval]

Back to Araban Question, here is a more complete version of hyperpape answer; (with the inital 3 valued event)

let P(TZT ;n)= prob that pattern TZT appear for the first time at match n AND TTZ did not happened before
P(TTZ;n) = prob that pattern TTZ appear for the first time at match n AND TZT did not happened before

Q(n): neither pattern arise at rank n AND nth match was vs a T;

we want to know if sum P(TTZ;n) > sum P(TZT;n)
P(TTZ;n) P(TZT;n) and Q(n) are hard to compute exactly and the sum are worse
BUT it is enough to prove that P1(n) >= P2(n) for all n.
Hyperpape proves it for n=3 and 4;
more generally
we have P(TZT;n+2)=[Q(n) - p(Match n-1 was T knowing Q(n))]/9
( we need to substract p(Match n-1 was T ...) becasue in that case first occurrence is TTZ at rank n+1)
P(TTZ;n+2)=Q(n)/9
so P1(n+2)<=P2(n+2) for each n we do not know pp(Match n-1 was T) but it does not matter
so pattern TTZ has a greater chance of appearing first but computing it exactly is not easy (it probably converge quickly though)

with that i am more or less convinced