Necco Odds

[Siegmund]

If we imagine a very long roll of wafers, we can say that 1/64 of the wafers will be immediately followed by at least two identical wafers. In a 10,000-wafer roll we can safely conclude there'll be rouughly 150 matches. That's not the question the original poster asked, of course; but we can get a rough estimate by saying that we expect about 38/64 matches in a roll of 40, and then reduce this a bit more for the chance of streaks of four or two sets of three in one roll.


If you want an exact answer, yes, a recurrence relation works to count the total number of stacks of size n that have no threepeats: x[1]=8, y[1] = 0; x(i)= 7*(x[i-1]+y[i-1]); y(i) = x[i-1].

Are you sorry you asked? Out of 1329227995784915872903807060280344576 possible 40-wafer sequences, 774855372983096359078760714768858504 of them have no sequences of three identical wafers. So: if every sequence is equally likely, 51.95% of rolls have no sets, 48.05% have one or more sets.

[pzhon]

I think you made at least one and possibly two fence-post errors. You can convert a sequence of 40 flavors into a sequence of 39 change/no change events. Then, 3 identical flavors in a row is a sequence of 2 "no change" events in a row, not 3.

[gaming_mouse]

[ QUOTE ]
I think you made at least one and possibly two fence-post errors.

[/ QUOTE ]

What's a fence-post error?

[ QUOTE ]
You can convert a sequence of 40 flavors into a sequence of 39 change/no change events. Then, 3 identical flavors in a row is a sequence of 2 "no change" events in a row, not 3.

[/ QUOTE ]

I like that trick, but I'm not sure how that negates the results of my sim or of Bruce's method? Btw, since the question being asked seems to have changed over the course of the thread, I should clarify:

I calculated the chance of at least one streak of 3 licorice wafers in a row, where the chance of each wafer being licorice is 1/8, independently. I think I did that correctly, but let me know if not.

gm

[pzhon]

[ QUOTE ]
Out of 1329227995784915872903807060280344576 possible 40-wafer sequences, 774855372983096359078760714768858504 of them have no sequences of three identical wafers. So: if every sequence is equally likely, 51.95% of rolls have no sets, 48.05% have one or more sets.

[/ QUOTE ]
Your count agrees with mine, but the quotient should be 58.29% with no sets, and 41.71% with one or more sets.

Here is the distribution of the number of sets in the sense of the original poster, where a streak of 6 in a row counts as 4 sets of 3:

0: .582936
1: .285553
2: .0966622
3: .0266832
...
37: 8.42594 x 10^-35
38: 6.01853 x 10^-36

I used the following transfer matrix T:

7/8 7/8 7/8
1/8 0 0
0 x/8 x/8

The above are the coefficients of x^n in row(1,1,1) T^39 column(1,0,0).

Of course, the expected number of sets is 38/64.

[pzhon]

[ QUOTE ]
[ QUOTE ]
I think you made at least one and possibly two fence-post errors.

[/ QUOTE ]

What's a fence-post error?

[/ QUOTE ]
It means being off by 1, e.g., iterating a loop once too often in a program or failing to include the last element. If you have 10 lengths of fence for a straight fence, you don't need 10 fence posts. You need 11.

[ QUOTE ]
I calculated the chance of at least one streak of 3 licorice wafers in a row, where the chance of each wafer being licorice is 1/8, independently. I think I did that correctly, but let me know if not.

[/ QUOTE ]
I believe the original poster wanted to know about streaks of any flavor, not just licorice.

I get 6.34585% for the probability of a streak of locorice wafers of length at least 3 out of 40, by BruceZ's method and by a transfer matrix. I get 6.18469% by both methods in a roll of 39, so I think there might be an arithmetic error in your computation. Perhaps it is a round-off error.

0.0634585 = 84350775414536497477575025431563999/1329227995784915872903807060280344576

[gaming_mouse]

[ QUOTE ]

It means being off by 1, e.g., iterating a loop once too often in a program or failing to include the last element. If you have 10 lengths of fence for a straight fence, you don't need 10 fence posts. You need 11.

[/ QUOTE ]

That's a great term. I make those all the time [img]/images/graemlins/smile.gif[/img]

[ QUOTE ]

I get 6.34585% for the probability of a streak of locorice wafers of length at least 3 out of 40, by BruceZ's method and by a transfer matrix. I get 6.18469% by both methods in a roll of 39, so I think there might be an arithmetic error in your computation. Perhaps it is a round-off error.

0.0634585 = 84350775414536497477575025431563999/1329227995784915872903807060280344576

[/ QUOTE ]

I ran the sim again with 2 million trials, and got .0636. I'm sure you are right and that I made a fence post error in my application of BruceZ's method in excel.

Thanks,
gm

[gaming_mouse]

[ QUOTE ]
x[1]=8, y[1] = 0; x(i)= 7*(x[i-1]+y[i-1])

[/ QUOTE ]

Where does x[1] come from? Are there 3 flavors? (EDIT: That makes no sense. It would be 8 flavors)

Also, I don't follow the rucursion relation. Could you explain the concept? (EDIT: I'm realizing that you were solving a different problem than I was....)

[Siegmund]

Since your answer was very close to 1/8 our answer, it seems to have gotten you the right place.

The recurrence relation I was using was for counting the number of rolls in which no colour ever appears three times. Such a roll can either have the last two candies the same colour, or different.

X(1)=8 and Y(1)=0: there are 8 rolls of length one where the last candy doesn't match the previous one (there IS no previous one), and one where it does.
Y(i)=X(i-1): each sequence that ends in an unpaired candy can be extended to a longer sequences that ends in a pair in one way.
X(i)=7(X(i-1)+Y(i-1)): a new sequence ending with an unpaired candy can be made in 7 ways for any shorter sequence, whether the short sequence was paired or not.
The OP wishes to know (X(40)+Y(40))/8^40 = (X(40)+X(39))/8^40. (The Y's turn out not to contribute anything to the complexity of the recurrence relation, but it's not as easy to put into words where X(i)=7X(i-1)+7X(i-2) comes from.)

[eephus]

>>I believe the original poster wanted to know about streaks of any flavor, not just licorice.

correct. i realize now that i wasn't overly clear about that.

so, am i correct in thinking the following?

1. (1 x 1/8 x 1/8) is the chance of drawing three like-flavored wafers in a row, given one draw from a random mixture of wafers, with equal numbers of each flavor therein.

2. therefore, (1 - 1/64) is the chance of NOT drawing three etc. etc.

3. (1 - 1/64)^38 (55%) is the chance of NOT drawing three wafers under the above conditions, given 38 tries.

4. therefore, if you make rolls of 40 wafers, a ballpark estimate of the percentage of rolls w/at least one sequence of like-flavored wafers is about 45%.

5. to fully solve the problem, you have to take into account that wafers 1, 2, 39, and 40 have less impact by being different from their neighbors than do wafers 3 through 38.

is this correct?

thanks!

[BruceZ]

[ QUOTE ]
3. (1 - 1/64)^38 (55%) is the chance of NOT drawing three wafers under the above conditions, given 38 tries.

[/ QUOTE ]

This is incorrect, except as an approximation. Because the events of wafers starting a run are not independent, these probabilities cannot be multiplied.