In a setting where m stores generate tickets independently on demand, each distinct lottery ticket can be ranked or, equivalently, put in a bijection with a distinct integer ranging from 0 to N – 1. It is a straightforward task to unrank each such an integer into a ticket, as well as the inverse operation of ranking each ticket to its corresponding integer using a recursive combinatoric approach. This can be combined with a pseudo-random number generator for the integers, to ensure that the tickets look sufficiently randomized when ranking (see appendix).
Our analysis considers a ticket as winning only if it claims part of the grand prize, ignoring any smaller prizes granted for similar but incomplete matches, and assumes the winning ticket will be drawn uniformly at random over the ticket space. To simplify the analysis, it assumes that all tickets are bought through a Quick Pick mechanism, meaning that customers cannot or do not select their own combinations.
The goal is to devise an efficient, distributed mechanism to implement Quick Pick to optimize the expected value of a ticket, given that n tickets have been sold. There are three models.
Independent Generation-This is the simplest ticket generation strategy, and the one presumably implemented in current lottery point-of-sales terminals. Each store generates an integer in the ticket space from 0 to N – 1 uniformly at random on demand for each customer, which is unranked to generate an appropriate combination. Equivalently, the process of selecting balls from an urn could be simulated to generate tickets on demand.
Under such a system, each of the m stores generates tickets independently, without memory of what they or any other store have generated in the past. The downside is that there is no mechanism to prevent the same ticket being generated twice, in different stores or even the same store.
Central Server Generation-At the other end of the spectrum, stores communicate with a central server, to ensure that no duplicate ticket ever gets sold until the (N +1)st request.
Such a server could be implemented by constructing a random permutation of the entire ticket space and responding to the ith ticket request with the ith element in this ordering. After N tickets have been sold, each subsequent ticket will result in a collision, but this is clearly unavoidable due to the pigeonhole principle.
Although this central server idea appears to be optimal in terms of preventing collisions, it requires constant communication between each sales terminal and the server. If this connectivity is lost at any point, tickets cannot be dispensed. We seek a generation approach where ticket machines can work independently without any need of external communication, while still minimizing collisions.
Deterministic Pairing-In this strategy, each store is assigned a "partner" and each store and its partner comprise a pair. Thus, m stores yield p = [m / 2] pairs. Partitioning the ticket space N into p regions, and assigning a distinct region of size N / p to each pair, represents the range of tickets that a particular pair is allowed to sell from. (Recall that each possible ticket is represented by a distinct integer from 0 to N – 1.)
One of the stores in each pair sells tickets in increasing order from the front of the region, while the other store sells tickets in decreasing order from the back. This guarantees that no collisions will occur for each pair until they exhaust the entire region, making it optimal for two stores. All the ticket numbers are first run through a pseudo-random number generator such as a linear congruential generator to get a "random"-looking number before the actual sale. This will avoid sequential tickets from appearing between any pair of stores. Once the store partners and ticket ranges have been assigned, stores need not communicate further with any external party.