Betting Wheels, Lotteries & Lotto Designs
by
G.H.J. van Rees
1 Introduction
2 Scope of Problem
3 Applications
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
How many tickets must I buy to guarantee winning the t prize?
A lot of people are interested in this question: betters, governments, web sites, salesman of lottery wheels.
This number is called: L(n,k,p,t).
For lotto 649, 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 ksubsets (or blocks) of a nset that are needed to ensure that any psubset of the nset 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 psubset of the nset 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 } }
LD(7,3,4,2)=2
Big Example; LD(20,10,6,4;6)
{ { 1, 3, 5, 6, 7,10,11,12,13,14 },
{ 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 10set 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=6set 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 6set in at least three elements or there are at least 4 elements from the 27 elements and there is a block intersecting the 6set in at least 3 elements.
Now LD*(22,6,3,3;77) is a wellknown 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 errortrapping decoding of errorcorrecting codes, data compression, covering codes
Research Approach
Theory – Recursive – Constructions
Programming – lower bound – backtracking
= Tables
History
Lots of stuff on L(n,k,t,t) then and now
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: L(n,k,p,t)
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 2sets
1234, 1325, 1435, 1524, 2345 are 5 4sets holding all the 2sets. I claim this is a LD(5,4,3,2;5). Take any 3set {1,2,3} and find a 2set 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 = 15 5sets.
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 5sets.
L(7,4,5,3) 3.
This is easy to generalize.
Complements: L(n,k,p,t) = L(n,nk,np, nkp+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 2t1+max{n2k,0}pn+tk+1
L(n,k,p,t) = 3 iff p min{2t2+max{n2k,0},nk+t1} and
t 3k2+max{m3n,o}, if m 2n,
t (3/2)k1+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 kt or pt gets large the bound is not much use.
Theorem (Construction)
Let n=n_{1}+n_{2} and p=p_{1}+p_{2}1,
L(n,k,p,t) L(n_{1},k,p_{1},t) + L(n_{2},k,p_{2},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).
Proof by picture.
Theorem:(Construction)
Let n, k, p, t, n_{1}, k_{1},and r be integers so that n_{1} < n, pr t, k_{1}tr1 and k_{1} = kn +n_{1}. Then
L(n,k,p,t) L(n_{1},k,pr,t) + L(n_{1}, k_{1}, pr1,tr1).
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. Cooperative MultiLevel 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 cooperate 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.
 
