[bonanova]

We usually reason that if something is improbable we will wait longer to see it happen.

To be more specific, if p is the probability of something happening in one trial, we logically expect the event to happen after 1/p trials.

So if two events have the same probability, we wouldn't expect [on average] to wait longer for one event than for the other.

Flip a coin three times.

One of these events will occur, each with likelihood of .5³ = 1/8:

1. HHH
   
2. HHT
   
3. HTH
   
4. HTT
   
5. TTT
   
6. TTH
   
7. THT
   
8. THH
   

Now suppose we flip a coin seventeen times [say].

Within that string of 17 Hs and Ts, would we expect these events to occur [a] with any predictable order, or in random order?

Edited February 27, 2009 by bonanova
Changed case 8: from TTT to THH

[peace*out]

We usually reason that if something is improbable we will wait longer to see it happen.

To be more specific, if p is the probability of something happening in one trial, we logically expect the event to happen after 1/p trials.

So if two events have the same probability, we wouldn't expect [on average] to wait longer for one event than for the other.

Flip a coin three times.

One of these events will occur, each with likelihood of .5³ = 1/8:

1. HHH
   
2. HHT
   
3. HTH
   
4. HTT
   
5. TTT
   
6. TTH
   
7. THT
   
8. TTT
   

Now suppose we flip a coin seventeen times [say].

Within that string of 17 Hs and Ts, would we expect these events to occur [a] with any predictable order, or in random order?

in random order, because there are predictions of those things happening, but you could mix it up in any order, making it random...unless im wrong...

[Guest]

We usually reason that if something is improbable we will wait longer to see it happen.

To be more specific, if p is the probability of something happening in one trial, we logically expect the event to happen after 1/p trials.

So if two events have the same probability, we wouldn't expect [on average] to wait longer for one event than for the other.

Flip a coin three times.

One of these events will occur, each with likelihood of .5³ = 1/8:

1. HHH
   
2. HHT
   
3. HTH
   
4. HTT
   
5. TTT
   
6. TTH
   
7. THT
   
8. TTT
   

Now suppose we flip a coin seventeen times [say].

Within that string of 17 Hs and Ts, would we expect these events to occur [a] with any predictable order, or in random order?

Are you saying to break the string of 17 down into 15 groups of 3?

123

234

345

etc?

If so, then the order will be somewhat predictable based on the strings that have already come up. Obviously, if the first 3 (1,2,3) is HHH, then the second string (2,3,4) can only be HHT and HHH. Each of these would be equally likely. (3,4,5) could then be HHH, HHT, HTH, HTT with equal probability.

[bonanova]

Are you saying to break the string of 17 down into 15 groups of 3?

Yes.

And if you are lead then to believe that can affect the likely order of occurrence,

can you find a pair of triples for which one triple would be expected to occur before the other?

Going further down that path:

If different pairs of triples do not all have the same likelihood of an expected order,

is there a pair of cases where the likelihood of an expected order is greater than for any other pair?

With the exception of just interchanging H and T, of course; symmetry makes things happen in pairs.

Or is equal likelihood the predominant force, and all outcomes are random?

[Prime]

There are 2¹⁷ possible outcomes. They represent the number of orderings for any imbeded strings.

Including the same instance of the coin toss into the different triplets makes them dependent. I.e., if we were to consider ordering of 15 completely independent triplets of coin tosses, the number of variations would be 2¹⁸. One way or another, nothing is there to make random sequence predictable.

[Guest]

We usually reason that if something is improbable we will wait longer to see it happen.

To be more specific, if p is the probability of something happening in one trial, we logically expect the event to happen after 1/p trials.

So if two events have the same probability, we wouldn't expect [on average] to wait longer for one event than for the other.

Flip a coin three times.

One of these events will occur, each with likelihood of .53 = 1/8:

1. HHH

2. HHT

3. HTH

4. HTT

5. TTT

6. TTH

7. THT

8. TTT

Now suppose we flip a coin seventeen times [say].

