1

在我尝试使用一组随机数据作为熵源处理时出现的数学/编程问题。在我使用 Random.org 的预生成随机文件作为熵源的情况下。像这样的原始数据是随机的 0 和 1，并且可以作为随机字节 (0-255) 或更大的范围作为 2 的幂。我试图尽可能高效地使用这个随机源，因为它的长度是有限的，所以我不想使用比我需要的更大的集合。

如果您想要一个可以被 256 整除的数字（例如 100 到 355、0 到 15 等），那么随机字节是公平的。但是，如果我想要一个从 1 到 100 的数字怎么办？这不太适合 256。我可以将 0-199 分配给 1-100 范围两次，留下 200-255 作为额外的，如果抽到就必须丢弃，否则该范围内的 55 个数字将被不公平地加权更频繁地出现。

扔掉超出范围的数字是唯一公平的选择吗？或者是否有一种数学方法可以在 1-100 范围内相当“模糊”这 55 个数字？

我想出的唯一一个知道我将能够使用该数字而不丢弃结果的其他选择是吸收更多的字节数，以便偏差程度更小（0-255会有一些数字在 1-100 中，有两个“平局”，有些有三个；3:2 几率 = 50% 的可能性。十个字节（0-2,550）将有 26:25 的几率 = 4% 的可能性。等等）用完更多数据，但更可预测。

有没有我想要做的事情的术语（不能谷歌我不能命名的东西）？是否有可能，或者我是否必须承认我将不得不丢弃与我想要的范围不完全匹配的数据？

4

1 回答 1

1

如果每个数字使用 7 位，则得到 0-127。每当你得到一个大于 100 的数字时，你必须丢弃它。您失去了对该数据点的使用，但它仍然是随机的。每 128 个或大约 20% 的随机信息，你会丢失 28 个。

如果你一次使用 20 位，你会得到一个介于 0 和 1,048,575 之间的数字。这可以分解为 0 到 99 之间的 3 个随机值（如果添加 1，则为 1-100）。除法时，您必须使用整数算术或丢弃任何小数部分。

if (number > 1000000) discard it.
a = number % 100;
b = (number / 100) % 100;
c = (number / 10000) % 100;

您只浪费了 1048575 中的 48,575 个值或大约 5% 的随机信息。

你可以这样想这个过程。通过将 20 位转换为十进制整数来获取数字。分解出 10 和 1 的数字、1000 和 100 的数字以及 100,000 和 10,000 的数字，并将它们用作三个随机数。它们是真正随机的，因为这些数字可以是原始数字中的任何值。此外，我们丢弃了任何偏向三者特定值的值。

所以有一种方法可以更有效地利用随机位。但是你必须做一些计算。

注意：下一个有趣的位组合是 27 位，浪费了大约 25%。14 位会浪费大约 60%。

于 2013-06-03T20:11:06.323 回答