10

upperBound也就是说，它永远不会使用某些特定参数连续生成超过 16 个偶数：

Random random = new Random();

int c = 0;
int max = 17;
int upperBound = 18;

while (c <= max) {
    int nextInt = random.nextInt(upperBound);
    boolean even = nextInt % 2 == 0;
    if (even) {
        c++;
    } else {
        c = 0;
    }
}

在此示例中，代码将永远循环，而当upperBound例如 16 时，它会快速终止。

这种行为的原因是什么？该方法的javadoc中有一些注释，但我没有理解它们。

UPD1：代码似乎以奇数上限终止，但可能会卡在偶数上限

UPD2：我修改了代码以捕获c评论中建议的统计信息：

Random random = new Random();

int c = 0;
long trials = 1 << 58;
int max = 20;
int[] stat = new int[max + 1];

while (trials > 0) {
    while (c <= max && trials > 0) {
        int nextInt = random.nextInt(18);
        boolean even = nextInt % 2 == 0;
        if (even) {
            c++;
        } else {
            stat[c] = stat[c] + 1;
            c = 0;
        }
        trials--;
    }
}

System.out.println(Arrays.toString(stat));

现在它试图20在行中达到偶数 - 以获得更好的统计数据，并且upperBound仍然是18.

结果令人惊讶：

[16776448, 8386560, 4195328, 2104576, 1044736, 
 518144, 264704, 132096, 68864, 29952, 15104, 
 12032, 1792, 3072, 256, 512, 0, 256, 0, 0]

起初它按预期减少了 2 倍，但请注意最后一行！在这里它变得疯狂，捕获的统计数据似乎完全奇怪。

这是对数刻度的条形图：

c 统计

如何c获得17256倍的价值又是一个谜

4

3 回答 3

5

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html：

此类的一个实例用于生成伪随机数流。该类使用 48 位种子，该种子使用线性同余公式进行修改。（参见 Donald Knuth，计算机编程的艺术，第 3 卷，第 3.2.1 节。）

如果使用相同的种子创建 Random 的两个实例，并且为每个实例进行相同的方法调用序列，它们将生成并返回相同的数字序列。[...]

它是一个伪随机数生成器。这意味着您实际上并没有掷骰子，而是使用公式根据当前随机值计算下一个“随机”值。为了创造随机化的错觉，seed使用了 a。种子是与公式一起用于生成随机值的第一个值。

显然javas随机实现（“公式”），不会连续生成超过16个偶数。

这种行为是seed通常随时间初始化的原因。当你开始你的程序时，你会得到不同的结果。

这种方法的好处是您可以生成可重复的结果。例如，如果你有一个生成“随机”地图的游戏，你可以记住种子来重新生成相同的地图，如果你想再次玩它。

对于真正的随机数，一些操作系统提供了特殊的设备，可以从鼠标移动或网络流量等外部事件产生“随机性”。但是我不知道如何利用java。

来自secureRandom的 Java 文档：

许多 SecureRandom 实现采用伪随机数生成器 (PRNG) 的形式，这意味着它们使用确定性算法从真正的随机种子生成伪随机序列。其他实现可能会产生真正的随机数，而其他实现可能会使用这两种技术的组合。

请注意，secureRandom 也不保证真正的随机数。

为什么改变种子没有帮助

让我们假设随机数的范围只有 0-7。现在我们使用以下公式生成下一个“随机”数：

 next = (current + 3) % 8

序列变为0 3 6 1 4 7 2 5。

如果你现在拿到种子3，你所做的就是改变起点。

在这个仅使用前一个值的简单实现中，每个值在序列环绕并重新开始之前可能只出现一次。否则会有一个无法到达的部分。

例如想象一下顺序0 3 6 1 3 4 7 2 5。这些数字0,4,7,2 and 5永远不会生成超过一次（根据种子的深度，它们可能永远不会生成），因为一旦序列循环 3,6,1,3,6,1,... 。

简化的伪随机数生成器可以被认为是范围内所有数字的排列，并且您使用种子作为起点。如果它们更高级，则必须将排列替换为可能多次出现相同数字的列表。

更复杂的生成器可以有一个内部状态，允许相同的数字在序列中出现多次，因为状态让生成器知道从哪里继续。

于 2013-07-24T10:09:32.490 回答
2

Random 的实现使用了一个简单的线性同余公式。这样的公式在它们生成的序列中具有自然的周期性和各种非随机模式。

你所看到的是这些模式之一的人工制品......没有故意的。这不是偏见的例子。相反，它是自相关的一个例子。

如果您需要更好（更“随机”）的数字，那么您需要使用SecureRandom而不是Random.

而“为什么以这种方式实施”的答案是……性能。一个调用Random.nextInt可以在几十个或几百个时钟周期内完成。调用SecureRandom可能会慢至少 2 个数量级，甚至可能更多。

于 2013-07-24T10:20:28.077 回答
1

为了可移植性，Java 指定实现必须使用 java.util.Random 的劣质 LCG 方法。这种方法对于任何严重使用随机数（如复杂模拟或蒙特卡洛方法）都是完全不可接受的。使用具有更好 PRNG 算法的附加库，例如 Marsaglia 的 MWC 或 KISS。Mersenne Twister 和滞后斐波那契发生器通常也可以。

我确信这些算法有 Java 库。如果对您有用，我有一个带有 Java 绑定的 C 库：ojrandlib。

于 2013-07-24T10:23:49.580 回答