How to Build Fair Lottery Systems Using Linear Congruential Generators

Background

Lottery is a typical interactive gameplay form that combines high anticipation with low cost, making it popular in many operational scenarios, especially on platforms like Xianyu where it appears in cash treasure hunts, low‑carbon Double‑11 iPhone draws, and recycled‑clothing lucky‑draw events.

About Randomness

Pseudorandom Numbers and Linear Congruential Generator

For efficiency, most systems use pseudorandom numbers, the most widespread being the Linear Congruential Generator (LCG). The core formula is:

The parameters a, b, and p determine whether the output is uniformly distributed. The sequence stays within [0, p‑1] and can achieve a full period of p when the parameters satisfy certain number‑theoretic conditions.

Parameter Choices

Choosing a large prime modulus p often yields good distribution, but using a power‑of‑two modulus (e.g., 2^n) allows the modulo operation to be replaced by bit shifts and masks, improving performance.

b and p are coprime

c = a‑1 is a multiple of all prime factors of p

If p is a multiple of 4, then c is also a multiple of 4

In practice, Java chooses a small prime 11 for b, while GCC often uses 12345. When p = 2^n, the constraint simplifies to a‑1 being divisible by 4.

Implementation Considerations

Even with a full‑period LCG, reducing the range by taking a modulo can expose low‑bit bias. The low bits repeat with a short cycle, producing patterns like 0,1,0,1,… for a 0‑1 range, which feels non‑random.

To mitigate this, many implementations discard low bits and use the high bits as the random output.

private final AtomicLong seed;
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

Details in Use

The seed is the most critical factor; Java’s default seed combines a high‑resolution timestamp with a static uniquifier:

public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}
private static long seedUniquifier() {
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}
private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);

Because the seed itself is generated by an LCG (with b = 0), it is not cryptographically secure. For high‑concurrency scenarios, Alibaba recommends using ThreadLocalRandom instead.

Note that pseudorandom generators are unsuitable for cryptographic purposes; stronger generators should be used when true randomness is required.

Fair Lottery Algorithms

Dimensions of Fairness

Fairness can be viewed from multiple angles: user‑perceived fairness, objective statistical fairness, and algorithmic fairness. An algorithm that always selects the same user index can be “fair” in a deterministic sense but unfair to users with slower connections or later participation.

Key Business Dimensions

Beyond fairness, lottery design must consider participation limits, draw timing, prize distribution rules, and concurrency constraints (QPS, latency).

Common Lottery Algorithms

1) Selection Method

Generate a random integer in 1‑n and pick the corresponding user. Collisions are rare for large user bases but must be handled if they occur. Xianyu’s “Hundred‑Coin Treasure Hunt” uses this approach.

2) Shuffle Method

Shuffle the entire participant list and select users at predetermined positions. This method incurs the most I/O but can be optimized with partitioning. It suits scenarios where each participant receives a distinct prize.

3) Reservoir Sampling

Maintain a pool of size k (the number of prizes). Each incoming user replaces an existing entry with probability k/n, where n is the current participant count. This yields uniform selection without knowing the total number of participants in advance.

4) Red‑Packet Splitting Algorithm

WeChat’s classic algorithm gives each user a base amount of 0.01 CNY, then adds a random value up to twice the remaining average. The last user receives the leftover. This ensures equal expected value but increasing variance, and it requires knowing the total participant count beforehand.

5) Probability Method

Assign a fixed winning probability to each prize (e.g., 30 % for prize A) and evaluate it in real time for each participant. This method is simple but can become unfair when inventory depletes, requiring probability‑preserving adjustments to redistribute odds.

All of these algorithms can be scaled with distributed techniques, partitioning the prize pool and participants, and can be combined to meet specific business goals.

Conclusion

The article explored the fundamentals of random number generation and several practical lottery algorithms, highlighting how parameter choices affect period and distribution, the importance of seed quality, and the trade‑offs between fairness, performance, and implementation complexity. Future posts will delve deeper into rights distribution, user‑driven models, and advanced lottery designs.