Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Reply
 
Thread Tools Display Modes
  #11  
Old 08-27-2005, 10:00 PM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default Re: Exact answer 11.7327% ? (edited)

I fixed some typos in the post below

I think it's possible to use recurrence formulas like Bruce's formaulas to get the exact answer.

Look at the 1000 hands as 900 overlapping windows of width 100.

The Probability p[n] that the nth window will have exactly 14 hands is 0.0014279740790007608. Let g[n] be the probability that the nth window has exactly 14 hands and that no previous window had 14 hands. Let r[n,i] be the probability that the nth window will have exactly 14 hands given that the ith window had exactly 14 hands. Note that r[n,i] = r[n-i] because it only depends on the difference between n and i. Then

p[n] = Sum[ g[j] * r[n-j] , {j, 1, n}].

( p is the convolution of g and r so we might be able to use Fourier Transforms to solve the problem, but I won't use those in this post. )

If we can solve this equation for g[n] then the answer to the original poster's question is:


Sum[ g[n], {n,1,900}].

Notice that r[0] = 1 so:

p[n] = Sum[ g[j] * r[n-j] , {j, 1, n}]
p[n] = g[n] + Sum[ g[j] * r[n-j] , {j, 1, n-1}]
g[n] = p[n] - Sum[ g[j] * r[n-j] , {j, 1, n-1}]
g[n] = 0.0014279740790007608- Sum[ g[j] * r[n-j] , {j, 1, n-1}].

Now we just need the sequence r[n] to compute g[n]. If n<100, r[n] is the sum over k=0,...,14 of the probability that the first n hands of a window has k pairs times the probability that the next n hands after the window have k pairs. (If n>=100, r[n] = 0.0014279740790007608.)

Code:


r[n] = Sum[ C[n, i]
*(1/17^i)*(16/17)^(n - i) * prfirst[n, i],
{i, 0, Min[n, 14]}]



The probability that the first n hands of a 100 hand window have i pairs is

Code:


prfirst[i, j] = If[ j < 14 - (100 - i),
0,
C[i, j]*C[100 - i, 14 - j] / C[100, 14]]



Using those formulas, the 110 values of r are 0.81765, 0.68107, 0.57759, 0.49818, 0.43635, 0.38746, 0.34817, 0.31607, 0.28941, 0.26693, 0.24769, 0.231, 0.21634, 0.20332, 0.19166, 0.18111, 0.17151, 0.16272, 0.15461, 0.1471, 0.14012, 0.13361, 0.12751, 0.12178, 0.11639, 0.1113, 0.10648, 0.10192, 0.09759, 0.09347, 0.08955, 0.08581, 0.08224, 0.07883, 0.07557, 0.07245, 0.06946, 0.06659, 0.06384, 0.0612, 0.05866, 0.05622, 0.05387, 0.05162, 0.04945, 0.04736, 0.04534, 0.0434, 0.04154, 0.03974, 0.038, 0.03633, 0.03472, 0.03317, 0.03168, 0.03023, 0.02884, 0.0275, 0.02621, 0.02497, 0.02377, 0.02262, 0.02151, 0.02044, 0.01941, 0.01841, 0.01746, 0.01654, 0.01566, 0.01482, 0.014, 0.01322, 0.01247, 0.01175, 0.01107, 0.01041, 0.00977, 0.00917, 0.00859, 0.00804, 0.00752, 0.00701, 0.00654, 0.00608, 0.00565, 0.00524, 0.00485, 0.00448, 0.00413, 0.0038, 0.00349, 0.0032, 0.00292, 0.00266, 0.00242, 0.00219, 0.00198, 0.00178, 0.0016, 0.00143, 0.00143, 0.00143, 0.00143, 0.00143, 0.00143, 0.00143, 0.00143, 0.00143, 0.00143, and 0.00143.

Plugging these values into the formula for g gives

g[1] = 0.00142797
g[2] = 0.000260395
g[3] = 0.000242518,
g[4] = 0.000227544, ...

Adding up the first 900 values of g gives an answer of 11.7327%. This number seems a bit higher than the simulation values so I'm not real confident about it yet.

Any comments?
Reply With Quote
  #12  
Old 08-28-2005, 12:58 PM
alThor alThor is offline
Junior Member
 
Join Date: Mar 2004
Posts: 6
Default Re: Exact answer 11.7327% ? (edited)

[ QUOTE ]
Look at the 1000 hands as 900 overlapping windows of width 100.

[/ QUOTE ]

I found no mistake in your formulas, but wouldn't use want to use 901 windows?

OTOH, I am confused by some entries in your sim post. Cell E1 should be =D1; the other 900 (or 899?) cells Ei should max cells Di and E(i-1). Is that what you actually did? Perhaps this explains the discrepancy.

alThor
Reply With Quote
  #13  
Old 08-28-2005, 02:41 PM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default Theory: 11.7447%, Excel Simulation: 10.4%, Mathematica Sim 11.3%

I agree, there are 901 windows. That changes the theoretical answer to 11.7447%.

For the Excel simulation, I agree that cell E1 should be =D1. In the other E cells I had max of cells D(i-1) and E(i-1) which I think works as well as your formula.

I reran the Excel simulation with your corrections. Among the 200,000 virtual deals there were 20,789 deals that had 14 pairs or more in a window. That simulation gives a 10.4% estimate of the probability. I wrote a simulator in Mathematica and got 22,545 deals with 14 pairs or more. That's 11.3%. Given the size of the simulations, either there is a bug one of the simulation programs and the theoretical derivation, or these random generators are not good enough. Hmm.
Reply With Quote
  #14  
Old 08-28-2005, 05:03 PM
alThor alThor is offline
Junior Member
 
Join Date: Mar 2004
Posts: 6
Default Re: Theory: 11.7447%, Excel Simulation: 10.4%, Mathematica Sim 11.3%

[ QUOTE ]
I reran the Excel simulation with your corrections. Among the 200,000 virtual deals there were 20,789 deals that had 14 pairs or more in a window. That simulation gives a 10.4% estimate of the probability.

[/ QUOTE ]

Just so we are clear, does 200k deals mean 200 million hands?

In any case, I also wrote a sim from scratch in Python. After 20k trials (i.e. up to 20 million "hands"), I got around 10.3%, which has a conf. interval size around +/- half a percent, so I believe it is below 11%.

[ QUOTE ]
I wrote a simulator in Mathematica and got 22,545 deals with 14 pairs or more. That's 11.3%. Given the size of the simulations, either there is a bug one of the simulation programs and the theoretical derivation, or these random generators are not good enough. Hmm.

[/ QUOTE ]

It is not a problem with the random generators (though with something that big, I wouldn't trust Excel completely). Perhaps we both made the same sim mistake, whatever it is. I also checked some of your numbers; I agree with your "r" values, etc. We are missing something. Oh well.

alThor
Reply With Quote
  #15  
Old 08-29-2005, 12:42 AM
DougOzzzz DougOzzzz is offline
Senior Member
 
Join Date: Dec 2004
Posts: 132
Default Re: Exact answer 11.7327% ? (edited)

I haven't tried to understand your post yet explaining your method for solving the problem

I can speak for Excel's RNG being crappy though. There are some very obvious patterns if you analyze a large sequence of randomly generated numbers. I almost always get incorrect answers when I write simulations in Excel even with millions of trials.

Still, it seems a bit strange that BruceZ's method could be so far off. I understood his method, and it makes sense. The flaw in the method also makes sense, and logically I concluded that the error would cause the odds to increase.

However the difference still seems large. I'll try to understand your method at a later time. I don't have as much mathematical training as most of you here so sometimes it's difficult for me to translate these formulas into something that makes sense to me.

I do appreciate the effort that everyone put into answering my question, though.
Reply With Quote
  #16  
Old 09-14-2005, 08:08 PM
BruceZ BruceZ is offline
Senior Member
 
Join Date: Sep 2002
Posts: 1,636
Default Re: Exact answer 11.7327% ? (edited)

I have PMed irchans about this, and he agrees with my objections.

This method has a problem similar to the one in my solution.


[ QUOTE ]

The Probability p[n] that the nth window will have exactly 14 hands is 0.0014279740790007608. Let g[n] be the probability that the nth window has exactly 14 hands and that no previous window had 14 hands. Let r[n,i] be the probability that the nth window will have exactly 14 hands given that the ith window had exactly 14 hands. Note that r[n,i] = r[n-i] because it only depends on the difference between n and i. Then

p[n] = Sum[ g[j] * r[n-j] , {j, 1, n}].

[/ QUOTE ]

For this formula to be correct, r[n,i] must be the probability that the nth window will have exactly 14 hands given that the ith window had exactly 14 hands, and given that no window previous to i had 14 hands. This latter condition will change the probability.

Further, it is not true that r[n,i] only depends only on n-i, because when the windows overlap, small values for the starting position of the first window i place different constraints on the window starting at n than larger values of i, since there would be more potential windows with 14 pairs that could start before a large value of i, and the hands in the window starting at n would be constrained to preclude this.


[ QUOTE ]
Now we just need the sequence r[n] to compute g[n]. If n<100, r[n] is the sum over k=0,...,14 of the probability that the first n hands of a window has k pairs times the probability that the next n hands after the window have k pairs. (If n>=100, r[n] = 0.0014279740790007608.)

Code:


r[n] = Sum[ C[n, i]
*(1/17^i)*(16/17)^(n - i) * prfirst[n, i],
{i, 0, Min[n, 14]}]



The probability that the first n hands of a 100 hand window have i pairs is

Code:


prfirst[i, j] = If[ j < 14 - (100 - i),
0,
C[i, j]*C[100 - i, 14 - j] / C[100, 14]]

[/ QUOTE ]

Because of the conditional issue discussed above, all C[100,14] do not have the same probability when the window starting at n overlaps with the first window. In this case, arrangements which put more pairs at lower values of n would be less likely, since these arrangements are constrained to preclude a window of 14 starting before the first window. The C[i, j]*C[100 - i, 14 - j] would be similarly constrained.
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 01:42 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.