Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@comcast-dot-net.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: random generation from discrete probability distribution function
Date: Tue, 23 Jun 2015 07:37:22 -0400
Organization: A noiseless patient Spider
Lines: 76
Message-ID: <mmbgb3$c64$1@dont-email.me>
References: <f078c43f-bc67-4a50-b660-68294042b23e@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 23 Jun 2015 11:36:04 +0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="858a9d65d95f4ea4d355bd116aa2cdbf"; logging-data="12484"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX187n7hGZaRSAucmuzIWGhiV"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0
In-Reply-To: <f078c43f-bc67-4a50-b660-68294042b23e@googlegroups.com>
Cancel-Lock: sha1:TXBCIClLiK4sb7n1ZNfO04cN6i4=
Xref: csiph.com comp.lang.java.programmer: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