algorithm - 生成带有熵参数的伪随机流

Question

如何生成长度为n的二进制结果流，其中 0 和 1 的数量相等，但成对结果的频率有偏差，即给定交替率k ( freq(01) + freq(10) ) / ( freq(00) + freq(11) ) = k

Answer 1

生成具有以下转移概率的随机马尔可夫链：

        0       1
0   1/(k+1)  k/(k+1)

1   k/(k+1)  1/(k+1)

本质上，如果您刚刚生成 0，则以概率 1/(k+1) 生成另一个 0

注意：如果要保证要求，请使用以下方法

让我们假设您要生成 mk 个不相等的组合和 m 个相等的组合。

1. 令reserve_eq = m，reserve_uneq=mk。
2. 以相等的概率生成一个随机位 0/1。让 cur 成为那一点
3. 输出电流
4. 以加权概率 (reserve_eq,reserve_uneq) 生成 new_cur = (cur,1-cur)
5. 如果 new_cur= cur 则递减 reserve_eq，否则递减 reserve_uneq
6. cur = new_cur
7. 转到第 3 步

如果reserve_eq 和reserve_uneq 都为零，则在步骤4 中退出。输出字符串的长度为 km+m+1。