Necesito muestrear números de una distribución, pero las probabilidades de todos los números deben ser algo que pueda controlar.
Por ejemplo, supongamos que tengo 5 nodos (a, b, c, d, e) en un gráfico, y cada nodo tiene una "probabilidad de conexión" que determina la probabilidad de que un nuevo nodo agregado al gráfico se "pegue" a él.
Por ejemplo, las probabilidades de conexión de mis 5 nodos podrían ser:
{ a: 0.1 b: 0.1 c: 0.2 d: 0.1 e: 0.5 }Cuando agrego un nuevo nodo, debe adjuntarse al nodo "e" la mayor parte del tiempo (ya que tiene la probabilidad más alta) pero, por supuesto, esto no debería ser todo el tiempo, ya que estas son probabilidades.
Podría crear manualmente una muestra de, digamos, 1000 números, cuyas ocurrencias siguen las probabilidades anteriores. Entonces, la matriz tendría 100 letras a, 100 letras b, 200 letras c, 100 letras d y 500 letras e. Entonces podría hacer una muestra aleatoria de esta matriz, que sería lo mismo que sacar una distribución con las probabilidades mencionadas anteriormente.
¿Hay alguna otra forma (menos manual) de hacer esto en javascript? ¿La API Math o random tiene una forma de especificar las probabilidades que subyacen al muestreo?
Mi solución
const STEP = 1 const CONF = { a: 1, b: 1, c: 2, d: 1, e: 5, } function getDistribution() { const distributionMap = {} let start = 0 for (let key in CONF) { for (let i = 0; i < CONF[key]; i += STEP) { distributionMap[start++] = key } } return distributionMap[Math.floor(Math.random() * start)] } // Test const testDistribution = {} for (let i = 0; i < 1000; i++) { const key = getDistribution() testDistribution[key] = testDistribution[key] ? testDistribution[key] + 1 : 1 } console.log(testDistribution) // {a: 96, c: 183, e: 511, d: 110, b: 100} // {e: 511, c: 194, a: 107, d: 90, b: 98} // {e: 500, a: 106, c: 210, d: 90, b: 94}La opción estándar para el muestreo con reemplazo dado un conjunto de pesos es hacer una suma acumulativa de los pesos, luego elegir un valor aleatorio < la suma y elegir el índice que se superpone al valor.
Por ejemplo:
const weighted_choice = function(table) { const choices = [], cumweights = []; let sum = 0; for (const k in table) { choices.push(k); // work with the cumulative sum of weights cumweights.push(sum += table[k]); } return function() { const val = Math.random() * sum; // a binary search would be better for "large" tables for (const i in cumweights) { if (val <= cumweights[i]) { return choices[i]; } } }; };Estoy devolviendo una lambda para que las sumas acumulativas no tengan que volver a calcularse cada vez. En comparación con el código de Frank, esto no supone que esté pasando conteos de enteros, por lo que los pesos pueden abarcar de manera eficiente un rango mucho más grande.
Podrías probar la función anterior así:
const gen = weighted_choice({ a: 0.1, b: 0.1, c: 0.2, d: 0.1, e: 0.5, }); const counts = {}; for (let i = 0; i < 10000; i++) { const val = gen(); counts[val] = (counts[val] || 0) + 1; } console.log(counts);que imprime algo como:
{ a: 1014, b: 952, c: 1971, d: 990, e: 5073 }Creo que mi idea original tiene más sentido, aunque es probable que las respuestas proporcionadas hagan lo mismo.
Primero, creo una función que crea "contenedores" en función de los pesos de probabilidad pasados:
function create_bins_from_probability_weights(options) { const res = {}; Object.keys(options.table_of_probs).forEach(function(key) { var prob = options.table_of_probs[key]; var bin_size = (prob * options.population_size); res[key] = bin_size; }) return (res) }Luego creo una función para hacer una población representativa, cuyos miembros reflejen los valores en los contenedores anteriores:
function create_population_from_bins(options) { const res = []; Object.keys(options.bins).forEach(function(key) { for(var i = 0; i < options.bins[key]; i++) { res.push(key); } }) return (res) }Finalmente, creo una función para tomar una muestra aleatoria de la población representativa anterior:
function random_sample_from_array(options) { const res = options.array[Math.floor(Math.random() * options.array.length)]; return (res) }En conjunto, podemos usar estas funciones de la siguiente manera:
Usando una tabla de probabilidades:
table = { a : 0.1, b : 0.1, c : 0.2, d : 0.1, e : 0.5 }...crear contenedores:
var bins = create_bins_from_probability_weights({ table_of_probs: table, population_size: 1000 })...crear una población representativa a partir de los contenedores:
array_of_values = create_population_from_bins({ bins : bins })... tomar una sola muestra de la población anterior:
var final = random_sample_from_array({ array : array_of_values }) La variable final es la muestra individual más probable de extraer, ya que se extrae de una población cuyos miembros reflejan las probabilidades utilizadas para crear la distribución.