42

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

在此处输入图像描述

我知道这个主题已经有几十个主题了，我很抱歉创建了一个新主题，但我似乎无法从它们中创建我需要的内容。我知道使用import java.util.*;，代码

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

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

GENERALIZATION：任何用于创建任意分布的整数的提示，即f(n)=some function, P(n)=f(n)/(f(1)+...+f(k)))，也将不胜感激，例如：

在此处输入图像描述.

4

11 回答 11

20

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

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

此外，这里是从 start index 到 stopIndex 范围内的正函数（负函数实际上没有意义）的一般解决方案：

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 调用。

于 2011-05-11T19:42:59.043 回答
7

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

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

等等

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

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

等等

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

注意右边的数字是三角数！这意味着对于随机生成X的 from1到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现在应该具有指定的分布。

于 2011-05-11T20:43:47.117 回答
6

有很多方法可以做到这一点，但最简单的可能就是生成 两个随机整数，一个在0and之间k，调用它x，一个在0and之间h，调用它y。If y > mx + b( mandb选择得当...) then k-x, else x。

编辑：在这里回复评论，这样我可以有更多的空间。

基本上我的解决方案利用了原始分布中的对称性，其中p(x)是 的线性函数x。我在您对泛化进行编辑之前做出了回应，并且此解决方案在一般情况下不起作用（因为在一般情况下没有这种对称性）。

我想象过这样的问题：

  1. 你有两个直角三角形，每个k x h都有一个共同的斜边。复合形状是k x h矩形。
  2. 生成一个随机点，该点以相等的概率落在矩形内的每个点上。
  3. 一半的时间它会落在一个三角形中，一半的时间会落在另一个三角形中。
  4. 假设该点落在下三角形中。
    • 三角形基本上描述了 PMF，三角形在每个 x 值上的“高度”描述了该点将具有这样的 x 值的概率。（请记住，我们只处理下三角形中的点。）所以通过产生 x 值。
  5. 假设该点落在上三角形中。
    • 反转坐标并像上面一样用下三角形处理它。

您还必须处理边缘情况（我没有打扰）。例如，我现在看到您的分布从 1 开始，而不是 0，所以那里有一个非一的，但它很容易修复。

于 2011-05-11T19:45:42.770 回答
6

让我也尝试另一个答案，受 rlibby 启发。这种特定分布也是从同一范围内均匀随机选择的两个值中较小的一个的分布。

于 2011-05-11T20:28:47.880 回答
4

如果您的分布是这样的，您可以计算其累积分布函数 (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 可以提供一些照顾。这是您从分布中随机抽取的值。

于 2011-05-11T20:08:15.760 回答
3

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

于 2011-05-11T21:39:03.620 回答
2

想到的第一个解决方案是使用阻塞阵列。每个索引将根据您希望它的“可能”程度指定一系列值。在这种情况下，您将为 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;
}

现在的问题只是找到一个随机数，然后将该数字映射到它的存储桶。只要您可以离散每个区间的宽度，您就可以对任何分布执行此操作。如果我在解释算法或其正确性时遗漏了什么，请告诉我。不用说，这需要优化。

于 2011-05-11T19:38:50.530 回答
2

像这样的东西......

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.
    }
}
于 2011-05-11T21:00:29.893 回答
2

累积分布函数适用于众数（最高加权概率）为 1x^2的三角分布，如此处[0,1]所示。

因此，将均匀分布（如 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
于 2017-02-25T00:34:42.687 回答
1

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

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;

二分查找的成本相当小，但不如直接查找效率高（对于小数组）

对于任意分布，您可以将 adouble[]用于累积分布并使用二进制搜索来查找值。

于 2011-05-11T19:46:51.990 回答
0

有很多方法可以生成具有自定义分布（也称为离散分布）的随机整数。选择取决于很多因素，包括可供选择的整数数量、分布的形状以及分布是否会随时间变化。

选择具有自定义权重函数的整数的最简单方法之一f(x)是拒绝抽样方法。以下假设 的最高可能f值为max。拒绝抽样的时间复杂度平均是恒定的，但很大程度上取决于分布的形状，并且最坏的情况是永远运行。k要使用拒绝采样在 [1, ] 中选择一个整数：

  1. i在 [1, k]中选择一个均匀的随机整数。
  2. 带着概率f(i)/max，回归i。否则，转到步骤 1。

其他算法的平均采样时间不太依赖于分布（通常是常数或对数），但通常需要您在设置步骤中预先计算权重并将它们存储在数据结构中。其中一些在平均使用的随机位数方面也很经济。这些算法包括别名方法、Fast Loaded Dice Roller、Knuth-Yao 算法、MVN 数据结构等。有关调查，请参阅我的“带替换的加权选择”部分。

于 2020-07-30T02:46:06.613 回答