pipette
ESEspañol

Dice enterprises and polynomial approximation: uniform query tails

Jessica Taylor

Preprint

In the authors' words

A binary-output dice enterprise uses independent rolls of a die with unknown face probabilities (along with fair coin flips) to simulate a coin with bias . We determine which power-law tails, uniform over the closed probability simplex, are attainable for the number of rolls. For continuous with values in and , some enterprise for satisfies if and only if can be approximated uniformly by polynomials of degree with error . When this holds, the same tail bound is attained by an oblivious enterprise, which chooses its number of rolls before rolling. The characterization extends to multiple dice, with total degree on a product of simplices; it then suffices to roll the dice in a fixed cyclic order. For , these enterprises have a uniformly bounded expected number of rolls.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 13 pages, no figures