probabilidad - numeros aleatorios negativos y positivos en java

Número aleatorio con Probabilidades

Question

Me pregunto ¿cuál sería la mejor manera (por ejemplo, en Java) para generar números aleatorios dentro de un rango particular donde cada número tiene una cierta probabilidad de ocurrir o no?

p.ej

Genere enteros aleatorios desde [1; 3] con las siguientes probabilidades:

P (1) = 0.2
P (2) = 0.3
P (3) = 0.5

En este momento estoy considerando el enfoque para generar un entero al azar dentro de [0; 100] y hacer lo siguiente:

Si está dentro de [0; 20] -> obtuve mi número aleatorio 1.
Si está dentro de [21; 50] -> Obtuve mi número aleatorio 2.
Si está dentro de [51; 100] -> obtuve mi número aleatorio 3.

¿Qué dirías?

Answer 1

Escrita esta clase para una entrevista después de hacer referencia al artículo señalado por pjs en otra post , la población de la tabla base64 puede optimizarse aún más. El resultado es sorprendentemente rápido, la inicialización es un poco cara, pero si las probabilidades no cambian a menudo, este es un buen enfoque.

* Para la clave duplicada, se toma la última probabilidad en lugar de combinarse (ligeramente diferente del comportamiento EnumeratedIntegerDistribution)

public class RandomGen5 extends BaseRandomGen {
private int[] t_array = new int[4];
private int sumOfNumerator;
private final static int DENOM = (int) Math.pow(2, 24);
private static final int[] bitCount = new int[] {18, 12, 6, 0};
private static final int[] cumPow64 = new int[] {
(int) ( Math.pow( 64, 3 ) + Math.pow( 64, 2 ) + Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),
(int) ( Math.pow( 64, 2 ) + Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),
(int) ( Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),
(int) ( Math.pow( 64, 0 ) )
};
ArrayList[] base64Table = {new ArrayList<Integer>()
, new ArrayList<Integer>()
, new ArrayList<Integer>()
, new ArrayList<Integer>()};
public int nextNum() {
int rand = (int) (randGen.nextFloat() * sumOfNumerator);
for ( int x = 0 ; x < 4 ; x ++ ) {
if (rand < t_array[x])
return x == 0 ? (int) base64Table[x].get(rand >> bitCount[x])
: (int) base64Table[x].get( ( rand - t_array[x-1] ) >> bitCount[x]) ;
}
return 0;
}
public void setIntProbList( int[] intList, float[] probList ) {
Map<Integer, Float> map = normalizeMap( intList, probList );
populateBase64Table( map );
}
private void clearBase64Table() {
for ( int x = 0 ; x < 4 ; x++ ) {
base64Table[x].clear();
}
}
private void populateBase64Table( Map<Integer, Float> intProbMap ) {
int startPow, decodedFreq, table_index;
float rem;
clearBase64Table();
for ( Map.Entry<Integer, Float> numObj : intProbMap.entrySet() ) {
rem = numObj.getValue();
table_index = 3;
for ( int x = 0 ; x < 4 ; x++ ) {
decodedFreq = (int) (rem % 64);
rem /= 64;
for ( int y = 0 ; y < decodedFreq ; y ++ ) {
base64Table[table_index].add( numObj.getKey() );
}
table_index--;
}
}
startPow = 3;
for ( int x = 0 ; x < 4 ; x++ ) {
t_array[x] = x == 0 ? (int) ( Math.pow( 64, startPow-- ) * base64Table[x].size() )
: ( (int) ( ( Math.pow( 64, startPow-- ) * base64Table[x].size() ) + t_array[x-1] ) );
}
}
private Map<Integer, Float> normalizeMap( int[] intList, float[] probList ) {
Map<Integer, Float> tmpMap = new HashMap<>();
Float mappedFloat;
int numerator;
float normalizedProb, distSum = 0;
//Remove duplicates, and calculate the sum of non-repeated keys
for ( int x = 0 ; x < probList.length ; x++ ) {
mappedFloat = tmpMap.get( intList[x] );
if ( mappedFloat != null ) {
distSum -= mappedFloat;
} else {
distSum += probList[x];
}
tmpMap.put( intList[x], probList[x] );
}
//Normalise the map to key -> corresponding numerator by multiplying with 2^24
sumOfNumerator = 0;
for ( Map.Entry<Integer, Float> intProb : tmpMap.entrySet() ) {
normalizedProb = intProb.getValue() / distSum;
numerator = (int) ( normalizedProb * DENOM );
intProb.setValue( (float) numerator );
sumOfNumerator += numerator;
}
return tmpMap;
}
}