Within that string of 17 Hs and Ts, would we expect these events to occur [a] with any predictable order, or in random order?

I would like to point out that you have TTT listed twice as an outcome. Is this on purpose?

[bonanova]

I would like to point out that you have TTT listed twice as an outcome. Is this on purpose?

Nope, it's a brain fart - I'll edit the OP.

Nice catch, thanks.

[Guest]

I have no idea how to figure out that math, but I did flip a coin in 2 separate sets of 17 here's what happened

1H

2T

3T

4T

5T

6H

7T

8H

9H

10H

11H

12H

13H

14H

15T

16H

17H

1H

2T

3H

4H

5T

6T

7T

8H

9H

10T

11T

12T

13H

14H

15H

16T

17H

[Prime]

There are 2¹⁷ possible outcomes. They represent the number of orderings for any imbeded strings.

Including the same instance of the coin toss into the different triplets makes them dependent. I.e., if we were to consider ordering of 15 completely independent triplets of coin tosses, the number of variations would be 2¹⁸. One way or another, nothing is there to make random sequence predictable.

I made a typing error: for 15 independent triplets the number of variations is 2⁴⁵, of course.

I am afraid, I don't see the point with predictability. Does it mean, if you make 17 tosses, then randomly picked triplet of tosses, say (1,9,17) are more likely to be heads?

(Note there are 680 different triplets within a collection of 17 tosses.)

[bonanova]

I made a typing error: for 15 independent triplets the number of variations is 2⁴⁵, of course.

I am afraid, I don't see the point with predictability. Does it mean, if you make 17 tosses, then randomly picked triplet of tosses, say (1,9,17) are more likely to be heads?

(Note there are 680 different triplets within a collection of 17 tosses.)

I picked 17 for two reasons:

[1] to give a reasonable chance for all eight patterns to appear and be ordered.

[2] because my computer will handle arrays of 8 x 2¹⁷.

Neither of these reasons bears on the idea of the puzzle, so let's examine the main idea more simply.

Pick two triples, t₁ and t₂, then flip a coin until one of these patterns appears.

What are the odds that it will be t₁?

Are they necessarily 50%?

[Prime]

I understand, a triplet is 3 consecutive coin tosses. And the triplets overlap. That is the same coin toss may be used in up to 3 consecutive triplets.

That seems to create a dependency.

Any given triplet is as likely to occur as another. However, some sequences are more limited than others.

Nomenclature: 0=Heads, 1=Tails. Consider all possibilities for 4 tosses, and compare how many times "000" occurred before "011".

0000*

0001*

0010

0011+

0100

0101

0110+

0111+

1000*

1001

1010

1011+

1100

1101

1110

1111

Instances where "000" appeared first are marked with "*"; the "011" appearing first marked with "+".

So there are 4 instances of "011" occuring first against 3 instances of "000". The "000" sequence is packed tighter in some variations. Like in the instance of "0000", where the trailing "000" lost its opportunity to have a different immediately preceding triplet. The "011" strings are spaced further apart from each other.

[HoustonHokie]

I understand, a triplet is 3 consecutive coin tosses. And the triplets overlap. That is the same coin toss may be used in up to 3 consecutive triplets.

That seems to create a dependency.

Any given triplet is as likely to occur as another. However, some sequences are more limited than others.

Nomenclature: 0=Heads, 1=Tails. Consider all possibilities for 4 tosses, and compare how many times "000" occurred before "011".

0000*

0001*

0010

0011+

0100

0101

0110+

0111+

1000*

1001

1010

1011+

1100

1101

1110

1111

Instances where "000" appeared first are marked with "*"; the "011" appearing first marked with "+".

So there are 4 instances of "011" occuring first against 3 instances of "000". The "000" sequence is packed tighter in some variations. Like in the instance of "0000", where the trailing "000" lost its opportunity to have a different immediately preceding triplet. The "011" strings are spaced further apart from each other.

in your first sequence, "000" actually occurred twice:

0000

0000

