probabilidad - Java: entero aleatorio con distribución no uniforme

metodo random java

Question

¿Cómo puedo crear un entero aleatorio n en Java, entre 1 k con una "distribución lineal descendente", es decir, 1 es más probable, 2 es menos probable, 3 menos probable, ..., k menos probable, y las probabilidades descienden linealmente, así:

Sé que ya hay muchos hilos sobre este tema, y ​​me disculpo por hacer uno nuevo, pero parece que no puedo crear lo que necesito de ellos. Sé que al usar import java.util.*; , el código

Random r=new Random();
int n=r.nextInt(k)+1;

crea un entero aleatorio entre 1 k , distribuido uniformemente.

GENERALIZACIÓN: Cualquier sugerencia para crear un entero arbitrariamente distribuido, es decir, f(n)=some function , P(n)=f(n)/(f(1)+...+f(k)) ), también sería apreciado, por ejemplo: .

Answer 1

Algo como esto....

class DiscreteDistribution
{
    // cumulative distribution
    final private double[] cdf;
    final private int k;

    public DiscreteDistribution(Function<Integer, Double> pdf, int k)
    {
        this.k = k;
        this.cdf = new double[k];
        double S = 0;
        for (int i = 0; i < k; ++i)
        {
            double p = pdf.apply(i+1);         
            S += p;
            this.cdf[i] = S;
        }
        for (int i = 0; i < k; ++i)
        {
            this.cdf[i] /= S;
        }
    }
    /**
     * transform a cumulative distribution between 0 (inclusive) and 1 (exclusive)
     * to an integer between 1 and k.
     */
    public int transform(double q)
    {
        // exercise for the reader:
        // binary search on cdf for the lowest index i where q < cdf[i]
        // return this number + 1 (to get into a 1-based index.
        // If q >= 1, return k.
    }
}

Answer 2

Déjame probar otra respuesta también, inspirada en rlibby. Esta distribución particular también es la distribución del menor de dos valores elegidos uniformemente y al azar del mismo rango.

Answer 3

Entonces, necesitamos la siguiente distribución, de la menos probable a la más probable:

*
**
***
****
*****

etc.

Tratemos de mapear una variable aleatoria entera uniformemente distribuida a esa distribución:

1
2  3
4  5  6
7  8  9  10
11 12 13 14 15

etc.

De esta forma, si generamos un entero aleatorio distribuido uniformemente de 1 a, por ejemplo, 15 en este caso para K = 5 , solo tenemos que averiguar qué cubo le queda. La parte difícil es cómo hacer esto.

Tenga en cuenta que los números a la derecha son los números triangulares. Esto significa que para X generado de forma aleatoria de 1 a T_n , solo necesitamos encontrar N tal que T_(n-1) < X <= T_n . Afortunadamente, existe una fórmula bien definida para encontrar la ''raíz triangular'' de un número dado , que podemos usar como núcleo de nuestro mapeo desde la distribución uniforme hasta el cubo:

// Assume k is given, via parameter or otherwise
int k;

// Assume also that r has already been initialized as a valid Random instance
Random r = new Random();

// First, generate a number from 1 to T_k
int triangularK = k * (k + 1) / 2;

int x = r.nextInt(triangularK) + 1;

// Next, figure out which bucket x fits into, bounded by
// triangular numbers by taking the triangular root    
// We''re dealing strictly with positive integers, so we can
// safely ignore the - part of the +/- in the triangular root equation
double triangularRoot = (Math.sqrt(8 * x + 1) - 1) / 2;

int bucket = (int) Math.ceil(triangularRoot);

// Buckets start at 1 as the least likely; we want k to be the least likely
int n = k - bucket + 1;

n ahora debería tener la distribución especificada.

Answer 4

Esto debería darle lo que necesita:

