Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > General Gambling > Probability

Notices

Probability Discussions of probability theory

Reply
 
Thread Tools Display Modes
Old 12-23-2012, 04:36 AM   #31
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

You are an amazing person, I am sincerely grateful for your kindness
Mirapep is offline   Reply With Quote
Old 12-23-2012, 06:05 AM   #32
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

1 3 5 7 8 9 11 13 15 17 0 0
0 0 1 3 5 7 8 9 11 13 15 17

How do you get this?

I have to understand what performs this function:

c (x, rep (0, r-1))

and what values

function (x, k, r)

Mirapep is offline   Reply With Quote
Old 12-23-2012, 01:22 PM   #33
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,876
Re: lottery probability

Quote:
Originally Posted by Mirapep View Post
1 3 5 7 8 9 11 13 15 17 0 0
0 0 1 3 5 7 8 9 11 13 15 17

How do you get this?

I have to understand what performs this function:

c (x, rep (0, r-1))

and what values

function (x, k, r)

x is a single combination of lottery numbers in ascending order that got created by combn and passed to function shiftsub. The function apply applies the function shiftsub to every combination. rep(0,r-1) inserts r-1 zeroes. c(x,rep(0,r-1)) is an array with r-1 zeroes inserted at the end of x. Then c(rep(0,r-1),x) is an array with r-1 zeros and inserted at the beginning of x That shifts x and makes both the same length for subtract. k and r are the values you passed to consec. So for consec(20,10,3), n = 20, k = 10, and r = 3.

Code:
> x = c(1,3,5,7,8,9,11,13,15,17)
> x
 [1]  1  3  5  7  8  9 11 13 15 17
>
> r = 3
> c(rep(0,r-1),x)
 [1]  0  0  1  3  5  7  8  9 11 13 15 17
>
> c(x,rep(0,r-1))
 [1]  1  3  5  7  8  9 11 13 15 17  0  0
>
> c(x,rep(0,r-1))- c(rep(0,r-1),x)
 [1]   1   3   4   4   3   2   3   4   4   4 -15 -17
>
> k = 10
>  (c(x,rep(0,r-1))- c(rep(0,r-1),x))[r:k]
[1] 4 4 3 2 3 4 4 4
>
> any((c(x,rep(0,r-1))- c(rep(0,r-1),x))[r:k] == 2)
[1] TRUE
You get help on any R function like rep or any by typing ?rep or ?any.

Last edited by BruceZ; 12-23-2012 at 02:13 PM.
BruceZ is offline   Reply With Quote
Old 12-24-2012, 10:38 AM   #34
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

Ok, I realized that examines each combination. If it does this is still a fast algorithm. I was thinking of a recursive formula only on the combinations to subtract.
Merry Christmas
Mirapep is offline   Reply With Quote
Old 12-24-2012, 10:40 AM   #35
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

Applying triangle Tartaglia
Mirapep is offline   Reply With Quote
Old 12-26-2012, 02:04 PM   #36
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,876
Re: lottery probability

I've done it! I wrote a recursive program to quickly compute the probability of r consecutive numbers in a row when choosing k numbers from n numbers. I verified that it gives exactly the same numbers as the program that searched every combination for these test cases:

(n,k,r) =

(20,10,3)
(25,10,3)
(49,6,3)
(20,11,3)
(20,12,3)
(20,10,4)
(20,11,4)
(20,12,4)
(20,16,5)

You really need this because the 25 takes several minutes with the old program. The new one does it instantly. (49,6,3) used to take over 20 minutes, and now that is instantaneous.

There's just one problem. I got an error in R that I was nesting too deeply when I tried to use a for loop to continue the pattern for all k. I increased the limit on nesting, but then I got a protection stack size error. So I increased the size of the protection stack when R starts, but then I got an error that the C stack is too close to the limit! I have to try to change that through the OS, but I don't even know if I can. It may just be that I'm low on disk space, so I need to clean up. The first program below works, but you have to add lines for each k. Right now it will do up to k=2r+6, so 10 for r=3, 14 for r=4, 16 for r=5, etc. You should be able to do any n, and any r and k as long as you add enough lines for the k. You could do this automatically using macro expansion. The second program does it automatically with for loops, but I haven't been able to test it yet because of the problems. You should be able to easily translate that into VB and try it. The function choose(n,k) is combin(n,k) in VB. I will also try to get it to work, perhaps in another language besides R which really isn't designed for recursion.

