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

我怎样才能创build一个随机的整数n在Java之间， 1和k之间的“线性递减分布”，即1是最有可能的， 2是不太可能的， 3不太可能，…， k最不可能的，并且概率下降线性，如下所示：

我知道在这个话题上已经有了很多线索，而且我很抱歉做了一个新的话题，但是我似乎无法从他们那里创造我所需要的。 我知道使用import java.util.*; ， 代码

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

创build1和k之间的随机整数，均匀分布。

概括：任何build立任意分布整数的提示，也就是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; } 

另外，下面是从start索引到stopIndex范围内的POSITIVE函数的一般解决scheme（负函数没有意义）：

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

注意：对于可能返回负值的函数，一种方法可能是获取该函数的绝对值，并将其应用于上述每个函数调用的解决scheme。

Answer 2

所以我们需要从最不可能到最可能的以下分配：

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

等等

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

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

等等

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

请注意，右边的数字是三angular形数字！ 这意味着对于从1到T_n随机生成的X ，我们只需要findN使得T_(n-1) < X <= T_n 。 幸运的是，有一个明确定义的公式来查找给定数字的“三angular根” ，我们可以用它作为我们从均匀分布到桶的映射的核心：

 // 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

有很多方法可以做到这一点，但最简单的方法是生成两个随机整数，一个介于0和k之间，称之为x ，一个介于0和h之间，称之为y 。 如果y > mx + b （ m和b恰当地select…），那么kx ，否则x 。

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

基本上我的解决scheme利用你的原始分布的对称性，其中p(x)是p(x)的线性函数。 我在编辑之前回应了泛化，而这个解决scheme在一般情况下不起作用（因为在一般情况下没有这种对称性）。

我想像这样的问题：

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

你也必须照顾边缘案件（我没有打扰）。 比如我现在看到你的分配从1开始，而不是从0开始，所以这里有一个off-by-one，但是很容易修复。

Answer 4

让我尝试另外一个答案，灵感来自rlibby。 这个特定的分布也是从相同的范围中均匀select的两个值中较小的一个的分布。

Answer 5

如果你的分布是这样的，你可以计算它的累积分布函数（cdf），那么不需要用数组来模拟这个。 上面有一个概率分布函数（pdf）。 h实际上是确定的，因为曲线下的面积必须是1.为了math的简单，让我也假设你正在select一个数字[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可以提供一些照顾。 这是你的分布随机抽样值。

Answer 6

这被称为三angular形分布 ，尽pipe你是一个退化的情况下，模式等于最小值。 维基百科有如何创build一个给定一个均匀分布（0,1）variables的方程。

Answer 7

想到的第一个解决scheme是使用阻塞数组。 每个索引都会根据您希望的“可能”的大小来指定一个值的范围。 在这种情况下，你将使用更宽的范围1，更宽的2，等等，直到你达到一个小值（让我们说1）为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; } 

现在问题是find一个随机数字，然后将该数字映射到它的存储桶。 你可以做任何分配，只要你可以离散每个区间的宽度。 让我知道如果我在解释algorithm或其正确性丢失的东西。 不用说，这需要优化。

Answer 8

像这样的东西….

 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 9

累积分布函数对于模式（加权概率最高）为1的三angular形分布[0,1]为x^2 ，如此处所示。

因此，我们所需要做的就是将均匀分布（例如Java的Random::nextDouble ）转换为方便的加权为1的三angular形分布：简单地取平方根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((ba) * weightedRand); result += a; // offset by lower bound if(result >= b) result = a; // handle the edge case 

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<=ki;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; 

二进制search的成本相当小，但不如直接查找（对于小型arrays）

---

对于任意分布，可以使用double[]作为累积分布，并使用二分search来查找值。