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

Groups > comp.lang.java.programmer > #31845 > unrolled thread

random generation from discrete probability distribution function

Back to article view | Back to comp.lang.java.programmer

Contents

  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

#31845 — random generation from discrete probability distribution function

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.

Thanks

[toc] | [next] | [standalone]

#31846

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

[toc] | [prev] | [next] | [standalone]

#31868

On 6/23/2015 7:37 AM, Eric Sosman wrote:
> On 6/23/2015 4:46 AM, saha.noruz@gmail.com wrote:
>> I need to code a probability matrix and then choose a random number
>> for each row according to the their probability.

>      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.

In special but common cases where all p are multiple of 1/N and N are
not too big, then I like the approach of an array with N elements and
picking a random int as index into array.

Arne

[toc] | [prev] | [next] | [standalone]

#31847

On Tuesday, June 23, 2015 at 4:46:56 AM UTC-4, Saha 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.
> 
> Thanks

This sounds like asking someone to do your homework for you.

[toc] | [prev] | [next] | [standalone]

#31849

On 06/23/2015 04: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.
>
> Thanks
>
You might try something from the
org.apache.commons.math3.distribution
package.

There is a similar package that I used recently
to get samples from an exponential distribution
but I can't recall it.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web