Image by Author | Canva

Simulating randomness is a powerful tool in computer science, data science, and statistical analysis. One of the simplest yet most insightful experiments you can run is simulating coin tosses. But instead of using an actual coin, we’ll use four different pseudorandom number generators (PRNGs) to simulate the process.

Why PRNGs? These algorithms are crucial for generating “random” values in computing. But not all PRNGs are created equal. Some are faster, others are more statistically uniform, and some have certain biases. In this experiment, we’ll simulate 100,000 coin tosses using four popular PRNGs and compare how each one performs.

What Are PRNGs?

Before we get into the experiment, let’s understand what PRNGs are. A PRNG is an algorithm that produces sequences of numbers that appear random but are entirely determined by an initial value (the seed). The key difference from true randomness is that PRNGs are deterministic: the same seed will always generate the same sequence.

For this experiment, we’ll be using the following four PRNGs:

• Linear Congruential Generator (LCG): One of the oldest and simplest PRNGs
• Mersenne Twister: A widely used PRNG known for its large period and high-quality randomness
• Xorshift: A faster, simpler PRNG known for its efficiency in generating random numbers
• PCG (Permuted Congruential Generator): A newer PRNG that balances performance and statistical quality

Each PRNG has its strengths and weaknesses, and by simulating 100,000 coin tosses, we’ll explore how well each of them mimics true randomness. You can learn more about these algorithms in the Wikipedia article on PRNGs.

The Coin Toss Simulation Setup

Now that we understand PRNGs, let’s set up the experiment. We’ll simulate 100,000 coin tosses for each of the four PRNGs. The idea is to model a fair coin toss, where each toss has an equal probability of landing heads (1) or tails (0).

For each PRNG, we’ll use a uniform distribution between 0 and 1, then map values greater than 0.5 to heads and values less than or equal to 0.5 to tails. The expected result is that 50% of the tosses should be heads and 50% should be tails, but let’s see how well each PRNG performs.

The code below outlines the simulation setup:

import numpy as np
import random

# Define the number of tosses
num_tosses = 100000

# Initialize PRNGs
# Mersenne Twister (default for numpy)
np_random = np.random.default_rng()

# Linear Congruential Generator (LCG)
def lcg(seed=42):
    a, c, m = 1664525, 1013904223, 2**32
    state = seed
    while True:
        state = (a * state + c) % m
        yield state / m

# Xorshift
def xorshift(seed=42):
    state = seed
    while True:
        state ^= state << 21
        state ^= state >> 35
        state ^= state << 4
        yield state & 0xFFFFFFFFFFFFFFFF

# Permuted Congruential Generator (PCG)
def pcg(seed=42):
    state = seed
    while True:
        state = (state * 6364136223846793005 + 1) & 0xFFFFFFFFFFFFFFFF
        yield (state >> 18) & 0x7FFFFFFF

# Simulate coin tosses for each PRNG
def simulate_coin_tosses(prng, num_tosses):
    return [1 if next(prng) > 0.5 else 0 for _ in range(num_tosses)]

# Create the PRNG instances
lcg_gen = lcg()
xorshift_gen = xorshift()
pcg_gen = pcg()

# Simulate tosses
np_tosses = np_random.random(num_tosses) > 0.5
lcg_tosses = simulate_coin_tosses(lcg_gen, num_tosses)
xorshift_tosses = simulate_coin_tosses(xorshift_gen, num_tosses)
pcg_tosses = simulate_coin_tosses(pcg_gen, num_tosses)

# Calculate the proportions of heads for each PRNG
np_heads = np.sum(np_tosses) / num_tosses
lcg_heads = np.sum(lcg_tosses) / num_tosses
xorshift_heads = np.sum(xorshift_tosses) / num_tosses
pcg_heads = np.sum(pcg_tosses) / num_tosses

print(f'Mersenne Twister Heads: {np_heads}')
print(f'Linear Congruential Generator Heads: {lcg_heads}')
print(f'Xorshift Heads: {xorshift_heads}')
print(f'PCG Heads: {pcg_heads}')

