随机数分布不均匀/不均匀

Question

我注意到了c#中随机数生成的一个奇怪问题，看起来集合(模式)比您预期的要频繁得多。

我正在编写一个生成激活代码的机制，该机制由7个数字组成(范围为0-29)。通过计算，应该有30^7 (220亿)可能的激活代码组合。基于此，在生成第10亿个代码之前，不太可能得到一个重复的激活代码。然而，运行我的测试，我开始得到重复的代码后，大约60,000次迭代，这是非常令人惊讶的。我也尝试过使用类似的结果的RNGCryptoServiceProvider，在大约100,000次迭代中得到重复。

我真的很想知道这是.Net中随机数生成的缺陷/限制，还是我做错了什么。

以下代码是验证生成代码的唯一性的测试：

        static void Main(string[] args)
    {
        Random rand = new Random();
        RandomActivationCode(rand, true);
        Console.Out.WriteLine("Press enter");
        Console.ReadLine();
    }

    static void RandomActivationCode(Random randomGenerator)
    {
        var maxItems = 11000000;
        var list = new List<string>(maxItems);
        var activationCodes = new HashSet<string>(list);
        activationCodes.Clear();
        DateTime start = DateTime.Now;
        for (int i = 0; i < maxItems; ++i)
        {
            string activationCode = "";
            for (int j = 0; j < 7; ++j)
            {
                activationCode += randomGenerator.Next(0,30) + "-";
            }
            if (activationCodes.Contains(activationCode))
            {
                Console.Out.WriteLine("Code: " + activationCode);
                Console.Out.WriteLine("Duplicate at iteration: " + i.ToString("##,#"));
                Console.Out.WriteLine("Press enter");
                Console.ReadLine();
                Console.Out.WriteLine();
                Console.Out.WriteLine();
            }
            else
            {
                activationCodes.Add(activationCode);
            }
            if (i % 100000 == 0)
            {

                Console.Out.WriteLine("Iteration: " + i.ToString("##,#"));
                Console.Out.WriteLine("Time elapsed: " + (DateTime.Now - start));
            }

        }
    }

我的解决办法是使用10个数字激活代码，这意味着测试运行时不会产生任何重复的值。这个测试最多需要1100万次迭代(在那之后，它就耗尽了内存)。

Answer 1

这一点都不奇怪，这正是你应该期待的。当可能性空间很大时，您认为应该需要很长时间才能生成副本，这是完全错误的，因此不再相信。开始相信真相:如果有n个可能的代码，那么你应该开始在生成的n个代码的平方根上得到重复，如果n是220亿，大约是15万。

这样想一想:当您生成root-n代码时，它们中的大多数已经有了碰撞的机会。把根-n乘以大致的-n-n，然后你得到.大约100%的机会发生碰撞。

这当然不是一个严格的论点，但它应该给你正确的直觉，以取代你错误的信念。如果这个论点不能令人信服，那么你可能想读一下我关于这个主题的文章：

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

如果您想要生成一个唯一的代码，那么就生成一个GUID；这就是它们的用途。注意到GUID不一定是随机的，它只保证是唯一的。

另一种产生随机看似代码的方法是生成数字1，2，3，4，.你想要多少都行，然后用乘法逆技术对这些数字进行随机的唯一编码。详情请参见http://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/。