Online Random Sampling with Real Probabilities

What the math gives to ML

The paper gives a constructive entropy-optimal way to generate a long sequence of nonuniform discrete random variables while retaining only a small local random state, rather than restarting an independent sampler for every draw. Its transferable asset is randomness recycling: unused fractional information from one categorical draw is converted into a discrete uniform state and reused by later draws, with expected fair-bit consumption near the sum of output entropies and only logarithmic persistent state. This is most promising for inference-time categorical generation, stochastic MoE routing, and on-device randomized training where true random-bit consumption, rather than pseudorandom arithmetic, is a resource constraint.