1

Say I have a function that returns a weighted selection from a set of resources, according to a desired distribution. For argument's sake let that resource be string colors.

const distribution = {
  red: .1666,    // We want 1/6th of colors in the world to be 'red'  
  yellow: .3333, // ... 1/3 to be 'yellow'
  blue: .5       // ... and 1/2 to be 'blue'
}

// returns ~1/6 'red', ~1/3 'yellow', ~1/2 'blue'
function getWeightedColor() {...}

If I wanted to further weight the return value based on existing data with the purpose of guiding the data toward the desired distribution more quickly, how would I achieve that?

// Accepts a counts dict in the format `{<color>: count, ...}` and based on
// the distribution of that dict, further weights the selection such that
// the return value adjusts the dict toward the desired distribution.
function getWeightedColor(colorCounts) {...}

// Examples:

getWeightedColor({red: 100, yellow: 200, blue: 300}); 
// given distribution already normal, so we'd use the unadjusted weights

getWeightedColor({red: 100, yellow: 250, blue: 10});
// given distribution has far too few blues and somewhat too many yellows, 
// so the weights would be adjusted to compensate. The odds of 'blue'
// would be greatly increased, red somewhat decreased and yellow moreso.
18
  • "with the purpose of guiding the data back toward the desired distribution" you're going to have to first define how you want the historical data to influence the weighting. That decision is not trivial. Jan 24, 2018 at 2:44
  • 3
    Possible duplicate of Unevenly distributed random number generation
    – gnat
    Jan 24, 2018 at 3:58
  • 2
    @numbers1311407: No historical influence? You clearly are not aware of what you don't know. You need to read en.wikipedia.org/wiki/Gambler%27s_fallacy and think hard about the conflict in what you just wrote. Jan 24, 2018 at 6:16
  • 1
    Possible duplicate of How to generate random numbers with a (negative) sloping distribution?
    – user22815
    Jan 24, 2018 at 18:48
  • 1
    @gnat should have VTC'd as the question that the one you voted for is a duplicate of. It even has a really nice answer written up by the late, great MichaelT that explains what OP needs perfectly.
    – user22815
    Jan 24, 2018 at 18:49

2 Answers 2

2

If I wanted to further weight the return value based on existing data with the purpose of guiding the data toward the desired distribution more quickly, how would I achieve that?

This is the crux of the question, and what makes it different from the proposed duplicates. You want a weighted distribution, but one which skews toward the desired ratio while the algorithm is running.

The easiest way to do this is to treat this like a deck of cards where each card is one outcome possible in your algorithm (e.g. color, in your example). The algorithm looks like this:

  1. Construct a deck of N cards where N is the least common multiple of the denominator in each of the odds. In your example, LCM(2,3,6) = 6.
  2. Add cards for each possibility so the overall ratio is correct. In your example, you would add one red, two yellow, and three blue. 1/6 red, 2/6 = 1/3 yellow, and 3/6 = 1/2 blue.
  3. Shuffle the deck.
  4. Each time a color is requested, pull the next card off the top of the deck.
  5. If the previous step fails because there are no more cards, return to step 1 and continue to the previous step.

This differs from a typical algorithm for selecting weighted values because each draw is dependent on the previous one. Consider a game of Monopoly. Each time a player rolls the dice, any of the eleven possibilities (2-12) can occur with varying odds and this is true no matter when the player rolls. Compare to landing on Chance or Community Chest. The odds of drawing a specific card vary over the course of the game as the decks are depleted and eventually reshuffled. If there is a single card left to draw, and the player has been keeping track (or looks in the discard pile), it is possible to know exactly what the card is before drawing it. The first example is an independent event, the second example is a dependent event because drawing card N relies on all draws from 1 to N-1. The order is random, but the overall odds are precisely 1/6, 1/3, and 1/2 given a multiple of six draws.

1

If you just keep running the function long enough it will naturally converge to the weights you specified.

But that's not fast enough.

What you want is dynamic weights. The problem with that is, that there is no one right way to do it and it would determinately make your algorithm "less random" it would to some height become predictable.

For instance your distribution could become:

red
1/6 + 1/6*(1/6 - redamound/totalamount)
yellow
1/3 + 1/3*(1/3 - yellowamount/totalamount)
blue:
1/2 + 1/2*(1/2 - blueamount/totalamount)

This will push your distribution towards your desired distribution faster if it further from it.

1
  • This is along the lines of what I'm looking for. Predictability is fine here. I think that point may have confused the question. Do you know of any resources where I can research similar techniques as the one you describe? Jan 24, 2018 at 15:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.