论文标题
蒙特卡洛算法中随机位数量的下限
Lower bounds for the number of random bits in Monte Carlo algorithms
论文作者
论文摘要
我们继续研究一般环境中受限制的蒙特卡洛算法。在这里，我们在确定性最小误差方面显示了设置中最小误差的下限，并显示有限的限制。这概括了Heinrich，Novak和Pfeiffer，2004年的自适应环境的结果。结果，该论文的随机位数上的下限也可以在这种情况下。我们还得出了在Wiener空间上集成Lipschitz函数所需位数的下限，并补充了Giles，Hefter，Mayer和Ritter的结果，Arxiv：1808.10623。
We continue the study of restricted Monte Carlo algorithms in a general setting. Here we show a lower bound for minimal errors in the setting with finite restriction in terms of deterministic minimal errors. This generalizes a result of Heinrich, Novak, and Pfeiffer, 2004 to the adaptive setting. As a consequence, the lower bounds on the number of random bits from that paper also hold in this setting. We also derive a lower bound on the number of needed bits for integration of Lipschitz functions over the Wiener space, complementing a result of Giles, Hefter, Mayer, and Ritter, arXiv:1808.10623.