public static int getLinnearRandomNumber(int maxSize){
    //Get a linearly multiplied random number
    int randomMultiplier = maxSize * (maxSize + 1) / 2;
    Random r=new Random();
    int randomInt = r.nextInt(randomMultiplier);

    //Linearly iterate through the possible values to find the correct one
    int linearRandomNumber = 0;
    for(int i=maxSize; randomInt >= 0; i--){
        randomInt -= i;
        linearRandomNumber++;
    }

    return linearRandomNumber;
}

Además, aquí hay una solución general para las funciones POSITIVAS (las funciones negativas no tienen sentido) a lo largo del rango desde el índice de inicio hasta el índice de parada:

public static int getYourPositiveFunctionRandomNumber(int startIndex, int stopIndex) {
    //Generate a random number whose value ranges from 0.0 to the sum of the values of yourFunction for all the possible integer return values from startIndex to stopIndex.
    double randomMultiplier = 0;
    for (int i = startIndex; i <= stopIndex; i++) {
        randomMultiplier += yourFunction(i);//yourFunction(startIndex) + yourFunction(startIndex + 1) + .. yourFunction(stopIndex -1) + yourFunction(stopIndex)
    }
    Random r = new Random();
    double randomDouble = r.nextDouble() * randomMultiplier;

    //For each possible integer return value, subtract yourFunction value for that possible return value till you get below 0.  Once you get below 0, return the current value.  
    int yourFunctionRandomNumber = startIndex;
    randomDouble = randomDouble - yourFunction(yourFunctionRandomNumber);
    while (randomDouble >= 0) {
        yourFunctionRandomNumber++;
        randomDouble = randomDouble - yourFunction(yourFunctionRandomNumber);
    }

    return yourFunctionRandomNumber;
}

Nota: Para las funciones que pueden devolver valores negativos, un método podría ser tomar el valor absoluto de esa función y aplicarla a la solución anterior para cada llamada a su función.

Answer 5

Hay muchas formas de hacerlo, pero probablemente la más sencilla sea generar dos enteros aleatorios, uno entre 0 k , llamarlo x , uno entre 0 y h , llamarlo y . Si y > mx + b ( m y b elegidos apropiadamente ...) entonces kx , else x .

Editar : responde a los comentarios aquí para que pueda tener un poco más de espacio.

Básicamente, mi solución explota la simetría en su distribución original, donde p(x) es una función lineal de x . Respondí antes de su edición acerca de la generalización, y esta solución no funciona en el caso general (porque no existe tal simetría en el caso general).

Imaginé el problema así:

1. Tienes dos triángulos rectángulos, cada kxh , con una hipotenusa común. La forma compuesta es un rectángulo kxh .
2. Genera un punto aleatorio que cae en cada punto dentro del rectángulo con la misma probabilidad.
3. La mitad del tiempo caerá en un triángulo, la mitad del tiempo en el otro.
4. Supongamos que el punto cae en el triángulo inferior.
   • El triángulo básicamente describe el PMF, y la "altura" del triángulo sobre cada valor x describe la probabilidad de que el punto tenga dicho valor x. (Recuerde que solo estamos tratando con puntos en el triángulo inferior). Entonces, ceda el valor x.
5. Supongamos que el punto cae en el triángulo superior.
   • Invierta las coordenadas y manipúlelas como se muestra arriba con el triángulo inferior.

También tendrás que ocuparte de los casos extremos (no me molesté). Por ejemplo, ahora veo que su distribución comienza en 1, no en 0, por lo que hay una lista por ahí, pero se soluciona fácilmente.

Answer 6

La Función de Distribución Acumulativa es x^2 para una distribución triangular [0,1] con modo (probabilidad ponderada más alta) de 1, como se muestra here .

Por lo tanto, todo lo que necesitamos hacer para transformar una distribución uniforme (como Random::nextDouble ) en una distribución triangular conveniente ponderada hacia 1 es: simplemente tome la raíz cuadrada Math.sqrt(rand.nextDouble()) , que puede entonces multiplicado por cualquier rango deseado.

