Coin tossing patterns revisited

[bonanova]

With a nod to harey and Penney and SP

http://brainden.com/forum/index.php/topic/16773-a-tossing-game-you-sure-win/?p=337091

We can select a pattern of four coin tosses, say it's HTTH, and flip a fair coin until we observe it.

We can determine the number of tosses on average that will precede that pattern.

We call that the Wait Time. Each pattern has a wait time that may not be unique.

Clearly THHT has the same wait time as HTTH.

We also can select two patterns of four tosses, say TTTT and HTTT.

By extension of the previous puzzle we know that HTTT is likely to happen first.

Is it possible that for two 4-patterns a and b,

a has the longer Wait Time but is more likely to happen first?

- Puzzle due to Martin Gardner.

[plasmid]

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.

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.

	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	1

Based 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.

[bonanova]

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.

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.

	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	1

Based 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.

I'll mark this solved if no one else posts a reply.

Plasmid's well-described example shows that "waiting time" is a quantity that is less intuitive than first imagined. A binary number comprising random bits that takes a "long time" to happen (on average) doesn't give equal likelihood for other binary numbers to occur first. It also points out that waiting times and precedence (between two numbers) are not simple things to calculate.

I'll leave the thread open in case anyone wants to find a quadruplet that is likely to precede a quadruplet having a shorter wait time. Then if anyone is interested I can share a quick method (one that I read) of getting wait times and ordering probabilities for arbitrary sequences.