Java:具有非均匀分布的随机整数

Question

如何n在Java中创建一个随机整数,在"线性递减分布" 之间1和之间k,即1最有可能,2不太可能,3不太可能,......,k最不可能,并且概率线性下降,如下所示:

我知道已经有关于这个主题的线程,我为制作一个新主题道歉,但我似乎无法从他们那里创造我需要的东西.我知道使用import java.util.*;代码

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

在1and 之间创建一个随机整数k,均匀分布.

GENERALIZATION:任何提示创建任意分布的整数,即f(n)=some function,P(n)=f(n)/(f(1)+...+f(k))),也将受到赞赏,例如: .

Answer 1

这应该给你你需要的东西:

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

此外,这是从开始索引到stopIndex的范围内POSITIVE函数(负函数实际上没有意义)的一般解决方案:

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

注意:对于可能返回负值的函数,一种方法可以是获取该函数的绝对值,并将其应用于每个yourFunction调用的上述解决方案.

Answer 2

所以我们需要以下分布,最不可能的是:

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

等等

让我们尝试将均匀分布的整数随机变量映射到该分布:

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

等等

这样,如果我们生成一个均匀分布的随机整数,从1到15,在这种情况下为15 K = 5,我们只需要找出它适合它的桶.棘手的部分是如何做到这一点.

请注意,右边的数字是三角形数字!这意味着,对于随机生成的X,从1到T_n,我们只需要找到N这样T_(n-1) < X <= T_n.幸运的是,有一个明确定义的公式可以找到给定数字的"三角形根",我们可以将其用作从均匀分布到存储区的映射的核心:

// 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 现在应该具有指定的分布.

Answer 3

有很多方法可以做到这一点,但可能是最简单就是生成 2个随机整数,一个之间0和k,称它为x之间一个0和h,把它y.如果y > mx + b(m并b适当选择......)那么 k-x,否则x.

编辑:回复此处的评论,以便我可以有更多的空间.

基本上我的解决方案利用原始分布中的对称性,其中p(x)是线性函数x.我在编辑之前回复了关于泛化的问题,并且这个解决方案在一般情况下不起作用(因为在一般情况下没有这种对称性).

我想象这样的问题:

1. 你有两个直角三角形,每个k x h都有一个共同的斜边.复合形状是k x h矩形.
2. 生成一个随机点,该点随机概率落在矩形内的每个点上.
3. 一半时间会落在一个三角形中,一半时间落在另一个三角形中.
4. 假设该点落在下三角形中.
   • 三角形基本上描述了PMF,并且每个x值上三角形的"高度"描述了该点具有这样的x值的概率.(请记住,我们只处理下三角形中的点.)因此,通过得到x值.
5. 假设该点落在上三角形中.
   • 反转坐标并使用下三角形处理它.

你也必须照顾边缘情况(我没有打扰).例如,我现在看到你的发行从1开始,而不是0,所以那里有一个一个一个,但它很容易修复.

Answer 4

让我尝试另一个答案,受到rlibby的启发.该特定分布也是从相同范围均匀地和随机地选择的两个值中的较小值的分布.