Будет ли это вносить смещение в то, что должно быть случайными числами?

Предположим, файл данных содержит более 80 миллионов единиц и нулей, сгенерированных случайным образом.

Из этого файла мы хотим создать список случайных десятичных целых чисел.

Это план сделать это преобразование.

Разделите 80 миллионов цифр на группы из 4 двоичных цифр.
Преобразуйте каждый 4-значный двоичный код в десятичный.
Отменить все десятичные значения больше 9.

Это должно привести к строке случайных целых чисел от 0-9

Здесь проблема. 24 двоичные цифры, которые составляют 6 групп по 4 двоичных цифры, которые соответствуют значениям от 10 до 15, содержат 17 единиц и только 7 нулей. Повлияет ли этот дисбаланс на распределение четных и нечетных целых чисел или каким-либо образом компрометирует случайность конечной строки десятичных цифр?

Обновление: Судя по приведенным выше ответам, приведенный выше метод является правильным. Я согласен с этим выводом. Тем не менее, я до сих пор не понимаю, почему удаление более чем вдвое большего числа нулей из двоичной строки не смещает результат в сторону уменьшения числа нечетных чисел. Я ищу объяснения.

monte-carlo random-generation randomness Джоэл В.
источник

Есть более эффективные методы. Например, вы можете разбить строку битов на группы по 10, преобразовать их в их основание 10 из трех цифр и отбросить любую со значениями 1000 или больше. Это будет использовать 97,6% битов, а не только 62,5% из них. Вы не можете сделать намного лучше, чем это. (Вы можете использовать группы из 681 и преобразовать их в 205-значные строки из 10 цифр, используя, таким образом, почти 99,7% битов.)

whuber

Ответы:

Давайте посчитаем и посмотрим. По построению файла все 4-битные строки одинаково вероятны. Есть 16 таких строк. Вот они:

Ваша процедура выбрасывает строки с 10 по 15. Таким образом, в тех случаях, которые вы фактически используете, вы будете выбирать от 0 до 9, каждый из которых одинаково вероятен, по желанию. И мы знаем, что сгенерированные десятичные цифры не зависят друг от друга, потому что каждая использует отдельную строку из 4 бит, и все биты являются независимыми. Ваша процедура представляет собой простой вид отбраковки .

Kodiologist
источник

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

Джоэл В.

@JoelW Думаю, я не вижу твоего аргумента. Окончательное распределение касается десятичных цифр, а не битов, поэтому распределение битов не имеет значения.

Кодиолог

Это правильно, но это только частично решает вопрос. Чтобы решить вопрос о «случайной компромиссности ... любым образом», необходимо также установить, что получаемые десятичные цифры в превосходном приближении независимы . Ради полноты, стоит посвятить одно предложение объяснения этому (очевидному) результату.

whuber

Джоэл, я вижу, откуда ты. Здесь может быть неправильное восприятие: вы не можете полностью изменить процесс. Если вы хотите восстановить поток битов из потока десятичных цифр, вам нужно будет сделать что-то вроде удаления всех 8 и 9 и преобразовать оставшиеся цифры в двоичные тройки. Это восстановит баланс. На самом деле, легко увидеть, что это «круговое движение» сводится к разбивке вашего исходного потока на четырехбитные кусочки и отбрасыванию их наиболее значимых битов, в результате чего получается хорошая равномерно распределенная последовательность из 60 миллионов битов.

whuber

@ достаточно честно; добавлено.

Кодиолог

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

Код R для приведенного выше графика

generza=matrix(sample(0:1,4*1e6,rep=TRUE),ncol=4)
uniz=generza[,1]+2*generza[,2]+4*generza[,3]+8*generza[,4]
barplot(hist(uniz[uniz<10],breaks=seq(-0.5,9.5,le=11))$counts,col="steelblue")

Сиань
источник