Java: entier aléatoire avec distribution non uniforme

Question

Comment puis-je créer un nombre entier aléatoire n en Java, entre 1 et k avec un "linéaire décroissant de distribution", c'est à dire 1 est le plus probable, 2 est moins probable, 3 moins susceptibles, ..., k moins susceptibles, et les probabilités de descendre de façon linéaire, comme ceci:

Je sais qu'il y a dosens de discussions sur ce sujet déjà, et je m'excuse pour faire un nouveau, mais je ne peux pas semblent être en mesure de créer ce que j'ai besoin d'eux. Je sais que l'utilisation d' import java.util.*;, le code

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

crée un entier aléatoire compris entre 1 et k, répartis de manière uniforme.

GÉNÉRALISATION: Tous les conseils pour la création d'un arbitrairement distribués entier, c'est à dire f(n)=some function, P(n)=f(n)/(f(1)+...+f(k))), serait également appréciée, par exemple: .

Answer 1

Cela devrait vous donner ce dont vous avez besoin:

 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;
}
 

En outre, voici une solution générale pour les fonctions POSITIVES (les fonctions négatives n'ont pas vraiment de sens) sur la plage allant de l'index de démarrage à l'index d'arrêt:

 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;
}
 

Remarque: Pour les fonctions qui peuvent renvoyer des valeurs négatives, une méthode pourrait être de prendre la valeur absolue de cette fonction et de l'appliquer à la solution ci-dessus pour chaque appel yourFunction.

Answer 2

Nous avons donc besoin de la suite de la distribution, de la moins probable plus probable:

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

etc.

Permet d'essayer de cartographie distribuées uniformément entier variable aléatoire à distribution:

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

etc.

De cette façon, si nous générons un aléatoire uniformément distribué entier de 1 à, disons, 15 dans ce cas, pour K = 5, nous avons juste besoin de comprendre le seau, il s'adapte à elle. La partie la plus délicate est de savoir comment le faire.

Notez que les nombres sur la droite sont les nombres triangulaires! Cela signifie que pour généré de façon aléatoire X de 1 de T_n, nous avons juste besoin de trouver N tels que T_(n-1) < X <= T_n. Heureusement, il existe une bien défini formule pour trouver la " triangulaire de la racine d'un nombre donné, que l'on peut utiliser comme base de notre cartographie à partir d'une distribution uniforme dans le seau:

// 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 devriez maintenant avoir la distribution spécifié.

Answer 3

Il y a beaucoup de façons de le faire, mais probablement la méthode la plus simple est juste de générer deux entiers aléatoires, entre 0 et k, appellent x, entre 0 et h, appellent y. Si y > mx + b (m et b choisi de manière appropriée...) alors k-x, le reste x.

Edit: en réponse aux commentaires jusqu'ici pour que je puisse avoir un peu plus d'espace.

Fondamentalement, ma solution exploits de symétrie dans l'original de votre distribution, où la p(x) est une fonction linéaire de la x. J'ai répondu avant votre modifier la généralisation, et cette solution ne fonctionne pas dans le cas général (car il n'existe pas de symétrie dans le cas général).

J'ai imaginé le problème comme ceci:

1. Vous avez deux triangles rectangles, chacun k x h, avec une commune de l'hypoténuse. La forme composite est un k x h rectangle.
2. Générer un point aléatoire qui tombe sur chaque point à l'intérieur du rectangle avec une probabilité égale.
3. La moitié du temps il va tomber dans un triangle, la moitié du temps dans l'autre.
4. Supposons que le point de chute dans le triangle inférieur.
   • Le triangle décrit la P. M. F., et la "hauteur" du triangle sur chaque valeur x décrit la probabilité que le point d'avoir un tel x-valeur. (N'oubliez pas que nous sommes seulement à faire avec des points dans le triangle inférieur.) Donc, par le rendement de la valeur x.
5. Supposons que le point de chute dans le triangle supérieur.
   • Inverser les coordonnées et traiter comme ci-dessus avec le triangle inférieur.

Vous aurez à prendre soin de l'arête cas aussi (je n'ai pas pris la peine). E. g. Je vois maintenant que votre distribution commence à 1 et non 0, il y a donc un tout-en-un, mais il est facilement résolu.

Answer 4

Il n'est pas nécessaire de simuler ce avec des tableaux et, si votre distribution est telle que vous pouvez calculer sa fonction de répartition cumulative (cdf). Ci-dessus, vous avez une fonction de distribution de probabilité (pdf). h est en fait déterminé, étant donné que l'aire sous la courbe doit être de 1. Pour des raisons de simplicité de mathématiques, permettez-moi aussi de supposer que vous êtes la cueillette d'un nombre dans [0,k).

Le pdf est ici f(x) = (2/k) * (1 - x/k), si je vous lis à droite. Le cdf est juste partie intégrante de la pdf. Ici, c'est F(x) = (2/k) * (x - x^2 / 2k). (Vous pouvez répéter cette logique pour toute fonction pdf si elle est intégrable.)

Ensuite, vous devez calculer l'inverse de la fonction de répartition la fonction, F^-1(x) et si je n'étais pas paresseux, je le ferais pour vous.

Mais la bonne nouvelle c'est que cela: une fois que vous avez F^-1(x), il vous suffit de l'appliquer à une valeur aléatoire de distribution uniforme dans [0,1] et d'appliquer la fonction de celle-ci. java.util.Aléatoire peut prévoir qu'avec un peu de soin. C'est votre échantillon aléatoire de la valeur de votre distribution.