位序列中 N 个连续真实位的统计概率？

Question

假设我有一个 N 位的生成位流。（在我的例子中是 64kilobits。）

找到包含在 N 位流中的 X "all true" 位序列的概率是多少。其中 X = (2 至 16)，且 N = (16 至 1000000)，且 X < N.

例如：如果N=16且X=5，在16位数字中找到11111的可能性是多少

喜欢这个伪代码：

int N = 1<<16; // (64KB)
int X = 5;
int Count = 0;
for (int i = 0; i < N; i++) {
    int ThisCount = ContiguousBitsDiscovered(i, X);
    Count += ThisCount;
}
return Count;

也就是说，如果我们运行一个从 0 到 64K-1 的循环中的整数...11111 会在这些数字中出现多少次。

额外规则：1111110000000000 不算在内，因为它连续有 6 个真值，而不是 5 个。所以：

1111110000000000 = 0x // because its 6 contiguous true bits, not 5.
1111100000000000 = 1x
0111110000000000 = 1x
0011111000000000 = 1x
1111101111100000 = 2x

我正在尝试做一些涉及基于物理的运行dom-number 生成和检测 "how random" 数字的工作。这就是它的用途。

...

如果 N 小于 32 左右，这将很容易解决，我可以 "run a loop" 从 0 到 4GB，然后在循环完成后计算检测到的连续位的数量。然后我可以存储该号码并在以后使用它。

考虑到 X 运行ges 从 2 到 16，我实际上只需要存储 15 个数字，每个数字少于 32 位！（如果 N=32）！

但在我的例子中，N = 65,536。所以我需要运行一个循环，进行 2^65,536 次迭代。基本不可能:)

没办法"experimentally calculate the values for a given X, if N = 65,536"。所以我基本上需要数学。

Answer 1

有点蛮力，但我会这样做以避免陷入统计理论的泥潭：

循环时乘以概率（1 位 = 0.5，2 位 = 0.5*0.5，等等）
跟踪每个 X，当你有 X 位的乘积时，翻转它并继续
从小例子 (N = 5, X=1 - 5) 开始，以确保你得到正确的边缘情况，与蛮力方法进行比较。

这可能表示为 Sum (Sum 0.5^x (x = 1 -> 16) (for n = 1 - 65536) ，但需要考虑边缘情况（即 7 位不'fit, discard probability），这让我有点头疼。:-)

Answer 2

修复 X 和 N，严重地 X < N。您的位号中有 2^N 个可能的 0 和 1 组合值，并且您有 N-X +1 个 1*X 的可能序列（在这部分我只寻找 1's一起）包含在你的位号中。考虑例如 N = 5 和 X = 2，这是一个可能的有效位数 01011，因此固定最后两个字符（最后两个 1's）你有 2^2 该 1*X 序列的可能组合。那么你有两种情况：

边界大小写：你的1*X在边界内，那么你有(2^(N -X -1))*2种可能的组合

内壳：你有(2^(N -X -2))*(N-X-1)种可能的组合。

所以，概率是(border + inner )/2^N

示例：

1)N = 3, X =2,则概率为2/2^3
2)N = 4, X = 2,则概率为5/16

Answer 3

@Andrex 的回答完全错误，因为它多次计算了某些组合。

例如考虑案例 N=3、X=1。然后组合 101 只发生 1/2^3 次，但边界计算计算了两次：一次是从 10 开始的序列，另一次是从 01 结束的序列。

他的计算给出了 (1+4)/8 的概率，而只有 4 个唯一序列至少有一个连续的 1（与 011 等情况相反):

所以概率是4/8.

要计算唯一序列的数量，您需要考虑可能出现多次的序列。只要 X 小于 N/2 就会发生这种情况。不知道如何计算它们。

位序列中 N 个连续真实位的统计概率？

Statistical probability of N contiguous true-bits in a sequence of bits?

math

statistics

probability

bit