Explanation

With the simulation set up, we can now run it to collect the results. Our goal is to simulate 100,000 coin tosses for each PRNG and track how many heads vs. tails occur in each case.

Here’s how we’ll handle the data collection:

• For each PRNG, we run the coin toss simulation (with 100,000 tosses)
• Each PRNG generates a sequence of tosses, which are stored in separate lists: np_tosses, lcg_tosses, xorshift_tosses, and pcg_tosses
• Afterward, we calculate the proportion of heads for each PRNG and display the results

Once the simulation runs, we’ll examine how closely each PRNG approximates the expected 50% heads and 50% tails distribution. The results show that:

Image by Author

As we can see, the Mersenne Twister and Linear Congruential Generator give results close to 50% heads (with minor deviations), while the Xorshift and PCG generators return 100% heads. This indicates that, for some reason, both Xorshift and PCG didn’t produce randomness in the expected manner. 

Let’s investigate why this might be.

Analyzing the Results: The True vs. Simulated Coin Tosses

After running the simulations, the results should reflect approximately 50% heads and 50% tails. However, due to the inherent randomness of each PRNG, there are usually slight deviations. In this case, we see major deviations with the Xorshift and PCG PRNGs, which returned 100% heads.

Expected vs. Observed:

• Mersenne Twister and LCG gave proportions close to 50%, showing they performed well for simulating coin tosses.
• Xorshift and PCG generated extreme results, with all tosses being heads, which suggests an issue with their implementation or statistical quality.

To understand whether these deviations are statistically significant, we can use a chi-squared test to compare the observed number of heads and tails with the expected number (50% heads, 50% tails). This test helps us determine if the differences are due to chance or if the PRNGs have a systematic bias.

Let’s calculate the chi-squared statistic for the Xorshift and PCG PRNGs:

from scipy.stats import chisquare

# Define expected values (50% heads, 50% tails)
expected_heads = num_tosses / 2
expected_tails = num_tosses / 2

# Observed counts for Xorshift and PCG
observed_xorshift = [np.sum(xorshift_tosses), num_tosses - np.sum(xorshift_tosses)]
observed_pcg = [np.sum(pcg_tosses), num_tosses - np.sum(pcg_tosses)]

# Perform chi-squared tests
chi2_xorshift, p_xorshift = chisquare(observed_xorshift, [expected_heads, expected_tails])
chi2_pcg, p_pcg = chisquare(observed_pcg, [expected_heads, expected_tails])

print(f'Xorshift Chi-squared: {chi2_xorshift}, p-value: {p_xorshift}')
print(f'PCG Chi-squared: {chi2_pcg}, p-value: {p_pcg}')

Results

Image by Author

Key Observations

• Mersenne Twister and Linear Congruential Generator (LCG) performed well, producing results close to 50% heads and tails. They are statistically consistent with the expected distribution.
• Xorshift and PCG showed extreme bias. The chi-squared statistic for both is 100,000, and the p-value is 0.0, indicating that their results are highly significant and do not conform to the expected 50% heads/tails distribution. These values suggest that both PRNGs failed to generate randomness correctly, producing 100% heads across 100,000 tosses.

The p-value of 0.0 is far below the typical threshold of 0.05, confirming that the deviation observed in these PRNGs is not due to chance. This bias could stem from issues in their statistical properties or implementation.

Visualizing the Data: How Each PRNG Performed

To better understand the performance of each PRNG, it’s essential to visualize the results. By generating histograms and scatter plots, we can compare how each PRNG approximates the 50% heads and 50% tails distribution. We’ll also explore how the results vary across different PRNGs.

Histograms of Heads vs. Tails

We can use Matplotlib to plot histograms of the results from each PRNG. The histograms show the frequency of heads (1) and tails (0) generated by each PRNG, allowing us to visually assess how evenly the outcomes are distributed.

Here’s how you can plot the histograms:

import matplotlib.pyplot as plt

