Как реализовать Random (a, b) только с Random (0,1)?

Возможный дубликат:
как получить равномерную случайность между a, b известной унифицированной случайной функцией RANDOM (0,1)

В книге "Введение в алгоритмы" есть акциз:

Опишите реализацию процедуры Random (a, b), которая вызывает только вызовы Random (0,1). Каково ожидаемое время работы вашей процедуры, как функция a и b? Вероятность результата Random (a, b) должна быть чистой равномерно распределенной, как Random (0,1)

Для случайной функции результаты представляют собой целые числа между a и b, включительно. Например, Random (0,1) генерирует либо 0, либо 1; Случайное (a, b) порождает a, a + 1, a + 2,..., b

Мое решение таково:

for i = 1 to b-a
    r = a + Random(0,1)
return r

время работы T = b-a

Это правильно? Являются ли результаты моих решений равномерно распределенными?

Спасибо

Что делать, если мое новое решение выглядит так:

r = a
for i = 1 to b - a //including b-a
    r += Random(0,1)
return r

Если это неверно, почему r + = Random (0,1) делает r неравномерно распределенным?

Ответ 1

Другие объяснили, почему ваше решение не работает. Здесь правильное решение:

1) Найдите наименьшее число p, такое, что 2^p > b-a.

2) Выполните следующий алгоритм:

r=0
for i = 1 to p
    r = 2*r + Random(0,1)

3) Если r больше, чем b-a, перейдите к шагу 2.

4) Ваш результат r+a

Итак, попробуйте Random (1,3).
Итак, b-a равно 2.
2^1 = 2, поэтому p должно быть равно 2, так что 2^p больше 2.
Итак, мы займемся два раза. Попробуйте все возможные выходы:

00 -> r=0, 0 is not > 2, so we output 0+1 or 1.
01 -> r=1, 1 is not > 2, so we output 1+1 or 2.
10 -> r=2, 2 is not > 2, so we output 2+1 or 3.
11 -> r=3, 3 is > 2, so we repeat.

Итак, 1/4 времени, мы выводим 1. 1/4 времени, которое мы выводим 2. 1/4 времени, которое мы выводим 3. И 1/4 времени мы должны повторить алгоритм второй время. Выглядит хорошо.

Обратите внимание, что если вам нужно сделать это много, удобны две оптимизации:

1) Если вы используете один и тот же диапазон, используйте класс, который вычисляет p один раз, поэтому вам не нужно его вычислять каждый раз.

2) Многие процессоры имеют быстрый способ выполнить шаг 1, который не отображается на языках высокого уровня. Например, процессоры x86 имеют команду BSR.

Ответ 2

Нет, это не правильно, этот метод будет сосредоточен вокруг (a+b)/2. Это биномиальное распределение.

Вы уверены, что Random(0,1) создает целые числа? было бы более разумно, если бы оно создавало значения с плавающей запятой между 0 и 1. Тогда решение было бы аффинным преобразованием, время выполнения которого не зависело от a и b.

Идея, которую я только что имел, в случае, если она касается целочисленных значений: используйте bisection. На каждом шаге у вас есть диапазон low-high. Если Random(0,1) возвращает 0, следующий диапазон равен low-(low+high)/2, else (low+high)/2-high. Детали и сложность остались вам, так как это домашнее задание.

Это должно создать (приблизительно) равномерное распределение.

Изменить: приблизительно важное слово. Равномерное, если b-a+1 - степень 2, не слишком далеко, если она закрывается, но в целом недостаточно. Ах, ну, это была спонтанная идея, она не может их исправить.

Ответ 3

Я прочитал другие ответы. Для удовольствия, вот еще один способ найти случайное число:

Выделите массив элементами b-a. Установите все значения на 1. Итерации через массив. Для каждого ненулевого элемента, как бы переверните монету. Если он подошел 0, установите элемент в 0.

Всякий раз, когда после полной итерации у вас останется только один элемент, у вас есть случайное число: a+i где i - это индекс ненулевого элемента (при условии, что мы начинаем индексирование на 0). Тогда все числа одинаково вероятны. (Вам придется иметь дело с тем случаем, когда это галстук, но я оставляю это как упражнение для вас.)

У этого было бы O(infinity)...:) В среднем, однако, половина номеров будет устранена, поэтому у нее будет среднее время работы log_2 (b-a).

Ответ 4

Прежде всего, я предполагаю, что вы на самом деле накапливаете результат, а не добавляете 0 или 1 на каждый шаг. Используя некоторые вероятности, вы можете доказать, что ваше решение не равномерно распределено. Вероятность того, что результирующее значение r (a + b)/2 больше. Например, если a равно 0 и b равно 7, вероятность того, что вы получите значение 4, равна (комбинация 4 из 7), деленная на 2, поднятая до мощности 7. Причина этого заключается в том, что независимо от того, какой из 4 значений из 7 1, результат все равно будет 4.

Вы правильно оцениваете время выполнения.

Ответ 5

В алгоритме, который вы создали, он действительно неравномерно распределен.

Результат "r" всегда будет либо "a", либо "a + 1". Это никогда не выйдет за рамки этого.

Он должен выглядеть примерно так:

r=0;
for i=0 to b-a
   r = a + r + Random(0,1)

return r;

Включая "r" в ваш расчет, вы включаете "случайность" всех предыдущих циклов цикла "for".

Ответ 6

Нет, ваше решение неверно. Эта сумма будет иметь биномиальное распределение.

Однако вы можете создать чистую случайную последовательность из 0, 1 и рассматривать ее как двоичное число.

repeat
  result = a
  steps = ceiling(log(b - a))

  for i = 0 to steps
    result += (2 ^ i) * Random(0, 1)
until result <= b

KennyTM: мой плохой.

Ответ 7

Ваше псевдокод решения должен выглядеть так:

r=a
for i = 0 to b-a
    r+=Random(0,1)
return r

Что касается равномерного распределения, считая, что случайная реализация этого генератора случайных чисел основана на совершенно равномерной, вероятность получения 0 или 1 составляет 50%. Поэтому получение нужного вам числа является результатом этого выбора, сделанного снова и снова.

Итак, для a = 1, b = 5 существует 5 вариантов.

Шансы получить 1 включают в себя 5 решений, все 0, шансы на которые равны 0.5 ^ 5 = 3.125%

Шансы получить 5 включают в себя 5 решений, все 1, шансы на которые равны 0.5 ^ 5 = 3.125%

Как вы можете видеть из этого, распределение неравномерно - вероятность любого числа должна быть 20%.