Great problem solved - original material - Page 2

irchans · #11 07-16-2003, 11:23 PM

Hi Carl,
I am pretty sure that solution 5 is not 100% correct. We can write approximation 5 as

"prob of 3 sequential successes in n tries"
~= 1 - (1 - q^3)^(n-2)

where q is the probability of a single success. To show why this is not 100% correct, consider the case where n = 4. Then then the solution 5 approximation gives

approximation 5 of "prob of 3 sequential in 4 tries"
~= 1 - (1 - q^3)^2 = 2*q^3 - q^6.

But "prob of 3 sequential successes in 4 tries" can be computed directly. It is the sum of the probabilities of the following 3 cases: SSSF, FSSS, SSSS where S is success and F is fail. That sum is

"prob of 3 sequential successes in 4 tries"
= pr(SSSF) + pr(FSSS) + pr(SSSS)
= (1-q)*q^3 + (1-q)*q^3 + q^4
= 2*q^3 - q^4

Notice that the q^4 term is in the correct answer, but approximation 5 has a q^6 term there.

This problem is much trickier than it first appears. It is tempting to assume that the probability of getting m sequences of 3 in n tries is

Combin(n-2, m)* p^m*(1-p)^(n-2-m),

where p is the probability of 3 sequential successes, but that formula is only correct under the assumption of independence which does not hold here.

Cheers,
Irchans

BruceZ · #12 07-17-2003, 02:04 AM

Argh! You fell into the standard trap of thinking this is an elementary problem. It looks like it should be, but it is certainly not.

We do not have 3*248=744 independent hands. We only have 250 hands all together, and the trials overlap. A run could start on hand 1 or it could start on hand 2. Clearly these are not independent. Whether or not a run starts on hand 1 changes the probability of one starting on hand 2. I have shown this in detail in my reply above. When you are talking about runs, the process absolutely has memory. That is why there are 4 states in the Markov state machine. Also, who says there are 248 trials? That would only be the case if you assume the first 247 trials are all failures. The number of trials depends on the results, so these are in no way Bernoulli trials. Method 3 goes a long way towards correcting for this by taking the average number of trials which is 248/1.004484216, but even this is an approximation, albeit a very good one.

If you ask elementary students of probability "what is the probability of getting 2 heads in a row in 10 flips of a fair coin", most would think that this is an elementary problem. Actually, the exact answer obtained by my advanced methods happens to be be F[12]/2^10 = 144/1024, where F[12] it the 12th Fibonacci number, and ALMOST NO ONE (loosely speaking) KNOWS THAT. For those who don't know, the Fibonacci numbers are 1,1,2,3,5,8,13,21,34,55,89,144,... where each number in the sequence is the sum of the two numbers preceding it.

Your example of 4 coin flips is a good one because you happened to pick one of the few examples where the Bernoulli equation fails miserably. What is the probability of getting 2 heads in a row in 4 flips of a fair coin? By my method, the answer is F[6]/2^4 = 8/16 = 1/2, where F[6] is the 6th Fibonacci number = 8. To verify this, just write out all 16 possibilities and note the ones where we get a run of 2 heads:

0. TTTT
1. TTTH
2. TTHT
3. TTHH - run
4. THTT
5. THTH
6. THHT - run
7. THHH - run
8. HTTT
9. HTTH
10. HTHT
11. HTHH - run
12. HHTT - run
13. HHTH - run
14. HHHT - run
15. HHHH - run

There are 8 sequences that have runs, and since each of the 16 sequences are equally likely, the probability of a run is 8/16 = 1/2 as I predicted. Now let's see what the Bernoulli approximation gives us:

1 - (1-1/2^2)^3 = 57.8%

Pretty far from 1/2 isn't it?

All of the methods I gave in my table other than the 1st method labeled "EXACT" are only approximations. It is just that the approximations are ALMOST always extremely close to the exact answer, especially methods 2 and 3. The exact solution requires sophisticated techniques that come under the heading of renwal theory. If elementary solutions were possible, I would not have spent a year of my life on the problem (I did do other things [img]/forums/images/icons/smile.gif[/img] ) and Feller would not have presented a sophisticated approximate solution for runs of coin flips using partial fraction expansion.

