The Amplified Loaded Dice Roller (Experiments)

This repository contains experiments relating to the Amplified Loaded Dice Roller (ALDR), a fast algorithm for generating rolls of an $n$-sided die with rational probabilities, as described in the following article.

Efficient Rejection Sampling in the Entropy-Optimal Range. Thomas L. Draper, Feras A. Saad. arXiv:2504.04267 [cs.DS], 2025. https://doi.org/10.48550/arXiv.2504.04267

For a reference implementation of ALDR in C, please use the standalone repository at https://github.com/probsys/amplified-loaded-dice-roller.

Installation

To use a Python 3 virtual environment, run the following command.

python3 -m venv aldr-experiments
source aldr-experiments/bin/activate

To install the required Python dependencies, run the following command.

python -m pip install -r requirements.txt

The c/ and rust/ directories include benchmarking programs for ALDR and an exact implementation of the Walker alias method, using the probability distributions from distributions/*.dist. To build and run these benchmarks, follow the instructions in c/README.md and rust/aldr/README.md.

Running the experiments

The following instructions show how to reproduce Figures 4, 5, 6, 8, and 11 from the main paper, as well as other related computations. This software is tested on Ubuntu 24.04. After installing the dependencies, the notebooks can be run by launching a Jupyter server in the browser as follows.

python -m jupyter lab

Figure 4

Run the notebook in python/figure-4-aldr-tree-tolls-478.ipynb.

Figure 5

Run the notebook in python/figure-5-aldr-generic-toll-bound.ipynb.

Figure 6

Run the notebook in python/figure-6-relative-tolls.ipynb.

Figure 8

Run the notebook in python/figure-8-aldr-tolls-1669.ipynb.

Figure 11

Run the notebook in python/figure-11-alias-aldr-compare.ipynb.

Further experiments

More complete benchmarking data is included in python/aldr-alias-performance-data.txt. To collect this data for your system, make sure that the c/ and rust/aldr/ projects are built, and then run python/experiment-benchmark.py. The notebook python/experiment-benchmark.ipynb contains more visualizations for these data compared to python/figure-11-alias-aldr-compare.ipynb.

The notebooks python/experiment-*.ipynb contain more experiments and examples of ALDR trees, as well as analysis of the entropy cost.

Entropy cost bounds

The script python/verification-toll-aldr-p-2k-leq-2.py provides a concise verification that the toll of ALDR is less than $2$ at depths satisfying $2k \leq K < 16$, which completes the computational part of the proof of Theorem (Bounding the toll of ALDR) in the paper. The following scripts give further computational confirmation of the Theorem:

1. python/bruteforce-max-toll.py: a brute-force search over integer partitions of $m$ (in exponential time),
2. python/dp-*.py: an array dynamic programming algorithm to compute the worst-case toll of any $m$-type distribution (in quadratic time),
3. python/relative-toll-*.py: a linear check of the stronger bound that the relative toll of each $A_i$ given weight sum $M$ is less than two for each $a_i \in \{ 1, \ldots, m \}$.

Experimental Python library

The file python/customtree.py contains an implementation of the Knuth and Yao entropy-optimal tree for finite rational discrete distributions, as well as FLDR and ALDR with related functions for entropy cost. The file python/customtreeplot.py contains automatic plotting functions for tolls of ALDR trees as a function of depth.