Weighted Randomness

BlitzMax Forums/BlitzMax Programming/Weighted Randomness

siread(Posted 2008) [#1]
Is there an efficient way of choosing a random number where the result is weighted in favour of one end of the scale?

For instance, when getting a random number between 1 and 100, then number 1 is 100 times more likely to come up than the number 100, but only 50 times more likely to come up than the number 50.


sswift(Posted 2008) [#2]
http://blitzmax.com/codearcs/codearcs.php?code=963


siread(Posted 2008) [#3]
Ah sweet. I did a search but must have used the wrong combination of words. :D


sswift(Posted 2008) [#4]
There's also another way to weight random numbers that you could use, if you have a lot of numbers or you're dealing with floating point numbers:

Min# = 10
Max# = 100
Power# = 2.0

N# = Min# + Rnd(0,1)^Power#*(Max#-Min#)

So basically, you calculate a random number between 0 and 1. Then you raise that by some power. Then you multiply it to scale it up to fit your range, Max-Min. Then you add Min to offset the range so instead of starting at 0, the smallest value is Min.

Raising it by 2 will give you for example:

0*0 = 0
0.5*0.5 = 0.25
1*1 = 1

So, lower numbers will be more likely to appear, in an exponential manner.

If you wish to do the reverse and make lower numbers less likely to appear, then use 1/Exponent# for the exponent, which in the case of an exponent of 2 would be 0.5.

So, an exponent of 1 will give you an equal chance for all numbers. Anything over 1 will start to bias you towards the lower numbers. And anything less than 1 will bias you towards the higher numbers.


Floyd(Posted 2008) [#5]
In general you want some way to have several numbers count as a single number.

For example if you generate Rand(1,3) and then treat 3 as if it were 2 then 2 is twice as likely as 1.

If you want n to be n times as likely as 1 for n = 1 to 100 then you can use a little high school algebra ( quadratic formula ) to derive this algorithm:

kMax = 100 * (100 + 1) / 2	' kMax = 1 + 2 + 3 + ... + 100

Print

For k = 1 To 21
	n = Floor( Sqr(2*k - 1.75) + 0.5 )
	Print n
Next

Note that n takes the values 1, 2,2, 3,3,3, 4,4,4,4, etc.

To get a weighted random value you select a random element from this list.
First generate k = Rand( 1, kMax ). Then the random result is Floor( Sqr(2*k - 1.75) + 0.5 ).