How to generate weighted random numbers?

JenniferMurphy

Well-known Member
Joined
Jul 23, 2011
Messages
2,687
Office Version
  1. 365
Platform
  1. Windows
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
 
Let's see if I can help with some Pseudocode.

Take your 0.9, 0.7, 0.5, 0.2, 0.1
Convert those values to the cumulative values 0.9, 1.6, 2.1, 2.3, 2.4
Convert those values to integers, in this case, multiply those values by 10
At that point, you will have 9, 16, 21, 23, 24
Now you can treat them just like the integer approach

9 - 1's
16 - 2's
21 - 3's
etc.
 
Last edited by a moderator:
Upvote 0

Excel Facts

Who is Mr Spreadsheet?
Author John Walkenbach was Mr Spreadsheet until his retirement in June 2019.
Jennifer,

There is a method called the Alias Method that works with non-integer weights. . . .

OK. I found this website that has an explanation that I think I was able two follow.



I was able to implement this:

Cell Formulas
RangeFormula
H6,H20:H21H6=SUM(C6:G6)
I6I6=H6/5
J7,J9:J18J7=AliasMethod(Box_1, Box_2, NumResults)
C8:G8,G12,F10:G10C8=C6-C7
K9:K18K9=TallyResults(J9)
C17:G17C17=C15+C16
C20:G20C20=C6/$H$6
C21:G21C21=C20*NumResults
Named Ranges
NameRefers ToCells
'Alias Method'!Box_1='Alias Method'!$C$14:$G$14J7, J9:J18
'Alias Method'!Box_2='Alias Method'!$C$18:$G$19J7, J9:J18
'Alias Method'!NumResults='Alias Method'!$C$3J7, C21:G21, J9:J18


Here's th VBA code:

VBA Code:
'========================================================================================
'             Tally the number in each weight and show the %
'========================================================================================
Function TallyResults(pResults As String) As String

Dim i As Long             'Loop index
Dim Results As Variant
Dim Tallies() As Variant
Dim NumResults As Long    'The number of results to tally
Dim NextResult As Variant '
Dim NumWts As Long        'The number of weights

Results = Split(pResults)
NumResults = UBound(Results)

NumWts = 0                'Start it at zero
For i = 1 To NumResults   'Loop thru the results
  NextResult = Results(i)
  If NextResult > NumWts Then
    NumWts = NextResult
    ReDim Preserve Tallies(NumWts)
    End If
  Tallies(NextResult) = Tallies(NextResult) + 1
Next i

For i = 1 To NumWts
  TallyResults = TallyResults & Right("   " & Tallies(i), 4)
'                 & Format(Tallies(i) / NumResults, "  0.00") & " "
Next i

End Function


'========================================================================================
'           Test the Alias Method of Generating Weighted Random Numbers
'========================================================================================
Function AliasMethod(pBox1 As Range, pBox2 As Range, pNumResults As Long) As String
Const MyName As String = "AliasMethod"  'Function name for messages

Const MaxResults As Long = 50

Dim i As Long         'Loop index
Dim Box1 As Variant
Dim Box2 As Variant
Dim NumWts As Long    'The number of weights
Dim iBox1 As Long     'The Box1 index
Dim iBox2 As Long     'The Box2 index

Box1 = pBox1.Value2
Box2 = pBox2.Value2

' Validity checking
If UBound(Box1, 1) <> 1 Then
  MsgBox "Box1 must have exactly 1 row", vbOKOnly, MyName
  Exit Function: End If
If UBound(Box2, 1) <> 2 Then
  MsgBox "Box2 must have exactly 2 rows", vbOKOnly, MyName
  Exit Function: End If
NumWts = UBound(Box1, 2)  'Number of weights
If UBound(Box2, 2) <> NumWts Then
  MsgBox "Box1 and Box2 must have the same number of columns", vbOKOnly, MyName
  Exit Function: End If
If pNumResults > MaxResults Then
  MsgBox "Number of results > " & MaxResults, vbOKOnly, MyName
  Exit Function: End If
 
' Do it
AliasMethod = ""
For i = 1 To pNumResults
  iBox1 = Int(Rnd() * NumWts) + 1 'Select a random Box1 element
  iBox2 = Int(Rnd() * 2) + 1      'Select a random side of the selected Box2
  AliasMethod = AliasMethod & " " & Box2(iBox2, iBox1)
Next i

'Debug.Print AliasMethod

End Function

It seems to sorta work. I am not sure how. I'm too tired to continue now. Tomorrow I'll implement one of the other methods and compare the results.
 
Upvote 0
OK. I found this website that has an explanation that I think I was able two follow.


I was able to implement this:
I just discovered a flaw in the above implementation. I'll have a corrected version ready shortly. Should I just post the correct version and tell how this one above is wrong? Or would it better to delete these last 2 posts and I'll post a correct implementation? It might be useful to keep the incorrect one, because explaining where I went wrong mught make everything easier to understand. Once I found the error, the rest was clear to me.
 
Upvote 0
Would you be so kind to post a sample XL2BB sheet with the results that you really care about seeing?
 
Upvote 0
Want to get randomized numbers with probability?
Just creating numbers or draw them from stack?
Where draw numbers is written (write them one per cell)?

My apologies for any quirks, English is not my native language.
 
Upvote 0
I believe this is not what you asked, but is it applicable to your use?

This creates data for test use from the following data:
1. Values to randomize.
2. Number of occurrences for each Value. (You need to Revert weights to occurrences?)
3. How many times draw.

My apologies for any quirks, English is not my native language.

How to generate weighted random numbers ReDone v003.xlsm
ABCDEFGHIJKLMNOPQR
1Value to randomizeNumber of occurrencesA share of occurrencesDiceA share of occurrencesValue to randomizeCount Number of occurrences from share of occurrencesA share of occurrences
2120000,03278688511Horse3,2786885250,032786885
3220000,03278688521Budgie3,2786885250,032786885
4320000,03278688531Spider3,2786885250,032786885
5430000,04918032841Snake4,9180327870,049180328
6540000,0655737751Mouse6,5573770490,06557377
7650000,08196721361Goldfish8,1967213110,081967213
8750000,081967213Rabbit8,1967213110,081967213
9880000,131147541Guinea pig13,11475410,131147541
109100000,163934426Cat16,393442620,163934426
1110200000,327868852Dog32,786885250,327868852
12
13
14
15
16
17
18Total Occurrences61000Total Occurrences100
Sheet1
Cell Formulas
RangeFormula
C2:C11C2=B2/SUM($B$2:$B$11)
Q2:Q11Q2=$Q$18*R2
B18B18=SUM(B2:B12)


How to generate weighted random numbers ReDone v003.xlsm
ABCDEFGHIJKLM
1Random DataValueOccurrenceRound resultsExpected resultDifferenceTest Array
210#DIV/0!3,279 %#DIV/0!
320#DIV/0!3,279 %#DIV/0!
430#DIV/0!3,279 %#DIV/0!
540#DIV/0!4,918 %#DIV/0!
650#DIV/0!6,557 %#DIV/0!
760#DIV/0!8,197 %#DIV/0!
870#DIV/0!8,197 %#DIV/0!
980#DIV/0!13,115 %#DIV/0!
1090#DIV/0!16,393 %#DIV/0!
11100#DIV/0!32,787 %#DIV/0!
12
13Sum0#DIV/0!1,000000#DIV/0!
Sheet2
Cell Formulas
RangeFormula
D2:D11D2=COUNTIF($A:$A,C2)
F2:F11F2=D2/$D$13*100
H2:H11H2=Sheet1!C2
J2:J11J2=F2-(H2*100)
D13,J13,H13,F13D13=SUM(D2:D11)


VBA Code:
Option Explicit
Public DataARR As Variant

Function Fu_SortARR(ByVal DataVAR As Variant, Optional CoINT As Integer) As Variant
Dim RowsARR As Variant, ReturnARR As Variant
Dim i As Long, j As Long, DataLNG As Long

    DataARR = DataVAR
    DataLNG = UBound(DataARR, 1)

ReDim RowsARR(1 To DataLNG)
For i = DataLNG To 1 Step -1
    RowsARR(i) = i
Next i

ReDim ReturnARR(1 To DataLNG, 1 To UBound(DataARR, 2))
For i = 1 To DataLNG
    For j = 1 To UBound(ReturnARR, 2)
        ReturnARR(i, j) = DataARR(RowsARR(i), j)
    Next j
Next i

Fu_SortARR = ReturnARR

End Function

Function Fu_Fill_RNG(SrcRNG As Range, FillRows As Long, Optional DstRNG As Range, Optional NoRepetion As Boolean = False, Optional There_is_Headers As Boolean = False) As Variant
On Error GoTo ErrHand: Application.Calculation = xlManual: Application.ScreenUpdating = False: Application.DisplayAlerts = False: Dim coT As Single: coT = Timer() ' Timer start
'Dim wb As Workbook, wsR As Worksheet, wsW As Worksheet
Dim i As Long, j As Long, iR As Long, iRt As Long, SrcARRSum As Long, SeaSNG As Single, TrgSNG As Single, Fill_Values As Long
Dim SrcARR As Variant, DstARR() As Variant, FillARR As Variant
'Dim TrueCounter As Long ' Only for Debuging
If There_is_Headers Then Set SrcRNG = SrcRNG.Offset(1, 0).Resize(SrcRNG.Rows.Count - 1, SrcRNG.Columns.Count)