Para tu ejemplo:

int a = 1; // lower bound, inclusive
int b = k; // upper bound, exclusive
double weightedRand = Math.sqrt(rand.nextDouble()); // use triangular distribution
weightedRand = 1.0 - weightedRand; // invert the distribution (greater density at bottom)
int result = (int) Math.floor((b-a) * weightedRand);
result += a; // offset by lower bound
if(result >= b) result = a; // handle the edge case 

Answer 7

La primera solución que se me viene a la mente es usar una matriz bloqueada. Cada índice especificaría un rango de valores dependiendo de qué tan "probable" quieras que sea. En este caso, usaría un rango más amplio para 1, menos ancho para 2, y así sucesivamente hasta que alcance un valor pequeño (digamos 1) para k.

int [] indexBound = new int[k];
int prevBound =0;
for(int i=0;i<k;i++){
    indexBound[i] = prevBound+prob(i);
    prevBound=indexBound[i];
}
int r = new Random().nextInt(prevBound);
for(int i=0;i<k;i++){
    if(r > indexBound[i];
        return i;
}

Ahora el problema es encontrar un número aleatorio y luego asignar ese número a su cubo. puede hacer esto para cualquier distribución siempre que pueda discretizar el ancho de cada intervalo. Avíseme si me falta algo, ya sea para explicar el algoritmo o su corrección. No hace falta decir que esto debe ser optimizado.

Answer 8

Lo más simple es generar una lista o conjunto de todos los valores posibles en sus pesos.

int k = /* possible values */
int[] results = new int[k*(k+1)/2];
for(int i=1,r=0;i<=k;i++)
   for(int j=0;j<=k-i;j++)
       results[r++] = i;
// k=4 => { 1,1,1,1,2,2,2,3,3,4 }

// to get a value with a given distribution.
int n = results[random.nextInt(results.length)];

Esto funciona mejor para k valores relativamente pequeños. k <1000.;)

Para números más grandes puedes usar un enfoque de cubo

int k = 
int[] buckets = new int[k+1];
for(int i=1;i<k;i++)
   buckets[i] = buckets[i-1] + k - i + 1;

int r = random.nextInt(buckets[buckets.length-1]);
int n = Arrays.binarySearch(buckets, r);
n = n < 0 ? -n : n + 1;

El costo de la búsqueda binaria es bastante pequeño pero no tan eficiente como una búsqueda directa (para una matriz pequeña)

Para una distribución arbitraria puede usar un double[] para la distribución cumulativa y usar una búsqueda binaria para encontrar el valor.

Answer 9

No es necesario simular esto con matrices y demás, si su distribución es tal que puede calcular su función de distribución acumulativa (cdf). Arriba tienes una función de distribución de probabilidad (pdf). h en realidad está determinado, ya que el área bajo la curva debe ser 1. Por simplicidad matemática, déjame asumir que estás eligiendo un número en [0, k).

El pdf aquí es f (x) = (2 / k) * (1 - x / k), si te leo bien. El cdf es solo una parte integral del pdf. Aquí, eso es F (x) = (2 / k) * (x - x ^ 2 / 2k). (Puede repetir esta lógica para cualquier función de PDF si es integrable).

Entonces necesitas calcular el inverso de la función cdf, F ^ -1 (x) y si no fuera flojo, lo haría por ti.

Pero la buena noticia es esta: una vez que tienes F ^ -1 (x), todo lo que haces es aplicarlo a una distribución de valor aleatorio uniformemente en [0,1] y aplicarle la función. java.util.Random puede proporcionarlo con algo de cuidado. Ese es el valor muestreado al azar de su distribución.

Answer 10

Esto se llama distribución triangular , aunque el suyo es un caso degenerado con el modo igual al valor mínimo. Wikipedia tiene ecuaciones sobre cómo crear una dada una variable uniformemente distribuida (0,1).