Dice enterprises and polynomial approximation: uniform query tails
math.PR
Submitted: 2026-10-28
Updated: 2026-10-28
Comments: 13 pages, no figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: A binary-output dice enterprise uses independent rolls of a die with unknown face probabilities p (along with fair coin flips) to simulate a coin with bias f(p).
Abstract
A binary-output dice enterprise uses independent rolls of a die with unknown face probabilities p (along with fair coin flips) to simulate a coin with bias f(p). We determine which power-law tails, uniform over the closed probability simplex, are attainable for the number N of rolls. For continuous f with values in (0,1) and q>0, some enterprise for f satisfies p P p(N>n)=O(n-q) if and only if f can be approximated uniformly by polynomials of degree k with error O(k-2q). 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 q>1, these enterprises have a uniformly bounded expected number of rolls.
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves
- A zero-one law for swap-invariant events in uniform spanning forests
- Bernoulli flow for Erd s-R'enyi graphs