We consider the problem of computing with many coins of unknown bias. We are given samples access to $n$ coins with \emph{unknown} biases $p_1,\dots, p_n$ and are asked to sample from a coin with bias $f(p_1, \dots, p_n)$ for a given function $f:[0,1]^n \rightarrow [0,1]$. We give a complete characterization of the functions $f$ for which this is possible. As a consequence, we show how to extend various combinatorial sampling procedures (most notably, the classic Sampford Sampling for $k$-subsets) to the boundary of the hypercube.
翻译：我们考虑的是使用许多不明偏差的硬币进行计算的问题。 我们被允许抽样使用 $n 的硬币, 并使用 $p_ 1,\ dots, p_n$, 并且被要求使用 $f (p_ 1,\ dots, p_n) 的硬币样本, 用于给定函数 $f : [0,1]n\rightrow [0,1]$。 我们给出了可能的功能的完整特征描述 $f 。 因此, 我们展示了如何将各种组合取样程序( 最显著的是经典的Sampford Samplings for $k$-subsets) 扩大到超立方的边界 。
相关内容
微信扫码咨询专知VIP会员