Documents

Royal Drought

Categories
Published
of 5
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Related Documents
Share
Description
calculation of royal flush possibilities
Transcript
  Problem:  A player plays video poker. The probability of hitting a royalflush on any hand is  p . What is the probability that in  n  hands there will beno “drought” of   d  consecutive hands without a royal flush? Solution 1.  Assume that the player plays at a constant speed, and choosethe unit of time such that expected number of royal flushes per unit timeis 1.Let  X  i  be the time of the  i th royal flush, we can model this with the jumptimes of a homogeneous Poisson process with parameter 1. We can consider X  i  ( i  = 1 , 2 , 3 ,... ) as a sequence of random variables such that  X  1 ,  X  2 − X  1 , X  3 − X  2 , etc., are independent exponentially distributed random variableswith parameter 1.The question can be restated in these term as follows. Given  k  and  x ,what is the probability that  X  1 ,  X  2 − X  1 ,  ... ,  X  m − X  m − 1  and  x − X  m  areall at most  k , where  X  m  is the largest  m  such that  X  m  < x ? (In the srcinalquestion,  d  = 200000,  n  = 1000000,  p  = 1 / 40391, so  k  = 200000 / 40391, x  = 1000000 / 40391.)Let this probability be  f  ( x ). Clearly  f  ( x ) = 1 if 0 ≤ x ≤ k . If   x > k , thenconsider  X  1 . We must have  X  1  ≤  k , and then  X  i − X  i − 1  ( i  = 2 , 3 ,...,m )and  x − X  m  must all be at most  k , which has probability  f  ( x − X  1 ). Thisgives the following equation for  f  ( x ) if   x > k : f  ( x ) =    k 0 e − t f  ( x − t ) dt.  (1)By using the Dirac  δ  -function, this can be rewritten in a form valid for all  x : f  ( x ) =    k 0 e − t ( f  ( x − t ) +  δ  ( x − t )) dt.  (2)(The  δ  -function is not a “real” function, it is a so-called generalized functionor distribution. It can be considered as a notational convenience, it is definedby the property that    ∞−∞ g ( x ) δ  ( x ) dx  =  g (0) for any function  g . In the aboveequation it adds  e − x to the right-hand side if 0  ≤  x  ≤  k  to make it correctfor all  x >  0.)The Laplace transform  L ( g ) of a function  g ( t ) defined on [0 , ∞ ) is L ( g )( s ) =    ∞ 0 g ( t ) e − st dt. 1  Let  h ( x ) =  e − x if 0 ≤ x ≤ k , and 0 otherwise. Then the right-hand side of (2)is the convolution of   h ( x ) with  f  ( x ) +  δ  ( x ), and it is a well-known propertyof Laplace transforms that the Laplace transform of the convolution is theproduct of the Laplace transforms of the factors.. Hence we obtain L ( f  ) = L ( h )( L ( f  ) + L ( δ  )) . L ( δ  ) = 1 and  L ( h ) = 1 − e − k (1+ s ) 1 +  s  . We can solve for  L ( f  ), L ( f  ) =  L ( h )1 −L ( h ) =  − 1 +  e k (1+ s ) 1 +  e k (1+ s ) s .  (3)The middle expression can be expanded into a power series, so  L ( f  ) = ∞  r =1 [ L ( h )] r .  The Laplace transform converts convolutions to products, there-fore by inverting it we get  f  ( x ) = ∞  r =1 ∗ r h ( x ) ,  where  ∗ r h ( x ) is the  r -foldconvolution of   h  with itself. This seems to be the most explicit form of   f  ( x )but it does not appear to be useful for calculations.Instead of an exact form we need to find an approximation. The asymp-totic behaviour of   f  ( x ) as  x  → ∞  is determined by the poles of   L ( f  ), theplaces where L ( f  ) is not defined because the denominator is 0. Both real andcomplex values need to be considered. Near a real pole  s  =  a ,  L ( f  ) behaveslike  A/ ( s − a ) for some constant  A , and this corresponds to a term  Ae ax in f  ( x ). Complex poles come in conjugate pairs,  b ± ci , and their joint effect isa term of the form  e bx ( α cos( cx ) +  β   sin( cx )).We need to find where the denominator of  L ( f  ) vanishes. 1+ e k (1+ s ) s  = 0cannot be solved for  s  using standard functions. It can be rearranged to theform kse ks = − ke − k .  (4) s  = − 1 is clearly a solution, but there is no pole there unless  k  = 1, becausethe numerator of   L ( f  ) also vanishes. There is a function called productlog,sometimes denoted by  W  , which is the inverse of   ze z , so that it satisfies z   =  W  ( z  ) e W  ( z ) . Let a  =  W  ( − ke − k ) k , 2  where we are using the non-standard convention that out of the two possiblereal values of   W   we take the one not equal to − k , unless  k  = 1, in which casethe only possible value is  − 1.  s  =  a  and  s  =  − 1 are the only real solutionsof 1 +  e k (1+ s ) s  = 0 and  L ( f  ) has a pole at  s  =  a .If   k  = 1 then  a  = − 1, if   k   = 1, then  k  can be expressed in terms of   a  as k  =  − ln( − a )1 +  a . For practical purposes  a  can be calculated by solving this equation numeri-cally to the required accuracy.We now claim that  f  ( x ) is asymptotically equal to  Ae ax for some  A . Theonly real pole of   L ( f  ) is at  s  =  a , if the dominant term of   f  ( x ) came from apair of complex poles, then it would be of the form  e bx ( α cos( cx )+ β   sin( cx )),but since it oscillates and changes sign, it cannot be the dominant term in f  ( x ) which is positive and monotonically decreasing. (This might also followfrom certain properties of the complex values of the  W   function, which maybe known to people who deal with it more often than I do.)The coefficient  A  can be determined as A  = lim s → a ( s − a ) L ( f  )( s ) = lim s → a ( s − a )( − 1 +  e k (1+ s ) )1 +  e k (1+ s ) s . If   k   = 1, L’Hˆopital’s rule gives A  = (1 +  a ) 2 1 +  a − a ln( − a ) = 1 +  a 1 +  ak, while if   k  = 1, L’Hˆopital’s rule needs to be applied twice to get  A  = 2.Therefore if   k   = 1, f  ( x ) ≈  1 +  a 1 +  ake ax , while if   k  = 1, f  ( x ) ≈ 2 e − x . Summary Let  p  be the probability of the royal flush,  d  the length of the “drought”,  n the total number of hands played.3  1. Set  k  =  dp ,  x  =  np .2. If   k  = 1 then let  a  = − 1, otherwise find  a  such that  k  = − ln( − a ) / (1+ a ).( a  is a negative number, if   k >  1 then  − 1  < a <  0, if   k <  1 then  a <  − 1,and  a  needs to be calculated to high accuracy.)3. If   k  = 1, then let  A  = 2, otherwise let  A  = (1 +  a ) / (1 +  ak ).4. The probability of no “drought” of length  d  in  n  hands is approximately Ae ax .In the srcinal problem,  k  = 200000 / 40391 = 4 . 9516,  x  = 1000000 / 40391 =24 . 758. Hence  a  =  − 0 . 00733363,  A  = 1 . 03007, and the probability of no“drought” is  f  ( x ) ≈ 0 . 859042, and the probability of there being a“drought”is 1 − f  ( x ) ≈ 0 . 140958. Solution 2. Let  b n  be the probability that in  n  hands of video poker there is no royalflush “drought” of length  d .  b 0  =  b 1  =  ...  =  b d − 1  = 1, and for  n  ≥  d , b n  =  p d  i =1 (1 −  p ) i − 1 b n − i , this is the discrete equivalent of (1).Let φ ( x ) =  x d −  p d  i =1 (1 −  p ) i − 1 x d − i =  x d +1 − x d +  p (1 −  p ) d x − (1 −  p )  . It can be verified that  φ ( x ) has no multiple roots, so the exact formula isof the form  b n  = d  i =1 α i x ni  , where the  x i  ( i  = 1 , 2 ,...,d ) are the roots of thecharacteristic equation  φ ( x ) = 0.The coefficients can be determined by using Joshua Green’s idea from http://www.princeton.edu/~jvgreen/RandomEvent.pdf  as α i  = (1 −  p ) d φ  ( x i )(1 − x i ) .φ ( x ) has a root of maximum modulus close to but slightly less than 1,call it  x 1 . For large  n , all the terms in  b n  apart from  α 1 x n 1  are negligible, and b n  ≈ α 1 x n 1  = (1 −  p ) d x n 1 φ  ( x 1 )(1 − x 1 ) . 4

OM 2

Jul 23, 2017

Furuno Vhf Fm-8500

Jul 23, 2017
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks