3
$\begingroup$

Presume I have the following case:

  • int value a
  • int value b, for which a < b
  • int value i, for which a <= i < b
  • I need an int value x, for which a <= x < b, randomly chosen, according to a non-uniform distribution: the distribution should follow a bell curve which is centered around i.

In Java, I have the following methods available on java.util.Random:

  • nextInt(int m): int between 0 and m
  • nextDouble(): double between 0.0 and 1.0
  • nextGaussian(): double between -Infinity and +Infinity, usually close to 0.0.

How do I build such a non-uniform distribution from these building blocks? How do I reliably and efficiently transform nextGaussian() into nextGaussian(a, b, i)? The part I am struggling with is to enforce that x is selected between a and b (without doing a trial-and-error).

$\endgroup$
4
  • 1
    $\begingroup$ You need to be more precise about the properties you require. The function that deterministically returns $i$ implements your current spec. $\endgroup$ Commented Nov 29, 2013 at 14:18
  • $\begingroup$ There are similar questions in stackoverflow. stackoverflow.com/questions/5969447/… $\endgroup$
    – Parham
    Commented Nov 29, 2013 at 18:18
  • $\begingroup$ @DavidRicherby Any continuous function for which i + x has a lower chance that i, and i + y with y > x has a lower chance that i + x is good for me. $\endgroup$ Commented Nov 29, 2013 at 21:29
  • 1
    $\begingroup$ @GeoffreyDeSmet If that is your only criteria, do you really need a bell curve? Why not try a triangular distribution? There is a brief snippet in that Wikipedia article on how to generate triangular random variates. $\endgroup$
    – mhum
    Commented Dec 2, 2013 at 22:49

3 Answers 3

5
+50
$\begingroup$

I would generate a beta distribution, and then expand to the desired range and round to the nearest integer.

A beta distribution on the 0-1 scale has two parameters: $Beta(a,b)$. $Beta(1,1)$ is simply a flat uniform. You want $a$ and $b$ to be > 1 or it won't have a central peak. The mean is $a/(a+b)$, and the mode (peak) is $(a-1)/(a+b-2)$.

The larger $a$ and $b$ are, the more "peaked" the distribution is.

Here's how to generate it from uniform random numbers if $a$ and $b$ are integers:

First, here's how you generate a Gamma variate $Gamma(1,a)$.

double Gamma1(int n){
  double sum = 0;
  for (int i = 0; i < n; i++){
    sum += -log(getUniform());
  }
  return sum;
}

Then

double Beta(int a, int b){
  double x = Gamma1(a);
  double y = Gamma1(b);
  return x/(x+y);
}

Then for your problem, you have a span from A to B with mode at I. Then the distance from A to I is fraction $(I-A)/(B-A)$, so that is the mode of the distribution. Then decide how large you want $a+b$ to be, the more the sharper. You might start with 10, call it $n$. Then calculate $$a = (I-A)/(B-A)*(n-2)+1$$ and use the nearest integer value for $a$, and of course $b=n-a$.

Then all you gotta do is calculate

A + (B-A)*Beta(a,b)

and round to the nearest integer.

It sounds like your requirements are pretty flexible, so this should be good enough.

Anyway, look up Beta distribution.

EDIT: Another way that might be simpler: Use order statistics. Generate $n$ uniforms, sort them, and then choose the $a$th one, and scale that.

$\endgroup$
1
5
$\begingroup$

Your problem is rather vague: "bell curve" and "centered around i" are not well defined.

One possible recipe is to generate a truncated gaussian: define s= min(b-i,i-a)/c where c is a free parameter (suggested values: [1,3] range), generate a gaussian with mean i and standard deviation s - and round it to the nearest integer. If the value falls outside the [a,b] range, try again.

Related.

$\endgroup$
5
  • $\begingroup$ Is there any way to avoid the "try again". So avoid the trial and error? $\endgroup$ Commented Nov 29, 2013 at 21:27
  • $\begingroup$ Sure. But it seems the most natural and efficient to me. It's quite standard. Why do you want to avoid it? $\endgroup$
    – leonbloy
    Commented Nov 29, 2013 at 22:14
  • $\begingroup$ Because it's a performance leak if 20% or more of the return values of Random.nextGaussian() get thrown away and cause it to redo the loop. Also note that the i is not necessarily the average of a and b, in fact it be very close to a and very far from b. $\endgroup$ Commented Dec 2, 2013 at 10:42
  • $\begingroup$ The "performance leak" depends on how peaked the bell curve is , and that is tunable by the c paramenter (I don't know where you get that 20% from). I repeat: trial-and-error is a standard procedure, and relatively efficient (to call that a "leak" is... strange) And I never assumed that i is the average of a and b $\endgroup$
    – leonbloy
    Commented Dec 2, 2013 at 12:23
  • $\begingroup$ The 20% is pulled out of thin air. Your answers are very helpfull, but I 'd still like to avoid the trial and error. The Random.nextGaussian() is a symmetrical bell curve, so I presume that if i == a (or almost equals it), that half the trials are errors? Or am I missing something? $\endgroup$ Commented Dec 6, 2013 at 10:42
5
$\begingroup$

Use the alias method. There's a fairly elaborate description by Keith Schwarz, which there is no reason to repeat here. Instead, I'll explain what the final algorithm looks like.

Before describing the algorithm, let me explain the data you need to come up with. You need to decide on a probability distribution over the set $\{100,\ldots,180\}$. That is, you need to decide on numbers $p_{100},\ldots,p_{180}$ such that the probability that your random number is $i \in \{100,\ldots,180\}$ equals $p_i$.

Given the $p_i$, you can construct another array $q_{100},\ldots,q_{180} \in [0,1]$ and two integer arrays $a_{100},b_{100},\ldots,a_{180},b_{180} \in \{100,\ldots,180\}$ such that the following function samples the distribution $p_i$:

  1. Sample uniformly a number $t \in \{100,\ldots,180\}$ and a real $\theta \in [0,1]$.
  2. If $\theta < q_t$ then return $a_t$, otherwise return $b_t$.

Keith Schwarz's essay explains how to generate the arrays $q_i,a_i,b_i$ (he uses different letters; look under the section The Alias Method). The essay gives several algorithms for generating these arrays; in your case the range $\{100,\ldots,180\}$ is very small, so you can use whichever you prefer.

$\endgroup$
3
  • $\begingroup$ Very interesting. Would this work on a continuous variable, such as all java double values between -5.0 and 5.0? That number of values is more than a thousand billion, so I presume I 'd go out of memory? I cannot hold the set in memory (or even enumerate it). $\endgroup$ Commented Dec 6, 2013 at 10:46
  • 1
    $\begingroup$ This method works only for discrete random variables, which is what you were asking for. However, it probably works even if the range of the variable is much bigger than your $81$ numbers. $\endgroup$ Commented Dec 6, 2013 at 16:19
  • $\begingroup$ Agreed, I didn't specify that clearly. Actually, I need to support both discrete and continuous variable ranges, so I 'll go with the Beta distribution approach for now, as that seems to cater for both use cases. Nevertheless, this is an interesting answer, thanks. $\endgroup$ Commented Dec 6, 2013 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.