时间戳

首页 > 解决方案 > 对随机序列进行下采样会使其随机性降低吗？有没有一个原理/定理可以证明这一点？

c++ - 对随机序列进行下采样会使其随机性降低吗？有没有一个原理/定理可以证明这一点？

问题描述

我想知道对随机（或伪随机）序列进行下采样是否会使其随机性降低或保持其随机性。例如，如果您采用一系列伪随机字节，如下面的代码所示，并丢弃除字母数字字符之外的所有字符，那么生成的字母数字字符串是否仍然是伪随机字符？随机案例呢？

是否有数学或计算原理或定理以一种或另一种方式显示这一点？

我看了这个问题： 随机序列的子集也是随机的吗？

但这并没有具体涵盖一个选择过程，其中包括正在选择的值的知识。MusiGenesis 的回答似乎是说这可能会导致更少的随机性。

// Open the /dev/urandom file to read random bytes
ifstream rand_file("/dev/urandom");

if (!rand_file) {
    cout << "Cannot open /dev/urandom!" << endl;
    return return_code::err_cannot_open_file;
}

string password("");
vector<char> rand_vec(rand_vec_length, 0);
while (password.length() < pwd_length) {
     fill_rand_vec(rand_vec, rand_file);

    // Iterate through the vector of psuedo-random bytes and add 
    // printable chars to the password
    for (auto rand_char : rand_vec) {
        if (isprint(rand_char) && !isspace(rand_char)) {
            password += rand_char;
        }

        if (password.length() >= pwd_length) {
            break;
        }
    }
}

标签： c++linuxrandom

解决方案

我不是数学家，但在我看来，假设你的初始字节序列是均匀分布的，在丢弃所有不在你想要的范围内的字节之后，剩余的字节仍然必须是均匀分布的。只是您事先不知道需要多少随机字节才能得到给定的所需数量的随机字母数字字符。它实际上可能需要任意长的时间，这使得这种方法不是特别有效。但是您获得输出值的方法并不喜欢任何字母数字字符值而不是任何其他字符值，因此生成的字母数字字符，无论它们可能有多少，实际上除了均匀分布之外也不能真正成为任何东西。

在我看来，您所描述的基本上是拒绝采样，这是一种能够从任意概率分布生成样本的标准技术。您可能想阅读数学证明。我相信您的特定示例可以被视为拒绝对概率分布进行抽样，其中字母数字字符值的概率为 1/36（我认为，这取决于您究竟认为字母数字是什么），而其他所有值的概率为 0……

推荐阅读