Gray codes generation algorithm and theoretical evaluation of random walks in \(N\)-cubes
type: Item
instance of: scholarly article
title: Gray codes generation algorithm and theoretical evaluation of random walks in \(N\)-cubes
zbMATH Open document ID: 1454.94007
author: S. Contassot-Vivier
author: Jean-François Couchot
author: Pierre-Cyrille Héam
published in: Mathematics
publication date: 2018-12-18T00:00:00Z
review text: Summary: 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 Chaotic 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.
Mathematics Subject Classification ID: 94A05
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 82C41
zbMATH DE Number: 6994629
zbMATH Keywords: Gray codes
zbMATH Keywords: Hamiltonian cycles
zbMATH Keywords: \(N\)-cube
zbMATH Keywords: mixing time
zbMATH Keywords: PRNG
describes a project that uses: TestU01
describes a project that uses: Diehard
describes a project that uses: CIPRNG
MaRDI profile type: Publication
full work available at URL: math6060098
OpenAlex ID: W2805683563
cites work: Asymptotic analysis of a random walk on a hypercube with many dimensions
cites work: Random Walk: A Modern Introduction
cites work: Exact solution for a class of random walk on the hypercube
cites work: Q4595047
cites work: Random Walk in a N-Cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations
cites work: Q5715090
cites work: Canonical form of Gray codes in \(N\)-cubes
cites work: Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion
cites work: On the Link between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems
cites work: TestU01
cites work: Handbook of computational statistics. Concepts and methods.
cites work: Counting sequences
cites work: Balanced Gray codes
cites work: A construction of Gray codes inducing complete graphs
cites work: On locally balanced gray codes
cites work: Explicit definition of the binary reflected Gray codes
cites work: On binary reflected Gray codes and functions
cites work: Markov Chains
Wikidata QID: Q129728296
DOI: 10.3390/MATH6060098
description: scientific article; zbMATH DE number 6994629