1

好吧，我测试了下面的方法。

生成x时间之间的随机数0~x，然后检查未生成的随机数。

我认为这将非常接近 100%。我的意思是0~x生成之间的所有数字。

但结果令人震惊。大约36%的数字丢失了。

我的随机函数不是真的随机吗？

在我的随机课程下面：

private static Random seedGenerator = new Random();

private static ThreadLocal<Random> random = 
    new ThreadLocal<Random>(SeededRandomFactory);

private static Random SeededRandomFactory()
{
    lock (seedGenerator)
        return new Random(seedGenerator.Next());
}

public static int GenerateRandomValueMin(int irRandValRange, int irMinValue)
{
    return random.Value.Next(irMinValue, irMinValue + irRandValRange);
}

以下是结果：

在 0-10 之间，缺失数字计数：4，百分比：40%
在 0-100 之间，缺失数字计数：36，百分比：36%
在 0-1000 之间，缺失数字计数：369，百分比：36.9%
在 0-10000 之间，缺失数字计数：3674，百分比：36,74%
在 0-100000 之间，缺失数字计数：36583，百分比：36,58%
在 0-1000000 之间，缺失数字计数：367900，百分比：36,79%
在 0-10000000 之间，缺失数字计数：3678122，百分比：36,78%
在 0-100000000 之间，缺失数字计数：36797477，百分比：36.8%

这是我如何检查的代码：

File.WriteAllText("results.txt", "");

int irFirst = 10;

for (int i = 0; i < 8; i++)
{
    HashSet<int> hsGenerated = new HashSet<int>();

    for (int k = 0; k < irFirst; k++)
    {
        hsGenerated.Add(GenerateRandomValue.GenerateRandomValueMin(irFirst, 0));
    }

    int irNotFound = 0;
    for (int k = 0; k < irFirst; k++)
    {
        if (hsGenerated.Contains(k) == false)
            irNotFound++;
    }

    string srSonuc = 
        string.Format(
            "Between 0-{0}, missing numbers count: {1}, percent: {2}%", 
            irFirst, irNotFound,
            Math.Round((Convert.ToDouble(irNotFound)/Convert.ToDouble(irFirst))*100.0, 2).ToString()
            );

    using (StreamWriter w = File.AppendText("sonuclar.txt"))
    {
        w.WriteLine(srSonuc);
    }

    irFirst = irFirst * 10;
}
4

3 回答 3

13

As mentioned in the comments, your testing method is off.

You draw x times a number between 0 and x. The probability that a specific number is not drawn is:

((x-1)/x)^x

As x approaches infinity, p will go towards 1/e (or approx. 36.7879441%) And this is the number you are seeing in your results. Also, as x approaches infinity, you will observe this probability as outcome of your sample (Law of large numbers)

This has to do with probability. When you have a bowl with a red and a white marble. And you take one, put it back an take another one you cannot guarantee that you see both. You could take the red one twice. You are doing the same thing with more objects.

To elaborate on true true randomness:

I would expect close to 99% percent instead of 64%. Or at least 90%+ percent. So you say this isn't possible with current technology

That is simple. Thanks to modern math, technology and my super powers I can tell you how to do that: You need more draws than numbers to choose from. The formula becomes:

more math

where n is you desired percentage of missing numbers. For example if you are willing to accept 5% numbers missing, you must draw three times as many random numbers. For a 1% chance, you need to iterate 4.6 times the maximum number.

This math assumes a perfectly uniform random number generation.

于 2013-03-30T16:39:47.290 回答
5

您的结果正是您通过替换采样的均匀分布所期望的结果。

考虑最简单的例子。你有一个硬币，扔了两次。所以我们假设我们是从一个均匀的离散分布中抽样的。

以 0.25 的等概率发生的可能结果是：

TT
TH
HT
HH

As you can see, only two of the four outcomes have both heads and tails.

This is known as sampling with replacement. So, once we have sampled a tails, then we "put it back in the bag", and it could come out again on the next sample.

Now suppose we sample without replacement. In that case there are two possible outcomes:

TH
HT

And as you see, each possible value appears exactly once.

Essentially your expectation for the results is not correct. As another example, suppose you toss a coin and it comes down tails. What do you expect will happen on the next toss. You are arguing that the coin must now come down heads. But that is clearly nonsense.

If you did want to sample without replacement, and it's not clear that's really what you want, then you do so with the Fisher-Yates shuffle.

于 2013-03-30T16:34:39.033 回答
-1

如果你想要 1 亿个唯一随机数，你可以这样做：

现在使用 Fisher-Yates suffle 算法：

List<int> numbers = new List<int>(100000000);
for (int i = 0; i < numbers.Capacity; i++)
{
    int rnd = random.Next(numbers.Count + 1);
    if (rnd == numbers.Count)
        numbers.Add(i);
    else
    {
        numbers.Add(numbers[rnd]);
        numbers[rnd] = i;
    }
}

顺便说一句，您可以更快地计算 irNotFound：

int irNotFound = irFirst - hsGenerated.Count;

祝你的任务好运。

于 2013-03-30T16:29:11.190 回答