If NoRepetion And FillRows > Application.Sum(SrcRNG.Columns(2)) Then FillRows = Application.Sum(SrcRNG.Columns(2))
Fill_Values = SrcRNG.Rows.Count

ReDim FillARR(1 To FillRows, 1 To 1) ' Fit FillARR for return values
'Dim TestARR As Variant: ReDim TestARR(1 To FillRows, 1 To 1) ' Fit TestARR for randomed values, only for test/debuging

Randomize
If SrcRNG.Columns.Count = 1 Then ' No Probability calculated, ALL VALUES HAVE EQUAL PROBABILITY!
    SrcARR = SrcRNG.value
    For i = LBound(FillARR) To UBound(FillARR)
        TrgSNG = Application.RoundDown(Rnd() * Fill_Values + 1, 0)
        FillARR(i, 1) = SrcARR(TrgSNG, 1)
        ' TestARR(i, 1) = TrgSNG ' Only for Debuging
    Next i

ElseIf SrcRNG.Columns.Count = 2 Then ' Probability numbers found from column(2) calculating probabilities, ALL VALUES HAVE OWN PROBABILITY!
        ReDim DstARR(1 To SrcRNG.Rows.Count, 1 To 4) ' Values and frequensy
        SrcRNG.Sort Key1:=SrcRNG.Cells(1, 2), Order1:=xlAscending ' SORTING SOURCE RANGE!
        SrcARR = SrcRNG.value ' Source Range to Array
        
        ' Summing all occurrences from Columns(2) for counting probabilities.
        With Application.WorksheetFunction
            SrcARRSum = .Sum(.Index(SrcARR, 0, 2))
        End With

    '***** Filling DstARR with SrcARR values AND adding probabilities.
        For i = LBound(SrcARR) To UBound(SrcARR)
            For j = LBound(SrcARR, 2) To UBound(SrcARR, 2)
                DstARR(i, j) = SrcARR(i, j)
                DstARR(i, j + 1) = Round(CSng(DstARR(i, 2) / SrcARRSum), 5)
                DstARR(i, j + 2) = Round(CSng(Application.Sum(Application.Index(DstARR, 0, 3))), 4)
            Next j
        Next i
        
    If Not NoRepetion Then
    '***** RANDOMING FILL VALUES! ***********************************************************************
        For i = LBound(FillARR) To UBound(FillARR)
            TrgSNG = Rnd()
            ' TestARR(i, 1) = TrgSNG ' Only for Debuging
            For j = LBound(DstARR) To UBound(DstARR)
                SeaSNG = DstARR(j, 4)
                If SeaSNG > TrgSNG Then
                    FillARR(i, 1) = DstARR(j, 1)
                    Exit For
                End If
            Next j
        Next i
    Else
    
        For i = LBound(FillARR) To UBound(FillARR)
            TrgSNG = Rnd()
            'TestARR(i, 1) = TrgSNG ' Only for Debuging
            
            For j = LBound(DstARR) To UBound(DstARR)
                SeaSNG = DstARR(j, 4)
                    If DstARR(j, 4) > TrgSNG And 0 < DstARR(j, 2) Then
                        'TrueCounter = TrueCounter + 1 ' Only for Debuging
                        FillARR(i, 1) = DstARR(j, 1)
                        DstARR(j, 2) = DstARR(j, 2) - 1
                        SrcARRSum = Application.Sum(Application.Index(DstARR, 0, 2))
                        
                            For iR = LBound(DstARR) To UBound(DstARR)
                                If DstARR(iR, 2) = 0 Then
                                    DstARR(iR, 3) = 0
                                Else
                                    DstARR(iR, 3) = Round(CSng(DstARR(iR, 2) / SrcARRSum), 5)
                                End If
                            Next iR
                            
                            DstARR = Fu_SortARR(DstARR, 3)
                            
                            For iR = LBound(DstARR) To UBound(DstARR)
                                DstARR(iR, 4) = 0
                                For iRt = LBound(DstARR) To iR
                                    DstARR(iR, 4) = DstARR(iR, 4) + DstARR(iRt, 3)
                                Next iRt
                                DstARR(iR, 4) = Round(DstARR(iR, 4), 4)
                            Next iR
                            
                        Exit For
                    End If
            Next j
        Next i
    End If
    