Answer 2

Hace un tiempo escribí una clase de ayuda para resolver este problema. El código fuente debe mostrar el concepto lo suficientemente claro:

public class DistributedRandomNumberGenerator {
private Map<Integer, Double> distribution;
private double distSum;
public DistributedRandomNumberGenerator() {
distribution = new HashMap<>();
}
public void addNumber(int value, double distribution) {
if (this.distribution.get(value) != null) {
distSum -= this.distribution.get(value);
}
this.distribution.put(value, distribution);
distSum += distribution;
}
public int getDistributedRandomNumber() {
double rand = Math.random();
double ratio = 1.0f / distSum;
double tempDist = 0;
for (Integer i : distribution.keySet()) {
tempDist += distribution.get(i);
if (rand / ratio <= tempDist) {
return i;
}
}
return 0;
}
}

El uso de la clase es el siguiente:

DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator();
drng.addNumber(1, 0.3d); // Adds the numerical value 1 with a probability of 0.3 (30%)
// [...] Add more values
int random = drng.getDistributedRandomNumber(); // Generate a random number

Controlador de prueba para verificar la funcionalidad:

 public static void main(String[] args) {
DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator();
drng.addNumber(1, 0.2d);
drng.addNumber(2, 0.3d);
drng.addNumber(3, 0.5d);
int testCount = 1000000;
HashMap<Integer, Double> test = new HashMap<>();
for (int i = 0; i < testCount; i++) {
int random = drng.getDistributedRandomNumber();
test.put(random, (test.get(random) == null) ? (1d / testCount) : test.get(random) + 1d / testCount);
}
System.out.println(test.toString());
}

Muestra de salida para este controlador de prueba:

{1=0.20019100000017953, 2=0.2999349999988933, 3=0.4998739999935438}

Answer 3

Intente esto: en este ejemplo utilizo una matriz de caracteres, pero puede sustituirlo por su matriz de enteros.

La lista de peso contiene para cada char la probabilidad asociada. Representa la distribución de probabilidad de mi juego de caracteres.

En la lista de pesos para cada char, almacené su probabilidad real más la suma de cualquier probabilidad de antecedente.

Por ejemplo, en weightsum el tercer elemento correspondiente a ''C'', es 65:
P (''A'') + P (''B) + P ('' C '') = P (X => c)
10 + 20 + 25 = 65

Entonces weightsum representa la distribución acumulativa de mi juego de caracteres. weightsum contiene los siguientes valores:

Es fácil ver que el octavo elemento corresponde a H, tiene una brecha más grande (80 por supuesto, como su probabilidad) ¡entonces es más como que sucederá!

 List<Character> charset = Arrays.asList(''A'',''B'',''C'',''D'',''E'',''F'',''G'',''H'',''I'',''J'');
List<Integer> weight = Arrays.asList(10,30,25,60,20,70,10,80,20,30);
List<Integer> weightsum = new ArrayList<>();
int i=0,j=0,k=0;
Random Rnd = new Random();
weightsum.add(weight.get(0));
for (i = 1; i < 10; i++)
weightsum.add(weightsum.get(i-1) + weight.get(i));

