How do I value from an array that returns objects at the beginning more often?

Question

Given an array like [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], I want to get a random value that takes into consideration the position.

I want the likelihood of 1 popping up to be way bigger than 10.

Is something like this possible?

Answer 1

For the sake of simplicity let's assume an array arr = [x, y, z] from which we will be sampling values. We'd like to see following relative frequencies of x, y and z:

frequencies = [5, 2, 1]

Preprocess these frequencies to calculate margins for our subsequent dice roll:

thresholds = frequencies.clone
1.upto(frequencies.count - 1).each { |i| thresholds[i] += thresholds[i - 1] }

Let's sum them up.

max = frequencies.reduce :+

Now choose a random number

roll = 1 + rand max
index = thresholds.find_index { |x| roll <= x }

Return arr[index] as a result. To sum up:

def sample arr, frequencies
  # assert arr.count == frequencies.count
  thresholds = frequencies.clone
  1.upto(frequencies.count - 1).each { |i| thresholds[i] += thresholds[i - 1] }
  max = frequencies.reduce :+
  roll = 1 + rand(max)
  index = thresholds.find_index { |x| roll <= x }
  arr[index]
end

Let's see how it works.

data = 80_000.times.map { sample [:x, :y, :z], [5, 2, 1] }

A histogram for data shows that sample works as we've intended.

Answer 2

def coin_toss( arr )
  arr.detect{ rand(2) == 0 } || arr.last
end

a = (1..10).to_a
10.times{ print coin_toss( a ), ' ' } #=> 1 1 1 9 1 5 4 1 1 3 

This takes the first element of the array, flips a coin, returns the element and stops if the coinflip is 'tails'; the same with the next element otherwise. If it is 'heads' all the way, return the last element.

Answer 3

A simple way to implement this with an logarithmic probabilistic of being selected is to simulate coin flips. Generate a random integer 0 and 1, the index to that array to choose is the number of consecutive 1s you get. With this method, the chance of selecting 2 is 1/2 as likely as 1, 3 is 1/4th as likely, etc. You can vary the probability slightly say by generating random numbers between 0 and 5 and count the number of consecutive rounds above 1, which makes each number in the array 4/5th as likely to appear as the one before.

A better and more general way to solve this problem is to use the alias method. See the answer to this question for more information: Data structure for loaded dice?