Else
    End
End If

'***** Selecting if return value are written directly to range or given as Function Return value ***********
If Not DstRNG Is Nothing Then
    DstRNG.Resize(FillRows, 1).value = FillARR
    Fu_Fill_RNG = True
Else
    Fu_Fill_RNG = FillARR
End If

' Test and Debug value
'Taul3.Range("L2").Resize(UBound(TestARR) - 1, 1).value = TestARR

ErrHand:
Application.Calculation = xlAutomatic: Application.ScreenUpdating = True: Application.DisplayAlerts = True
If Err.Number <> 0 Then MsgBox "Something went badly wrong!" & vbCrLf & "Function Fu_Fill_RNG FAILED!!!" & vbCrLf & "VBA-code is ended!" & vbCrLf & vbCrLf & "Error number: " & Err.Number & " " & Err.Description: End
End Function

Sub Use_Fu_Fill_RNG()
Dim x As Variant, x2 As Variant, FillRows As Long, SourceRNG As Range, DestinationRNG As Range
Dim coT As Single: coT = Timer() ' Timer start
Dim TEST As Variant
'********** INSTRUCTIONS *************************************************************************************
'*  If DestinationRNG is not defined, function "Fu_Fill_RNG" return ARRAY of values to x !
'*  If DestinationRNG is defined, function "Fu_Fill_RNG" write values DIRECTLY to DestinationRNG.
'*        Return value to x is then Type: Boolean True/False (True=No Errors, False = Errors function FAILED!
'* If SourceRNG is 1 Column then all VALUES ARE SELECTED RANDOMLY with EQUAL POSIBILITIES _
'*      if SourceRNG is 2 Column, Second Column must contain NUMBER OF POSIBILITIES (how many of each value there are) _
'*      Function count posibilities by NUMBER OF POSIBILITIES (The dice have 6 "Value" and each have 1 "NUMBER OF POSSIBILITIES")
'*  Dice "Col A" "Col B"
'*          1       1
'*          2       1
'*          3       1
'*          4       1
'*          5       1
'*          6       1
'**************************************************************************************************************


'********** PARAMETERS FOR "Fu_Fill_RNG" FILL WANTED VALUES HERE! *********************************************
FillRows = 60998                                        ' How many Cells(rows) to Fill?
Set SourceRNG = Worksheets(1).Range("A2:B11")           ' Where Found Values to use?
Set DestinationRNG = Worksheets(2).Range("A2")          ' What Column will be Filled? Only First Cell address
'********** PARAMETERS END! ***********************************************************************************


x = Fu_Fill_RNG(SourceRNG, FillRows, DestinationRNG, True)
Debug.Print Format(Timer() - coT, "#0.00", 2)
End Sub
 
Upvote 0
I believe this is not what you asked, but is it applicable to your use?
Wow! That will take quite a bit of time to get my head around all that. I have a version of the Alias Method almost working. I want to finish that so I can put it to work befire I tackle anything else. Thanks for the effort you put in. I hope someone is able to make use of it.

Cheers
 
Upvote 0
Would you be so kind to post a sample XL2BB sheet with the results that you really care about seeing?

I will extend one last olive branch:

JenniferMurphyWeightedDrawings.xlsm
ABCDEFG
1Iteration CountWeightsCumulative WeightsCumulative Weights as IntegersRandom # GeneratedInteger equate
2100.90.9991
30.71.616835
40.52.121614
50.22.323815
60.12.424805
7373
8865
9815
10604
11905
12
Sheet2


Let us know what the results you are looking for are supposed to look like.
 
Upvote 0
Let us know what the results you are looking for are supposed to look like.
I think I was pretty clear about what I am looking for in my original post. The 2 methods I understand, one of which looks like the one you just posted, have drawbacks if the list of items is large. One involved looping and the other a very large array. I said I remembered seeing something about a method that used a table and could handle very large numbers quickly. The project I am working on could have upwards of 100 items to be selected by weighted random numbers.

mikenelena posted a link to a discussion of the Alias Method, which is exactly what I was looking for. I then found another website with a clearer explanation. This method involves a bit more setup, but then it can select a weighted random element from a list of elements of practically any length with just two random numbers.

I then posted a quick 'n' dirty implementation that was partly manual that I thought worked perfectly. Then I discovered a bug (actually 2 bugs). I said I would post a corrected version. I have that almost working. I do have a few other things to do, so it might be a day or so before I can post the solution.

And I really don't like olives.
 
Last edited by a moderator:
Upvote 0

Forum statistics

Threads
1,223,886
Messages
6,175,193
Members
452,616
Latest member
intern444

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top