Here is a good link about the theory of runs (as well as a world of other things):

runs from mathworld.com

If you have trouble viewing the equations, in internet explorer hold the ctl key and click reload, or clear your cache. I believe the formula they give for R2(n) has an error. The 2^n+1 should be 2^n. This is a fantastic site, but I have found a number of little errors in the short time I've been reading it. I will eventually add my own general formula to this page since it is not there now.

BruceZ · #13 07-17-2003, 02:38 AM

If you ask elementary students of probability "what is the probability of getting 2 heads in a row in 10 flips of a fair coin", most would think that this is an elementary problem. Actually, the exact answer obtained by my advanced methods happens to be be F[12]/2^10 = 144/1024, where F[12] it the 12th Fibonacci number, and ALMOST NO ONE (loosely speaking) KNOWS THAT.

Including me. It's 1 - F[12]/2^10 = 85.9%. Bernoulli gives 1 - (1-1/2^2)^9 = 92.5%.

Same correction for 4 flips, but it didn't matter since the probability was 1/2:

What is the probability of getting 2 heads in a row in 4 flips of a fair coin? By my method, the answer is F[6]/2^4 = 8/16 = 1/2

1 - F[6]/2^4 = 1/2.

BruceZ · #14 07-17-2003, 07:59 PM

Irchans has pointed out a couple of typos in my table of methods. Method 2 is much more accurate than I posted. I also had a parentheses problem in the Feller method, though the number was correct. Here is an updated table with explanations added. This can as a summary of a number of methods of probability calculation in general.

The general problem is to compute the probability of a run of length at least m of an event with probability p in n consecutive trials. The prototype problem for which the numerical answers have been computed below is the probability of being dealt 3 AA in a row in 250 hands. For this prototype problem, m=3, n=250, p=1/221.

1.) EXACT .002287222419 = 1 in 43721.15242

These exact answers were obtained by two different methods. The first is a new method which was derived:

P(m,n,p) = Sum{k = 1 to n} F[k]

Where F[k] is given by the recurrence relation:

F[k] = F[k-1] - (1/p - 1)*F[k-m-1]*p^(m+1) for k > m+1

And the initial conditions:

F[k] = 0 for k< m
F[m] = p^m
F[m+1] = (1-p)*p^m

The second method is to use the method of Markov chains:

The probability P(m,n,p) of at least 1 occurrence of a run of length at least m of an event with probability p in n trials is given exactly by:

P(m,n,p) = v[m] (last element)

Where v is an m+1 dimensional vector given by the m+1 x m+1 matrix product:

<pre>code:<hr>
[ 1-p 1-p 1-p . 1-p 0 ] ^n [ 1 ]
v = | p 0 0 . 0 0 | | 0 |
| 0 p 0 . 0 0 | * | 0 |
| 0 0 p . 0 0 | | 0 |
| … . … | | … |
[ 0 0 0 . p 1 ] [ 0 ]
</pre><hr>
The matrix represents the transition probabilities between m+1 states. The states are 0 in a row, 1 in a row…up to m in a row having been obtained. The columns of the matrix represent the current state, and the rows represent the next state.

2.) (248/1.004484216)*(1/221)^3 .002287345363 = 1 in 43718.80244

This approximation assumes that the runs are mutually exclusive, meaning that it overcounts the times we get more than 1 run, and it multiplies the average number of trials by the probability of a run on any given trial which is (1/221)^3. This is an accurate approximation because the probability of more than one run is very low. Multiplying by the average number of tries is also only approximately correct.

The average length of a trial is 1*(220/221) + 2*(1/221)*(220/221) + 3*(1/221)^3 = 1.004484216. The average number of trials is 248 divided by the length of a trial.

3.) 1–(1-1/221)^3^(248/1.004484216) .002287319310 = 1 in 43719.30039

