Gray Codes Generation Algorithm and Theoretical Evaluation of Random Walks in N-Cubes

Sylvain Contassot-Vivier, Jean-François Couchot and Pierre-Cyrille Héam
Additional contact information
Sylvain Contassot-Vivier: Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), UMR 7503, Université de Lorraine, F-54506 Vandoeuvre-lès-Nancy, France
Jean-François Couchot: FEMTO-ST Institute, UMR 6174, Université Bourgogne Franche-Comté, 19 Av. du Maréchal Juin, F-90000 Belfort, France
Pierre-Cyrille Héam: FEMTO-ST Institute, UMR 6174, Université Bourgogne Franche-Comté, 19 Av. du Maréchal Juin, F-90000 Belfort, France

Mathematics, 2018, vol. 6, issue 6, 1-16

Abstract: In previous works, some of the authors have proposed a canonical form of Gray Codes (GCs) in N -cubes (hypercubes of dimension N). This form allowed them to draw an algorithm that theoretically provides exactly all the GCs for a given dimension N . In another work, we first have shown that any of these GC can be used to build the transition function of a Pseudorandom Number Generator (PRNG). Also, we have found a theoretical quadratic upper bound of the mixing time, i.e., the number of iterations that are required to provide a PRNG whose output is uniform. This article, extends these two previous works both practically and theoretically. On the one hand, another algorithm for generating GCs is proposed that provides an efficient generation of subsets of the entire set of GCs related to a given dimension N . This offers a large choice of GC to be used in the construction of Choatic Iterations based PRNGs (CI-PRNGs), leading to a large class of possible PRNGs. On the other hand, the mixing time has been theoretically shown to be in N log ( N ) , which was anticipated in the previous article, but not proven.

Keywords: Gray Codes; Hamiltonian cycles; N-cube; mixing time; PRNG (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/6/6/98/pdf (application/pdf)
https://www.mdpi.com/2227-7390/6/6/98/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:6:y:2018:i:6:p:98-:d:151517

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().