# Decrease probability of picking a list's item based on its index

I have a list of sounds that are to be played when the user presses a button.
For now I just generate a random number within the range of the list and just pick the sound with that index. (I also prevent that sound from being played the next time the button is clicked. Since that is easy, I would like to concentrate only on the selection algorithm and leave the exclusion behind.)
Since that makes it possible for a few sounds to be played repeatedly in a pattern, I would like to adjust my algorithm:

Once a file is played it gets moved to the end of the list. Sounds from the beginning have a greater chance of being played than those at the end - therefore minimizing repetition.
Instead of assigning a weight to each index, I want to have one factor determining the probability falloff. For example, I would set this factor to be 1.2 which means that each index is 1.2 times as probable to be played as the following one. This hopefully produces a nice falloff in probability.

The fastest solution seems to be a mathematical function that maps the random number to the range of indices. That way I do not have to set up intervals, but can directly calculate the result based on the random number.

I just cannot figure out the math and implementiation behind this idea, so I need you to lay it out for me. The algorithm will be used in an Android app, so the programming language I am using is Java.

• What's the problem with using the factor to assign a weight to each index? – Doval Jul 11 '14 at 16:19
• I would like to have one parameter to influence the falloff. How would I determine the appropriate weight for each index? – J0hj0h Jul 11 '14 at 17:45
• `weight 0 = 1 | weight n = (weight (n-1)) * factor`. The problem you're trying to solve is the same as the one where you've assigned a weight to each index; the only difference is that you're calculating the weights. – Doval Jul 11 '14 at 17:50
• @Doval I adjusted my question: Instead of making it weight-based, I'd like a mathematical function to map the random number to the indices. That way a can quickly calculate the result based on one input without needing to store intervals. – J0hj0h Jul 13 '14 at 12:43

## 1 Answer

There are many ways to implement weighting, but you should start by thinking of this as a weighting function. In pseudo-code:

``````function weight(int max) returns integer;
``````

The integer is an index in the range of 0..max-1 which will select a sound.

You have available a random number generator which returns a uniform distribution [0..1).

``````function random() returns real;
``````

Now you need a formula to translate one distribution into another.

``````// linear
return integer(random() * max);
``````

To implement the 'factor' you propose requires a bit of maths, which perhaps someone else can help with. It could go something like this.

``````return integer(max*(1-x^1.2))
``````

I suggest the use of a graphing tool to visualise the distributions: http://rechneronline.de/function-graphs/.