Random numbers with different probabilities

A fairly generic method would be to have in a data structure (for example in two separate lists) the possible numbers to be generated and the possible "relative weights" of each one, for example the probability in percent that they come out.

From the list of weights we get a list of probabilities. We must ensure that the probabilities add up to 1, so in the list that contains those weights we could divide each element by the sum of all of them.

From the list of probabilities we build another list of "cumulative" probabilities, which are, for each element, its probability plus the sum of all the previous probabilities.

For example, if the input lists are:

datos = [ 5, 10, 25, 50, 80 ]
pesos = [ 63, 29.99, 7, 0.01, 0.0001 ]

that of "readjusted" weights would be:

probabilidades = [0.6299994, 0.2998997, 0.0699999, 0.0001000, 0.0000010]

and the cumulative probabilities would be:

acumuladas = [0.62999937, 0.92989907, 0.999899  , 0.999999  , 1.]

So, once we have the latter, the algorithm would be:

• Generate a random number between 0 and 1 (eg: suppose 0.8543 comes up)
• Go through the array acumuladasand find the index of the first element that exceeds the number obtained in the previous section (in the example, the first number that meets it is 0.92989907, whose index is 1)
• Select datosthe one with that index from the list (continuing with the example, the selected one would be datos[1]10.

If the first step generates the random numbers uniformly distributed between 0 and 1, this algorithm will select the numbers datoswith the specified probabilities.

Extension

In case someone finds it useful, and to compare with other languages, here is a possible implementation in Python:

from itertools import accumulate
import random

def elige_con_probabilidad(datos, pesos):
  suma = sum(pesos)
  pesos = accumulate(peso/suma for peso in pesos)
  r = random.random()
  for i, p in enumerate(pesos):
    if p > r:
      break
  return datos[i]

To see how it goes, I generate 10,000 random numbers with a given distribution and count how many times each one occurs:

from collections import Counter

datos = [25, 50, 75, 100]
pesos = [0.6, 0.3, 0.07, 0.03]
muchos = [ elige_con_probabilidad(datos, pesos) for _ in range(10000) ]
print(Counter(muchos))

Counter({25: 5977, 50: 3002, 75: 707, 100: 314})

The colleague @abulafia was ahead of me, but since he had already prepared a code in C# that demonstrated the method, I'll leave it here.

Basically, the method is the same. Is about:

1- Have two collections of equal size, one with the values, and another with the probabilities

2- The accumulated weights are computed, that is, for each array position, the value of the position plus the sum of the previous ones is placed.

3- A random number between 0 and the sum of the weight values ​​is obtained (ideally, 1)

4- The index of the first value greater than the random number obtained is obtained, and that is the index of the value that is selected.

Let's go with the code:

Random rn = new Random();
//paso 1

int[] arrayvalores = new int[] { 25, 50, 75, 100 };
double[] pesos = new double[] {0.6,0.3,0.07,0.03 };

double acc=0;

//paso 2
double[] pesosAcumulados = pesos.Aggregate((IEnumerable<double>)new List<double>(),
            (x, i) => x.Concat(new[] { x.LastOrDefault() + i })).ToArray();

double rando = 0;

int[] resultadoaleatorio = new int[4];
for (int i=0;i<10000;i++)
{
    //paso 3
    rando = rn.NextDouble() * pesos.Sum();
    //paso 4
    int posicionArray = pesosAcumulados.ToList().IndexOf(pesosAcumulados.Where(x => x > rando).FirstOrDefault());
    resultadoaleatorio[posicionArray]++;
}

for(int i=0;i<4;i++)
{
    Console.WriteLine($"Indice {i} - peso {pesos[i]} - veces que ha salido {resultadoaleatorio[i]} - porcentaje {(resultadoaleatorio[i]*100/10000)/100.0}");
}

As you can see in this example, I do the random roll 10,000 times to see if the method works correctly. This is an example of the output of a run:

Indice 0 - peso 0,6 - veces que ha salido 6043 - porcentaje 0,6
Indice 1 - peso 0,3 - veces que ha salido 2992 - porcentaje 0,29
Indice 2 - peso 0,07 - veces que ha salido 670 - porcentaje 0,06
Indice 3 - peso 0,03 - veces que ha salido 295 - porcentaje 0,02

As you can see, this method adjusts quite well to input percentages.

To generate discrete random variables there are two cases: the first one has already been developed - with replacement - and the second is without replacement .

As it was mentioned that the inspiration came from a game, I thought of Playing Cards. These are shuffled or permuted before being distributed, the latter should not be confused with the change of variable or Monty Hall problem since the probabilities change with each extraction.

Continuing with the case of cards, at the beginning the probability of obtaining any card is 1/54, when drawing the second it is 1/53 and so on.

Taken the following input values

datos = { 5, 10, 25, 50, 80 }
probabilidades = {0.6299994, 0.2998997, 0.0699999, 0.0001000, 0.0000010}
probaAcumulada = {0.6299994,0.9298991,0.999899,0.999999,1}

Suppose we need to extract three data.

Before the First extraction, there is a cumulative probability diagram, which is identical to the case with detailed replacement already by several in this trend . When generating the pseudo-random number 0.725... -between 0 and 1- which falls on the ordinate axis (y-axis) it corresponds to the number 10 of the abscissas (x-axis)

Since 10 comes out, the remaining probabilities are added and this result then divides each of them... as in the example of the cards, one of the 54 comes out, I add all the remaining ones, which gives 53 and that total divides each card 1/53.

Therefore, the input data for the second extraction would be as follows:

datos = { 5, 25, 50, 80 }
probaAcumulada = {0.899870204,0.999855735,0.9999985722,1}

Being its graphical representation this:

As number 5 came out, the input data and its corresponding graph of probabilities, remain like this for a third extraction if it is necessary to carry it out.

datos = { 25, 50, 80 }
probaAcumulada = {0.99855922,0.999985735,1}

The extraction bears the name of sample and it is this amount that goes in a loop -as a condition- until the data that is needed is extracted.

Summarizing the algorithm can be verbalized as follows:

We have data ( d ), its probabilities ( p ), the sample size ( m ) and the current amount extracted ( q ) which is initially zero

Paso 00: Calcular las probabilidades acumuladas (`pAcum`) de `p`
Paso 01: Generar un número pseudo-aleatorio (`u`) entre 0 y 1
Paso 02: Verificar para cada pAcum cuál es la primera en superar a `u` y extraer su indice (`i`)
Paso 03: Guardar el valor de `d` correspondiente a la posición `i`
Paso 04: Remover de `d` y `p` el valor correspondiente a la posición `i`
Paso 05: Re-calcular las probabilidades acumuladas (`pAcum`) de `p`
Paso 06: Sumarle a `q` uno
Paso 07: Mientras `m>=q` volver al Paso 01

A final clarification, if the sample is the size of all the data, this is equivalent to permuting the data, that is, to shuffling the cards, although unlike these, your case is interesting since the probabilities are different.

A practical application of generating discrete random variables is the virtual keyboards of the banks, where the keys {1,2,3,4,5,6,7,8,9,0} must be mixed or permuted for each session and / or user.

Here is a Lua implementation of discrete va generation with and without replacement

-- funcion de ayuda
local rand = math.random

-- valores de entrada
datos = { 5, 10, 25, 50, 80 }
probabilidades = {0.6299994, 0.2998997, 0.0699999, 0.0001000, 0.0000010}


-- funcion de ayuda para sumar elementos de una tabla en Lua
table.suma = function (list, fn)
    local acc
    for k, v in ipairs(list) do
        acc = k==1 and v or fn(acc, v)
    end
    return acc
end


-- funcion para acumular probabilidades
local acumProba = function(prob)
    local r = {prob[1]}
    for i=2, #prob do r[#r+1] = prob[i]+r[i-1] end
    return r
end


-- funcion para recalcular probabilidades cuando un elemento de la
-- tabla salió elegido
-- tener cuidado con el cambio de variable en este caso esta funcion
-- puede no ser valida
local acumProbAdj = function(prob)
    local total = table.suma(prob, function(a,b) return a+b end)
    local probAdj={}
    for _,valorProb in pairs(prob) do
        probAdj[#probAdj+1] = valorProb/total
    end
    return probAdj
end


-- eleccion de elementos al azar con reposicion
local conReposicion = function(dat, prob)
    local aleatorio = rand()

    for id, probAcumulada in pairs(prob) do
        if probAcumulada>aleatorio then
            return dat[id], id
        end
    end

end


-- eleccion de elementos al azar sin reposicion
-- tener en cuenta si la cantidad de muestra es
-- igual al total de datos se obtendrá un mezcla
-- al azar de los datos originales
local sinReposicion = function(dat, prob, cantMuestra)
    local d, p = {unpack(dat)}, {unpack(prob)}
    local muestras = {}
    local muestra, id

    for i=1, cantMuestra do
        muestra, id = conReposicion(d,acumProba(p))
        table.remove(d,id); table.remove(p,id)
        p = acumProbAdj(p)
        muestras[#muestras+1] = muestra
    end

    return muestras

end


-------------------------------------------
-- EJEMPLOS
-------------------------------------------

-- se obtiene las probabilidades acumuladas
print("\nSe obtiene las probabilidades acumuladas")
print(unpack(acumProba(probabilidades)))
print("\nPara los datos")
print(unpack(datos))



-- se obtiene solo un resultado de los datos al azar
print("\nCon resposición: se obtiene solo un resultado de los datos al azar. \nSe intenta 16 veces")
for i=1,16 do
    print("Intento "..i.." >",({conReposicion(datos,acumProba(probabilidades))})[1])
end




-- sin reposición para una muestra de 2, 3 y de 5 datos = #datos
-- cuando es 5 es equivalente a permutar o barajar los datos
print("\nSin reposición: para una muestra de 3, 2, 5, 1 y 4")
local a = {3, 2, 5, 1, 4}
for _,id in pairs(a) do
    print(id..">",unpack(sinReposicion(datos,probabilidades,id)))
end




-- Ejemplo de teclado virtual de banco
-- Creamos los valores de entrada, todos los números:
-- 1,2,3,4,5,6,7,8,9,0 tienen la misma probabilidad 1/10
local p,n={},{}
for i=1, 10 do table.insert(p,i,1/10); table.insert(n,i,i) end
n[#n]=0

-- Se permutan los números
local a = sinReposicion(n,p,10)

print("\nImprimimos teclado Virtual\n",
    "\n",a[1],a[2],a[3],
    "\n",a[4],a[5],a[6],
    "\n",a[7],a[8],a[9],
    "\n",a[10],"Ingresar"
)

You can run the Lua code here in replit

Finally, I made the graphics in R, the source code is in replit , but I edited it in Skitch .