Enter pconsec(20,10,3) for example. If you just want the number instead of the probability, use nconsec(20,10,3).

This one works, but you have to expand it manually for k > 2r+6:

Code:
pconsec = function(n,k,r) { nconsec(n,k,r) / choose(n,k)}

nconsec = function(n,k,r) {
  if (n == k) {s = 1} else {

    s = choose(n-r,k-r) + (n-r)*choose(n-r-1,k-r)

    if (k >= 2*r) {
      for (m in r:(n-k+r-1)) {s = s - nconsec(m,r,r)*choose(n-r-1-m,k-2*r)} }

    if (k >= 2*r+1) {
       for (m in (r+1):(n-k+r)) {s = s - nconsec(m,r+1,r)*choose(n-r-1-m,k-2*r-1)} }

    if (k >= 2*r+2) {
      for (m in (r+2):(n-k+r+1)) {s = s - nconsec(m,r+2,r)*choose(n-r-1-m,k-2*r-2)} }

    if (k >= 2*r+3) {
      for (m in (r+3):(n-k+r+2)) {s = s - nconsec(m,r+3,r)*choose(n-r-1-m,k-2*r-3)} }

    if (k >= 2*r+4) {
      for (m in (r+4):(n-k+r+3)) {s = s - nconsec(m,r+4,r)*choose(n-r-1-m,k-2*r-4)} }

    if (k >= 2*r+5) {
      for (m in (r+5):(n-k+r+4)) {s = s - nconsec(m,r+5,r)*choose(n-r-1-m,k-2*r-5)} }

    if (k >= 2*r+6) {
      for (m in (r+6):(n-k+r+5)) {s = s - nconsec(m,r+6,r)*choose(n-r-1-m,k-2*r-6)} }

### Continue these for higher values of k

  }
  s
}

> pconsec(20,10,3)
[1] 0.8697309
> nconsec(20,10,3)
[1] 160688



This one should do the same thing, but it gives stack errors on my machine:

Code:
pconsec = function(n,k,r) { nconsec(n,k,r) / choose(n,k)}

nconsec = function(n,k,r) {
  if (n == k) {s = 1} else {
    s = choose(n-r,k-r) + (n-r)*choose(n-r-1,k-r)
    for (j in (2*r):k) {
      if (k >= j) {
        i = j-2*r
        for (m in (r+i):(n-k+r+j-1)) {s = s - nconsec(m,r+j,r)*choose(n-r-1-m,k-2*r)}
      }
    }
  }
  s
}
If you want to try this one in R on your machine, first do

>options(expressions = 30000)

The default is 5000 which doesn't work. You can go as high as 500000. Then if that doesn't work, try invoking R with

R --max--ppsize=100000

or even 500000. The default is 10000.

Last edited by BruceZ; 12-26-2012 at 10:37 PM.
BruceZ is offline   Reply With Quote
Old 12-26-2012, 06:53 PM   #37
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,876
Re: lottery probability

I got the short recursive code working now in both VB and R. The stack error was caused by my own bug.

This VB version runs in Excel, so replace Application.Combin with Combin if you use it standalone. These often run very fast, but they will slow down as you increase the ratio of k to r, and when n becomes large.

Code:
Function pconsec(n As Long, k As Long, r As Long)
    pconsec = nconsec(n, k, r) / Application.Combin(n, k)
End Function
    
Function nconsec(n As Long, k As Long, r As Long)
    
    Dim s   As Long
    Dim j   As Long
    Dim i   As Long
    Dim m   As Long

    If (n = k) Then
        nconsec = 1
    Else
        nconsec = Application.Combin(n - r, k - r) + (n - r) * Application.Combin(n - r - 1, k - r)
        For i = 0 To k - 2 * r
            For m = r + i To n - k + r + i - 1
                nconsec = nconsec - nconsec(m, r + i, r) * Application.Combin(n - r - 1 - m, k - 2 * r - i)
            Next m
        Next i
    End If
    
End Function

R version:

Code:
pconsec = function(n,k,r) { nconsec(n,k,r) / choose(n,k)}

nconsec = function(n,k,r) {
  if (n == k) {s = 1} else {
    s = choose(n-r,k-r) + (n-r)*choose(n-r-1,k-r)
    if (k >= 2*r) {
      for (i in 0:(k-2*r)) {
          for (m in (r+i):(n-k+r+i-1)) {s = s - nconsec(m,r+i,r)*choose(n-r-1-m,k-2*r-i)}
      }
    }
  }
  s
}