Luego utilizo un ciclo para obtener 30 extracciones de caracteres al azar del conjunto de caracteres, cada uno dibujado de acuerdo con la probabilidad acumulada.

En ki almacenamos un número aleatorio de 0 al valor máximo asignado en weightsum. Luego miro hacia arriba en weightsum para un número más grande que k, la posición del número en weightsum corresponde a la misma posición de la char en charset.

 for (j = 0; j < 30; j++)
{
Random r = new Random();
k = r.nextInt(weightsum.get(weightsum.size()-1));
for (i = 0; k > weightsum.get(i); i++) ;
System.out.print(charset.get(i));
}

El código muestra esa secuencia de char:

HHFAIIDFBDDDHFICJHACCDFJBGBHHB

¡Hagamos las matemáticas!

A = 2
B = 4
C = 3
D = 5
E = 0
F = 4
G = 1
H = 6
I = 3
J = 2

Total.:30
Como deseamos D y H tienen más ocurrencias (70% y 80% de problema)
Otherwinse E no salió en absoluto. (10% prob.)

Answer 4

La suya ya es una buena manera y funciona bien con cualquier rango.

Solo estoy pensando: otra posibilidad es deshacerse de las fracciones multiplicándolas por un multiplicador constante, y luego construir una matriz con el tamaño de este multiplicador. Multiplicando por 10 obtienes

P(1) = 2
P(2) = 3
P(3) = 5

Luego, crea una matriz con los valores inversos: ''1'' entra en los elementos 1 y 2, ''2'' en 3 a 6, y así sucesivamente:

P = (1,1, 2,2,2, 3,3,3,3,3);

y luego puedes elegir un elemento aleatorio de esta matriz en su lugar.

(Agregar). Usando las probabilidades del ejemplo en el comentario de kiruwka:

int[] numsToGenerate = new int[] { 1, 2, 3, 4, 5 };
double[] discreteProbabilities = new double[] { 0.1, 0.25, 0.3, 0.25, 0.1 };

el multiplicador más pequeño que lleva a enteros enteros es 20, lo que te da

2, 5, 6, 5, 2

y entonces la duración de numsToGenerate sería 20, con los siguientes valores:

1 1
2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4
5 5

La distribución es exactamente la misma: la probabilidad de ''1'', por ejemplo, es ahora 2 de 20, todavía 0.1.

Esto se basa en sus probabilidades originales, todas sumando 1. Si no lo hacen, multiplique el total por este mismo factor (que también será la longitud de su matriz).

Answer 5

Si tiene problemas de rendimiento en lugar de buscar todos los n valores O (n)

podrías realizar una búsqueda binaria que cuesta O (log n)

Random r=new Random();
double[] weights=new double[]{0.1,0.1+0.2,0.1+0.2+0.5};
// end of init
double random=r.nextDouble();
// next perform the binary search in weights array

solo necesita acceder a log2 (pesos.length) en promedio si tiene muchos elementos de ponderaciones.

Answer 6

Su enfoque está bien para los números específicos que eligió, aunque podría reducir el almacenamiento utilizando una matriz de 10 en lugar de una matriz de 100. Sin embargo, este enfoque no se generaliza bien a un gran número de resultados o resultados con probabilidades tales como 1/e o 1/PI .

Una solución potencialmente mejor es usar una tabla de alias . El método de alias requiere O(n) para configurar la tabla de n resultados, pero luego es un tiempo constante para generar independientemente de cuántos resultados haya.

Answer 7

Usted ya escribió la implementación en su pregunta. ;)

final int ran = myRandom.nextInt(100);
if (ran > 50) { return 3; }
else if (ran > 20) { return 2; }
else { return 1; }

Puede acelerar esto para implementaciones más complejas calculando el resultado en una tabla de conmutación como esta:

t[0] = 1; t[1] = 1; // ... one for each possible result
return t[ran];

Pero esto solo debe usarse si se trata de un cuello de botella de rendimiento y se llama varios cientos de veces por segundo.