生成具有一定熵的随机数序列

Question

我需要生成部分随机的数字序列，使序列整体具有一定的熵水平。

例如如果我将生成的数据输入 gzip，它就可以压缩它。事实上，这将是代码的确切应用，测试数据压缩器。

我正在用 C++ 对此进行编程，我想到的第一个想法是用随机种子初始化一堆 std::mt19937 PRNG，然后随机选择一个并用它制作随机长度模式。 std::mt19937 每次都使用相同的种子进行重置，因此它始终生成相同的模式：

#include <iostream>
#include <random>
#include <vector>

int main() {

    std::random_device rd;
    std::vector<std::mt19937> rngs;
    std::vector<int> seeds;

    std::uniform_int_distribution<int> patternrg(0,31);
    std::uniform_int_distribution<int> lenghtrg(1,64);
    std::uniform_int_distribution<int> valuerg(0,255);

    for(int i = 0; i < 32; ++i) {
        seeds.push_back(rd());
        rngs.emplace_back(seeds.back());
    }

    for(;;) {
        // Choose generator and pattern lenght randomly.
        auto gen = patternrg(rd);
        auto len = lenghtrg(rd);
        rngs[gen].seed(seeds[gen]);
        for(int i = 0; i < len; ++i) {
            std::cout << valuerg( rngs[gen] )<<"\n";
        }
    }
}

以上代码满足生成可压缩随机性的第一个要求，但第二个更难：如何控制级别entropy/randomness?

Answer 1

让我写几句你会觉得有用的句子。假设我们想用给定的熵采样一位。所以它不是0就是1，你想要的熵等于e.

H(10|p) = -p log₂(p) - (1 - p) log₂(1 - p)，其中 p 是获得 1 的概率。简单测试 - 在 p=1/2 的情况下，一个人将获得 1 的熵 - 最大熵。那么你选择 e 等于小于 1 的某个值，求解方程

-p log₂(p) - (1 - p) log₂(1 - p) = e

然后返回 p，然后您可以使用 Bernoulli distribution. Simple demo is here. And in C++ one could use standard library routine.

开始采样

好的，假设你想用给定的熵对一个字节进行采样。它有 256 个值，熵

H(byte|\vec{p}) = -Sum(1...256) p_i log₂( p_i).

同样，如果所有组合都是等概率的 (p_i=1/256)，您将得到 -256/256 log₂(1/256) = 8，这是最大熵。如果你现在固定你的熵（比如，我希望它是 7），那么 p_i 会有无限多的解，给定的熵没有唯一的实现。

您可以稍微简化问题 - 让我们再次考虑一个参数情况，其中找到 1 的概率是 p，找到 0 的概率是 (1-p)。因此，从 256 个结果中，我们现在得到其中的 9 个——00000000、00000001、00000011、00000111、00001111、00011111、00111111、01111111、11111111。对于每一种情况，我们都可以编写概率，计算熵，将其分配给你想要的任何东西，然后求解回来找到 p.

抽样相对容易 - 第一步是通过 discrete distribution, and second step would be shuffle bits inside the byte using Fisher-Yates shuffle.

对 9 种组合进行抽样

同样的方法可能用于 32 位或 64 位 - 你有 33 或 65 个案例，构造熵，分配给你想要的任何东西，找到 p，对其中之一进行采样，然后混洗采样值中的位。

现在没有代码，但如果有兴趣，我可能稍后会写一些代码...

更新

记住另一个特殊的属性固定熵。即使对于单个位的简单情况，如果您尝试解决

-p log₂(p) - (1 - p) log₂(1 - p) = e

对于给定的 e，你会得到两个答案，而且很容易理解为什么 - 方程是对称的 p 和 1-p（或者用 1 代替 0和 1 与 0）。换句话说，对于熵来说，如果您主要使用零或主要使用零来传输信息是无关紧要的。对于自然文本之类的东西，情况并非如此。

Answer 2

熵率（根据输出 byte 值，而不是人类可读的字符）你的构造有几个复杂的问题，但是（对于许多小于 256 的生成器）这是一个很好的近似值，它是 每个选择 的熵（选择序列的 5 位加上其长度的 6 位）除以子序列的 平均长度 (65/2)，或每字节可能的 8 位中的 0.338 位。（这明显低于正常的英文文本。）您可以通过定义更多序列或减少绘制的子序列的典型长度来增加熵率从每个。（如果子序列通常只有一个字符，或者序列号有数百个，则冲突必然会将熵率降低到该估计值以下，并将其限制为每字节 8 位。）

另一个易于调整的序列 class 涉及从 [0,n] 中绘制单个字节，概率为 p<1/(n+1) 0 和其他人同样可能。这给出了熵率 H=(1-p)ln (n/(1-p))-p ln p 位于 [ln n,ln (n+1)), 所以任何想要的速率可以通过选择n[=37=来选择] 然后 p 适当。（如果你想要 bits 的熵，请记住使用 lg 而不是 ln。）

生成具有一定熵的随机数序列

Generate random number sequence with certain entropy

c++

random

entropy