coin toss

If you toss a coin 100 times, what's the probability of getting 5 (either
heads or
tails in a row)? 6 in a row?
How do you figure it out?

 

The answer to the last question is, "Recursively, by a Markov
conditioning argument."

Let a coin have probability p of coming up heads, 1-p of coming up
tails. If we flip the coin n times, what is the probability that
there is at least one instance of k consecutive identical toss
outcomes? We assume k>1.

In the following, the third argument i=1 indicates the event of a run
of k in the n tosses; i=0 indicates the complement of this event.

For 0 < x < k, let q(n,x,i) be the joint probability that tosses
n-x+1 through n come up heads and, if x < k-1, toss n-x comes up
tails.
For -k < x < 0, let q(n,x,i) be the joint probability of this event
given that tosses n+x-1 through n come up tails and, if x > 1-k,
toss n+x comes up heads.

We want
sum(x=1..k-2, p^x (1-p) q(n,x,1) + (1-p)^x p q(n,-x,1)) + p^(k-1)
q(n,k-1,1)
+ (1-p)^(k-1) q(n,1-k,1).


q(n,x,i) = 0 if n<k.

In the sequel, assume n>=k-1.

q(n+1,k-1,1) = p [q(n,k-1,0) + q(n,k-1,1) + q(n,k-2,1)]
q(n+1,1-k,1) = (1-p) [q(n,1-k,0) + q(n,1-k,1) + q(n,2-k,1)]
(If k=2, omit the terms with k-2 or 2-k.)

For x>1 and (i=0 or x<k-1),
q(n+1,x,i) = p q(n,x-1,i)
q(n+1,-x,i) = (1-p) q(n,1-x,i)

q(n+1,1,i) = p sum(j=1..k-1, q(n,-j,i))
q(n+1,-1,i) = (1-p) sum(j=1..k-1, q(n,j,i))


-S.J. Herschkorn
Math Tutor in Central New Jersey and Manhattan

 

Thankyou. ....now if someone will just explain to me what he just said.

 

Here's an easier way...

Let n be the number of tosses, and let x be the run length. We want the
probability that within the n tosses there is at least one run of at
least x consecutive heads or tails.

For i = 1,2,3 ... x-1, write down the numbers 2^(i-1). You have x-1
numbers written down. Calculate the next number as the sum of the
previous x-1 numbers, and repeat this until you have n numbers. Denote
the n'th (and last) number by y. The desired probability is 1 -
2*y/2^n. I THINK!!!

For x=2 and x=3 there will be a closed form solution for this
probability, but I'm not sure if there is for larger x, or how
complicated it gets. I might have a look at it...

Example. What is the probability of getting a run of at least 4 in 10
tosses (n = 10, x = 4)?

First write down the numbers:

1,2,4

The next number is 1+2+4 = 7, so now you have

1,2,4,7

The next number is 2+4+7 = 13, so now you have

1,2,4,7,13

Continue until you have 10 numbers:

1,2,4,7,13,24,44,81,149,274

The probability is 1 - 2*y/2^n = 1 - 2*274/2^10 = 0.46484375.

To answer your specific cases, I get the following results to 8 d.p.:

For n = 100, x = 5, Prob = 0.97168967
For n = 100, x = 6, Prob = 0.80682055

It helps if you use a computer!

 

Care to justify this answer? It rationale is not obvious to me.

Also, it looks like you are addressing the case of a fair coin only.

 

Correct, I assume a fair coin (which I'm pretty sure is what the OP
meant).

Let me illustrate the derivation with x = 4, and you will see how it
extends to all x.

I construct a table of the count of all the different possible
sequences of length n, such that there is no run of length 4 or
greater. I break this down by possible endings: end with TH, THH, THHH,
HT, HTT, or HTTT (no other ending is possible else you would have a run
of at least 4).

The first row, for n = 4, is easy to construct from first principles:

n TH THH THHH HT HTT HTTT
- ---- ---- ---- ---- ---- ----
4 4 2 1 4 2 1

To construct the next row we notice:

- To end on TH with n = 5 we must have ended on HT, HTT or HTTT with n
= 4 and then got H. There is only one way to get H; therefore the entry
for n = 5, TH must be 4 + 2 + 1, or 7.

- To end on THH with n = 5 we must have ended on TH with n = 4 and then
got H. Therefore the entry for n = 5, THH must be 4:

- To end on THHH with n = 5 we must have ended on THH with n = 4 and
then got H. Therefore the entry for n = 5, THHH must be 2:

And the second half of the table fills in in exactly the same way to
give:

n TH THH THHH HT HTT HTTT
- ---- ---- ---- ---- ---- ----
4 4 2 1 4 2 1
5 7 4 2 7 4 2

Now I'll continue the table for the next few rows:

n TH THH THHH HT HTT HTTT
- ---- ---- ---- ---- ---- ----
4 4 2 1 4 2 1
5 7 4 2 7 4 2
6 13 7 4 13 7 4
7 24 13 7 24 13 7
8 44 24 13 44 24 13

If we extend back to n = 2, where n = 2, 3 are "dummy" entries, you can
see that numbers in the TH column for n = 2,3,4,5,... are
1,2,4,7,13,24,... where 1,2,4 are the ascending powers of 2 that "kick
off" the sequence, and thereafter each term in the sequence is the sum
of the previous three terms.

The number in the TH column is always half the sum of the previous row,
so the same sequence 1,2,4,7,13,24,... serves to give us the half-sums
for n = 1,2,3,4,...

Let y be the n'th term in this sequence, and assume n >= 4. y is half
the total number of sequences of n tosses s.t. there is no run of
length >= 4. Therefore the total number of such sequences is 2*y. The
total number of sequences overall is 2^n, and all sequences are
equiprobable, so the probability that there are no runs of length >= 4
is 2*y/2^n, and the probability that there is at least one run of
length >= 4 is 1 - 2*y/2^n.

 

I follow what you are doing, but you have to work out some kinks. For
x=4, the answer for n=4 is 2/16 = 1/8, and the answer for n=5 is
6/32 = 3/16. (I get these considering all possible sequences of four or
five tosses.) Your formula gives 1 - 2*4 / 16 = 1/2 and 1 - 14/32 =
9/16, respectively.

 

Ah, I see now: The value for n tosses is 1 - y_(n+1) / 2^(n-1), where

y_n = 2^(n-1) for n < x
y_n = sum(k=1..x-1, y_(n-k)) for n >= x,

as you said to begin with. Very good.

 

I think you misread. For x = 4 the relevant sequence is, as stated,
1,2,4,7,13,24,...

The fourth term is 7, so the probability for n = 4 is 1 - 2*7/2^4 =
1/8.

The fifth term is 13, so the probability for n = 5 is 1 - 2*13/2^5 =
3/16.

This agrees with your answers.

 

Now that I understand your method, we can generalize it to a coin with
probability p of coming up heads. Let me revert to the use of k to
represent the length of the run of identical outcomes.

Let x(n,j) = the probability of ending up on the nth toss with a string
of exactly j heads and never having thrown k identical tosses
consecutively, 0 < j < k.
Let y(n,j) = the probability of ending up on the nth toss with a string
of exactly j tails and never having thrown k identical tosses
consecutively, 0 < j < k.
Our desired probability is 1 - sum(j=1..k-1, x(n,j) + y(n,j)).

x(k,j) = p^j (1-p)
y(k,j) = p (1-p)^j

For n >= k,
x(n+1, 1) = p sum(j=1..k-1, y(n,j))
x(n+1, j) = p x(n, j-1) for j > 1
y(n+1, 1) = (1-p) sum(j=1..k-1, x(n,j))
y(n+1, j) = (1-p) y(n-1, j) for j > 1

Thus, another way to express our answer is 1 - [x(n+1,1)/p +
y(n+1,1)/(1-p)]. Off hand, I don't see a way to simplify this recursion
as Matt did for the case of p = 1/2.

 

Incorrect. We simply want sum(x=1..k-1, q(n,x) + q(n,-x)).

This is also incorrect for i = 0. However, since I prefer Matt's
method, I will not go through the effort of coming up with the correct
formulae.

Actually, the case of k=2 is easy to treat on its own.

 

Nope, I scribbled out a few expansions and nothing immediately leapt to
my mind either. You never know with these things though!

 

Fairly obviously, for x = 2 the closed form expression for the
probability is:

1 - 1/2^(n-1)

For x = 3 it is:

1 - ((1+sqr(5))^(n+1) - (1-sqr(5))^(n+1))/(2^(2*n)*sqr(5))

And for x = 4 it is:

1 - (f(a) + f(b) + f(c))/2^(n-1)

where:

a, b and c are the three roots of x^3 + x^2 + x - 1 = 0 (two of
which are complex), and f is defined as

f(z) = 1/(z^(n+1)*(1 + 2*z + 3*z^2))

Beyond this I don't know!

 

the n'th (and last) number by y. The desired probability is 1 -

Hi. This link suggests you are very close, but slightly off.
http://mathworld.wolfram.com/Fibonaccin-StepNumber.html

Ok course, I'm not sure. A brute force on small sizes suggest the following
is correct...
[Using Mathematica 5.2]

n = 10; k = 4;

1. - FibonacciNStep[n + 2, k]/2^n

0.2451171875

n = 100; k = 5;

1. - FibonacciNStep[n + 2, k]/2^n

0.810109599196358

Hope I got it right. :>)