# Convert boolean toss results to integers (True -> 1, False -> 0)
np_tosses_int = np_tosses.astype(int)
lcg_tosses_int = np.array(lcg_tosses).astype(int)
xorshift_tosses_int = np.array(xorshift_tosses).astype(int)
pcg_tosses_int = np.array(pcg_tosses).astype(int)

# Create a figure with subplots
plt.figure(figsize=(12, 8))

# Mersenne Twister Histogram
plt.subplot(2, 2, 1)
plt.hist(np_tosses_int, bins=2, color='blue', edgecolor='black', alpha=0.7)
plt.title('Mersenne Twister Tosses')

# LCG Histogram
plt.subplot(2, 2, 2)
plt.hist(lcg_tosses_int, bins=2, color='orange', edgecolor='black', alpha=0.7)
plt.title('LCG Tosses')

# Xorshift Histogram
plt.subplot(2, 2, 3)
plt.hist(xorshift_tosses_int, bins=2, color='green', edgecolor='black', alpha=0.7)
plt.title('Xorshift Tosses')

# PCG Histogram
plt.subplot(2, 2, 4)
plt.hist(pcg_tosses_int, bins=2, color='red', edgecolor='black', alpha=0.7)
plt.title('PCG Tosses')

# Adjust layout and show plot
plt.tight_layout()
plt.show()

This will create four histograms in a 2×2 grid, each representing the distribution of heads and tails for a specific PRNG. The x-axis will be heads (1) and tails (0), and the y-axis will show the frequency of each outcome.

Result

Image by Author

Scatter Plots of Coin Toss Sequences

Scatter plots can be useful to visualize the sequence of heads and tails generated by each PRNG. We’ll plot the results as a sequence of tosses over time (from 1 to 100,000 tosses). This will give us a visual representation of how each PRNG behaves across the simulation.

Here’s the code for plotting scatter plots:

# Create a figure with subplots
plt.figure(figsize=(12, 8))

# Mersenne Twister Scatter Plot
plt.subplot(2, 2, 1)
plt.scatter(range(1, num_tosses + 1), np_tosses, color='blue', s=1, alpha=0.5)
plt.title('Mersenne Twister Tosses Sequence')

# LCG Scatter Plot
plt.subplot(2, 2, 2)
plt.scatter(range(1, num_tosses + 1), lcg_tosses, color='orange', s=1, alpha=0.5)
plt.title('LCG Tosses Sequence')

# Xorshift Scatter Plot
plt.subplot(2, 2, 3)
plt.scatter(range(1, num_tosses + 1), xorshift_tosses, color='green', s=1, alpha=0.5)
plt.title('Xorshift Tosses Sequence')

# PCG Scatter Plot
plt.subplot(2, 2, 4)
plt.scatter(range(1, num_tosses + 1), pcg_tosses, color='red', s=1, alpha=0.5)
plt.title('PCG Tosses Sequence')

# Adjust layout and show plot
plt.tight_layout()
plt.show()

These scatter plots will display the sequence of heads and tails (1s and 0s) for each PRNG, allowing you to see how randomly distributed the tosses are. For PRNGs like Mersenne Twister and LCG, you should see a fairly balanced distribution. For Xorshift and PCG, the sequence will be far more clustered (all heads in this case).

Result

Image by Author

Wrapping Up

After completing the experiment, we gained several key insights:

• Mersenne Twister and Linear Congruential Generator (LCG) performed well, producing results close to 50% heads and tails. Their chi-squared p-values were near 1, suggesting no significant deviation from the expected distribution.
• Xorshift and PCG performed poorly, returning 100% heads in all simulations. Their chi-squared p-values were 0.0, indicating that the deviation was not random but a result of systematic bias in the algorithms.
• Statistical Tests: The chi-squared test confirmed that Xorshift and PCG were biased, while Mersenne Twister and LCG showed no such bias.

The results highlight the importance of choosing the right PRNG depending on the application. In real-world applications like cryptography, which require highly reliable randomness, such failures are significant. However, for simple simulations, PRNGs like Mersenne Twister are often acceptable.