UOJ Logo liu_cheng_ao的博客

博客

最小期望次数生成随机有理数

2017-09-21 17:32:35 By liu_cheng_ao

已知:随机数生成元件等概率返回 $[0,p)$ 中的整数,要构造一个以概率比 $a_0:a_1:...:a_n(\gcd(a_i)=1)$ 返回 $[0,n)$ 中的整数的随机数生成器,求元件的最小期望使用次数。

设第 $i$ 次返回的结果分配了 $K_{i,j}$ 个给返回值 $j$。则:

$$ \begin{array} \forall j ,\sum_i p^{-i}K_{i,j}=\frac{a_j}{\sum a} & (1)\\ \text{minimum.} \sum_{i,j}ip^{-i}K_{i,j} & (2) \end{array} $$

引理1 $\forall i,j ,K_{i,j}\in [0,p) $

证:使用调整法:

若 $\forall i,j ,K_{i,j}\neq p $,由 $(1)$ 有 $i>0$ ,则可令 $K_{i-1,j}$ 增加 $1$,$K_{i,j}$ 减少 $p$,显然 $(1)$ 式仍成立。

$(2)$ 式的改变量为 $(i-1)p^{-i+1}-pip^{-i}=-p^{-i+1} < 0$ ,得到了一个更优解。

证毕。

现在来构造 $K$。考虑返回值为 $j$ 的情况,取出 $K$ 的第 $j$ 列向量,设为 $\vec{k}$。

则 $\vec{k}$ 是 $p$ 进制的 $\frac{a_j}{\sum a}$ 的位向量。当 $\sum a$ 是 $p$ 的幂时有两解,取最后为 $0$ 循环的一解;否则 $\vec{k}$ 是唯一的。证明从略。

至此找到了一个下界 $K$。在决策树上第 $i$ 层给 $j$ 分配 $K_{i,j}$ 个点,用归纳法可以证明方案是存在的。

另外可得推论:

推论1 “$a$ 是有理数”与“存在一个有 $n$ 个终态,字符集为 $[0,p)$ ,按随机数生成元件的结果转移,返回终止的状态的DFA满足条件。”是等价的。

证明从略。解释说明:由于 DFA 是有限状态的,因而对应的概率是循环小数(有理数)。反之则可用上述方法构造。

评论

ztr
令m为ai的和,对于单个概率x=ai/m,考虑一个贡献f(x),可以发现这里的贡献是互相独立的,总期望就是f(x)之和。 推一下有f(x)和f(x*p%1.0)(这里%表示fmod)的线性关系,而且x*p%1.0和x一样可以有一个t/m(t是整数)的表示。 所以考虑所有f(i/m)(0<=i<m),可以列出恰好m个线性关系。可以发现是一个环套树的东西,于是可以O(m)解出所有f(i/m)。 显然对于要求解的同一组ai,m是相同的,所以整个可以O(m)计算。
613
我为啥有一种第一个式子就有毛病的错觉

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。