Saving fractional bits: A practical entropy efficient code for fair die rolls

Autor:	Ömer, Bernhard, Pacher, Christoph
Rok vydání:	2014
Předmět:	Computer Science - Information Theory
Druh dokumentu:	Working Paper
Popis:	We give an implementation of an algorithm that uses fair coin flips to simulate fair rolls of an $n$-sided die. A register plays the role of an entropy pool and holds entropy that is generated as a by-product during each die roll and that is usually discarded. The entropy stored in this register is completely reused during the next rolls. Consequently, we can achieve an almost negligible loss of entropy per roll. The algorithm allows to change the number of sides of the die in each round. We prove that the entropy loss is monotone decreasing with increasing entropy pool size (register length). Comment: 5 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1412.7407 Zobrazit plný text záznamu View this record from Arxiv