How to generate weighted random numbers?

[JenniferMurphy]

I know a couple of ways to generate weighted random numbers.

If the weights are all integers and there are not too many of them, I can generate a list and randomly select an element from that list. For example, if the weights are

2 4 5 7 9

then the list would be 2 1s, 4 2s, 5 3s, 7 4s, and 9 5s:

1 1 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5

Then I just generate a random integer on [1,27]. If that number is 17, for example, the random value would be 4.

If the weights are not integers, I can generate a cumulative list. For example, if the weights are

0.9 0.7 0.5 0.2 0.1

The cumulative list would be

0.9 1.6 2.1 2.3 2.4

I can generate a random number on [0, 2.4] and then loop through the list until I find the upper limit. For example, if the random number is 1.937562, that would fall between 1.6 and 2.1, so the random number would be 2.

Both of these approaches have limitations. It seems to me that some time ago I read about another method that uses a 2-dimensional array that removed most of these limitations. Can anyone provide a link to that method? Or is there another method that will work with large numbers of non-integer weights?

Thanks

 

[mikenelena]

Jennifer,

There is a method called the Alias Method that works with non-integer weights. The Alias Method works by dividing the weights into two categories; the "good" weights and the "bad" weights. The "good" weights are those that are over the average weight, and the "bad" weights are those that are under the average weight. The Alias Method then creates a two-dimensional array. The first row of the array contains the "good" weights and the second row contains the "bad" weights. The array is then filled such that each row adds up to the same total weight. To generate a weighted random number using the Alias Method, you pick a random row and then randomly select a number from that row. This ensures that each weight is equally likely to be selected. This method works well with large numbers of non-integer weights, as it requires only two rows of weights and can be used to generate a random number in constant time.

Let’s say you have the following weights: 0.9 0.7 0.5 0.2 0.1 First, you need to calculate the average weight, which is 0.5 in this case. Then, you create a two-dimensional array with two rows. The first row contains the "good" weights, which are those that are above the average, and the second row contains the "bad" weights, which are those that are below the average. Good Weights: 0.9 0.7 Bad Weights: 0.5 0.2 0.1 Then, you fill each row such that the sum of the weights in the row equals the total weight. In this case, the total weight is 2.5, so the first row would be filled with 0.9 and 0.7, and the second row would be filled with 0.5, 0.2, and 0.1. Now, to generate a weighted random number, you randomly select a row and then randomly select an element from that row. For example, if you randomly select the second row, you would randomly select either 0.5, 0.2, or 0.

I hope this is helpful!

 

[johnnyL]

Sounds way too complicated to me. Why can't you just add a few lines of code & treat it just like the integer example?

 

[JenniferMurphy]

mikenelena,

That sounds like what I think I remember. A couple of questions:

I think you meant 0.9 0.7 0.5 0.3 (not 0.2) 0.1. That makes sum=2.5 and average=0.5. Correct?

And now 0.5 is equal to the average. It is not above or below. So which row does it go in?

I am confused as to how to populate the rows. There is only 1 way to populate the Good Weights row so that it adds up to 2.5, but many ways to populate the Bad Weights row. Here's what I have so far:

Typing Tutor Adaptive Learning Algorithm.xlsm
	B	C	D	E	F	G	H	I	J
5							Sum	Mean
6		0.9	0.7	0.5	0.3	0.1	2.5	0.5
7
8					Sum
9	Good weights	0.9	0.9	0.7	2.5
10
11									Sum
12	Bad weights	0.5	0.5	0.5	0.3	0.3	0.3	0.1	2.5
13		0.5	0.5	0.5	0.5	0.3	0.1	0.1	2.5
Alias Method

Cell Formulas
Range	Formula
H6	H6	=SUM(C6:G6)
I6	I6	=AVERAGE(C6:G6)
F9	F9	=SUM(C9:E9)
J12:J13	J12	=SUM(C12:I12)

I found several links to "alies method", but they are too technical for me to follow. Here's one:

The Alias Method: Efficient Sampling with Many Discrete Outcomes | Laboratory for Intelligent Probabilistic Systems

lips.cs.princeton.edu

Here's another:

Alias method - Wikipedia

en.wikipedia.org

 

[JenniferMurphy]

Sounds way too complicated to me.

Then you should probably not use it. As for me, I recall that it was more efficient and elegant.

Why can't you just add a few lines of code & treat it just like the integer example?

For one thing, my weights are not integers. For another, I could have upwards of 100 weights. I know that's still not a big deal for VBA, but if there is a more elegant solution, I'm willing to take the time to explore it.

ymmv

 

[johnnyL]

For one thing, my weights are not integers. For another, I could have upwards of 100 weights. I know that's still not a big deal for VBA, but if there is a more elegant solution, I'm willing to take the time to explore it.

Is there something stopping you from making them integers?

 

[JenniferMurphy]

Is there something stopping you from making them integers?

My numbers are failure percentages, like 27/147 = 0.183673469. I could make them integers, I suppose, but they would be pretty large, which would defeat the purpose of the integer method.

 

[johnnyL]

Ok, forget my previous posts here in this thread.

 

[bebo021999]

With this
0.9 0.7 0.5 0.2 0.1
Can we change it to (multiply to 10):
9 7 5 2 1
then using RandBetween(1,24)
???

 

[JenniferMurphy]

With this
0.9 0.7 0.5 0.2 0.1
Can we change it to (multiply to 10):
9 7 5 2 1
then using RandBetween(1,24)
???

If those were the actual weights, yes. But, as I already said, they are not that simple.