生成具有可变比例"1"位的随机二进制数

Question

我需要一个函数来生成随机整数.(long现在假设Java 类型,但这将扩展到BigInteger或BitSet稍后.)

棘手的部分是有一个参数P,它指定结果中任何位的(独立)概率为1.

如果P = 0.5,那么我们可以使用标准随机数发生器.P的一些其他值也易于实现.这是一个不完整的例子:

Random random = new Random();

// ...

long nextLong(float p) {
    if      (p == 0.0f)   return 0L;
    else if (p == 1.0f)   return -1L;
    else if (p == 0.5f)   return random.nextLong();
    else if (p == 0.25f)  return nextLong(0.5f) & nextLong(0.5f);
    else if (p == 0.75f)  return nextLong(0.5f) | nextLong(0.5f);
    else if (p == 0.375f) return nextLong(0.5f) & nextLong(0.75f); // etc
    else {
      // What goes here??
      String message = String.format("P=%f not implemented yet!", p);
      throw new IllegalArgumentException(message);
    }
}

有没有办法将P的任何值在0.0和1.0之间进行推广？

Answer 1

首先是一些你已经在代码中使用的丑陋数学。

定义 x 和 y 分别是 X = p(x=1), Y = p(y=1) 的概率为 1 的位。然后我们有

 p( x & y = 1) = X Y
 p( x | y = 1) = 1 - (1-X) (1-Y)
 p( x ^ y = 1) = X (1 - Y) + Y (1 - X)

现在如果我们让 Y = 1/2 我们得到

P( x & y ) = X/2
P( x | y ) = (X+1)/2

现在将 RHS 设置为我们想要的概率，我们有两种情况可以解决 X

X = 2 p        // if we use &
X = 2 p - 1    // if we use |

接下来我们假设我们可以再次使用它来根据另一个变量 Z 获得 X ......然后我们继续迭代，直到我们已经完成了“足够”。

这有点不清楚，但请考虑 p = 0.375

0.375 * 2 = 0.75  < 1.0 so our first operation is &
0.75 * 2 = 1.5 > 1.0 so our second operation is |
0.5 is something we know so we stop.

因此我们可以通过 X1 & (X2 | X3 ) 得到 p=0.375 的变量

问题是对于大多数变量，这不会终止。例如

0.333 *2 = 0.666 < 1.0 so our first operation is &
0.666 *2 = 1.333 > 1.0 so our second operation is |
0.333 *2 = 0.666 < 1.0 so our third operation is &
etc...

所以 p=0.333 可以由

X1 & ( X2 | (X3 & (X4 | ( ... ) ) ) )

现在我怀疑在系列中使用足够多的项会给你足够的准确性，这可以写成一个递归函数。然而，也可能有更好的方法......我认为操作的顺序与 p 的二进制表示有关，我只是不确定到底如何......并且没有时间更深入地思考它。

无论如何，这里有一些未经测试的 C++ 代码可以做到这一点。您应该能够轻松地对其进行 javaify。

uint bitsWithProbability( float p )
{
   return bitsWithProbabilityHelper( p, 0.001, 0, 10 );
}

uint bitsWithProbabilityHelper( float p, float tol, int cur_depth, int max_depth )
{
   uint X = randbits();
   if( cur_depth >= max_depth) return X;
   if( p<0.5-tol)
   {
     return X & bitsWithProbabilityHelper( 2*p, 0.001, cur_depth+1, max_depth );
   }
   if(p>0.5+tol)
   {
     return X | bitsWithProbabilityHelper( 2*p-1, 0.001, cur_depth+1, max_depth );
   }
   return X;
}

Answer 2

这是我最终解决的方法。

\n\n

\n
1. 生成 0..16 之间的整数 N，遵循二项式分布。这给出了 16 位部分结果中“1”位的数量。
\n
2. 随机生成查找表的索引，该索引包含 16 位整数，其中包含所需数量的“1”位。
\n
3. 重复4次，得到4个16位整数。
\n
4. 将这四个 16 位整数拼接在一起得到一个 64 位整数。
\n

\n\n

这部分是受到 Ondra \xc5\xbdi\xc5\xbeka 的回答的启发。

\n\n

这样做的好处是，它将调用次数减少到Random.nextLong()每 64 位输出 8 次调用。\n相比之下，滚动每个单独的位将需要 64 次调用。按位 AND/OR 使用 2 到 32 次调用，具体取决于P

\n\n

当然，计算二项式概率同样昂贵，因此它们会放入另一个查找表中。

\n\n

虽然代码很多，但在性能方面却得到了回报。

\n\n\n\n

更新- 将其与按位 AND/OR 解决方案合并。如果它猜测该方法会更有效（就调用而言Random.next()），它现在会使用该方法。

\n