Generation of uniform distribution robust to nonequiprobability of the initial digits

F. M. Malyshev

Diskretnaya Matematika, Tome 17 (2005) no. 4, pp. 72-80

Résumé

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$.