PDA

View Full Version : Great problem solved - original material

BruceZ
07-12-2003, 06:34 PM
A couple of months ago, someone asked for the probability of getting 3 AA in a row in 250 hands. This gave rise to the more general question which was phrased as:

Do you have the formula for "at least 1 streak of at least m occurences in n trials"? I don't. Show us yours.

This is an important problem in the theory of runs. At the time, I had given a number of approximations which were very close to the exact answer. Last year, I discovered an exact solution to the particular problem for m=2 and probability of success = ½ in terms of the Fibonacci series. Since that time I have had a project on the back burner to extend this exact solution to the general question asked above. I have now completed this project, and I have not one but two different exact closed form solutions to this problem, and I have verified unequivocally that they are both correct. Although accurate approximate solutions can be found by elementary methods, the exact solution is of a very different nature than one may initially expect, and the solution is quite elegant and beautiful. Hence I am now prepared to show you mine as requested.

To restate the problem, we want the probability P(m,n,p) of at least 1 occurrence of a run of of length at least m of an event with probability p in n trials. For the question of 3 AA in a row in 250 hands, m = 3, n=250, p=1/221. For a coin flip problem, p=1/2.

Exact closed form solution 1

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) = 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 &gt; m+1

And the initial conditions:

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

The F[k] can easily be computed and summed in Excel. For the 3 AA problem simply set:

A1 = 0
A2 = 0
A3 = 1/221^3
A4 = (220/221)*(1/221)^3
A5 = A4-220*A1/221^4
.
.
.
Copy the last formula down to cell A250. Then compute =sum(a1:a250) for the exact probability. An Excel spreadsheet is available upon request.

For 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 as derived previously, and this simplifies too:

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

Subsequent to this derivation, I have found a relatively recent reference to the Fibonacci series solution for this special case in the literature; however, I have not found the closed form exact solution to the more general problem which I have given above . There is a slight chance that I am the only one in possession of it.

Exact closed form solution 2

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+1]

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

<pre><font class="small">code:</font><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. This is called a Markov chain. Such a solution was once presented by irchans for a similar problem.

Matrix multiplication can be carried out in Excel using MMULT to produce all of the n vectors. You have to use a ctl-shift-enter sequence to define the size of the vector as explained in the help to MMULT. An example spreadsheet is available upon request.

Derivation of exact solution 1

I give here a concise derivation of the most general form of the equation, but it is not especially easy to understand the derivation in this general form. It is easiest to refer to the derivation for the special case of m=2, p=1/2, and then insert those constants into the derivation below. It may be helpful to refer to the intial thread where the Fibonacci solution was derived for the case of m=2 and p=1/2 Fibonacci solution for coin tossing (http://www.twoplustwo.com/forums/showthreaded.php?Cat=&amp;Board=probability&amp;Number=358 0&amp;page=&amp;view=&amp;sb=&amp;o=&amp;vc=1)

Remember that the view we take here is that of a death and renewal process in which we consider a population of sequences at each stage, each of which reproduces by having a success or failure appended to it, and then some of the sequences die or terminate because m in a row have been obtained. We wish to determine the number that terminate at each stage which well call t(n). The key realization is that this is equal to the number of sequences which do not end in a success m stages previous, which well call k(n-m). This is because each of these sequences may be followed by m successes, and only those sequences will terminate at stage n. o(n) are the total number of outcomes or sequences after the nth stage. Thus:

t(n) = k(n-m)

= (1-p)*o(n-m)

= [ (1-p)/p ] * [ o(n-m-1)  t(n-m-1) ]

= [ (1-p)/p ]*{ [ 1/(1-p) ]*t(n-1)  t(n-m-1) ]

= (1/p)*t(n-1)  (1/p  1)*t(n-m-1)

Since t(n) is the number of sequences that end in m successes at each stage, it remains to divide each of these by 2^n total sequences and sum these to get the final probability.

P(n,m,p) = sum{k = 1 to n} t(k)/2^k

In computing the above difference equation in Excel, the terms become so large that they are no longer representable. The following difference equation absorbs the division by 2^k.

F[k] = F[k-1]  (1/p  1)*F[k-m-1]*p^(m+1) for k &gt; m+1

With initial conditions:

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

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

Comparison of approximate and exact results

In the original thread I gave a number of approximate solutions to the problem of 3 AA in a row in 250 hands, all of varying degrees of precision and varying degrees of complexity, all of which I knew to be very useable. The lack of an exact solution led to some disparaging comments (Bruce's notion is unfortunately extremely inadequate, and from Robk Sorry Bruce, but I think you are way off on this one). I have tabulated below the results of all of the approximation methods given by me and by other posters in that thread, along with the exact answer computed by the methods described above. As can be seen, all of the approximation methods give probabilities which are quite adequate for all practical applications, and none of them are way off with the exception of the solution given by Robk which is indeed way off simply due to an error in his post which I have corrected. I have listed the corrected answer obtained from the method which he intended. Refer to Feller pp. 324-325. I used the goal seek feature of Excel to solve the cubic equation.

Approximations 3 and 4 appeared in the original thread. Approximations 1 and 2 are much more precise versions of 3 and 4 respectively which I have computed subsequent to that thread. The only difference is that the more precise versions use a different number of trials. Instead of 248, I have used 248 divided by the expected length of a trial which is 1*(220/221) + 2*(1/221)(220/221) + 3*(1/221)^3 = 248/1.004484216. These methods are both simple and very precise. I have given this method in other threads prior to this discussion, for example see the top of boxcars (http://www.twoplustwo.com/forums/showthreaded.php?Cat=&amp;Board=probability&amp;Number=154 611&amp;page=&amp;view=&amp;sb=&amp;o=&amp;vc=1). The bottom of that post is actually an early failed attempt at a more general solution which only works for m=2. This derivation should be ignored.

The inclusion-exclusion calculation is carried out to the number of terms in the original thread. The inclusion-exclusion approximation, the Feller approximation, and the computer program all give highly precise solutions correct to the nearest whole number. The exact solutions derived above are much simpler to compute than either inclusion-exclusion or the Feller approximation.

<pre><font class="small">code:</font><hr>

Method probability (%) 1 in

1.) EXACT(both methods above) <font color="red">.002287222419 43721.15242</font color>

2.) (248/1.004484216)*(1/221)^3 .002287112016 43723.26291

3.) 1(1-1/221)^3^(248/1.004484216) .002287319310 43719.30039

