估计GUID内的数字发生概率

Question

最近我决定调查用该Guid.NewGuid方法生成的全局唯一标识符的随机性程度(这也是该问题的范围).我记录了自己关于伪随机数,伪随机性的问题,我很惊讶地发现放射性衰变甚至产生了随机数.无论如何,我会让你自己发现有关这些有趣讲座的更多细节.

继续我的问题,关于GUID的另一个重要事项是:

包含MAC地址和时间的V1 GUID可以通过第三组数字的第一个位置中的数字"1"来标识,例如{2F1E4FC0-81FD-11DA-9156-00036A0F876A}.

V4 GUID使用后来的算法,这是一个伪随机数.它们在相同位置具有"4",例如{38A52BE4-9352-453E-AF97-5C3B448652F0}.

将它放在一个句子中,a 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.该规范没有说明如何生成第四组中的第一个字符.这可能会导致你的结果失败.

如果要进一步调查,则需要跟踪每个十六进制数字在每个位置出现的频率.我怀疑这将揭示差异,并帮助您确定您的理论估计是否关闭,或伪随机算法是否略有偏差.

Answer 2

吉姆得到了它(我刚刚发现了这个问题,其答案同样引入了v4 guid代).

因此,通过使用这些新知识改变预期方程,您得到:((10/16)*30+1+0.5)/32或者(10M * 100 / 16) * 30 / 32 + (150M / 32),大约63.28%,非常接近您获得的实验数据.