Java: случайное целое число с неравномерным распределением

Question

Как я могу создать случайное целое число n в Java, между 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))), также приветствуются, например: .

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:

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, в данном случае для 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

Есть много способов сделать это, но, вероятно, самый простой - просто сгенерировать два случайных целых числа, одно от 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, так что там есть одно за другим, но это легко исправить.

Answer 4

Позвольте мне попробовать другой ответ, вдохновленный Rlibby.Это конкретное распределение также является распределением меньшего двух значений, выбранных равномерно и случайно из одного и того же диапазона.

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] и применяете к нему функцию. Случайный может предоставить это с некоторой осторожностью. Это ваше случайное значение из вашего распределения.

Answer 6

Это называется треугольным распределением , хотя у вас вырожденный случай с модой, равной минимальному значению. В Википедии есть уравнения для того, как создать единицу с равномерно распределенной (0,1) переменной.

Answer 7

Функция кумулятивного распределения равна x^2 для треугольного распределения [0,1] с режимом (наибольшая взвешенная вероятность) 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 

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, менее широкий для 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;
}

Теперь проблема в том, чтобы просто найти случайное число и затем сопоставить это число с его корзиной. Вы можете сделать это для любого распределения при условии, что вы можете дискретизировать ширину каждого интервала. Дайте мне знать, если я что-то упустил в объяснении алгоритма или его правильности. Само собой разумеется, это должно быть оптимизировано.

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.ie.k <1000.;) </p>

Для больших чисел вы можете использовать групповой подход

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[] для накопительного распределения и использовать двоичный поиск, чтобы найти значение.