> pconsec(20,10,3)
[1] 0.8697309
> nconsec(20,10,3)
[1] 160688

Last edited by BruceZ; 12-27-2012 at 01:12 AM.
BruceZ is offline   Reply With Quote
Old 12-27-2012, 06:45 AM   #38
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

Thank you very much for the work you have done for me.
This evening, after returning home, I'll try the functions, you'll know the results
Mirapep is offline   Reply With Quote
Old 12-27-2012, 09:00 AM   #39
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,876
Re: lottery probability

Quote:
Originally Posted by Mirapep View Post
Thank you very much for the work you have done for me.
This evening, after returning home, I'll try the functions, you'll know the results
This will run a lot faster for you if you are using compiled VB. I'm running it in VBA with Excel which isn't compiled. If you do use it in VBA with Excel, I just found a way to speed it up by a factor of 4 by using the With WorksheetFunction statement instead of calling .Application Combin every time. Now it's 4 times faster than R even uncompiled. Speed may not even be an issue for you at all depending on your inputs.

I'm working on a way to get rid of the for loops in R by vectorizing, That should make the R program much faster too.

Code:
Function pconsec(n As Long, k As Long, r As Long)
    pconsec = nconsec(n, k, r) / Application.Combin(n, k)
End Function

Function nconsec(n As Long, k As Long, r As Long)
    
    Dim s   As Long
    Dim j   As Long
    Dim i   As Long
    Dim m   As Long
    
    With WorksheetFunction

        nconsec = .Combin(n - r, k - r) + (n - r) * .Combin(n - r - 1, k - r)
        For i = 0 To k - 2 * r
            nconsec = nconsec - .Combin(n - 2 * r - i - 1, k - 2 * r - i)
            For m = r + i + 1 To n - k + r + i - 1
                nconsec = nconsec - nconsec(m, r + i, r) * .Combin(n - r - 1 - m, k - 2 * r - i)
            Next m
        Next i
       
    End With
    
End Function

Last edited by BruceZ; 12-28-2012 at 01:37 AM. Reason: Removed if
BruceZ is offline   Reply With Quote
Old 12-28-2012, 05:01 AM   #40
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

Hello Bruce,
I tried the function in vb6, it is fast and perfect. However, there seems to be a problem for high values ​​of n and k. I did pc work all night and in the morning he had not yet finished. I also tried in R:
- Nconsec (100,15,5) has provided quick response;
- Nconsec (100,50,5) still work for several minutes.
Is a possible conflict in the routine?
Mirapep is offline   Reply With Quote
Old 12-28-2012, 05:33 AM   #41
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

Still working
Mirapep is offline   Reply With Quote
Old 12-28-2012, 10:03 AM   #42
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,876
Re: lottery probability

Quote:
Originally Posted by Mirapep View Post
Hello Bruce,
I tried the function in vb6, it is fast and perfect. However, there seems to be a problem for high values ​​of n and k. I did pc work all night and in the morning he had not yet finished. I also tried in R:
- Nconsec (100,15,5) has provided quick response;
- Nconsec (100,50,5) still work for several minutes.
Is a possible conflict in the routine?
There is no conflict, it just takes a very long time to compute all the terms when k is a large multiple of r. With the current algorithm, the time increases exponentially with k/r. It goes up by about a factor of 30 for every increase of 5. So (100,20,5) takes 30 times longer than (100,15,5), and (100,25,5) takes 30^2 = 900 times longer than (100,15,5), etc. So (100,50,5) takes about 30^7 = 20 billion times longer than (100,15,5). So even if (20,15,5) took only 0.1 seconds, (100,50,5) would take over 69 years! But if you did (100,50,17), that would be very fast. In fact, (10000,50,17) is very fast. It's also a tiny probability.

I'm working on a much faster algorithm. The current one computes many of the same numbers over and over recursively. I think I can compute them once, save them, and then reuse them. So instead of calling nconsec recursively, those numbers will already be in a precomputed in a table. Then I think the time will only increase linearly, not exponentially. So instead of taking 20 billion times longer, it should only take 35 times longer. The current algorithm is stupid, but it was an important first step to prove that the formula is right.

