c# - 估计 GUID 中数字出现的概率

Question

最近我决定调查使用 Guid.NewGuid method 生成的全局唯一标识符的随机程度(这也是本题的范围)。我记录了自己关于 pseudorandom numbers ， pseudorandomness 并且我很惊讶地发现甚至还有 random numbers generated by radioactive decay 。不管怎样，我会让你自己发现更多关于这些有趣讲座的细节。

继续我的问题，关于 GUID 的另一件重要事情是:

V1 GUIDs which contain a MAC address and time can be identified by the digit "1" in the first position of the third group of digits, for example {2F1E4FC0-81FD-11DA-9156-00036A0F876A}.

V4 GUIDs use the later algorithm, which is a pseudo-random number. These have a "4" in the same position, for example {38A52BE4-9352-453E-AF97-5C3B448652F0}.

用一句话来说，Guid 总是将数字 4(或 1，但超出我们的范围)作为其组成部分之一。

对于我的 GUID 随机性测试，我决定计算一些越来越大的 GUID 集合中的数字数量，并将其与数字出现的统计概率 expectedOccurrence 进行比较。或者至少我希望我做到了(请原谅任何统计公式错误，我只是尽力猜测来计算这些值)。我使用了下面列出的小型 C# 控制台应用程序。

class Program
{
    static char[] digitsChar = "0123456789".ToCharArray();
    static decimal expectedOccurrence = (10M * 100 / 16) * 31 / 32 + (100M / 32);
    static void Main(string[] args)
    {
        for (int i = 1; i <= 10; i++)
        {
            CalculateOccurrence(i);
        }
    }

    private static void CalculateOccurrence(int counter)
    {
        decimal sum = 0;
        var sBuilder = new StringBuilder();
        int localCounter = counter * 20000;
        for (int i = 0; i < localCounter; i++)
        {
            sBuilder.Append(Guid.NewGuid());
        }

        sum = (sBuilder.ToString()).ToCharArray()
                  .Count(j => digitsChar.Contains(j));

        decimal actualLocalOccurrence = sum * 100 / (localCounter * 32);

        Console.WriteLine(String.Format("{0}\t{1}",
            expectedOccurrence,
            Math.Round(actualLocalOccurrence,3)
            ));
    }
}

上述程序的输出是:

63.671875       63.273
63.671875       63.300
63.671875       63.331
63.671875       63.242
63.671875       63.292
63.671875       63.269
63.671875       63.292
63.671875       63.266
63.671875       63.254
63.671875       63.279

因此，即使理论发生率预计为 63.671875%，实际值也约为 ~63.2%。

如何解释这种差异？我的公式有错误吗？ Guid 算法中是否还有其他“晦涩” 规则？

Answer 1

在版本 4 GUID 中，第三组中的第一个字符是 4。第四组中的第一个字符是 8、9、a 或 b 中的一个。规范没有说明第四组中的第一个字符是如何生成的。这可能会影响您的结果。

如果您想进一步调查，您需要跟踪每个十六进制数字在每个位置出现的频率。我怀疑这会揭示差异，并帮助您确定您的理论估计是否有偏差，或者伪随机算法是否存在轻微偏差。