4.) 248/221^3 .002297602313 43523.63306

5.) 1  (1-1/221)^3^248 .002297576026 43524.13103

6.) Inclusion-Exclusion .002872000000 43721.58097

7.) Cyrus computer program .002287224379 43721.11495

8.) Robk approximation(w/error) .002248 44483.98577

9.) Feller approximation .002287222422 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
</pre><hr>

irchans
07-13-2003, 10:24 AM
Nice work Bruce. I think a general formula could be difficult to find. For the case m = 2, Mathematica gives the following formula for F

F[n] = (2^(1 - k)*p^2*(
-(1 - p - Sqrt[1 + (2 - 3*p)*p])^(-1 + k)
+(1 - p + Sqrt[1 + (2 - 3*p)*p])^(-1 + k)))/
Sqrt[1 + (2 - 3*p)*p].

For p = 1/2, that formula simplifies to

F[n] = (2^(-1 - k)*(
+ (1 + Sqrt) *((1 - Sqrt)/2)^k
- (1 - Sqrt) *((1 + Sqrt)/2)^k)/Sqrt

= 2^(-k) * Fibonacci[k-1]

as you showed a year ago.

There is another way to approach these problems using Fourier Series. I will look that up and send this problem to a friend of mine that does combinatorics.

Cheers, Irchans

Robk
07-13-2003, 08:03 PM
A few comments:

"Sorry Bruce, but I think you are way off on this one"

This was in reference to your claim that certain trials were independent (although still wrong /forums/images/icons/tongue.gif ) It was not a comment on the accuracy of your (or any) approximations. Those you gave at the time were obviously excellent, given the computer simulation data which appeared in the original thread. Anyway I'm glad it motivated you.

given by Robk which is indeed way off

It's not so bad /forums/images/icons/wink.gif

simply due to an error in his post which I have corrected

Thanks much for the correction. I am going to go take Feller out of the library because now I am curious about the derivation. I was working with my notes at the time which obviously sucked!

Carl_William
07-15-2003, 08:50 PM
Dear Bruce:

you published or print the following on the 2+2 probability forum (for the problem in question)

 A couple of months ago, someone asked for the probability of getting 3 AA in a row in 250 hands. This gave rise to the more general question which was phrased as:

Do you have the formula for "at least 1 streak of at least m occurences in n trials"? I don't. Show us yours.: (skipping down)

Method probability (%) 1 in

1.) EXACT(both methods above) .002287222419 43721.15242

5.) 1  (1-1/221)^3^248 .002297576026 43524.13103

