C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Random Numbers based on probability

 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message
Jason Schultz
Guest
PostPosted: Sun May 08, 2005 5:50 pm    Post subject: Random Numbers based on probability Reply with quote


Hi group,

I have a question regarding a problem I am working on. Basically I am
just looking for input on writing the algorithm, and if my thought
process is correct, or way off. I would like this to be as dynamic as
possible, as the probabilities change depending on the file read in.

I have an array of matrix transformations, and I have an array of
probabilities for those transformations, also stored in array.

I have no problem generating a random number. what I am having a problem
with is getting the correct transformation.
The probibilities are setup like this (for 1 file):
0.02
[Matrix transform]
0.8
[Matrix transform]
0.09
[Matrix transform]
0.09
[Matrix transform]

1st transformation will be selected 2% of the time.
2nd transformation will be selected 80% of the time.
3rd transformation will be selected 9% of the time
4th transformation will be selected 9% of the time.

[begin psuedo code]
Generate floating point random number between 0.0 and 1.0
for index = 0; index < number of probilities; index++
if random number < probabilityArray[index]
return index
[/end psuedo code]
This doesn't always work, as if the number generated is between .81 and
1.0, index is never set.

I have thought about setting up ranges ie:
Range 1 is between 0.0 and 0.02
Range 2 is between 0.02 and 0.82
Range 3 is between 0.82 and 0.91
Range 4 is between 0.91 and 1.0f

For this, would something like the following work
[begin psuedo code]
base = 0.0f
for index = 0; index < number of probabilities; index++
if random number >= base && random number <= probabilityArray[index]
return index;
else if index > number of probabilities
base = probabilityArray[index] - 1.0f
else
base = probabilityArray[index] + probabilityArray[index+1]
[/end psuedo code]

Thanks for your help.
Jason

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Gareth
Guest
PostPosted: Mon May 09, 2005 6:19 am    Post subject: Re: Random Numbers based on probability Reply with quote


Hi Jason,

Jason Schultz wrote:
Quote:
1st transformation will be selected 2% of the time.
2nd transformation will be selected 80% of the time.
3rd transformation will be selected 9% of the time
4th transformation will be selected 9% of the time.

Set up a cumulative probability array once you have read in the file.
In this example, the four elements would be 0.02, 0.82, 0.91, 1.00.

Quote:
For this, would something like the following work
[begin psuedo code]
base = 0.0f
for index = 0; index < number of probabilities; index++
if random number >= base && random number <= probabilityArray[index]
return index;
else if index > number of probabilities
base = probabilityArray[index] - 1.0f
else
base = probabilityArray[index] + probabilityArray[index+1]
[/end psuedo code]

Then you can simplify the loop:

for index = 0; index < number of probabilities; ++index
if random_number <= cumulative_probabilities[index]
return index
(Some appropriate error-handling here since program flow should never
reach this point)

That way, the loop is more efficient since it only does comparisons, no
FP arithmetic.

HTH, Gareth


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Pete Becker
Guest
PostPosted: Mon May 09, 2005 6:21 am    Post subject: Re: Random Numbers based on probability Reply with quote


Jason Schultz wrote:
Quote:

1st transformation will be selected 2% of the time.
2nd transformation will be selected 80% of the time.
3rd transformation will be selected 9% of the time
4th transformation will be selected 9% of the time.


You need an array with these values: .02, .82, .91. 1.00 (that is, each
element is the sum of the previous element and the next probability).
Then generate a random number between 0 and 1, and find the first array
element that's greater than or equal to that value.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Stefan Strasser
Guest
PostPosted: Mon May 09, 2005 10:13 am    Post subject: Re: Random Numbers based on probability Reply with quote
Jason Schultz schrieb:
Quote:
Hi group,

I have a question regarding a problem I am working on. Basically I am
just looking for input on writing the algorithm, and if my thought
process is correct, or way off. I would like this to be as dynamic as
possible, as the probabilities change depending on the file read in.

