Java：生成具有非均匀分布的随机整数

Question

我如何在Java中创建一个随机整数 n，介于1和k之间，并具有“线性下降分布”，即1最有可能出现，2不太可能，3更不可能，...，k最不可能出现，且概率呈线性下降，如下所示：

我知道这个话题已经有很多讨论了，很抱歉又开了一个新的主题，但是我似乎无法从它们中创建我所需的内容。我知道使用 import java.util.*; 这段代码。

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

创建一个介于1和k之间的随机整数，均匀分布。

推广：有没有关于创建任意分布整数的提示，例如 f(n)=some function，P(n)=f(n)/(f(1)+...+f(k))。如果有，也请分享一下，例如：

。

- Leo

---

这个回答解决了你的问题吗？装载骰子的数据结构？ - Peter O.

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

此外，这里是一个针对正函数（负函数没有意义）在起始索引到停止索引范围内的通用解决方案：

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调用的上述解决方案。

- Briguy37

---

你可以使用 randomMultiplier = maxSize * (maxSize + 1) /2;。 - Peter Lawrey

它有效，我在Mathematica中测试过了。谢谢。现在我只是在寻找最简单的解决方案。 - Leo

根据Peter的评论，编辑了通用解决方案并简化了原始解决方案。 - Briguy37

值得一提的是，这个算法被称为逆变换法。 - Adam Stelmaszczyk

Answer 2

所以我们需要以下分布，从最不可能到最可能：

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

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

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

等等，如果我们在这种情况下为K = 5生成一个从1到15的均匀分布的随机整数，我们只需要找出它适合哪个桶。关键是如何做到这一点。

请注意，右侧的数字是三角形数！这意味着对于从1到T_n随机生成的X，我们只需要找到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现在应该具有指定的分布。

- Greg Case

---

感谢提到“三角形根”。 - tomasbedrich

Answer 3

有许多方法可以做到这一点，但可能最简单的方法就是生成两个随机整数，一个在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.假设该点落在较低的三角形中。 - 三角形基本上描述了P.M.F.，并且每个x值上的三角形“高度”描述了该点具有该x值的概率。（请记住，我们只处理下三角形中的点。）因此通过产生x值。 5.假设该点落在较高的三角形中。 - 反转坐标并像上面处理较低的三角形一样处理它。

你还需要注意边缘情况（我没有费心）。例如，我现在看到您的分布从1开始而不是0，因此其中有一个差错，但很容易修复。

- rlibby

---

@rlibby：我非常感兴趣最简单的解决方案。您是否可以详细说明一下？ - Leo

至于更一般的问题：这里 f = mx + b，并且这种方法对于表示分布的任何 f 都可以直接使用 - 我想是这样的。对吗？ - Robin Green

@Robin Green, @rlibby：这里到底是怎么回事？为什么是then k-x, else x？ - Leo

@rlibby：什么？我不这么认为，你的分发产生了其他结果。 - Jason S

@rlibby：我应该如何生成一个介于0和h之间的整数y，因为h=2/k<1？这里我应该使用双精度浮点数吗？ - Leo

Answer 4

让我再试着给出另一个答案，这个答案灵感来自 rlibby。这个特定的分布也是从同一范围内均匀随机选择两个值中较小值的分布。

- Sean Owen

Answer 5

如果你的分布使你能够计算其累积分布函数（cdf），那么就没有必要使用数组等来模拟。上面给出了概率分布函数（pdf）。h是实际确定的，因为曲线下的面积必须为1。为简化数学，让我假设你选择的数字在[0，k)中。

如果我理解正确，这里的pdf是f(x) = (2/k) * (1 - x/k)。cdf只是pdf的积分。在这里，即F(x) = (2/k) * (x - x^2 / 2k)。(如果它是可积的话，你可以对任何pdf函数重复这个逻辑。)

然后你需要计算cdf函数的反函数F^-1(x)，如果我不懒的话，我会为你做的。

但好消息是：一旦你有了F^-1(x)，你所要做的就是将其应用于在[0，1]中均匀分布的随机值分布，并将其应用于该函数中。java.util.Random可以提供一定的帮助。这是你从分布中随机抽样的值。

- Sean Owen

Answer 6

这被称为三角分布，尽管你的情况是一个退化的例子，其中众数等于最小值。 给定一个均匀分布的(0,1)变量，维基百科有关于如何创建三角分布的方程式。

- user79758

---

谢谢。对于那些不理解所涉及的数学的人，我已经发布了一个更详细的答案，基于链接的信息。 - Patrick Parker

Answer 7

第一个解决方案是使用阻塞数组。每个索引将指定一个值范围，具体取决于您希望它有多“可能”。在这种情况下，您将为1使用更广泛的范围，为2使用较小的范围，以此类推，直到达到k的一个小值（假设为1）。

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

现在的问题就是找到一个随机数，然后将该数映射到其桶中。 只要你能离散化每个区间的宽度，就可以对任何分布进行此操作。 如果我在解释算法或其正确性方面漏掉了什么，请让我知道。不用说，这需要进行优化。

- R.K

---

这里不需要数组。你所需要的就是执行计算，就像你描述的那样将随机数放入桶中。 - Robin Green

是的，那“应该”是这样做的。谢谢。 - R.K

是的，这是一个非常直观的解决方案。然而，我认为Java中已经有一个内置函数可以做到这一点。让我感到困惑的是，为什么Java中几乎所有的东西都必须从头开始创建。谢谢 :)。 - Leo

Answer 8

Something like this....

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

- Jason S

Answer 9

累积分布函数是对于一个三角形分布而言[0,1]，其众数为1，函数形式为x^2，如此处所示：here。

因此，我们只需要将均匀分布（例如Java中的Random::nextDouble）转换成一个方便的三角形分布，使之重心朝向1，就可以：仅需取平方根Math.sqrt(rand.nextDouble())，然后乘以任意所需范围即可。

对于您的例子：

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 

- Patrick Parker

Answer 10

最简单的方法是生成一个包含所有可能权重值的列表或数组。

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)];

这个方法适用于相对较小的k值，即k < 1000。;)

对于更大的数字，您可以使用桶排序的方法。

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;

二分查找的成本相当小，但对于小数组而言，不如直接查找高效。

---

对于任意分布，您可以使用 double[] 来表示累积分布，并使用二分查找来查找值。

- Peter Lawrey