This approximation assumes that the probabilities of a run starting on each hand are independent. This approximation is accurate because the probability of a run starting on any hand is low, therefore the probability of a run starting on two different hands is approximately equal to the product of the probabilities of runs starting on the individual hands.

The average number of trials is computed as in method 2. The probability of obtaining a run on each of these trials is then raised to this power. This is the probability of NOT getting any runs, which is then subtracted from 1.

4.) 248/221^3 .002297602313 = 1 in 43523.63306

This is the same as method 2 except that the number of trials taken to be simply 248.

5.) 1 – (1-1/221)^3^248 .002297576026 = 1 in 43524.13103

This is the same as method 3 except that the number of trials is taken to be simply 248.

6.) Inclusion-Exclusion .002872000000 = 1 in 43721.58097

See this link for details.

7.) Cyrus’ computer program .002287224379 = 1 in 43721.11495

The method used by the program is unknown to me.

8.) Feller approximation .002287222422 = 1 in 43721.15236
(Robk method corrected)
1 – (1 - (1/221)*x) / [ (4 – 3x)(220/221)*x^251 ]
where x is the real root of (220/221)*x*[ 1 + (1/221)*x + (1/221)^2*x^2 ] = 1
x = 1.00000092

BruceZ · #15 07-17-2003, 08:58 PM

I forgot to fix the typos that I fixed earlier. Here is a complete update, so you can ignore the above post. I've also added the inclusion-exclusion explanation inline.

This can serve as a summary of a number of probability calculation methods in general.

The general problem is to compute the probability of a run of length at least m of an event with probability p in n consecutive trials. The prototype problem for which the numerical answers have been computed below is the probability of being dealt 3 AA in a row in 250 hands. For this prototype problem, m=3, n=250, p=1/221.

1.) EXACT .002287222419 = 1 in 43721.15242

These exact answers were obtained by two different methods. The first is a new method which was derived:

P(m,n,p) = Sum{k = 1 to n} F[k]

Where F[k] is given by the recurrence relation:

F[k] = F[k-1] - (1/p - 1)*F[k-m-1]*p^(m+1) for k > m+1

And the initial conditions:

F[k] = 0 for k< m
F[m] = p^m
F[m+1] = (1-p)*p^m

For the special case of m=2 and p=1/2, this reduces to

P(2,n,1/2) = sum{k = 2 to n} F[k-1]/2^k

Where F[k] is the Fibonacci series, and this can also be written:

P(2,n,1/2) = 1 - F[n+2]/2^n

The second method is to use the method of Markov chains:

The probability P(m,n,p) of at least 1 occurrence of a run of length at least m of an event with probability p in n trials is given exactly by:

P(m,n,p) = v[m] (last element)

Where v is an m+1 dimensional vector given by the m+1 x m+1 matrix product:
<pre>code:<hr>
[ 1-p 1-p 1-p . 1-p 0 ] ^n [ 1 ]
v = | p 0 0 . 0 0 | | 0 |
| 0 p 0 . 0 0 | * | 0 |
| 0 0 p . 0 0 | | 0 |
| … . … | | … |
[ 0 0 0 . p 1 ] [ 0 ]
</pre><hr>
The matrix represents the transition probabilities between m+1 states. The states are 0 in a row, 1 in a row…up to m in a row having been obtained. The columns of the matrix represent the current state, and the rows represent the next state.

2.) (248/1.004484216)*(1/221)^3 = .002287345363 = 1 in 43718.80244

This approximation assumes that the runs are mutually exclusive, meaning that it overcounts the times we get more than 1 run, and it multiplies the average number of trials by the probability of a run on any given trial which is (1/221)^3. This is an accurate approximation because the probability of more than one run is very low. Multiplying by the average number of tries is also only approximately correct.

The average length of a trial is 1*(220/221) + 2*(1/221)*(220/221) + 3*(1/221)^3 = 1.004484216. The average number of trials is 248 divided by the length of a trial.

