RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2005 Volume 17, Issue 4, Pages 72–80 (Mi dm130)

This article is cited in 1 paper

Generation of uniform distribution robust to nonequiprobability of the initial digits

F. M. Malyshev


Abstract: We consider procedures of generation of a random residue modulo $q$, where $q$ is some positive integer. We start from a sequence of independent equiprobable residues modulo $p$, where $p$ is some positive integer; the problem consists of minimisation of the average number of needed digits. Furthermore, the equiprobability of the output digit must be retained even in the case where the input of the procedure is fed by nonequiprobable independent identically distributed digits. Our attraction is toward more simple and less labour-consuming procedures. Our main results concern the cases $q=n!$ and $q=\binom nr$.

UDC: 519.2

Received: 14.10.2003
Revised: 15.01.2005

DOI: 10.4213/dm130


 English version:
Discrete Mathematics and Applications, 2005, 15:6, 581–589

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025