Генератор псевдослучайных чисел - экспоненциальное распределение

Question

Я хотел бы сгенерировать некоторые псевдослучайные числа, и до сих пор я очень доволен функцией Random.Next(int min, int max) библиотеки .Net. В PRNG этого сорта предполагается используется Равномерное распределение , но я бы очень хотел сгенерировать некоторые числа, используя Экспоненциальное распределение .

Я программирую на C #, хотя я приму псевдокод или C ++, Java или тому подобное.

Какие-либо предложения / фрагменты кода / алгоритмы / мысли?

Answer 1

Поскольку у вас есть доступ к унифицированному генератору случайных чисел, генерировать случайное число, распределенное по другому распределению, CDF которого вы знаете, легко, используя метод инверсии .

Итак, сгенерируйте равномерное случайное число u в [0,1), затем вычислите x по:

x = log(1-u)/( & минус; & лямбда; )

где & лямбда; является параметром скорости экспоненциального распределения. Теперь x - это случайное число с экспоненциальным распределением. Обратите внимание, что log выше ln, натуральный логарифм.

Answer 2

Основная теорема выборки гласит, что если вы можете нормализовать, интегрировать и инвертировать желаемое распределение, вы свободны дома.

Если у вас есть желаемое распределение F(x), нормализовано на [a,b]. Вы вычисляете

C(y) = \int_a^y F(x) dx

инвертируйте, чтобы получить C^{-1}, равномерно бросьте z на [0,1) и найдите

x_i = C^{-1}(z_i)

, который будет иметь желаемое распределение.

---

В вашем случае: F(x) = ke^{-kx} и я буду считать, что вы хотите [0,infinity]. Мы получаем:

C(y) = 1 - e^{-ky}

, который является обратимым, чтобы дать

x = -1/k  ln(1 - z)

для z, выброшенного равномерно на [0,1).

---

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

Answer 3

Если вам нужны хорошие случайные числа, рассмотрите возможность подключения к подпрограммам gsl: http://www.gnu.org/software/gsl/. У них есть подпрограмма gsl_ran_exponential. Если вы хотите генерировать случайные числа, используя встроенный генератор с равномерным распределением на [0, 1) (например, u = Random.Next (0, N-1) / N, для некоторого большого N), тогда просто используйте:

-mu * log (1-u)

См. Randist / exponential.c в источнике gsl.

РЕДАКТИРОВАТЬ: просто для сравнения с некоторыми более поздними ответами - это эквивалентно с mu = 1 / лямбда. mu - это среднее значение распределения, также называемое параметром масштаба на странице википедии, с которым связан OP, а лямбда - параметр скорости.

Answer 4

Одно интересное свойство экспоненциального распределения: рассмотрим процесс прибытия с экспоненциальным временем взаимодействия. Возьмите любой период времени (t1, t2) и прибытия в этот период. Эти прибытия равномерно распределены между t1 и t2. (Шелдон Росс, Стохастические процессы).

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

Вы можете:

1) Создать 1001 U (0,1) случайных величин.

2) Упорядочить по порядку

3) Вычтите второе из первого, третье из второго, ... чтобы получить 1000 отличий.

4) Эти различия представляют собой экспоненциальные RV с распределением со средним значением = 1,0.

Думаю, менее эффективным, но средством для достижения той же цели.

Answer 5

Библиотека с открытым исходным кодом Uncommons Maths от Dan Dyer предоставляет генераторы случайных чисел, вероятностные распределения, комбинаторику и статистику для Java.

Среди других ценных классов, ExponentialGenerator по существу реализовал идею, объясненную @Alok Singhal. В его учебном блоге приведен фрагмент кода, имитирующий случайное событие, которое происходит в среднем 10 раз в минуту:

final long oneMinute = 60000;
Random rng = new MersenneTwisterRNG();

// Generate events at an average rate of 10 per minute.
ExponentialGenerator gen = new ExponentialGenerator(10, rng);
boolean running = true;
while (true)
{
    long interval = Math.round(gen.nextValue() * oneMinute);
    Thread.sleep(interval);

    // Fire event here.
}

Конечно, если вы предпочитаете единицу времени per second (вместо a minute здесь), вам просто нужно установить final long oneMinute = 1000.

Углубившись в исходный код метода nextValue() из ExponentialGenerator, вы найдете так называемую выборку обратного преобразования , описанную в Generating_exponential_variates [wiki ] :

public Double nextValue()
{
    double u;
    do
    {
        // Get a uniformly-distributed random double between
        // zero (inclusive) and 1 (exclusive)
        u = rng.nextDouble();
    } while (u == 0d); // Reject zero, u must be positive for this to work.
    return (-Math.log(u)) / rate.nextValue();
}  

P.S .: В последнее время я использую библиотеку Uncommons Maths. Спасибо Дэн Дайер.

Answer 6

Это то, что я использовал, когда столкнулся с похожими требованиями:

// sorry.. pseudocode, mine was in Tcl:

int weighted_random (int max) {
    float random_number = rand();
    return floor(max - ceil( max * random_number * random_number))
}

Конечно, это формула возведения в квадрат случайного числа, поэтому вы генерируете случайное число вдоль квадратичной кривой.

Answer 7

Если я понимаю вашу проблему, и вы можете принять конечное число PRNG, вы можете воспользоваться следующим подходом:

• Создать массив, в котором каждый элемент находится в вашем экспоненциальном распределении
• Генерирует PRNG, который является целочисленным индексом в массиве. Вернуть элемент в массиве с этим индексом.