Last edited by BruceZ; 12-28-2012 at 01:55 PM.
BruceZ is offline   Reply With Quote
Old 12-29-2012, 03:05 AM   #43
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,876
Re: lottery probability

I got the fast routine working in R. It can do (100,15,5) in 40 seconds in R, and in compiled VB it will probably be just a few seconds. The time only increases linearly with k now, not exponentially.

> pconsec(100,50,5)
[1] 0.8428898
> nconsec(100,50,5)
[1] 8.504029e+28


It makes 2 tables of numbers that it reuses. You can still call it like that with just 3 parameters and it will make the tables for you, but if you want to do a lot of these with the same r, you can just make the main table 1 time like this:

> t = make_tables(20,10,3)
> pconsec(20,10,3,t)
[1] 0.8697309
> nconsec(20,10,3,t)
[1] 160688


Then every time you call it, it will use same table, and it won't have to recompute it every time. Just make it big enough for your largest n and k. You have to remake it if you change r though. You won't have to do this if it is already very fast for your inputs. Here is a sample table for (20,10,3):

Code:
      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
 [1,]    0    0    0    0    0    0    0
 [2,]    0    0    0    0    0    0    0
 [3,]    0    0    1    0    0    0    0
 [4,]    0    0    2    1    0    0    0
 [5,]    0    0    3    4    1    0    0
 [6,]    0    0    4    9    6    1    0
 [7,]    0    0    5   16   18    7    1
 [8,]    0    0    6   25   40   27    8
 [9,]    0    0    7   36   75   74   36
[10,]    0    0    8   49  126  165  116
[11,]    0    0    9   64  196  321  300
[12,]    0    0   10   81  288  567  666
[13,]    0    0   11  100  405  932 1323
[14,]    0    0   12  121  550 1449 2416
[15,]    0    0   13  144  726 2155 4131
[16,]    0    0   14  169  936 3091 6700
Interesting number sequence. I don't recognize it. If we could identify it as something, we may be able to compute it from built in functions. It changes with every r.

Code:
pconsec = function(n,k,r,...) {nconsec(n,k,r,...) / choose(n,k)}

nconsec = function(n,k,r,table) {
  if (n == k) {
    s = 1 } 
  else if (k < 2*r) {
    s = choose(n-r,k-r) + (n-r)*choose(n-r-1,k-r)} 
  else {
    ctable = make_ctable(n,k,r)
    if (missing(table)) {table = make_table(n,k,r,ctable)}
    s = recurse(n,k,r,ctable,table)
  }
  s
}
  

make_ctable = function(n,k,r) {
  ctable = matrix(rep(0,(n-r+1)*(k-r+1)),nrow=(n-r+1))
  ctable = choose(row(ctable)-1,col(ctable)-1)
  ctable
}


make_table = function(n,k,r,ctable) {
  table = matrix(rep(0,(n-r-1)*(k-r)),nrow=(n-r-1))
  for (x in r:(n-r-1)) {
    for (y in r:min(x,(k-r))) {table[x,y] = ifelse(x==y,1,recurse(x,y,r,ctable,table))} }
  table
}


make_tables = function(n,k,r) {
  ctable = make_ctable(n,k,r)
  make_table(n,k,r,ctable)
}


recurse = function(n,k,r,ctable,table) {
  s = ctable[n-r+1,k-r+1] + (n-r)*ctable[n-r,k-r+1]
  if (k >= 2*r) {
    for (i in 0:(k-2*r)) {
      for (m in (r+i):(n-k+r+i-1)) {s = s - table[m,r+i]*ctable[n-r-m,k-2*r-i+1] } }
   }
  s
}
The ... is for the optional parameter. The function missing(table) determines if you didn't supply the table, so it will then make it for you.

I ported it to VB, but it is NOT working yet. For some reason the ctable is not being made. This should get you started though. Let me know if you find the problem. I may not be passing arrays correctly in VB.

Code:
Option Explicit

Function pconsec(n As Long, k As Long, r As Long)
    pconsec = nconsec(n, k, r) / Application.Combin(n, k)
End Function

Function nconsec(n As Long, k As Long, r As Long)

    Dim ctable() As Long
    Dim table() As Long
    
    With WorksheetFunction
    
    If (n = k) Then
        nconsec = 1
    ElseIf (k < 2 * r) Then
        nconsec = .Combin(n - r, k - r) + (n - r) * .Combin(n - r - 1, k - r)
    Else
        ctable = make_ctable(n, k, r)
        table = make_table(n, k, r, ctable)
        nconsec = recurse(n, k, r, ctable, table)
    End If
  
  End With

