I asked a friend to throw a coin 100 times and record the outcome. For some reason I knew that he'd either do it or just write down a random looking sequence without ever tossing the coin. The list I got back looked random but I noticed that there was never more than three of a kind in a row.

It makes me wonder...what's the probability of (if the coin tosses are perfectly random) never getting more than three of a kind in a row in 100 tosses? Please write your reasoning also.

/Tomas

I could be wrong but here goes. Please bear in mind that my maths may be fundamentally flawed!

The first throw is irrelevant unless you're looking specifically for 3 heads or tails in a row, so there is no probability involved (unless you factor in a freak chance of landing on its edge).
The second throw has a 1:2 chance of matching the first.
The 3rd has a 1:2 chance of matching the second so 1:2 x 1:2 = a 1:4 chance of being 3 in a row. This implies that as there were 100 throws originally, he must have made the results up.

For not being 2 in a row or to throw a string of 99 specific outcomes (after the first throw), then its 1:2 x 1:2 ....99 times. This equates to 2^99 (633,825,300,114,114,700,748,351,602,688), roughly 6.3 x 10^28. Pretty long odds.

For not being 3 in a row WHEN 2 IN A ROW IS ALWAYS THROWN,every 3rd throw is 'wrong' at odds of 1:2 (as it's only this throw that is wrong). This occurs 33 times in 100 throws, so we get 1:2 x 1:2... 33 times. This equates to 2^33 (8,589,934,592), roughly 8.6 x10^8.

For not being 3 in a row at random, there's a 1:4 chance of it occuring. This occurs 33 times in 100 throws, so we get 1:4 x 1:4... 33 times. This equates to 4^33 (73,786,976,294,838,206,464), roughly 7.4 x10^18.

These figures seem a bit too long so I suspect I may have gone seriously wrong.

Regards,
Steve

Sorry if I was unclear. At some places there _was_ three in a row but _never_ more than three. The probability of there never being more than three in a row among 100 tosses was asked for, so a number between 0 and 1 should be the result.

/Tomas

No apology needed. I didn't read the question properly.

I was working in odds (a gambling habit!) and not probability.

The ODDS of being 4 of the same in a row is 1:8, so therefore the PROBABILITY is 1/8 = 0.125

For not being 4 in a row WHEN 3 IN A ROW IS ALWAYS THROWN,every 3th throw is 'wrong' at odds of 1:2 (as it's only this throw that is wrong). This occurs 25 times in 100 throws, so we get 1:2 x 1:2... 25 times for odds or 0.5 x 0.5 ...for probability. This equates to 0.5^25, roughly 0.3 x10^-7.

As for the rest, I'm still working. I'm still not sure if I'm on the right track so if anyone knows I'm wrong, please put me out of my misery!!

Regards,
Steve

Steve, I sense that you have an unusual definition of "odds". Usually it is defined as p/(1-p). In other words the odds of tossing a coin four times and getting all the same is 1:7, not 1:8. See http://mathforum.org/library/drmath/view/56706.html for example.

/Tomas

Thomas,the word in uk (ODDS) is a saying when discussing a bet(normally horse or dog racing),example its an (odds on favourite)or (what are the odds)its a cultural thing.

Tomas, I checked out your link and have been suitably educated!

I always thought odds and probability only differed in notation form but I realise now that there's is a fundamental difference.

Mike, thanks for sticking up for me but alas, I was still wrong!!

Regards,
Steve

Probability of flipping a coin 100 times and never getting
a "run" (of heads or tails) longer than 3
is roughly .0002846.

I'll explain my reasoning later since I don't have time
at the moment. If you get impatient, you can look
up "tribonacci numbers" and figure out how these numbers
relate to this problem.

Stan Alger

T(n+1) = t(n)+t(n-1)+t(n-2) connects to
The fourth one is not the same as the previous three
?

still 96 such 4-tupples

guess I don't recall my prob and stat from college 22 years ago that well.

The chance that a coin would land the same side down more than three times in a row in a hundred is so high, that the most probable sollution to your question is to think like your friend probably did:

"Eeehm, I'm not going to bother doing this..."
*starting typing random flips*
"Ehm, if I put more than three in a row it's going to look suspicious"

And there you got it

P.S. And congrats to Jonathan for going into the Eternal Order! 10000 posts, wow...

Okay, here's my reasoning.

Let's start by thinking about flipping a coin 10 times
and recording the results.

One possible outcome is HHHTTHTTTT. In terms of runs,
this can be represented by 3, 2, 1, 4. (3H, 2T, 1H, 4T)
TTTHHTHHHH would also be represented by 3, 2, 1, 4.
(3T, 2H, 1T, 4H)

HTHTHTHTHT would have a "run sequence" of 1,1,1,1,1,1,1,1,1,1.
THTHTHTHTH would have the same "run sequence."

HHHHHHHHHT would have a run seq. of 9,1. (As would
TTTTTTTTTH.)

Every ten-termed seq. of H's and T's would have a unique
"run sequence" associated with it...and every finite sequence
of positive integers whose terms summed to 10 would
represent exactly 2 different length-ten strings of H's and T's.
(One starting with a run of H's, the other starting with a run
of T's.)

If we tossed a coin 100 times, we could represent the outcome
as a run seq. consisting of positive integers which summed to 100.
Again, each outcome would be assigned a unique run seq., but each
run seq. would represent exactly two different HT outcomes.


Let's let N(n) denote the number of run seq. consisting only
of 1's, 2's, and 3's whose terms total n.

For small values of n we can compute N(n) directly.

N(1) = 1 since {1} is the only run seq. with a term total of 1.

N(2) = 2 since {1,1} and {2} are the only run seq. with a term
total of 2.

N(3) = 4 since {1,1,1}, {2,1}, {1,2}, and {3} are the only run
seq. with a term-total of 3.

N(4) = 7 since {1,1,1,1}, {2,1,1}, {1,2,1}, {1,1,2}, {2,2}, {3,1},
and {1,3} are the only run seq. containing no integer greater than three with a term-total of 4.

N(5) = 13.
{1,1,1,1,1}
{2,1,1,1}
{1,2,1,1}
{1,1,2,1}
{1,1,1,2}
{2,2,1}
{2,1,2}
{1,2,2}
{3,1,1}
{1,3,1}
{1,1,3}
{3,2}
{2,3}

What is N(100)? Well, a run seq. consisting only of 1's, 2's, and 3's
which has a term-total of 100 must start with either a 1, 2, or 3.

How many start with a 1? Since the remaining run-seq. terms must total
100-1 = 99, the answer is N(99).

Likewise, there are N(98) that start with a 2.

And N(97) that start with a 3.

Thus N(100) = N(99) + N(98) + N(97).

In general, for n>3,
N(n) = N(n-1) + N(n-2) + N(n-3).

This recursion relation, together with the "seed" values
N(1) = 1, N(2) = 2, N(3) = 4
allow us to compute N(n) for any positive integer n.

Thus N(4) = N(3) + N(2) + N(1) = 4 + 2 + 1 = 7
N(5) = N(4) + N(3) + N(2) = 7 + 4 + 2 = 13
(You can see that we worked too hard when we listed the
{1,2,3} run-seq. that totaled 5...and then counted them
in order to find N(5). We needed only do the explicit
listing followed by counting for n = 1,2,3.)

To find N(100), I wrote a short program for my TI-85.
This program recursively calculated N(100) by first
calculating N(4), N(5), N(6),...N(99).
It told me that N(100) is approximately
1.80396380815 * 10^26.

(The calculator was able to compute N(4), N(5),...N(46)
exactly. N(46) = 922,906,855,808. For N(47) and beyond,
the number of significant digits exceeded the limit of
what the calculator could display. So the figure above
for N(100) is only approximate.)

So there are 2*N(100) 100-coin-toss outcomes that have
no run (of heads or tails) longer than 3.

So the probability that Tomas requested is
2*N(100)/ 2^100 or N(100)/2^99.

According to my calculator, this probability is approx.
.0002846

I hope my explanation is clear, and my analysis is correct.

Stan Alger

Beautiful, Stan! That's _the_ way to solve it. And you are very excused for giving an approximate answer.

/Tomas