1

Alright I tested the way below.

Generated x times random numbers between 0~x and then checked the ones that were not generated.

I would assume that it would be very close to 100%. What I mean is all numbers between 0~x are generated.

But results are shocking. About 36% of the numbers are missing.

Is my random function not really random?

Here below my random class: 

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); }

Here the below results: 

 Between 0-10, missing numbers count: 4, percent: 40% Between 0-100, missing numbers count: 36, percent: 36% Between 0-1000, missing numbers count: 369, percent: 36,9% Between 0-10000, missing numbers count: 3674, percent: 36,74% Between 0-100000, missing numbers count: 36583, percent: 36,58% Between 0-1000000, missing numbers count: 367900, percent: 36,79% Between 0-10000000, missing numbers count: 3678122, percent: 36,78% Between 0-100000000, missing numbers count: 36797477, percent: 36,8%

Here the code how I check: 

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; }
Improve this question
26
  • 3
    How many times are you calling Generate? If you're only generating ten numbers for the 0-10 block, then getting 1 of each number is not expected. An even distribution is only expected on average, i.e. for a very large sample size. Commented Mar 30, 2013 at 16:24
  • 3
    @MonsterMMORPG: No, as Jason wrote, it's only expected on average. If you throw a die 6 times you normally don't get each of the six values, even though it's a "function" with uniform distribution. Commented Mar 30, 2013 at 16:35
  • 1
    Random does not mean all chances are equal. Uniform means that. Commented Mar 30, 2013 at 16:39
  • 1
    @MonsterMMORPG You need to slow down and read the answers and think a little. The problem lies in your head. Your expectation is not correct. Your results are fine. If you really do want every possible value to appear exactly once, use Fisher-Yates shuffle. Commented Mar 30, 2013 at 16:51
  • 1
    @MonsterMMORPG: Yep, with current dice technology, a D20 will not perform as you expect. Damn those dice and their crappy technology! Because you clearly expect that if you roll a D20 20 times, you'll see all the numbers from 1-20, unless there's something wrong with the "technology". Commented Mar 30, 2013 at 16:58

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

yes. i understood the reason. reason is computers are based on math so still not able to generate true random
@MonsterMMORPG: It is not because computers don't generate truly random numbers. Even if you throw a perfect dice 6 times, you are not guaranteed to get 6 different numbers. It is an inherent behaviour in randomness.
@MonsterMMORPG: It's nothing to do with not-truely-random numbers. You will get just the same effect with dice!
There is no possible way you can roll dice truely randomly :) If you pick a letter from bag of letters, you would give each letter equal chance. Am i incorrect? But it is clear here not the same. Even that your pick would not be true random.
@MonsterMMORPG: But you are doing different things! In one case you're rolling dice multiple times, where the outcome of each dice roll has no effect on the next. In the other case, you are removing items from a bag - where the outcome of each removal certainly DOES affect the next one - because once you're removed an item from the bag, it's never going to be drawn again. But if you roll a 6, you can roll another next time. You are expecting the dice rolling to behave like removing things from a bag - but it should be trivially obvious that they are not the same!
|
5

Your results are exactly what is to be expected from a uniform distribution where you sample with replacement.

Consider the simplest possible example. You have a coin and toss it twice. So we assume that we are sampling from a uniform discrete distribution.

The possible outcomes, which occur with equal probability of 0.25 are:

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.

Improve this answer

8 Comments

so you are saying 36% is expected ? well i would expect from true random close to 100% distribution
I see. Computers are nothing but math so it seems like true random is still not possible
The code in your question samples with replacement from the uniform distribution. Your expectations are simply incorrect. Read my updated answer again. Particularly the final example in the penultimate paragraph.
No i believe my expectation is correct. If you toss a coin 1000 times, i would expect close to 500 times down and close to 500 times up sides came.
You are not tossing a coin 1000 times. You are rolling a fair 1000 sided dice 1000 times. Your expectations are undeniably wrong.
|
-1

If you want 100 million unique random number you could do something like this:

Now using Fisher-Yates suffle algorithm:

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; } }

By the way you could calculate irNotFound much faster:

int irNotFound = irFirst - hsGenerated.Count;

Good luck with your quest.

Improve this answer

7 Comments

thanks but that is what i meant. I am generating a new random number but see that it is not truly distributed.
This code is generating a not-so-random permutation. "uniform distribution" is the wrong term here; a uniform distribution wouldn't enforce that each number occurs exactly once.
Well i will try your solution. If it is better that will improve my function for certain thing ^^
"not-so-random" because this implementation is broken and doesn't give a uniform distribution over all possible permutations. Look up "fisher-yates-shuffle" for the correct solution.
@Casperah You don't use uniform accurately at all. The code in the question samples uniformly. The code in this answer does nothing very useful.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.