I question the answers for method 1. I feel the probablility for at least 1 streak of at least m occurences in 250 trials should be higher in method 1 than the probability in method 5. Method 5 is the binomial probability distribution for one or more occurances of a streak of three AA being dealt out for 250 sets of three consecutive holdem hands (equivalent to 750 hands). In method 5 there is no overlap between the the first set of 3 hands and the second set of three hands (and so on). Thus method 5 (in my opinion) should have a lower probability for a streak of three or more consecutive sets of two aces.

I dont understand how to do method 1 and I dont doubt your fine work. I just think the magnitude of the answer (probability) for method 1 is too low when compared to method 5.

Where am I wrong?

Stay well

Carl

BruceZ
07-16-2003, 12:53 PM
I just think the magnitude of the answer (probability) for method 1 is too low when compared to method 5.
Where am I wrong?

First of all, there is a typo in method 5, and in method 3 as well. The numbers are correct, but the expressions should be:

method 5: 1 - (1 - 1/221^3)^248
method 3: 1 - (1 - 1/221^3)^(248/1.004484216)

The way I had it would give the probability of getting a single AA in 3 times 248 hands which would be very high. You probably still think that the exact answer of method 1 should be higher than method 5, but it is correct that it is lower.

Method 5 computes 1 minus the probability of no runs of length m or greater. The probability it computes of no runs is smaller than the exact number, so the final answer will be greater than the exact answer. The reason method 5 computes the probability of no runs smaller than exact is because it treats the probabilities of no run starting on each hand as independent and equal to 1 - 1/221^3 per hand. The exact result would be:

P(no run) = P(1)*P(2|1)*P(3|1,2)*...P(248|1,2,...247)

Where P(k) = P(run NOT starting on k) and P(k|j) = P(run NOT starting on k | run NOT starting on j).

This (exact) probability will be larger than 1 - (1/221^3)^248. For example, P(1) = 1 - 1/221^3. P(1|2) &gt; 1 - 1/221^3. The reason is that if a run DID start on hand 1, the probability of a run starting on hand 2 would be just the probability of AA on hand 4 since we already know we have AA on hands 2 and 3, and this probabity is just 1/221 &gt; 1/221^3. Thus the probability of a run starting on hand 2 given that one did NOT start on hand 1 or must be &lt; 1/221^3, and the probability of a run NOT starting on hand 2 given that a run did NOT start on hand 1 or P(1|2) would be &lt; 1/221^3 or &gt; 1 - 1/221^3. This will be true for all the terms, so the overall product in method 5 is smaller than the exact method, so it produces a probability of a run which is larger than the exact method.

