Betting Wheels, Lotteries & Lotto Designs
|
|  Yüklə 65.5 Kb.
|
| Betting Wheels, Lotteries & Lotto Designs
by G.H.J. van Rees 1 Introduction 2 Scope of Problem 4 History 5 Constructions 6 Algorithms How to Run a Lottery 1. Betters buy a ticket i.e. choose k numbers from n numbers 2. After sales are closed, the gov’t randomly chooses p numbers from the n numbers. 3. If the better gets exactly t of the gov’t’s numbers correct, then better wins the t prize. 4. The larger t is the more the better wins. 5. Never give out as much money as you take in. The best strategy for a better- Don’t bet. The Question
For lotto 6-49, the number is L(49,6,6,t) or if you count the bonus ball - L(49,6,7,t) This talk will not be about increasing your expected gain. Definition: L(n,k,p,t) is the minimum number of k-subsets (or blocks) of a n-set that are needed to ensure that any p-subset of the n-set intersects one of the blocks in at least t elements. Definition: LD(n,k,p,t;b) is a lotto design on b blocks in which any p-subset of the n-set intersects one of the blocks of size k in at least t elements. Definition: LD*(n,k,p,t;b) is a lotto design in which b=L(n,k,p,t). Example: The following is an LD(7,3,4,2;3): { { 1,2,3 }, { 3,4,5 }, { 5,6,7} } The following is an LD*(7,3,4,2;3): { { 1,2,3 }, {4,5,6 } }
{ 2, 4, 5, 6, 7, 8, 9,10,12,15 }, { 1, 2, 3, 4, 8, 9,11,13,14,15 }, { 3, 5, 6,10,12,16,17,18,19,20 }, { 1, 7, 9,11,14,16,17,18,19,20 }, { 2, 4, 8,13,15,16,17,18,19,20 } } Check every 10-set yourself. Trust no one!
Some of lotto numbers are easy to calculate. L(49,6,6,6)=  =13,983,816
L(49,6,6,1)=  ,
L(n,k,p,1) =  .
In the Hungarian Lottery L(90,5,5,2) = 100 is of interest. This is not easy, but it has been proved. L(49,6,6,3)??? We can get an upper bound by noticing the construction that gives: L(49,6,6,3) L(22,6,3,3) + L(27,6,4,3) 77+86 = 163. Proof: Take any p=6-set out of the 49 elements. Either there are at least 3 elements from the 22 elements and we have one of the 77 blocks intersecting the 6-set in at least three elements or there are at least 4 elements from the 27 elements and there is a block intersecting the 6-set in at least 3 elements. Now LD*(22,6,3,3;77) is a well-known combinatorial design and you could not get a better lotto design. Whereas LD(27,6,4,3;86) was found by a computer program using a simulated annealing algorithm. It can probably be improved. But even if LD(27,6,4,3;86) was the best you could do, there may be better ways to split the 49 elements or better different constructions. So we know that: 87 L(49,6,6 ,3) 163. Still a big gap. But why are there brazillions of web sites on this topic? In the advanced lotto countries of this world (not Canada), people are given the choice of betting an LD(n,k,p,t;b), for various parameters and small n. It encourages the better to know that b is absolutely as small as possible. Betters also believe in “their lucky numbers”. So if the gov’t picks p numbers that include r of the better’s v lucky numbers, he wants to buy tickets that guarantee the t prize. This would be an LD(v,k,t,t). These lottery wheels are sold in Australia and elsewhere. Some lotteries will provide the wheels for free and let you bet them with one super ticket that costs $L(v,k,t,t). Other Applications When p=t, this lotto problem becomes a classic problem called covering design problem. It has been much studied and has many applications. The main other ones are error-trapping decoding of error-correcting codes, data compression, covering codes Research Approach Theory – Recursive – Constructions Programming – lower bound – backtracking
= Tables History
Bate and Brouwer in 1978 - easy stuff – L(n,3,3,2) Furedi – 1996 – t=2 – graph theory like Hartmann – 1997 – theory of lower bounds Bate & van Rees –1998- L(49,6,6,2)=19. Structure Bluskov – 99,02 – heuristic algorithms Li & van Rees – 1999,00,02,06 – lower bounds, constructions, heuristic algorithms, frequency analysis and tables South Africans – 05,06 - small designs Lutful & van Rees -06?– small designs Li & Toulouse – 05- heuristic parallel algorithms for L(n,k,t,t) Lots and lots of work left to be done. Results Bound: Proof: L(n,k,p,t) 
Proof: L(5,4,3,2)  =5
12,34,13,25,14,35,15,24,23,45 are all the 2-sets 1234, 1325, 1435, 1524, 2345 are 5 4-sets holding all the 2-sets. I claim this is a LD(5,4,3,2;5). Take any 3-set {1,2,3} and find a 2-set in it, say 23. 23 is in block 5. This is trivial to generalize. Bound: L(n,k,p,t) Proof: L(7,4,5,3)( Every block of size 4 is represents 1234 represents 12356, 12367, 12357 12456, 12467, 12457 13456, 13467, 13457 23456, 23467, 23457 12345, 12346, 12347 So the minimum number of blocks times the number represented must be at least as big as the number of 5-sets. L(7,4,5,3) 3. This is easy to generalize. Complements: L(n,k,p,t) = L(n,n-k,n-p, n-k-p+t) Proof: Take an LD(n,k,p,t) and complement each block and check. Note that this cuts the tables in half. Theorem (S.A.) L(n,k,p,t) = 2 iff 2t-1+max{n-2k,0}pn+t-k+1 L(n,k,p,t) = 3 iff p min{2t-2+max{n-2k,0},n-k+t-1} and t 3k-2+max{m-3n,o}, if m 2n, t (3/2)k-1+max{m-(3/2)n,0}, if m < 2n. Since the most frequent numbers are 1, 2 and 3 we no longer have to write down those parts of the tables. Monotinicity(Li & van Rees)(easy) L(n,k,p,t) increases or stays the same as n increases t increases k decreases p decreases n and t decrease n and p decrease t and k increase t and p increase n and k and p and t increase What about t,k,p all increasing? Sometimes increase Theorem(Li) Generalized Schonheim L(n,k,p,t) This bound is good for L(n,k,p,t) when k=t or p=t in the complement. These are the classic cases and there the bound is called the Schonheim bound. Unfortunately as k-t or p-t gets large the bound is not much use. Theorem (Construction) Let n=n1+n2 and p=p1+p2-1, L(n,k,p,t) L(n1,k,p1,t) + L(n2,k,p2,t) Seen it earlier Theorem (Construction) L(n+1,k+1,p+1,t+1) L(n,k,p,t) + L(n,k+1,p+1,t+1).
Theorem:(Construction) Let n, k, p, t, n1, k1,and r be integers so that n1 < n, p-r t, k1t-r-1 and k1 = k-n +n1. Then L(n,k,p,t) L(n1,k,p-r,t) + L(n1, k1, p-r-1,t-r-1). Proof: Exercise Algorithms We need the theory to tell us as much about what the design looks like so we can fine tune our algorithms. Lower Bounds 1. Backtracking : Even with early isomorphism rejection, frequency analysis and precomputing, this needs to be done in parallel. Upper Bounds (Heuristics)(Bluskov, Finns) 1. Simulated Annealing – Bounce off the walls for a while and then settle down. 2. Tabu Search – Don’t look where you just looked. 3. Co-operative Multi-Level Search (Li & Toulouse 2005) 25 new and improved small L(n,k,t,t) numbers. These are the classic numbers that have received a lot of attention. So I consider this an important achievement. This is parallel work where the computers co-operate and communicate with each other. Further, they coarsen the search space to make it smaller and then take the solutions (approximations) they find back to the original search space and then search there. They may iterate this many times. References For more details and references see: 1. P.C. Li & G.H.J. van Rees, Lotto Designs, a section in The CRC Handbook of Combinatorial Designs, Editors – C.J. Colbourn & J.H. Dinitz Boca Raton, CRC Press, (2006) 10 pages ----appearing soon in a bookstore near you. This reference and the talk is on my web site. - - |
L(n,k,p,t) 
) 
