Non-Uniform Random Number Generation, from Uniform Random Number Generater [closed]

The project I am currently working on (in C#) requires generating random integer between 0 and Int64.MaxValue.

I have access to a Uniform RNG, which for pseudo-code purposes in the question, I will refer to as:

MyRNG(min, max)


My overall question has to do with how best to use MyRNG(min, max) to create a Non-Uniform RNG that behaves as follows:

• 0 has the highest chance of occurring.
• Int64.MaxValue has a near 0 percent chance of occurring.
• The chance of value X occurring is an asymptote approaching 0, as X approaches Int64.MaxValue

From what I have gathered in my research, it seems like the 2 important values needed to achieve this, are:

• The percent chance of the value 0 occurring.
• A description of the slope (possibly wrong word) of the asymptote. (Is this a classic decay problem I vaguely remember from High School?)

What I tried, that almost worked:

Initially, I wrote a recursive function to try and achieve this. It looked something like this:

int difficulty = 10    // <-- This was tuned to get close to desired output.

public int GetNonUniformRand(int remainingDifficulty, int currentMax) {
if (remainingDifficulty > 0) {
return GetNonUniformRand(remainingDifficulty-1, MyRNG(0, currentMax));
}
return MyRNG(0, currentMax));
}

int finalOutput = GetNonUniformRand(difficulty, Int64.MaxValue);


The behavior of this function when difficulty is 10, would be something like this:

• start with rand number between 0 and max... lets say 17024503.
• generate random number between 0 and 1702450... lets say 312523.
• generate random number between 0 and 312523... and so on.

Using this method worked okay. I assume there is still a very small chance of Int64.MaxValue, but it is very unlikely. The problem with this approach is that it I don't know how to find the probability of getting any particular value. Also, the recursion is not as efficient as I need it to be, as this will be running on a device that isn't very powerful.

Any advice on how to use MyRNG() in an algorithm that will provide the behavior I described, while also allowing me control over the "2 important values" I mention is greatly appreciated. Thank you all in advance.

• In your example, making numbers close to 100 appear more often doesn't even come close to making the mean 100. For example, suppose you choose 100 with probability 1/10 and any other value with equal probability: the mean is still going to be roughly 45% of the max value. – David Richerby Jul 16 '15 at 7:24
• "to weight the outputs in order to achieve an average expected value" -- that's too litte restriction. You can just put all weight on the desired expected value (i.e. derandomise). "in the long run, numbers closer to 100 will come up more frequently" -- not necessarily. You can have half of the weight left and right of the mean without ever coming close to it. – Raphael Jul 16 '15 at 8:26
• I think you succumb to quite a few misconceptions about how probability distributions work. Since you don't really tell us what your desired output it, there is no way we can help you. I suggest you do some research, e.g. starting here, and find out what exactly you want. – Raphael Jul 16 '15 at 8:27
• Thank you both for the replies. I see why the questions is not nearly complete enough. I will think about this some more, and then edit the question accordingly. – Erp12 Jul 17 '15 at 23:06
• Thanks for the edits. Before you ask how to generate this in C# code, your first step should be to identify what distribution you want. I suggest you post that kind of question on Math.SE, after spending some time studying standard distributions and fleshing out the requirements. Right now, your three requirements could be satisfied by any number of distributions -- e.g., the geometric distribution. You'll probably need to know what distribution you want to sample on before you're ready to ask a question that would be a good fit here. – D.W. Jul 18 '15 at 5:20