I also originally thought that method 5 should produce a lower bound, but I then realized even before I derived the exact answer that it would in fact be an upper bound, and I posted this here (http://www.twoplustwo.com/forums/showthreaded.php?Cat=&amp;Board=probability&amp;Number=253 752&amp;page=&amp;view=&amp;sb=&amp;o=&amp;vc=1) .

Method 1 must give the exact answer because it gives the identical answer as the Markov matrix method which must be correct. I also ran both my formula and the Markov matrix for m=5, n=250, p=1/221 and the results were again identical.

BruceZ
07-16-2003, 01:25 PM
This was in reference to your claim that certain trials were independent (although still wrong)

That's correct, the trials are not independent; however, to a high degree of approximation we can treat them as being independent. If this were not the case, approximations 5 and even better 3 would not be close by definition. I had reworded this claim in the original thread, but it did not appear until after you had posted.

I am going to go take Feller out of the library because now I am curious about the derivation. I was working with my notes at the time which obviously sucked!

You just added q in the denominator where it should have been multiplied.

Feller derives a difference equation in a different variable than I did, but in a footnote he alludes to the fact that the classical approach derives one in the same variable that I used. I didn't notice this note until after I had done my derivation. Feller never mentions the Fibonacci solution even though he has data on coin tossings. It is possible that he was not aware of this result. From his remarks it also seems possible he had not seen the general form that I have derived here.

Feller's solution is approximate as it only uses one root of the polynomial. This root is dominant, so the approximation is a good one. To make his method exact, all of the roots must be found, and this is much more complicated. So while his footnote claims that my approach is more complicated, it is much simpler for obtaining an exact solution.

BruceZ
07-16-2003, 01:51 PM
irchans,

I think a general formula could be difficult to find. There is another way to approach these problems using Fourier Series.

My solution is general in the sense that it gives a solution for all m,n,p and all the necessary terms are straightforward to compute. By general you mean F[n] = with no more reference to F[n] (no recursion). For that you would need to take the z-tranform (or generating function) of the difference equation, solve for F(z) = 1/(mth order polynomial in z), find all the roots of the polynomial, do a partial fraction expansion, and then invert the individual terms back to the n domain to get a sum of exponentials in n. For m=2, p=1/2 the roots are [ 1 +/- sqrt(5)] /2 as you found. It turns out that the real root always dominates, and this is what Feller's solution uses.

Is this what you mean by the Fourier series method? The z-transform is a general case of the discreet Fourier tranform. This is the technique I'm very familiar with.

I take it that mathematica doesn't spit out a result for general m? No closed form solution exists for factoring a general mth order polynomial, but it is not impossible that this particular family of polynomials could have a general solution.

I have found a non-recursive solution for F using only the single real root and a single term of F[n]. It is analogous to the reduced form of the Fibonacci solution.

BTW, since you will be looking at this closely, this line of the derivation:

= [ (1-p)/p ]*{ [ 1/(1-p) ]*t(n-1)  t(n-m-1) ]

uses a substitution from previous lines. This wasn't too obvious.

-Bruce

Carl_William
07-16-2003, 03:37 PM
Please disregard my post on July 15,2003 concerning "Re: Great problem solved - original material." I have thought things over and have a new slant which I think is pertinent. I will shortly post my new slant.

thank you

Carl_William
07-16-2003, 04:39 PM
Re: Great problem solved - original material  My new slant.

Dear Bruce and others interested in these types of problems,

In elementary probability problems where the probabilities are constant (Bernoulli trials), the use of the Markoff process is not necessary. Like they say: in fixed or constant probability problems  the cards, dice, and wheel, whatever has no memory. Therefore in a set of three deals of holdem hands, the odds are fixed and never change. For the problem in question: the answer can be determined by the elementary Bernoulli trial formula of sampling with replacement:

P = comb(n,x) * p^x * (1-p)^(n-x)

Where n = 248, p =(1/221)^3, x = number of successes,
and as you posted in Method 5: Answer = 1  (1-1/221)^3^248

This model used here can be thought of as: 248 sets of three deals (or 3*248 = 744 deals)  each set taken as independent of any other set. The probability is constant so this is a valid assumption. Look at it this way: set 1 = deal 1 + deal 2 + deal 3  this is one trial; set 2 = deal 4 + deal 5 + deal 6; . ; last set 248 = deal 742 + deal 743 + deal 744. Like I am trying to say, this is valid because the cards have no memory, and simplifies to the method 5 formula: Answer = 1  (1-1/221)^3^248.

If Methods(1) are also exact, then they should calculate the same answer as method 5. As you know, the choice of 250 deals: 248 sets of 3 deals is purely arbitrary  also the selection of p(AA) = 1/221 is also arbitrary:for Answer = 1  (1-1/221)^3^248. A simple example problem with flipping a coin where two consecutive heads appears in say 4 trials could easily verify that the simple Bernoulli trial formula works. This simple problem can be enumerated on an Excel spreadsheet. I would check the boundary (end conditions for method(s) 1  maybe they are tricky to handle.

Markoff process are generally use in dynamic programming problems where the odds change with time, and recent and past history can be used to determine future actions.

This is just my opinion and hopefully I dont have too many mistakes.

Regards &amp; stay well

Carl

Carl_William
07-16-2003, 07:51 PM
Excuse my typo error:
I repeated or carried on the error  should be:

Method 5.) Answer = 1  (1-1/221^3)^248 =2.2975760259003E-05

not: 1  (1-1/221)^3^248

---------------
Re: Great problem solved - original material  My new slant. I think I understand the problem definition.

Dear Bruce and others interested in these types of problems,

In elementary probability problems where the probabilities are constant (Bernoulli trials), the use of the Markoff process is not necessary. Like they say: in fixed or constant probability problems  the cards, dice, and wheel, or whatever have no memory. Therefore in a set of three deals of holdem hands, the odds are fixed and never change. For the problem in question: the answer can be determined by the elementary Bernoulli trial formula of sampling with replacement:

P = comb(n,x) * p^x * (1-p)^(n-x)

Where n = 248, p =(1/221)^3, x = number of successes,
and as you posted in Method 5: Answer = 1  (1-1/221^3)^248
=2.2975760259003E-05

MY LOGIC IS:
This model used here can be thought of as: 248 sets of three deals (or 3*248 = 744 deals)  each set taken as independent of any other set. The probability is constant so this is a valid assumption. Look at it this way: set 1 = deal 1 + deal 2 + deal 3  this is one trial; set 2 = deal 4 + deal 5 + deal 6; . ; last set 248 = deal 742 + deal 743 + deal 744. Like I am trying to say, this is valid because the cards have no memory, and simplifies to the method 5 formula: Answer = 1  (1-1/221^3)^248.

If Methods(1) are also exact, then they should calculate the same answer as method 5. As you know, the choice of 250 deals: 248 sets of 3 deals is purely arbitrary  also the selection of p (AA) = 1/221 is also arbitrary: for Answer = 1  (1-1/221^3)^248. A simple example problem with flipping a coin where two consecutive heads appears in say 4 trials could easily verify that the simple Bernoulli trial formula works. This simple problem can be enumerated on an Excel spreadsheet. I would check the boundary (end) conditions for method(s) 1  maybe they are tricky to handle.

Markoff processes are generally used in dynamic programming problems where the odds change with time, and recent and past history can be used to determine future actions. Also, in the real world, many answers that are within 1% or 5% are adequate -- no always but usually.

These are just my opinion and hopefully I dont have too many mistakes.

Regards &amp; stay well

Carl

irchans
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
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/2^10 = 144/1024, where F 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/2^4 = 8/16 = 1/2, where F 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 /forums/images/icons/smile.gif ) 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 (http://mathworld.wolfram.com/Run.html)

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
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/2^10 = 144/1024, where F it the 12th Fibonacci number, and ALMOST NO ONE (loosely speaking) KNOWS THAT.

Including me. It's 1 - F/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/2^4 = 8/16 = 1/2

1 - F/2^4 = 1/2.

BruceZ
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.

<font color="red">1.) EXACT .002287222419 = 1 in 43721.15242</font color>

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 &gt; m+1

