Best Answer plasmid, 04 January 2014 - 05:08 AM

I can't find one where I can prove that the wait time for A is longer than B while A is more likely to happen first, but I can prove a case where the wait time for A is longer than B and they are equally likely to happen first.

Spoiler for getting things started

Go to the full post
Let S be a target sequence of heads/tails, like HTTH or TTTH, and S(i) be the i-th term in that sequence.

Let F(n) be what you find on flip n, either H or T.

Let P(S,n) be the probability that you find the sequence S on flips F(n to n+3).

For any sequence S, the probability that it will appear on any four consecutive flips is 1/16. However, since the game stops once the sequence appears for the first time, in order to find P(S,n) we need to modify that 1/16 probability to account for all scenarios where S has already previously occurred.

For example, consider S = TTTT.

P(S,1) = 1/16, as it does for any sequence.

P(S,2) = [the probability that F(2 to 5) is TTTT] x [the probability that TTTT has not already occurred if you are given that F(2 to 5) is TTTT] (Oh no, it's Bayes! Run!)

If you know that F(2 to 5) is TTTT, then the possibilities for all of F(1 to 5) are HTTTT and TTTTT. Clearly there's a 50/50 chance that the game would already be over at F(1 to 4) if you only know that F(2 to 5) would be TTTT. So

P(S,2) = [ 1/16 ] x [ 1/2 ] = 1/32

Now consider the general solution to P(S,n). This equals [the probability that S appears on F(n to n+3), which we know is 1/16] times [the probability that S did not appear on any previous set of four flips, given the fact that S appeared on the n-th set of four flips]. The probability that S appeared in a previous set of flips (call them F(m to m+3)) would only be affected by the knowledge that it appeared on F(n to n+3) if there is overlap between the ranges (m to m+3) and (n to n+3); otherwise it's just P(S,m). So...

P(S,n) = 1/16 x [1-P(S,1)] x [1-P(S,2)] x ... x [1-P(S,n-4)] x gamma x beta x alpha

Now those alpha, beta, and gamma terms I slipped in there account for the probability that S appeared on F(m to m+3) if there is overlap between m and n, and their value is dependent on the specific sequence of S. In the example above where S was TTTT, if you knew that S appeared on F(5 to 8), there would be a 1/2 chance that F(4 to 7) was TTTT, so alpha would be 1/2. If S were THTT then if if you knew that S appeared on F(5 to 8), you would know for sure that THTT did not occur on F(4 to 7) so alpha would be 1 (F(6) would have to be H if S appears on F(5 to 8) but would have had to be a T if S appeared on F(4 to 7)).

Clearly, the values for alpha, beta, and gamma are what distinguish the probabilities for each sequence, and they can be solved by exhaustion. I will only list sequences starting with H since symmetry applies for those starting with T.

In order for you to toss either HHHT or HHHH on flips n to n+3, you must have tossed HHH on flips n to n+2. After tossing three heads in a row, you would know that you're equally likely to toss HHHH as HHHT. So HHHH and HHHT would be equally likely to happen first.

Let F(n) be what you find on flip n, either H or T.

Let P(S,n) be the probability that you find the sequence S on flips F(n to n+3).

For any sequence S, the probability that it will appear on any four consecutive flips is 1/16. However, since the game stops once the sequence appears for the first time, in order to find P(S,n) we need to modify that 1/16 probability to account for all scenarios where S has already previously occurred.

For example, consider S = TTTT.

P(S,1) = 1/16, as it does for any sequence.

P(S,2) = [the probability that F(2 to 5) is TTTT] x [the probability that TTTT has not already occurred if you are given that F(2 to 5) is TTTT] (Oh no, it's Bayes! Run!)

If you know that F(2 to 5) is TTTT, then the possibilities for all of F(1 to 5) are HTTTT and TTTTT. Clearly there's a 50/50 chance that the game would already be over at F(1 to 4) if you only know that F(2 to 5) would be TTTT. So

P(S,2) = [ 1/16 ] x [ 1/2 ] = 1/32

Now consider the general solution to P(S,n). This equals [the probability that S appears on F(n to n+3), which we know is 1/16] times [the probability that S did not appear on any previous set of four flips, given the fact that S appeared on the n-th set of four flips]. The probability that S appeared in a previous set of flips (call them F(m to m+3)) would only be affected by the knowledge that it appeared on F(n to n+3) if there is overlap between the ranges (m to m+3) and (n to n+3); otherwise it's just P(S,m). So...

P(S,n) = 1/16 x [1-P(S,1)] x [1-P(S,2)] x ... x [1-P(S,n-4)] x gamma x beta x alpha

Now those alpha, beta, and gamma terms I slipped in there account for the probability that S appeared on F(m to m+3) if there is overlap between m and n, and their value is dependent on the specific sequence of S. In the example above where S was TTTT, if you knew that S appeared on F(5 to 8), there would be a 1/2 chance that F(4 to 7) was TTTT, so alpha would be 1/2. If S were THTT then if if you knew that S appeared on F(5 to 8), you would know for sure that THTT did not occur on F(4 to 7) so alpha would be 1 (F(6) would have to be H if S appears on F(5 to 8) but would have had to be a T if S appeared on F(4 to 7)).

Clearly, the values for alpha, beta, and gamma are what distinguish the probabilities for each sequence, and they can be solved by exhaustion. I will only list sequences starting with H since symmetry applies for those starting with T.

alpha beta gamma HHHH 1/2 3/4 7/8 HHHT 1 1 1 HHTH 1 1 7/8 HHTT 1 1 1 HTHH 1 1 7/8 HTHT 1 3/4 1 HTTH 1 1 7/8 HTTT 1 1 1Based on these values for alpha, beta, and gamma, clearly HHHH would end up having the longest wait time out of all of the sequences, and HHHT would be tied for the shortest.

In order for you to toss either HHHT or HHHH on flips n to n+3, you must have tossed HHH on flips n to n+2. After tossing three heads in a row, you would know that you're equally likely to toss HHHH as HHHT. So HHHH and HHHT would be equally likely to happen first.