Dice enterprises and polynomial approximation: uniform query tails
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 suppℙ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
- Factor of i.i.d. with polynomial tails for the long-range Ising model
- Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231
- On the uniform flatness of polynomial graphs
- Uniform-in-time relative entropy estimates for Kac's approximation of the Landau equation
- Uniform W2,m approximation of almost isometric maps
BibTeX
@misc{taylor2026dice,
title = {{Dice enterprises and polynomial approximation: uniform query tails}},
author = {Jessica Taylor},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38964},
eprint = {2610.38964},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38964},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dice enterprises and polynomial approximation: uniform query tails
AU - Jessica Taylor
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38964
UR - https://arxiv.org/abs/2610.38964
AB - 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 sup_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.
ER -