And the initial conditions:

F[k] = 0 for k&lt; 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><font class="small">code:</font><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.

<font color="red">2.) (248/1.004484216)*(1/221)^3 .002287345363 = 1 in 43718.80244</font color>

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.

<font color="red">3.) 1(1-1/221)^3^(248/1.004484216) .002287319310 = 1 in 43719.30039</font color>

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.

<font color="red">4.) 248/221^3 .002297602313 = 1 in 43523.63306</font color>

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

<font color="red">5.) 1  (1-1/221)^3^248 .002297576026 = 1 in 43524.13103</font color>

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

<font color="red">6.) Inclusion-Exclusion .002872000000 = 1 in 43721.58097</font color>

See this link (http://www.twoplustwo.com/forums/showthreaded.php?Cat=&amp;Board=probability&amp;Number=253 814&amp;page=&amp;view=&amp;sb=&amp;o=&amp;vc=1) for details.

<font color="red">7.) Cyrus computer program .002287224379 = 1 in 43721.11495</font color>

The method used by the program is unknown to me.

<font color="red">8.) Feller approximation .002287222422 = 1 in 43721.15236</font color>
(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
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.

<font color="red">1.) EXACT .002287222419 = 1 in 43721.15242</font color>

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 &gt; m+1

And the initial conditions:

F[k] = 0 for k&lt; 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><font class="small">code:</font><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.

<font color="red">2.) (248/1.004484216)*(1/221)^3 = .002287345363 = 1 in 43718.80244</font color>

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.

<font color="red">3.) 1(1-1/221^3)*(248/1.004484216) = .002287319310 = 1 in 43719.30039</font color>

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.

<font color="red">4.) 248/221^3 = .002297602313 = 1 in 43523.63306</font color>

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

<font color="red">5.) 1  (1-1/221^3)^248 = .002297576026 = 1 in 43524.13103</font color>

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

<font color="red">6.) Inclusion-Exclusion .00228722 = 1 in 43721</font color>

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.

<font color="red">7.) Cyrus computer program .002287224379 = 1 in 43721.11495</font color>

The method used by the program is unknown to me.

<font color="red">8.) Feller approximation .002287222422 = 1 in 43721.15236</font color>

(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
07-18-2003, 03:43 AM
<font color="red">3.) 1(1-1/221^3)*(248/1.004484216)</font color>

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

x = 1.00000092

Should be 1.000000092...

Carl_William
07-18-2003, 02:01 PM
Hi Brucez, Irchans, &amp; others:

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

Stay well

Carl

Gus
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 /images/graemlins/laugh.gif

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

BruceZ
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.