fignewton

Four-in-a-row (or more) of the same answer letter has never appeared in the math portions of all the QAS exams since 2005. Not sure about the CR and writing sections, however. Lots of three-in-a-row.

The math answer letters (using the same sample above) are consistent with a uniform p=0.2 distribution for five outcomes.

pckeller

So here is a related probablilty challenge: If you flip a coin 100 times, what is the probability that you get at least one run of 5 heads in a row? Or if you prefer, what is the probability of getting no such runs?

I believe that this is a hard question, but sometimes probability questions seem hard until you see how to crack them. But unless I am missing something obvious, this is a lot harder than an SAT question. Anybody?

[To be clear: I do NOT have a solution to this challenge...if i come up with something, I'll post it.]

rspence

@pckeller that's more of an AIME-level question. I think you can do it by trying small cases (5,6 coins) then generalizing to 100. This should work because, for the n+1-th coin flip, you only need to check that the {n-3, ..., n+1}th coin flips do not have all heads or all tails.

ameliab12

@pckeller the probability of 5 heads in a row is (1/2)^5=1/(2^5)=1/32

As for the SAT randomness question, remember that the sequence ABCD is just as unlikely as BBBB, which is just as unlikely as ADBA. You only notice when there are 4 in a row because it's so obvious, but it's no less likely than the ADBA sequence that you'd never glance twice at.

rspence

@ameliab12 you're flipping 100 coins. Not 5. Question's a little more complicated...

Kyrix1

@rspence
I've been thinking about that problem since yesterday, and imo it's a bit too hard for AIME, since I can't find any way to solve it apart from massive (and I mean MASSIVE) amounts of casework. I thought about balls and urns, but then we have 5 in a row, not 2, and the fact that we have 5 answer choices also complicates this.

^watch though, my logic is probably flawed somewhere and there's a really simple way to do this somehow

ameliab12

Sorry about that, I guess I wasn't paying enough attention when I read it.

rspence

I think I have a solution...please correct me if I'm wrong.

Denote by A_n the number of strings of n H,T with no 5-in-a-row. For example,

A_m = 2^m where 1 <= m <= 4
A_5 = 30
A_6 = 58
A_7 = 112 (done by brute-forcing a bit)

Suppose we know A_5, ..., A_k. We wish to find A_{k+1}. If you treat the k+1 coin flips as a string of k flips followed by the k+1th flip, we can say that A_{k+1} = 2A_k.

However we have to subtract the number of (k+1)-sequences that end with five of the same type. Here, we only need to consider (k+1)-sequences ending in ...THHHHH or ...HTTTTT (if it ends in HHHHHH we wouldn't have counted it in the first place).

This is equivalent/bijective to finding the number of (k-4)-sequences ending in T, plus the number of (k-4)-sequences ending in H (since we are adding HHHHH or TTTTT). However these two must add up to A_(k-4).

Therefore, we have the recursion A_(k+1) = 2A_k - A_(k-4) for k >= 5. We can check this because

k=5 --> A_6 = 2A_5 - A_1 --> 58 = 2(30) - 2
k=6 --> A_7 = 2A_6 - A_2 --> 112 = 2(58) - 4

This recurrence can be solved using the characteristic polynomial x^5 - 2x^4 + 1 = 0.

Kyrix1

^this.
*facepalm*
Never thought of using recursion. Nice. I read up to about half of it, understood the rest implicitly. Although, you'd probably need a computer to solve this up to 100.

AND we also have 5 different answer choices rather than 2. I'm pretty sure that this is remedied very easily by taking the formula instead to be A_(k+1) = 5A_k - A_(k-4), and using 5^m rather than 2^m at the very beginning for m <= 4.

rspence

Yeah, with 5 answer choices you'll have much bigger numbers (although the characteristic polynomial should be similar).

I don't really feel like solving x^5 - 2x^4 + 1 = 0 without a computer. x = 1 works, but there are four other roots. Clearly, the probability is (A_100)/(2^100) (or 1 minus that if you're looking for 5-in-a-row).

Basically, the probability of obtaining a 5-in-a-row increases as the number of coin flips increases. Intuitively, it should converge to 1.

pckeller

OK, so I was right about one thing: it's a much harder problem than it looks like...

Check out this forum:

Math Forum - Ask Dr. Math

And in particular, this quote:

"I'm afraid if you want the full theory behind the approximate solution
shown above you will need to study 'Recurrent Events and Renewal
Theory' in books like that by William Feller. The treatment requires a
knowledge of probability-generating functions, solution of recurrence
relations, and the theoretical application of Normal approximations
for large n. It covers about 23 pages in the Feller book and cannot be
reproduced here."

He then goes on to describe a difficult method for exact solutions -- and RSpence had the right flavor (I think)!

Since that math is over my head, I think my next move would be to write a computer simulation and let it run a few million trials.

And I guess we can stop worrying about whether this will be on the SAT...

rspence

Yeah, a question like this definitely won't appear on the SAT. It might be in the #12-15 range on AIME, provided that the recursion isn't a 5th-degree polynomial.

An SAT-level question could be, "A coin is flipped 100 times. What is the probability of obtaining at least two heads or two tails in a row?" That one should take seconds to solve.

Kyrix1

^ (2^99-1)/(2^99)?

rspence

@Kyrix1, yep.

pckeller

^^ ...still too hard to be an SAT question. Change it to 5 flips and MAYBE it would be on the SAT2 level 2...