Случайное число с вероятностями

Question

Мне интересно, что было бы лучшим способом (например, в Java) генерировать случайные числа в определенном диапазоне, где каждый номер имеет определенную вероятность или нет?

например.

Генерация случайных чисел внутри [1, 3] со следующими вероятностями:

P (1) = 0,2
P (2) = 0,3
Р (3) = 0,5

---

Сейчас я рассматриваю подход генерировать случайное число в пределах [0; 100] и выполните следующие действия:

Если она находится в пределах [0; 20] -> Я получил мое случайное число 1.
Если она находится в пределах [21, 50] -> Я получил случайное число 2.
Если она находится в пределах [51, 100] -> Я получил мое случайное число 3.

Что бы вы сказали, ?

Answer 1

У вас уже неплохой путь и хорошо работает с любым диапазоном.

Простое мышление: еще одна возможность - избавиться от фракций, умножив их на постоянный множитель, а затем построить массив с размером этого множителя. Умножение на 10 вы получите

P(1) = 2 
P(2) = 3 
P(3) = 5 

Затем создается массив с обратными значениями - '1' переходит в элементы 1 и 2, '2' на 3 до 6, и так далее:

P = (1,1, 2,2,2, 3,3,3,3,3);

, а затем вы можете выбрать случайный элемент из этого массива.

---

(Добавить.) Используя вероятности из примера в комментарии kiruwka по:

int[] numsToGenerate   = new int[] { 1, 2, 3, 4, 5 }; 
double[] discreteProbabilities = new double[] { 0.1, 0.25, 0.3, 0.25, 0.1 }; 

наименьший множитель, который приводит ко всем-целых чисел 20, что дает вам

2, 5, 6, 5, 2 

и поэтому длина numsToGenerate будет 20, со следующими значениями:

1 1 
2 2 2 2 2 
3 3 3 3 3 3 
4 4 4 4 4 
5 5 

распределение является точно то же самое: шанс «1», например, теперь 2 из 20 - еще 0,1.

Это основано на ваших первоначальных вероятностях, суммирующих до 1. Если они этого не делают, умножьте общее на тот же коэффициент (который также будет вашей длиной массива).

Answer 2

Вы уже писали реализацию в своем вопросе. ;)

final int ran = myRandom.nextInt(100); 
if (ran > 50) { return 3; } 
else if (ran > 20) { return 2; } 
else { return 1; } 

Вы можете ускорить этот процесс для более сложных реализаций путем за вычислением результата на столе переключателя, как это:

t[0] = 1; t[1] = 1; // ... one for each possible result 
return t[ran]; 

Но это должно быть использовано только если это является узким местом производительности и вызывал несколько сотен раз в секунду.

Answer 3

Если у вас есть проблемы с производительностью, вместо поиска всех значений п О (п)

можно выполнить бинарный поиск, который стоит O (журнал N)

Random r=new Random();  
double[] weights=new double[]{0.1,0.1+0.2,0.1+0.2+0.5}; 
// end of init 
double random=r.nextDouble(); 
// next perform the binary search in weights array 

вам необходимо получить доступ log2 только (weights.length) в среднем, если у вас много элементов веса.

Answer 4

Некоторое время назад я написал вспомогательный класс для решения этой проблемы. Исходный код должен показать концепцию достаточно ясно:

public class DistributedRandomNumberGenerator { 

    private Map<Integer, Double> distribution; 
    private double distSum; 

    public DistributedRandomNumberGenerator() { 
     distribution = new HashMap<>(); 
    } 

    public void addNumber(int value, double distribution) { 
     if (this.distribution.get(value) != null) { 
      distSum -= this.distribution.get(value); 
     } 
     this.distribution.put(value, distribution); 
     distSum += distribution; 
    } 

    public int getDistributedRandomNumber() { 
     double rand = Math.random(); 
     double ratio = 1.0f/distSum; 
     double tempDist = 0; 
     for (Integer i : distribution.keySet()) { 
      tempDist += distribution.get(i); 
      if (rand/ratio <= tempDist) { 
       return i; 
      } 
     } 
     return 0; 
    } 

} 

Использование класса выглядит следующим образом: водитель

DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator(); 
drng.addNumber(1, 0.3d); // Adds the numerical value 1 with a probability of 0.3 (30%) 
// [...] Add more values 

int random = drng.getDistributedRandomNumber(); // Generate a random number 

Тест для проверки функциональных возможностей:

public static void main(String[] args) { 
     DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator(); 
     drng.addNumber(1, 0.2d); 
     drng.addNumber(2, 0.3d); 
     drng.addNumber(3, 0.5d); 

     int testCount = 1000000; 

     HashMap<Integer, Double> test = new HashMap<>(); 

     for (int i = 0; i < testCount; i++) { 
      int random = drng.getDistributedRandomNumber(); 
      test.put(random, (test.get(random) == null) ? (1d/testCount) : test.get(random) + 1d/testCount); 
     } 

     System.out.println(test.toString()); 
    } 

Пример вывода для этого испытательный водитель:

{1=0.20019100000017953, 2=0.2999349999988933, 3=0.4998739999935438} 

Answer 5

Ваш подход подходит для конкретных чисел, которые вы выбрали, хотя вы можете уменьшить объем хранилища, используя массив из 10 вместо массива из 100. Однако этот подход не очень хорошо обобщается на большое количество результатов или результатов с вероятностями, такими как как 1/e или 1/PI.

Возможным решением является использование alias table. Метод псевдонима принимает O(n) работу по настройке таблицы для результатов n, но тогда это постоянное время для создания независимо от того, сколько результатов есть.