nearuniform

Nearuniform, in probability and related fields, describes a discrete distribution over a finite domain that is close to uniform but not exactly so. A distribution D over a set of n outcomes is called ε-near-uniform if there exists ε ∈ [0,1) such that for every outcome i, (1-ε)/n ≤ P(i) ≤ (1+ε)/n. Equivalently, the maximum probability divided by the minimum probability is at most (1+ε)/(1-ε). Another common criterion uses total variation distance: D is ε-near-uniform if the distance to the uniform distribution on the same domain is at most ε.

Uniform is the special case ε = 0. In cryptography and randomized algorithms, near-uniform often means the distribution is statistically close to uniform, typically within a small or negligible ε; in some contexts "almost uniform" is used interchangeably.

Applications and examples include hashing, sampling, randomness extraction, and the design of randomized algorithms where unbiased outcomes are desired but exact uniformity is difficult to guarantee. Near-uniform outputs can be produced by randomness extractors, rejection sampling, or carefully designed generators that bound biases across the domain.

Limitations and considerations: the usefulness of near-uniform distributions depends on the acceptable bias in a given application. Larger ε increases potential bias and may affect security guarantees or algorithmic performance. When strong unpredictability is required, additional measures may be needed to ensure the distribution is sufficiently close to uniform.

See also: Uniform distribution, Almost uniform, Statistical distance, Pseudorandomness.