So it should get 2 * instead of just one, I think, making both 000 and 011 equally likely.

[Prime]

in your first sequence, "000" actually occurred twice:

0000

0000

So it should get 2 * instead of just one, I think, making both 000 and 011 equally likely.

That was my point precisely. I did say that all triplets are equally likely. And I pointed out the variation of "0000", stating that the trailing "000" lost its opportunity to have an immediate predecessor other than itself.

I understood, Bn asked whether some triplets are more likely to appear before others. And "011" is more likely to appear before "000" in 4 consecutive tosses.

[Prime]

I suggest the following nomenclature:

0=Heads

1=Tails

Since a triplet is represented by a 3-digit binary number, we could use octal system instead. I.e., 000=0, 001=1, 010=2, ... , 111=7.

Consider two immediately neighboring triplets (4 tosses)...

All possibilities for successor triplets (in octal) are as following:

00, 01,

12, 13,

24, 25,

36, 37,

40, 41,

52, 53,

64, 65,

76, 77.

There are 4 instances of each triplet in the field of all possible variations.

Using that, we can build longer strings. (Perhaps, this method could save execution time for Bonanova’s software.)

For example, given "36" resulting from 4 tosses, then 5th toss could produce 364, or 365.

That does represent a certain order. Note, that with just 2 triplets (4 tosses) the triplets "0" and "7" are in the unique position in way that they can have an identical triplet as its successor. That diminishes their chances for "precedence" compared to other triplets.

CR already noted the dependency.

So an example of triplets with less chance of appearing before others are "000" and "111". However, others may also not have the same probability of "precedence". So are we looking for the exact probability of precedence in 17 tosses for each triplet?

[Guest]

I'm not exactly sure what's being asked here, but when the string HHH or TTT occurs, there is a probability of 0.5 that it will be repeated with the next toss. With any other result, the next string is certain to be different. Because in any three consecutive tosses, each of the eight outcomes occurs with equal probability, and some would say also equal frequency, we conclude that HHH and TTT are then more likely to occur in clusters, and we are more likely to have to wait longer between such clusters.

Note also that the strings 101 and 010 might be repeated again after two tosses, while 001, 011, 100 and 110 need at least three more tosses. I expect these latter four to be more likely to appear sooner in the sequence.

[Guest]

I think I have it.

The answer is yes, some triplets are likely to occur before others.

Consider TTT and HTT.

The only way TTT can occur before HTT is if the sequence starts with TTT (with p=1/8, of course). If the sequence doesn't start with TTT, then HTT must occur before TTT can. And in a sequence of length 17, we can be reasonably sure an HTT sequence will show up somewhere. An exact calculation would be difficult, but I think we can agree that the probability would be significantly greater than 1/8.

There are other, weaker differences we can point out. Take HTT for example. It's likely that HHT or THT would come before HTT, by the same reasoning. Again, I don't have a calculated answer but I have a concept.

