通过排除 C 中的一个值来改变一组离散概率

Question

我在 C 的一个项目中工作，我想在以下条件下逐步改变

uint32_t

：

1. 位翻转的概率从最低有效位 (LSB) 的概率为 1/2 开始，然后左边的下一位为 1/4，下一位为 1/8，依此类推（参见示例数组） .
2. 翻转位

   k

   后，概率（k）的值根据第一步中的分布重新分配给所有其他位。
3. probability(k) 然后设置为零。

我想这些概率最好存储在长度为 32 的双精度数组中，因此一个非常有用的答案是一个函数，它接受长度为 32 的双精度数组和一些要排除的整数，并返回修改后的长度为 32 的数组.

这是否可以通过使用步骤 1 中的过程生成不包括

k

的长度为 31 的数组，将每个值乘以

array[k]

的值，然后使用

array[k] = 0

创建长度为 32 的数组并将其添加到输入数组（设置后

input[k] = 0

?

我想象可能会发生但我不确定如何解决的问题：

• 在第一步中，这些概率都是 1.) 大到足以用双精度表示和 2.) 2 的幂，因此它们被精确表示。但是，没有充分的理由说明它们会保持这种状态。下面的示例数组总和为 1，因为它们都可以精确表示。同样，我没有理由假设其他值也是如此。我不清楚如何保留粗略的实用能力，以相当于从总和为 1 的分布中进行选择的方式进行选择。

答案

解决方案必须使用 C，因为项目中的其余代码都是。抱歉，我敢肯定有非常酷的方法可以用其他语言解决这个问题。 R 中的 binomial 包可能有一些东西可以做到这一点，但这没有帮助。我可以手动调整代码以在 C 中工作的类 C 语言也很好。

我在台式计算机上，否则可以控制开发环境，因此欢迎任何可以简化此操作的库。谢谢。此外，我不希望有任何性能限制，因此速度慢或需要存储表的代码很好。

我这里的例子使用双打，但这不是确定的。我来这里问这个问题是因为我不知道该怎么做。如果您有一个完全适用于整数的答案，那么我很乐意看到它。

示例数组

void create_array32(double array[32]) {
    int i;
    for (i = 0; i < 32; i++) {
        array[i] = pow(2, -(32 - i));
    }
}
// The output, if that is easier to work with
double example[32] = {
0.0000000002328306, 0.0000000004656613,
0.0000000009313226, 0.0000000018626451,
0.0000000037252903, 0.0000000074505806,
0.0000000149011612, 0.0000000298023224,
0.0000000596046448, 0.0000001192092896,
0.0000002384185791, 0.0000004768371582,
0.0000009536743164, 0.0000019073486328,
0.0000038146972656, 0.0000076293945312,
0.0000152587890625, 0.0000305175781250,
0.0000610351562500, 0.0001220703125000,
0.0002441406250000, 0.0004882812500000,
0.0009765625000000, 0.0019531250000000,
0.0039062500000000, 0.0078125000000000,
0.0156250000000000, 0.0312500000000000,
0.0625000000000000, 0.1250000000000000,
0.2500000000000000, 0.5000000000000000}

Answer 1

不是维护概率数组，而是维护相应的选择频率数组：

uint32_t frequencies[32];

for (int i = 0; i < 32; i++) {
    frequencies[i] = (uint32_t) 1 << (31 - i);
}

如果愿意，您可以预先计算这些起始频率并将它们放入初始化程序中，而不是在运行时计算它们。

每次你想做选择的时候，

1. 计算频率的累积和数组：

   uint32_t cumulative[33] = {0};
   
   for (int i = 0; i < 32; i++) {
       cumulative[i + 1] = cumulative[i] + frequencies[i];
   }
   

2. 生成一个（均匀分布的）随机数

   x

   介于0（含）和

   cumulative[32]

   （不含）之间。

3. 找到值

   n

   使得

   cumulative[n] <= x && x < cumulative[n + 1]

   。这个

   n

   就是选择的位数。您可以使用二分搜索，但线性搜索会更简单，而且只有 32 个项目，速度差不多。

要从进一步考虑中删除位

n

，只需将其频率设置为0：

frequencies[n] = 0;

当您计算下一个选择的新累积总和时，这自然会将

n

排除在外，并通过计算修改后的总数来调整所有剩余选项的概率。