Как получить случайные числа с неправильным генератором

Question

Вопрос: Предположим, у вас есть генератор случайных чисел randn (), который возвращает равномерно распределенное случайное число от 0 до n-1. Для любого числа m напишите генератор случайных чисел, который возвращает равномерно распределенное случайное число от 0 до m-1.

Мой ответ:

-(int)randm() {
    int k=1;
    while (k*n < m) {
        ++k;
    }
    int x = 0;
    for (int i=0; i<k; ++i) {
        x += randn();
    }
    if (x < m) {
        return x;
    } else {
        return randm();
    }
}

Это правильно?

Answer 1

Вы близки, но проблема с вашим ответом в том, что существует несколько способов записать число в виде суммы двух других чисел.

Если m<n, то это работает, потому что числа 0,1,...,m-1 появляются с равной вероятностью, и алгоритм почти наверняка завершается.

Этот ответ вообще не работает, потому что существует более одного способа записать число в виде суммы двух других чисел. Например, есть только один способ получить 0, но есть много способов получить m/2, поэтому вероятности не будут равны.

Пример : n = 2 и m=3

0 = 0+0
1 = 1+0 or 0+1
2 = 1+1

так что распределение вероятностей по вашему методу

P(0)=1/4
P(1)=1/2
P(2)=1/4

который не является равномерным.

---

Чтобы исправить это, вы можете использовать уникальную факторизацию. Напишите m в базе n, отслеживая наибольший необходимый показатель, скажем, e. Затем найдите наибольшее значение, кратное m, которое меньше n^e, назовите его k. Наконец, сгенерируйте e чисел с помощью randn(), возьмите их за базовое n расширение некоторого числа x, если x < k*m, верните x, в противном случае попробуйте снова.

Если предположить, что m < n^2, то

int randm() {

    // find largest power of n needed to write m in base n
    int e=0;
    while (m > n^e) {
        ++e;
    }

    // find largest multiple of m less than n^e
    int k=1;
    while (k*m < n^2) {
        ++k
    }
    --k; // we went one too far

    while (1) {
        // generate a random number in base n
        int x = 0;
        for (int i=0; i<e; ++i) {
            x = x*n + randn(); 
        }
        // if x isn't too large, return it x modulo m
        if (x < m*k) 
            return (x % m);
    }
}

Answer 2

Это не правильно.

Вы добавляете однородные случайные числа, которые не дают равномерно случайный результат. Скажите n = 2 и m = 3, тогда возможные значения для x равны 0 + 0, 0 + 1, 1 + 0, 1 + 1. Таким образом, вы в два раза чаще получаете 1, чем 0 или 2.

Что вам нужно сделать, это написать m в базе n, а затем сгенерировать «цифры» представления base-n случайного числа. Когда у вас есть полный номер, вы должны проверить, если он меньше, чем m. Если это так, то все готово. Если это не так, то вам нужно начать все сначала.

Answer 3

Сумма двух генераторов случайных чисел не сгенерирована равномерно.Например, сумма двух кубиков, скорее всего, будет 7, а не 12, потому что, чтобы получить 12, вам нужно бросить две шестерки, тогда как вы можете получить 7 как 1 + 6 или 6 + 1 или 2 + 5 или 5 + 2 или...

Предполагая, что randn () возвращает целое число от 0 до n - 1, n * randn () + randn () равномерно распределяется между 0 и n * n - 1, поэтому вы можете увеличить егоспектр.Если randn () возвращает целое число от 0 до k * m + j - 1, вызывайте его несколько раз, пока не получите число <= k * m - 1, а затем разделите результат на k, чтобы получить число, равномерно распределенное между 0и м -1. </p>

Answer 4

Если предположить, что n и m являются положительными целыми числами, не будет ли работать стандартный алгоритм масштабирования?

return (int)((float)randn() * m / n);