Very nice puzzle, I like the counterintuitivity (it's a word, look it up).

[Guest]

An exact calculation would be difficult, but I think we can agree that the probability would be significantly greater than 1/8.

Very nice puzzle, I like the counterintuitivity (it's a word, look it up).

Maybe I'm missing something, but it seems to me that in n coin tosses, any string of three H and/or T has a chance of 1-(7/8)^(n-2) of occurring at least once. For n=17, that yields a probability of 0.865.

Counterintuitivity? I will consult my OED and get back to you. ;-p

[bonanova]

Prime asks:

So are we looking for the exact probability of precedence in 17 tosses for each triplet?

Better, probability of precedence in a string of tosses that only needs to be long enough for the first one to appear.

Chuck Rampart notes three pairs, with one being likely to appear first.

Correct on the first two; and I think you can calculate their likelihood: you almost have it for the first, most glaring, case.

But symmetry can be invoked on the first two tosses for your third pair: THT and HTT are equally likely to appear first.

Can you calculate the likelihoods for HTT before TTT and for HHT before HTT?

If we want to ignore pairs [all 14 nonredundant pairs can directly be calculated]

it's possible also just to think of how many tosses on average are needed

for each of the eight triples occur individually.

I don't know that this can be directly calculated; but it can be simulated.

For starters, since p=1/8, you might expect 8 tosses for each.

But would some actually occur later on average?

And why does the p=1/8 fact seem to be a red herring in this puzzle?

[Prime]

Here is a complete table of precedence for 17 tosses. (In case anyone cares.)

Each column represents precedence for the triplet at the heading of the column over the triplet naming the intersecting row.

For example, the cell (6,0) shows that "0" occurred before "6" 39.072 times; the cell (0,6) shows that “6” occurred before "0" 90,424 times. At the bottom the results for each column are tallied.

0 1 2 3 4 5 6 7
0 60656 72928 77640 104928 74528 90424 60656
1 60656 42792 43632 90408 49136 65424 39072
2 48896 84560 65424 63328 60656 81712 53296
3 51856 86928 65424 65424 64024 32760 16384
4 16384 32760 64024 65424 65424 86928 51856
5 53296 81712 60656 63328 65424 84560 48896
6 39072 65424 49136 90408 43632 42792 60656
7 60656 90424 74528 104928 77640 72928 60656

330816 502464 429488 510784 510784 429488 502464 330816

The table was produced in a spreadsheet (Excel); the program took more than half an hour to run. 17 tosses are too much.

This data is true and correct, unless I messed up. Here is the source code:

Sub triplprec()
Dim wk_tprec(8) As Boolean
Dim n As Long

tlen = CInt(InputBox("Enter # of tosses < 20"))
If tlen > 20 Or tlen < 3 Then Exit Sub

With ActiveSheet

For r = 2 To 9 'Initialize output table
For c = 2 To 9
If r <> c Then .Cells(r, c).Value = 0
Next c
Next r

'Traverse all possible strings. Each string of 17 tosses represented by n in binary.
For n = 0 To 2 ^ tlen - 1
Application.StatusBar = n
For i = 0 To 7 'Initialize record used to show whether the triplet has occured before
wk_tprec(i) = False
Next i
rlen = tlen - 3
Do While rlen >= 3
c = (n \ 2 ^ rlen) Mod 8 'Get next triplet
If Not wk_tprec© Then
wk_tprec© = True
For r = 0 To 7
If Not wk_tprec® Then .Cells(r + 2, c + 2).Value = .Cells(r + 2, c + 2).Value + 1
Next r
End If
rlen = rlen - 1
Loop
Next n
End With
End Sub

As I and HoustonHokie noticed earlier, each triplet occurs exact same number of times as any other.

As we already figured out "0" and "7" (HHH and TTT) suffered most in terms of precedence. Whereas, "3" and "4" (HTT and THH) are most likely to appear before any other triplet.

[Prime]

And as I took a second look into my code, I found a bug. It should be:

Do While rlen >= 0

instead of

Do While rlen >=3.

I rerun for 12 tosses only

0 1 2 3 4 5 6 7
0 1815 2185 2387 3118 2277 2774 1815
1 1815 1313 1359 2695 1534 2036 1211
2 1470 2567 2036 1920 1815 2538 1630
3 1598 2688 2036 2036 1960 1023 512
4 512 1023 1960 2036 2036 2688 1598
5 1630 2538 1815 1920 2036 2567 1470
6 1211 2036 1534 2695 1359 1313 1815
7 1815 2774 2277 3118 2387 2185 1815

10051 15441 13120 15551 15551 13120 15441 10051

[HoustonHokie]

If we want to ignore pairs [all 14 nonredundant pairs can directly be calculated]

it's possible also just to think of how many tosses on average are needed

for each of the eight triples occur individually.

I don't know that this can be directly calculated; but it can be simulated.

One of the reasons this is a difficult number to calculate is that there are a significant number of cases where, in a finite number of flips, the desired triplet doesn't occur at all.

Consider the OP with 17 coin flips. If you're looking for TTT, any combination of 17 flips where the coin lands heads-up at least 15 times will eliminate the possibility of TTT occurring. There are also numerous other cases where TTT doesn't occur in 17 flips (for example, TTHTTHTTHTTHTTHTT).

I haven't carried it out all the way to figure out in how many of the 17-flip cases TTT doesn't occur (or any of the other 7 triplets, for that matter), but what do we say about how many coin flips are required for that triplet to occur in those cases? It's definitely greater than 17, but how much greater? It's relatively easy to go through and figure out how many times TTT first occurs after 3, 4, 5, ..., 17 flips, and then multiply the number of flips by the relative probability of each case and sum to get the overall average number of flips required, assuming the triplet occurs at all. But I still don't know what to do with the cases where TTT doesn't occur at all.

One thought would be to allow the number of flips (n) to increase until n approaches infinity, but then I think you get into a situation where for an infinitesimally small probability of occurrence (p = 0.000000....), the triplet occurs after infinite flips, and zero times infinity is undefined.

Another thought, and better I think, would be to try to figure it out this way:

The probability of TTT occurring after just 3 flips is 1/8. What is the probability of TTT occurring after 4 flips but not in the first 3? The probability of such an occurrence is 1/16. After 5 flips but not in the first 4? 2/32. After 6 but not in the first 5? 4/64. So:

p(TTT,3) = 1/8

p(TTT,4) = 1/16

p(TTT,5) = 2/32

p(TTT,6) = 4/64

p(TTT,7) = 7/128

p(TTT,8) = 13/256

and so on (my computer will only handle binaries to 8 places and octals won't work because they don't alllow for overlapping triplets)

You could then say that the probability of TTT occurring at least once in the first 8 flips would be P(TTT,8) = p(TTT,3) + p(TTT,4) + ... + p(TTT,8) = 0.418

Finally, I notice that p(TTT,4) is not equal to p(TTH,4), which was what Prime was pointing out to me earlier (I guess I understand now - thanks!). p(TTH,4) = 2/16, and P(TTH,4) = 1/4 which is greater than P(TTT,4) = 3/16. So TTH would be more likely to occur at least once in the first four flips than TTT.

[bonanova]

One of the reasons this is a difficult number to calculate is that there are a significant number of cases where, in a finite number of flips, the desired triplet doesn't occur at all.

Right. There is no N, not matter how large, for which all of the 2^N distinct strings of flips will produce all possible triples.

For example, one of the distinct strings is N consecutive Ts, and another is N consecutive Hs.

As N increases, these comprise an increasingly small fraction of the distinct cases,

but in these strings only the triples TTT and HHH, respectively, appear.

... what do we say about how many coin flips are required for that triplet to occur in those cases?

Well, we can say there is no value of N that will ensure a triple will occur after N flips.

One thing we can ask, though, is the expected number of coin flips for a triple to occur: the expected "wait time."

[Guest]

One thing we can ask, though, is the expected number of coin flips for a triple to occur: the expected "wait time."

Well, I know how we all despise frequency analysis around here, but it does lead to some remarkably straightforward solutions that can be worked out in one's head. For example: since the eight triplets are all equally likely, the expectation is 8 flips between the start of two like triplets (i.e. 5 intervening flips).

However, their distribution is not uniformly random. As I noted earlier, half of the time HHH or TTT occurs, it will occur again on the next toss. If it does not, we expect to have to wait longer than eight more tosses for it to occur again. Without putting too much effort into it, I calculate the expectation to be 15 coin flips (including the one in which we failed, so 14 more if you want to look at it that way). Similarly, for THT and HTH, there is a probability of 1/4 of recurrence in two tosses, and if it does not, we expect to have to wait through 10 flips (or 8 more). For the remaining permutations, there is a 1/8 chance of repeating in three tosses, and otherwise the expectation is 61/7 =~ 8.7 coin flips (6.7). This is not appreciably different from the overall expectation, so we might expect these to be fairly evenly distributed.