3.) 1–(1-1/221^3)*(248/1.004484216) = .002287319310 = 1 in 43719.30039

This approximation assumes that the probabilities of a run starting on each hand are independent. This approximation is accurate because the probability of a run starting on any hand is low, therefore the probability of a run starting on two different hands is approximately equal to the product of the probabilities of runs starting on the individual hands.

The average number of trials is computed as in method 2. The probability of obtaining a run on each of these trials is then raised to this power. This is the probability of NOT getting any runs, which is then subtracted from 1.

4.) 248/221^3 = .002297602313 = 1 in 43523.63306

This is the same as method 2 except that the number of trials taken to be simply 248.

5.) 1 – (1-1/221^3)^248 = .002297576026 = 1 in 43524.13103

This is the same as method 3 except that the number of trials is taken to be simply 248.

6.) Inclusion-Exclusion .00228722 = 1 in 43721

Using inclusion-exclusion to do the dirty work for us: 248*(1/221)^3 counts all sequences of 3 or more, but it counts all sequences of 4 twice, sequences of 5 3 times etc. In addition, it counts all times we get 2 or more distinct sequences of 3 or more at least twice. We must subtract these cases. If we say the probability of sequences of 4 or more is 247*(1/221)^4, this over counts these sequences, but that's OK because we are going to subtract it, and we are now finding a lower bound. Later we will get an upper bound, and then show how these can be made as tight as you please. For 2 or more non-overlapping sequences, if one sequence is 3 long, then the other non-overlapping sequence has a maximum of 244 places it can start, so the maximum number of places the two sequences can start is C(245,2), and the probability is less than C(245,2)*(1/221)^3^2. Note that this allows the sequences to be longer than 3. So putting it together we get a lower bound of:

248*(1/221)^3 - 247*(1/221)^4 - C(245,2)*(1/221)^3^2 = 0.00228722218%.

This is even closer to the computer result. One more iteration produces a very tight upper bound:

248*(1/221)^3 - 247*(1/221)^4 - C(245,2)*(1/221)^3^2 + 246*(1/221)^5 + C(253,2)*(1/221)^4^2 = .002287230915%

So the answer lies between .00228722218 and .002287230915. Further iterations will narrow this range as tightly as you like.

7.) Cyrus’ computer program .002287224379 = 1 in 43721.11495

The method used by the program is unknown to me.

8.) Feller approximation .002287222422 = 1 in 43721.15236

(Robk method corrected)
1 – (1 - (1/221)*x) / [ (4 – 3x)(220/221)*x^251 ]
where x is the real root of (220/221)*x*[ 1 + (1/221)*x + (1/221)^2*x^2 ] = 1
x = 1.00000092

BruceZ · #16 07-18-2003, 03:43 AM

3.) 1–(1-1/221^3)*(248/1.004484216)

Should be 1–(1-1/221^3)^(248/1.004484216)

x = 1.00000092

Should be 1.000000092...

Carl_William · #17 07-18-2003, 02:01 PM

Hi Brucez, Irchans, & others:

Thanks for your time and appreciated contributions to the 2PLUS2 probability forum.

Stay well

Carl

Gus · #18 07-30-2003, 06:57 AM

yesterday playing a heads-up match on stars...

dealt 88 as my first hand
dealt 88 again about 10 hands later
then another 10 hands later...
dealt 88 three times in a row

probabilities are irrelevant at that point. The only thing that matters is that 8 is the lucky number in Chinese: I did won the match [img]/images/graemlins/laugh.gif[/img]

I'll try to dig out the exact sequence of hands I got on this one from the hand history

BruceZ · #19 07-30-2003, 01:51 PM

probabilities are irrelevant at that point

That's correct, after the fact they are always irrelevant. They would only be relevant if you had predicted this would happen before it did. Now when you can do *that*, you will really have a rare event to write about. Otherwise, what you observed was no more unusual than any other sequence of hands you might have gotten. They only appear unusual because our minds are wired to notice it, but it's all an illusion.