伪随机二进制序列预测

Question

给定一个有限值的伪随机二进制序列（例如：00101010010101），预测该序列将如何继续。请问有人可以告诉我最简单的方法吗？或者对于那些几乎无法在计算机上玩纸牌游戏的人来说，有人可以告诉我从哪里开始入门吗？ PS：这种技术能用于预测下一个电子轮盘号码的颜色吗（例如：将1和0分别指定为红色和黑色）？

- Rocket Power

Answer 1

加密安全的伪随机数生成器是专门用来防止您想做的事情。特别地，它们满足“下一位测试”：在给定其输出的k位的情况下，您不能以大于1/2的概率猜测第k + 1位。

普通的伪随机数生成器如果不符合下一位测试，则可能会受到攻击，实际上由于PRNG的选择，现实世界中的系统存在安全漏洞。特别地，已知线性同余生成器有些版本的Unix随机数可能使用了此算法，这种方法需要较高的数学水平。如果想要进行攻击，可以搜索"线性同余发生器预测"来开始。

另外一种攻击方式是，如果您知道PRNG的实现方式，尝试确定用于生成您正在分析的序列的种子。该种子有时基于可猜测的信息，如时间、进程ID等。

- user85509

Answer 2

先回答PS：不行，因为轮盘赌的旋转是独立事件，历史结果序列中没有任何预测性。

一般问题很难而且有趣。 这个网站可以从它们的初始值推断出惊人数量的序列：

http://www.research.att.com/~njas/sequences/

注意，这适用于任意整数序列。

我尝试了一些简单的模式，如 {0,0,1,1,0,0,1,1,...}，并且它输出了正确的结果。

- dreeves

Answer 3

对于伪随机序列，唯一的可能性是计算每种可能性之前出现的次数。如果1的数量超过0，那么下一个数字更有可能是0。这种可能性取决于每个数字相对出现的频率。

请注意，这对于真正的随机性不起作用，因为事件是独立的，尽管统计学家告诉你的是相反的:-)

当你使用轮盘赌的双倍投注法时，第一次在桌子上连续出现13个红色时，你会痛苦地发现这一点。无论如何，庄家从0（在某些桌子上还有双重0）中获得了优势，它们既不是红色也不是黑色。

- paxdiablo

---

我的直觉不允许我放弃蒙特卡罗谬论。黑色和红色在长时间内平衡的事实似乎意味着你需要一段红色的运行来抵消那段黑色的运行。显然，从理智上讲，我知道这是一个谬论，但它确实非常狡猾。 - Matt Mitchell

如果你假设这些事件是独立的，那么你是正确的。但如果不是，那么可能存在一个明显的模式，而你提出的统计方法将完全失败。例如，统计方法会建议在{1,0,0,1,0,0,1,0,0,1,0,0,...}中下一个数字为0。将其输入到整数序列在线百科全书（见我的答案）中，它将正确推断下一个数字为1。（当然，如果你知道这些事件确实是独立的，那么看似的模式就是巧合，你应该说0！） - dreeves

这是一个难以放手的问题，@Graphain。但是在我的脑海中，“长时间”意味着数以万亿计的事件，而不是你可以在赌场一夜之间完成的事情 :-) 另一件需要注意的事情是，尽管这些事件彼此独立，但它们并不一定独立于影响。我见过荷官能够可靠地将球放在特定的象限中（虽然这只是谣言，但我被告知有些人可以做到八分之一）。那就是你想要站在你这边的人，而不是庄家（至少在他被统计分析发现之前）。 - paxdiablo

我见过人们因为这样的偏见而获胜。我想知道荷官是否会感到无聊，只是说“今晚我要瞄准22号”。 - Matt Mitchell

Answer 4

这是一个不错的问题，但如果“你连纸牌都玩不好”，那么现在可能还达不到你的水平。

你应该考虑学习一门基础语言，大多数人会说PHP，但我不太敢向初学者推荐它（不过它很容易上手，可以看看XAMPP）。Java可能是一种“易于上手和使用”的语言，但我相信这里有更好的帖子讨论从哪种语言开始入门（Python或其他语言可能因为经验丰富的程序员喜欢它而获胜）。

顺便说一下，你的英语很好（我没有注意到你是非母语的英语说话者）。

现在，关于你的问题，如果你正在寻找真正的模式匹配。我倾向于将这个想法转化为代码：

 "CURRENTPOINT" is end of first letter.
 LOOP: Pick letter(s) from Start to "CURRENTPOINT"
 Break the rest of your binary string into blocks of the same size.
 See if these blocks all equal your picked letters.
 If not, move "CURRENTPOINT" along and repeat the LOOP until you run out of letters.
 If so, you have your "repeating section."

如果你只是猜测随机生成器暂时存在偏差，并且这种偏差会在相当短的时间内重新建立基线（平衡的0和1），那么你可以比较每个0和1的计数，并根据与基线的偏差来判断另一个更有可能。但是，要小心蒙特卡罗谬误。

- Matt Mitchell

---

大多数人会说PHP吗？真的吗？:P - Adrian Petrescu

每次我看到“新手应该学什么”这样的问题时，总会建议学习PHP，虽然对于初学者来说部署容易且很多程序员都缺乏Web基础知识，但是同时PHP也会因为你的编码不当而惩罚你，并给新手带来可怕的错误。 - Matt Mitchell

Answer 5

我注意到没有人告诉你关于周期性的事情。

伪随机序列总是基于数学运算的。 （直到量子计算机^^）

生成这种序列的一种常见方法是将两个质数相除（不确定这是否是正确的术语，但无论如何）。

例如

1/3=1.333333.....
9/7=1,2857142857142857142857142857143

这些数字相当小，我们注意到了什么？周期性。

1/3=1.3 3 3 3 3 3.....
9/7=1,2857 142857 142857 142857 142857 143

质数越大，序列就越大。例如：3和142857是很大的。

因此，如果您长时间查看伪随机序列，您可能会发现周期性并能够“猜测”下一个数字。但这可能需要一段时间。

附注：对不起我的英语有点生疏^^

- gawain

---

欢迎来到 Stack Overflow！请提供完整的答案：在这种情况下，您应该提供一些代码，或者至少提供一个算法作为您概念的证明。链接到外部资源也是可以的。 - Giulio Muscarello

另外，请注意英文字母不使用“àccéntéd léttérs” ;) - Giulio Muscarello

Answer 6

你需要考虑的是随机性的属性，研究它们。例如，“随机性会成群结队地出现”。将随机序列与可预测序列进行比较：在可预测的序列中通常不会发现成群的情况。要利用这些成群的情况，等待它们的到来。有一点运气的话，你就能赢得胜利。

- DAN