Non-Uniform Random Number Generator Implementation

问题:

I need a random number generator that picks numbers over a specified range with a programmable mean.

For example, I need to pick numbers between 2 and 14 and I need the average of the random numbers to be 5.

I use random number generators a lot. Usually I just need a uniform distribution.

I don't even know what to call this type of distribution.

Thank you for any assistance or insight you can provide.

回答1:

You might be able to use a binomial distribution, if you're happy with the shape of that distribution. Set n=12 and p=0.25. This will give you a value between 0 and 12 with a mean of 3. Just add 2 to each result to get the range and mean you are looking for.

Edit: As for implementation, you can probably find a library for your chosen language that supports non-uniform distributions (I've written one myself for Java).

A binomial distribution can be approximated fairly easily using a uniform RNG. Simply perform n trials and record the number of successes. So if you have n=10 and p=0.5, it's just like flipping a coin 10 times in a row and counting the number of heads. For p=0.25 just generate uniformly-distributed values between 0 and 3 and only count zeros as successes.

If you want a more efficient implementation, there is a clever algorithm hidden away in the exercises of volume 2 of Knuth's The Art of Computer Programming.

回答2:

You haven't said what distribution you are after. Regarding your specific example, a function which produced a uniform distribution between 2 and 8 would satisfy your requirements, strictly as you have written them :)

回答3:

If you want a non-uniform distribution of the random number, then you might have to implement some sort of mapping, e.g:

// returns a number between 0..5 with a custom distribution
int MyCustomDistribution()
{
  int r = rand(100); // random number between 0..100
  if (r < 10) return 1;
  if (r < 30) return 2;
  if (r < 42) return 3;
  ...
}

回答4:

Based on the Wikipedia sub-article about non-uniform generators, it would seem you want to apply the output of a uniform pseudorandom number generator to an area distribution that meets the desired mean.

回答5:

You can create a non-uniform PRNG from a uniform one. This makes sense, as you can imagine taking a uniform PRNG that returns 0,1,2 and create a new, non-uniform PRNG by returning 0 for values 0,1 and 1 for the value 2.

There is more to it if you want specific characteristics on the distribution of your new, non-uniform PRNG. This is covered on the Wikipedia page on PRNGs, and the Ziggurat algorithm is specifically mentioned.

With those clues you should be able to search up some code.

回答6:

My first idea would be:

• generate numbers in the range 0..1
• scale to the range -9..9 ( x-0.5; x*18)
• shift range by 5 -> -4 .. 14 (add 5)
• truncate the range to 2..14 (discard numbers < 2)

that should give you numbers in the range you want.

回答7:

You need a distributed / weighted random number generator. Here's a reference to get you started.

回答8:

Assign all numbers equal probabilities,

while currentAverage not equal to intendedAverage (whithin possible margin)

 pickedNumber = pick one of the possible numbers (at random, uniform probability, if you pick intendedAverage pick again)

 if (pickedNumber is greater than intendedAverage and currentAverage<intendedAverage) or (pickedNumber is less than intendedAverage and currentAverage>intendedAverage)

   increase pickedNumber's probability by delta at the expense of all others, conserving sum=100%

 else

   decrease pickedNumber's probability by delta to the benefit of all others, conserving sum=100%

 end if

 delta=0.98*delta (the rate of decrease of delta should probably be experimented with)

end while