Shannon Entropy Loss in Mixed-Radix Conversions

Entropy

Amy Vennos¹  Alan Michaels¹ 

[1] Hume Center for National Security and Technology, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, USA;

关键词: PRNG;    Shannon entropy;    mixed-radix conversion;   

DOI  :  10.3390/e23080967

来源: DOAJ

【 摘 要 】

This paper models a translation for base-2 pseudorandom number generators (PRNGs) to mixed-radix uses such as card shuffling. In particular, we explore a shuffler algorithm that relies on a sequence of uniformly distributed random inputs from a mixed-radix domain to implement a Fisher–Yates shuffle that calls for inputs from a base-2 PRNG. Entropy is lost through this mixed-radix conversion, which is assumed to be surjective mapping from a relatively large domain of size $2^J$ to a set of arbitrary size n. Previous research evaluated the Shannon entropy loss of a similar mapping process, but this previous bound ignored the mixed-radix component of the original formulation, focusing only on a fixed n value. In this paper, we calculate a more precise formula that takes into account a variable target domain radix, n, and further derives a tighter bound on the Shannon entropy loss of the surjective map, while demonstrating monotonicity in a decrease in entropy loss based on increased size J of the source domain $2^J$. Lastly, this formulation is used to specify the optimal parameters to simulate a card-shuffling algorithm with different test PRNGs, validating a concrete use case with quantifiable deviations from maximal entropy, making it suitable to low-power implementation in a casino.

【 授权许可】

Unknown