Как использовать случайные биты, чтобы симулировать честный 26-гранный кубик?

Question

Как использовать генератор случайных чисел, который выдает биты (0 или 1) для имитации честного 26-гранного кубика? Я хочу использовать поток битов, чтобы выбирать буквы английского алфавита так, чтобы шансы на появление одной буквы были такими же, как шансы на любую другую букву (я знаю, что настоящие слова не такие, и имеют определенные распределения частот для каждого письмо, но это не имеет значения здесь). Каков наилучший способ использовать двоичные решения 0/1 для правильного выбора букв из набора A-Z? Я могу придумать несколько способов отобразить биты на буквы, но для меня не очевидно, что они не будут предвзятыми. Есть ли известный хороший способ?

Answer 1

Если вы ограничиваете себя конечным числом битов, и у вашего кубика 26 сторон, метод всегда будет предвзятым. Вы должны допустить возможность того, что вам придется смотреть на потенциально неограниченное количество бит, чтобы быть уверенным, что оно беспристрастно.

Простой алгоритм состоит в том, чтобы выбрать случайное число от 0 до следующего наибольшего числа в форме 2^n - 1 (в данном случае 31). Если выбранное вами число слишком велико, отбросьте его и повторяйте, пока не получите число в диапазоне.

Очевидно, что это не оптимальный алгоритм, поскольку вы «тратите» некоторую информацию, но он должен быть достаточно хорош для большинства целей. Наиболее расточительно, если число сторон кристалла чуть выше 2^m для некоторых m, например: 33 стороны. В этом случае вам придется отказаться от значения почти в 50% случаев.

Answer 2

Основной ответ здесь кажется правильным - если ваше случайное число 0..32 больше 25, используйте reroll.Тем не менее, вы можете сложить шансы против произвольно длинного результата, посмотрев на коэффициент, кратный 26, что дает меньше шансов на длинную ставку.

 32 -  26 =  6
 64 -  52 =  12
128 -  78 =  50

... и так далее.Я собрал Python-скрипт, чтобы определить наилучшее доступное число бит до 32, для смеха, и получил такой результат:

2^13 - 26 * 315 = 2
2^14 - 26 * 630 = 4

Так что в любом случае, у вас есть шанс 1 в 2 ^ 12перезапуск, если вы используете 13 или 14 бит.Ваш алгоритм в этом случае будет:

def random_character():
    r = 8190
    while r >= 8190:
        r = rand(13) # assuming rand generates an N bit integer
    return chr(r % 26 + ord('a'))

РЕДАКТИРОВАТЬ: Из любопытства я сравнил эти шансы с несколькими важными значениями, чтобы увидеть, действительно ли 13 было оптимальным числом (при условии, что вы можете сгенерировать любоебиты, от 1 до 32, в одно и то же время - если вы не можете, 13 бит выглядит лучше).Исходя из моей (по-видимому, сонной) математики, если вы можете получить 32 бита дешевле, чем 16, сделайте это вместо этого.В противном случае сделайте ставку в пользу 13.

2^8 through 2^12: by definition, no better than 1/2^12 odds
2^16: diff is 16, so 1/2^11
2^17: diff is 6, so slightly under 1/2^14
2^18: diff is 12, so slightly under 1/2^12
2^19: diff is 24, so slightly under 1/2^14
2^20: diff is 22, so slightly under 1/2^15
2^21: diff is 18, so slightly under 1/2^16
2^22: diff is 10, so slightly under 1/2^18
2^23: diff is 20, so slightly under 1/2^18
2^24: diff is 14, so slightly under 1/2^20
2^25: diff is 2, so 1/2^24
2^26: diff is 4, so 1/2^24
2^27: diff is 8, so 1/2^24
2^28: diff is 16, so 1/2^24
2^29: diff is 6, so slightly under 1/2^26
2^30: diff is 12, so slightly under 1/2^26
2^31: diff is 24, so slightly under 1/2^26
2^32: diff is 22, so slightly under 1/2^27

Answer 3

Самый простой подход в вашем случае - бросить 5 бит, что дает 32 (0-31) равновероятных результатов.Если вы получите значение за пределами вашего диапазона (больше 25), вы попытаетесь снова (и снова ...)

Среднее число «монет» (битов), которые нужно выбросить в этом случае для каждой буквы, будет равно

 5 x 32 / 26  = 6.15

(Для справки см. Геометрическое распределение )

Answer 4

26 - это 11010 в двоичном формате.
Генерирует пять битов, если они превышают 26, либо:

1. Возвращает значение mod 26 (будет соответствовать младшим значениям)
2. Отменить результат и перейти снова (Имеет возможность никогда не заканчиваться)

Или обобщить его:
Генерировать (записать n в базе 2) + 1 бит.Если они превышают n, вернуть значение mod n или отменить и перейти снова.

Answer 5

Наивной реализацией было бы объединение случайных битов для получения десятичного или целочисленного значения с использованием фиксированного числа битов (скажем, 4 байта для получения целого числа). Разделите результат на максимально возможное значение для числа предоставленных битов, которое, я думаю, должно дать вам десятичное число, равномерно распределенное в диапазоне 0-1. (По сути, функция rand ()). Тогда сделай 26 * rand ()