Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #31846

Re: random generation from discrete probability distribution function

Show key headers only | View raw

On 6/23/2015 4:46 AM, saha.noruz@gmail.com wrote:
> Hi all,
>
> I need to code a probability matrix and then choose a random number for each row according to the their probability.
> I know I have to use Random(),but I do not know how can I use this one according to the probability.
> Also, I need to know how I can code the probability matrix.

     I don't know what you mean by "probability matrix" -- presumably
it's a matrix whose elements are probabilities, but that doesn't give
me much information to work with, so I can't help with that part.

     Also, I don't know what you mean by "Random()".  Java provides a
static method in the Math class called "Math.random()" -- note the
lower-case "r" -- and a class called "java.util.Random" -- note the
absence of "()" -- and I guess you probably mean one or the other of
these, but again: It's not clear to me what you want.

     However, I can help with the question of how to use a source of
random values to select one of N things with different probabilities.
For purposes of illustration, let's say there are three things to be
chosen with probabilities p1,p2,p3 where p1+p2+p3=1.  Each call to
the Math.random() method produces a pseudo-random value in [0,1),
and it turns out this is precisely what you need:

	double u = Math.random();  // 0 <= u and u < 1
	if (u < p1) {
	    // select thing 1
	} else if (u - p1 < p2) {
	    // select thing 2
	} else {
	    // select thing 3
	}

     This pattern would, of course, become very clumsy for selecting
between more than a very few things.  For larger candidate sets,
you'd probably want to put the probabilities in an array, like

	double[] p = { 0.1, 0.4, 0.2, 0.3 };

... and do the selection in a loop like

	double u = Math.random();
	for (int i = 0; i < p.length; ++i) {
	    u -= p[i];
	    if (u < 0) {
	        // select thing "i"
	        break;
	    }
	}

     Unfortunately, there's a subtle trap in this approach, because
floating-point arithmetic cannot represent all fractions with perfect
accuracy: You may well find that the errors in Java's approximations
to the p's mean that their sum is not exactly equal to unity.  One
way to deal with this is to just ignore one of the p's -- the last,
say -- and say it gets all the "leftover" probability not assigned
to the others.  The selection might then look like

	double u = Math.random();
	int choice = p.length - 1;
	for (int i = 0; i < p.length - 1; ++i) {
	    u -= p[i];
	    if (u < 0) {
	        choice = i;
	        break;
	    }
	}
	// select thing "choice"

     I have not come close to exhausting all the possible ways to
approach random-selection problems, but this should be enough to
get you started.  Good luck!

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

random generation from discrete probability distribution function "saha.noruz@gmail.com" <sahar.fakhar@gmail.com> - 2015-06-23 01:46 -0700
  Re: random generation from discrete probability distribution function Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-06-23 07:37 -0400
    Re: random generation from discrete probability distribution function Arne Vajhøj <arne@vajhoej.dk> - 2015-06-28 20:27 -0400
  Re: random generation from discrete probability distribution function e.d.programmer@gmail.com - 2015-06-23 04:51 -0700
  Re: random generation from discrete probability distribution function Jeff Higgins <jeff@invalid.invalid> - 2015-06-23 20:31 -0400

csiph-web