0

edited

I have a list with N elements, where K elements are "special" and the rest are "normal". What I'm trying to do is pick an element at random, but special elements should be selected 35% more often than normal items.

For example:

var myList = [
   {id: 1, special: 0},
   {id: 2, special: 1} // <= special item
];

After 600 selections, the normal element should be selected 250 times, and the second should be selected 35% more times than that, or 350 times.

This is different from the suggested duplicate question because my weights do not add up to 1. I can have any arbitrary of elements in my list, and zero or more of them are special. The weight is always 1.35 for special items, and 1.0 for normal items.

Community
  • 1
  • 1
rodrigo-silveira
  • 12,607
  • 11
  • 69
  • 123
  • 1
    possible duplicate of [Generate A Weighted Random Number](http://stackoverflow.com/questions/8435183/generate-a-weighted-random-number) – Jamiec Aug 13 '15 at 14:19
  • This question is not a duplicate of the suggested question. The proposed solutions there deal with a fundamentally different problem I'm trying to solve. – rodrigo-silveira Aug 13 '15 at 18:37

3 Answers3

2

Your question is ambiguous with regards to the "35% more often" part. (1) Does it mean that special values as a whole are chosen 35% more than normal values as a whole? (2) Or does it mean that special values are simply weighted 1.35 and normal values are weighted 1?

The two question variants I have described have different answers.

Answer (1)

Note you must always have at least one special and at least one normal value.

We know that every time you sample a value it is either Special or Normal, but not both:

P(Special) + P(Normal) = 1

We know that the likelihood of Special is 35% larger than the likelihood of Normal:

P(Special) = 1.35 * P(Normal)

This is a system of two linear equations with two unknowns. Here is its solution:

P(Normal) = 20 / 47
P(Special) = 27 / 47

Simply divide your set of values into two sets, Specials and Normals. Now to sample do the following:

  1. Sample r uniformly from [0, 1].
  2. If r < 20 / 47, then uniformly sample from Normals.
  3. Else, then uniformly sample from Specials.

Answer (2)

  1. Randomly select an item from the list.
  2. If it is special or Math.random() < 1 / 1.35, then you are done.
  3. Else, return to step 1.
Timothy Shields
  • 75,459
  • 18
  • 120
  • 173
  • Could you elaborate on answer #1, step 2? – Keith Aug 14 '15 at 00:27
  • 2
    @Keith Before specifying the algorithm, I have derived `P(Normal) = 20 / 47`. A random number in `[0, 1]` is less than `20 / 47` with a probability of `20 / 47`. – Timothy Shields Aug 14 '15 at 01:28
  • Thank you. What I'm looking for is Answer (2). – rodrigo-silveira Aug 14 '15 at 09:15
  • @TimothyShields How would I adapt answer (2) for a scenario where each item in the list has a different weight? For example: ```[{id: 1, weight: 1.0}, {id: 2, weight: 1.0}, {id: 1, weight: 1.3}, {id: 1, weight: 1.6}]``` (the sum of weights may or may not add up to 1.0) – rodrigo-silveira Aug 14 '15 at 10:53
  • 2
    @rodrigo-silveira Jamiec suggested a question to you as a possible duplicate, which is exactly what you just said. Check it out. – Timothy Shields Aug 14 '15 at 14:37
-1

You could take an approach where to first determine if you want to to trigger your "higher probability" code, and then pull from your custom list instead.

if ( Math.random() < .35 ) {
   element = randChoice(myCustomListOfMoreProbableChoices);
} else {
   element = randChoice(myListOfAllChoices);
}
Brandon
  • 983
  • 6
  • 15
  • This approach will select the second option 37% of the time. 40% more than 37% is not 63%. In other words, out of 1,000 selections, the second option will be chosen 370 times. 370 * 1.4 = 518. So 370 + 518 = 688 and 688 !== 1,000 – rodrigo-silveira Aug 13 '15 at 14:43
  • What exactly does "35% more often" mean? Perhaps you can do some quick math and then tweak the threshold to get the desired results. – Brandon Aug 13 '15 at 15:07
  • 35% more means that if the "normal" element is chosen 10 times, then the "special" element should be chosen 35% more often that the normal one: 10 * 1.35 = 13.5. No the normal element is chosen 10 times, and the special one 13 times. In this case, these numbers are calculated after 23 selections. – rodrigo-silveira Aug 13 '15 at 15:38
-3

Create an array for indexes to be chosen for your main array then randomly choose an element from that array to select from you main array:

var mainArray = [1, 2, 3];
var indexesArray = [0, 0, 0, 1, 2]; //1 has 3/5 chance of being chosen while 2 and 3 only have 1/5

Randomly select an index from indexesArray using a random number then:

mainArray[randomFromIndexArray];
brso05
  • 13,142
  • 2
  • 21
  • 40
  • In my case, ```mainArray = [0, 1];```. After one million selections later, I want ```mainArray[0]``` to have been selected about 430,000 times, and ```mainArray[1]``` to have been selected 35% more often, or about 580,500. Your solution doesn't do that. – rodrigo-silveira Aug 13 '15 at 14:31
  • @rodrigo-silveira you just have to adjust how many times you put each index in the `indexes` array you would need to do some math calculations this is just an example... – brso05 Aug 13 '15 at 14:38
  • I get the point, but that is not practical for my use case. What would the indexes array look like if my list has hundreds or thousands of elements, and half of those elements need to be chosen 35% more often? – rodrigo-silveira Aug 13 '15 at 14:52
  • @rodrigo-silveira well then in your case it doesn't make sense but you didn't specify that in your question... – brso05 Aug 13 '15 at 15:01
  • Who downvoted this answer? You should say why you downvote an answer and "no reason" is not a good reason... – brso05 Aug 13 '15 at 15:01