I have an array of matrix transformations, and I have an array of
probabilities for those transformations, also stored in array.

I have no problem generating a random number. what I am having a problem
with is getting the correct transformation.
The probibilities are setup like this (for 1 file):
0.02
[Matrix transform]
0.8
[Matrix transform]
0.09
[Matrix transform]
0.09
[Matrix transform]

1st transformation will be selected 2% of the time.
2nd transformation will be selected 80% of the time.
3rd transformation will be selected 9% of the time
4th transformation will be selected 9% of the time.

[begin psuedo code]
Generate floating point random number between 0.0 and 1.0
for index = 0; index < number of probilities; index++
if random number < probabilityArray[index]
return index
[/end psuedo code]
This doesn't always work, as if the number generated is between .81 and
1.0, index is never set.


if I understand you correctly I don't see why this could work at all.
either set your probabilities accordingly(i.e. 0.02, 0.82, 0.91, 1.0)
and use the above algorithm(which only works if the values are sorted),
or do something like:

foreach(probability as current){
if(randomnumber < current) return index;
randomnumber-=current;
}

with your original values

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
CE
Guest
PostPosted: Mon May 09, 2005 10:24 am    Post subject: Re: Random Numbers based on probability Reply with quote
Jason Schultz wrote:
Quote:
Hi group,

I have a question regarding a problem I am working on. Basically I am
just looking for input on writing the algorithm, and if my thought
process is correct, or way off. I would like this to be as dynamic as
possible, as the probabilities change depending on the file read in.

I have an array of matrix transformations, and I have an array of
probabilities for those transformations, also stored in array.

I have no problem generating a random number. what I am having a problem
with is getting the correct transformation.
The probibilities are setup like this (for 1 file):
0.02
[Matrix transform]
0.8
[Matrix transform]
0.09
[Matrix transform]
0.09
[Matrix transform]

1st transformation will be selected 2% of the time.
2nd transformation will be selected 80% of the time.
3rd transformation will be selected 9% of the time
4th transformation will be selected 9% of the time.

snip incorrect code

I have thought about setting up ranges ie:
Range 1 is between 0.0 and 0.02
Range 2 is between 0.02 and 0.82
Range 3 is between 0.82 and 0.91
Range 4 is between 0.91 and 1.0f

I have used this exact strategy for calculating weighted random values
in multiple projects. It will work fine.

-- MJF

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Mary K. Kuhner
Guest
PostPosted: Tue May 10, 2005 12:11 pm    Post subject: Re: Random Numbers based on probability Reply with quote
In article <7-SdneMHmLAMduPfRVn-vQ (AT) speakeasy (DOT) net>,
CE <hpalace (AT) hpalace (DOT) com> wrote:
Quote:
Jason Schultz wrote:

I have thought about setting up ranges ie:
Range 1 is between 0.0 and 0.02
Range 2 is between 0.02 and 0.82
Range 3 is between 0.82 and 0.91
Range 4 is between 0.91 and 1.0f

I have used this exact strategy for calculating weighted random values
in multiple projects. It will work fine.

You need to be careful about whether the ranges include their
endpoints or not, though. I inherited a few thousand lines of
Pascal meant to simulate DNA evolution, and after many, many
months of running it, got a DNA sequence one character shorter
than expected (which wrecked havoc with downstream operations).
It took me a long time to discover that the original author
assumed that his random number generator returned a number between
0 and 1 but never equal to either, whereas in fact it returned
a number greater than zero but less than or equal to one. This
led to fall-through in a switch statement, and failure to generate
DNA for that position. Took a *long* time to find this, since
the RNG only generated 1 once in a blue moon. (Thank goodness
it was a deterministic RNG or I would still be looking.)

Mary Kuhner [email]mkkuhner (AT) eskimo (DOT) com[/email]

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Page 1 of 1

 
  


Powered by phpBB © 2001, 2006 phpBB Group