

Three Heads in Row on Flips
Name: Yves
Status: student
Grade: 912
Location: OH
Country: USA
Date: Fall 2011
Question:
Hello In my computer science 1 class today, we were generating sequences of random numbers to generate coin flips. Then he decided to give us a question to ponder on, and test at home if we wish: First he gave us a random sequence of 10 heads/tails coin flips(h heads, t tails) {h,t,t,h,h,h,t,h,t,t} He pointed out that, in this case, the **Longest chain of heads in a row** was 3. Then he asked us, what would you **theoretically** expect the length of the longest chain of heads to be in a random sequence such as this? Many of my classmates (considering the individual probabilities) said 1. To point out how wrong this is, he had us imagine a sequence of one million flips. There must be some way to calculate the theoretically expected longest chain of heads in a row. He prompted guesses, and students guessed anywhere from 5 to 500. Later, I went home and considered this problem. I could not figure it out, but I wrote a program to test it. I randomly created sequences (length=10), each element containing a 0 or a 1. I looped this 10000 times stored the length of the longest chain of 0's in the sequence into an array, and averaged the results. I tried the test several times and consistently came to about 2.49. Could someone explain to me how I would go about solving this problem? I have taken up to algebra II and am currently in precalculus, not yet taken statistics.
Replies:
If it helps with the explanation, here is the code I used for the
program (it is written in Ruby): CODE BELOW class
Probability #running this function yields the average of expected
longest chains of zeros #for a sequence of length *length* and
repeats in *iterations* times. def self.findRowLengths(length,
iterations) lengthResults=[] iterations.times do randomNums=[]
zerosInRow_f=0 zerosInRow_i=0 length.times do randomNums << rand(2)
end randomNums.each do aNumber if aNumber==0 then zerosInRow_i+=1
else if zerosInRow_i > zerosInRow_f then zerosInRow_f=zerosInRow_i
end zerosInRow_i=0 end end lengthResults << zerosInRow_f end
avg=0.0 lengthResults.each do aResult avg+=aResult end avg/=lengthResults.length return avg end end
Yves,
Your question is both difficult and very interesting. The difficult
part of the question is when the instructor says
"theoretically". If you run the test out millions and billions and
trillions of flips, you can potentially see very long runs of 'all
heads' or 'all tails'.
Your idea to use a computer program to build the data is great,
especially when you think about actually flipping a coin 10,000 or more times.
I would go about using statistics to solve this problem by utilizing
what is called the Standard Deviation. First, I would covert my
data of heads and tails to data of 'length of run' where 3 heads in
a row is the same as 3 tails in a row (since the actual outcome is
not important). That data should plot on what is called a normal or
bell curve. The calculation of Standard Deviation is one that looks
at how 'spread out' the data is from the central point or average.
Depending on what you and your teacher would consider "theoretically
possible" you can then calculate what a spread of 2 Standard
Deviations is (2 being one SD above average and one SD below
average), what the spread of 4 SD is, and what the spread of 6 SD
is. The values within 2 SD will be 68% of all possible
outcomes. The values within 4 SD will be 95% of all outcomes. The
values within 6 SD will be 99.7% of all outcomes.
Once you have decided what "Theoretically possible" is (I vote that
6 SD or 99.7% should be your number), whatever the value of 3 SD
above average (which is the upper limit of your 6 SD range) would be
the longest run you would ever expect to see.
Ian Farrell
Click here to return to the Mathematics Archives
 
Update: June 2012