End Function

 
Function make_ctable(n As Long, k As Long, r As Long) As Long()
  
  ReDim ctable(0 To n - r, 0 To k - r) As Long
  Dim i As Long
  Dim j As Long
  
  With WorksheetFunction
  
  For i = 0 To n - r
    For j = 0 To k - r
     ctable(i, j) = .Combin(i, j)
    Next j
  Next i
  
  make_ctable = ctable()
  
  End With

End Function

Function make_table(n As Long, k As Long, r As Long, ctable() As Long) As Long()

    ReDim table(1 To n - r - 1, 1 To k - r) As Long
    Dim x As Long
    Dim y As Long
    
    For x = r To n - r - 1
        For y = r To Min(x, k - r)
            If x = y Then
                table(x, y) = 1
            Else
                table(x, y) = recurse(x, y, r, ctable, table)
            End If
        Next y
    Next x
    
    make_table = table()

End Function

Function recurse(n As Long, k As Long, r As Long, ctable() As Long, table() As Long)

    recurse = ctable(n - r, k - r) + (n - r) * ctable(n - r - 1, k - r)
    If k >= 2 * r Then
        For i = 0 To k - 2 * r
            For m = r + i To n - k + r + i - 1
                recurse = recurse - table(m, r + i) * ctable(n - r - m - 1, k - 2 * r - i)
            Next m
        Next i
    End If

End Function

Last edited by BruceZ; 12-29-2012 at 03:28 AM.
BruceZ is offline   Reply With Quote
Old 12-29-2012, 04:47 AM   #44
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

Bruce Ok, I'll try these functions. You have been exhaustive.
You've got to download the excel sheet Multimasaniello? I'm planning this in vb consecutive with the filter in order to increase the yield. This is to determine the progressive stakes in software for the lottery.
For this purpose I created a very interesting program that predicts the Italian lottery numbers to play. In an Italian lottery one winning number pays about 11 times the stake money. I use three numbers at a time so if they win I get about 3.5 times the amount bet. Now I have set the money management Multimasaniello total of three winds with height 3.5 that will be successful with one. The final yield is 1.5 times the initial cash. Next, I set up a second multimasaniello with 20 events total share for each 1.5, winning at least 5 out of 20. The final yeld is 0. From a statistical study of all winning lottery I found that very rarely will win 5 times in a row, so eliminating these combinations get a positive return final.
This explanation is to make known my motives. If you feel it interesting I'll try to be more specific
Mirapep is offline   Reply With Quote
Old 12-29-2012, 10:37 AM   #45
enthusiast
 
Join Date: Dec 2012
Posts: 53
Re: lottery probability

So Bruce,
I wrote your function in vb6 and there is error undefined function
Min (x, k - r)

Also I do not use combin excel. Using this function declared in a module

' returns: (n k) Binomial Coefficient = n! / (K! * (n-k)!)
' -1 If result overflows a long
' the number of ways to choose k elements from an n element set

Public Function Binomial (n As Long, k As Long) As Double
Dim i As Long, j As Long, u ()
On Error GoTo ErrOverflow

Select Case k
Case Is <0, Is> n 'valid range
Binomial = 0
Case 0, n 'trivial case 1
Binomial = 1
Case 1, n - 1 'trivial case n
Binomial = n
Case 2, n - 2 'simple case n * (n - 1) / 2
Binomial = (n \ (2 - (n And 1))) * ((n - 1) \ (1 + (n And 1)))
Case Else
ReDim u (n - k)
For j = 0 To (n - k)
u (j) = j + 1
Next j
For i = 2 To k 'recurrence: (nk) = (n-1 k-1) + (n-1 k)
For j = 1 To (n - k)
u (j) = u (j) + u (j - 1)
Next j
Next i
Binomial = u (n - k)
end Select

Exit Function
ErrOverflow:
Binomial = -1
end Function
Mirapep is offline   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
Trackbacks are Off
Pingbacks are Off
Refbacks are Off




All times are GMT -4. The time now is 06:03 AM.


Powered by vBulletin®
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0 ©2011, Crawlability, Inc.
Copyright 2008-2010, Two Plus Two Interactive