Почему на (0, 255) генерируется 8 случайных битов?

35

Я генерирую 8 случайных битов (0 или 1) и объединяю их вместе, чтобы сформировать 8-битное число. Простое моделирование Python дает равномерное распределение на дискретном множестве [0, 255].

Я пытаюсь объяснить, почему это имеет смысл в моей голове. Если бы я сравнил это с подбрасыванием 8 монет, разве ожидаемое значение не было бы где-то около 4 голов / 4 хвостов? Поэтому для меня имеет смысл, что мои результаты должны отражать всплеск в середине диапазона. Другими словами, почему последовательность из 8 нулей или 8 одинаково вероятна как последовательность из 4 и 4, или 5 и 3 и т. Д.? Что мне здесь не хватает?

стекловидный
источник
17
Ожидаемое значение распределения битов в равномерном случайном диапазоне [0,255] также составляет где-то около 4 1/4 0.
user253751
2
Тот факт, что вы присваиваете одинаковое значение каждому числу от 0 до 255, не означает, что результат функции «разница между числом от 1 до 0» также будет происходить один раз и только один раз. Я мог бы придать равный вес каждому человеку в моей организации. Не означает, что их возраст будет одинаково взвешенным. Некоторые возрасты могут быть гораздо более распространенными, чем другие. Но один человек не более распространен, чем любой другой человек.
Брэд Томас
2
Подумайте об этом так ... Ваш первый случайный бит будет определять значение бита 7, 1 стоит 128, а 0 - 0. Из 256 чисел у вас есть 50% -ная вероятность того, что число будет 0-127, если бит равен 0 и 128-255, если бит равен 1. Допустим, он равен 0, а следующий бит определяет, будет ли результат 0-63 или 64-127. Все 8 битов необходимы для формирования одного из 256 одинаково вероятных результатов. Вы думаете о суммировании, как если бы вы играли в кости. Шансы на получение 4 1 и 4 0 выше, чем на 8 1, но есть и другие способы их получения, чтобы получить другой результат.
Джейсон Гомаат
2
Предположим, что вы бросили честный 256-гранный куб с номерами от 0 до 255. Вы ожидаете равномерного распределения. Теперь предположим, что вы переименовали кубик так, что одна сторона говорит 0, 8 - 1, 28 - 2 и т. Д .; каждая сторона теперь помечена количеством битов в числе, которое раньше было на этой стороне. Вы снова бросаете кубик; почему вы ожидаете получить равномерное распределение чисел от 0 до 8?
Эрик Липперт
Если бы распределение работало так, то я мог бы делать большие ставки на рулетке только после того, как выпало 7 красных очков подряд. 7 и 1 более чем в 8 раз чаще, чем 8 и 0! ( без учета 0, но это перекос далеко перевешивает 0, а 00 перекос)
Cruncher

Ответы:

61

TL; DR: резкий контраст между битами и монетами в том, что в случае монет вы игнорируете порядок результатов. HHHHTTTT рассматривается так же, как TTTTHHHH (оба имеют 4 головы и 4 хвоста). Но в битах вы заботитесь о порядке (потому что для получения 256 результатов необходимо указать «веса» для битовых позиций), поэтому 11110000 отличается от 00001111.


Более подробное объяснение: эти концепции могут быть более точно объединены, если мы будем более формальными в формулировании проблемы. Рассмотрим эксперимент как последовательность из восьми испытаний с дихотомическими исходами и вероятностью «успеха» 0,5 и «неудачи» 0,5, и испытания являются независимыми. В общем, я назову это успехов, n полных испытаний и n - k неудач, а вероятность успеха равна p .КNN-Кп

  • В примере с монетой результат « головы, n - k хвосты» игнорирует порядок испытаний (4 головы - это 4 головы независимо от порядка появления), и это приводит к вашему наблюдению, что 4 головы более вероятны, чем 0 или 8 голов. Четыре головы более распространены, потому что есть много способов сделать четыре головы (TTHHTTHH или HHTTHHTT и т. Д.), Чем какое-то другое число (8 голов имеют только одну последовательность). Биноминальная теорема дает количество способов сделать эти различные конфигурации.КN-К

  • В отличие от этого, порядок важен для битов, потому что каждое место имеет связанный «вес» или «значение места». Одним из свойств биномиального коэффициента является то, что , то есть, если мы подсчитаем все различные упорядоченные последовательности, мы получим28=256. Это напрямую связывает идею о том, сколько существует различных способов сделатьkголов вnбиномиальных испытаниях с количеством различных последовательностей байтов.2Nзнак равноΣКзнак равно0N(NК)28=256kn

  • Кроме того, мы можем показать, что 256 результатов одинаково вероятны благодаря свойству независимости. Предыдущие испытания не влияют на следующее испытание, поэтому вероятность определенного упорядочения, как правило, равна (поскольку совместная вероятность независимых событий является произведением их вероятностей). Поскольку испытания справедливы, P ( успех ) = P ( сбой ) = p = 0,5 , это выражение сводится к P ( любой порядок ) = 0,5 8 =pk(1p)nkP(success)=P(fail)=p=0,5 . Поскольку все упорядочения имеют одинаковую вероятность, мы имеем равномерное распределение по этим результатам (которое с помощью двоичного кодирования может быть представлено как целые числа в[0,255]).P(any ordering)=0.58=1256[0,255]

  • Наконец, мы можем взять этот полный круг обратно к броску монеты и биномиальному распределению. Мы знаем, что появление 0 голов не имеет такой же вероятности, как у 4 голов, и это потому, что существуют разные способы упорядочения вхождений 4 голов, и что количество таких упорядочений определяется биномиальной теоремой. Таким образом, должен быть как-то взвешен, в частности, он должен быть взвешен по биномиальному коэффициенту. Так что это дает нам PMF биномиального распределения, P ( k  успеха ) = ( nP(4 heads). Может быть удивительным, что это выражение является PMF, особенно потому, что не сразу очевидно, что оно суммируется с 1. Чтобы убедиться, мы должны проверить, чтоk n k = 0 ( nP(k successes)=(nk)pk(1p)nk, однако это всего лишь проблема биномиальных коэффициентов:1=1n=(p+1-p)n= n k = 0 ( nk=0n(nk)pk(1p)nk=1.1=1n=(p+1p)n=k=0n(nk)pk(1p)nk

Sycorax говорит восстановить Монику
источник
Это имеет смысл ... но разве мы не ожидаем, что 15, 30, 60, 120 и 240 будут иметь больший вес в распределении, чем 0 или 255?
стекловидно
1
Я думаю, что понимаю это сейчас. Я собираюсь принять этот ответ, потому что я думаю, что ключевым моментом здесь является порядок, на который вы обратили внимание. Спасибо
стеклянный
Еще одно замечание - если использовать мой пример с монетами, это действительно подбрасывает 8 монет одновременно, а не 8 попыток подбрасывания монеты. В этом моя ложь.
стекловидно
2
Понятие «ценность места» из «арифметики начальных классов» особенно применимо здесь; Если использовать десятичную аналогию, можно считать 10001000и 10000001совершенно другие числа.
JM не является статистиком
17

почему последовательность из 8 нулей или 8 одинаково вероятна как последовательность из 4 и 4, или 5 и 3 и т. д.

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

  1. Последовательность (восемь нулей) также вероятна, как последовательность s 2 : 01010101 (четыре нуля, четыре единицы). (В целом: все 2 8 последовательностей имеют одинаковую вероятность, независимо от того, сколько у них нулей / единиц).s1:00000000s2:0101010128

  2. Событие « : последовательность имела четыре ноля » более вероятно ( более чем в 70 раз более вероятно), чем событие « e 2 : последовательность имела восемь нулей ».e170e2

Эти предложения оба верны. Потому что событие включает в себя множество последовательностей.e1

leonbloy
источник
8

Все последовательностей имеют одинаковую вероятность 1/2 8 = 1/256. Неправильно думать, что последовательности, которые ближе к равному числу 0 и 1, более вероятны при интерпретации вопроса. Должно быть ясно, что мы достигли 1/256, потому что мы предполагаем независимость от испытания к испытанию . Вот почему мы умножаем вероятности, и результат одного испытания не влияет на следующее.2828

Майкл Р. Черник
источник
2
Это было бы хорошо, если коротко, ответить ... если бы вопрос не включал слово "почему". На самом деле, вы просто повторяете одно из вопросов в вопросе без объяснения причин.
Tin Man
1
На самом деле ... Этот ответ на самом деле неправильный, см. Ответ Леонблоя, почему.
Tin Man
3
@ Это не так. Тонкость языка. Любая данная последовательность не является более вероятной, потому что она имеет меньший дисбаланс между 0 и 1 с. Таких последовательностей просто больше .
Хоббс
4
Кто-нибудь согласен со мной? Если 0 имеет вероятность 1/2 и 1 имеет вероятность 1/2 и один член в последовательности не зависит от следующего вероятность заданной последовательности длиной 8 имеет вероятность . и также любая другая последовательность 8.1/28=1/256
Майкл Р. Черник
4
@ Майкл Я полностью согласен и рад видеть - наконец-то! - явное обращение к самой сути вопроса: независимости. Я был бы рад подтвердить ваш ответ, если бы вы включили этот комментарий в него.
whuber
7

ПРИМЕР с 3 битами (часто пример является более иллюстративным)

Я запишу натуральные числа от 0 до 7 как:

  • Число в базе 10
  • Число в базе 2 (то есть последовательность битов)
  • Последовательность подбрасывания монет, подразумеваемая представлением основы 2 (1 обозначает переворот голов, а 0 обозначает переворот хвостов).

Base 10Base 2 (with 3 bits)Implied Coin Flip SeriesHeadsTails0000TTT031001TTH122010THT123011THH214100HTT125101HTH216110HHT217111HHH30

Выбор натурального числа от 0 до 7 с равной вероятностью эквивалентен выбору одного из рядов бросков монеты справа с равной вероятностью.

18383818

Мэтью Ганн
источник
3

Ответ Sycorax правильный, но кажется, что вы не совсем понимаете, почему. Когда вы подбрасываете 8 монет или генерируете 8 случайных битов с учетом порядка, ваш результат будет одним из 256 одинаково вероятных вариантов. В вашем случае каждый из этих 256 возможных результатов однозначно отображается в целое число, поэтому вы получаете равномерное распределение в качестве результата.

Если вы не принимаете во внимание порядок, например, учитывая, сколько у вас голов или хвостов, есть только 9 возможных результатов (0 голов / 8 хвостов - 8 голов / 0 хвостов), и они больше не одинаково вероятны , Причина этого заключается в том, что из 256 возможных результатов имеется 1 комбинация сальто, которая дает вам 8 голов / 0 хвостов (HHHHHHHH) и 8 комбинаций, которые дают 7 голов / 1 хвостов (хвосты в каждой из 8 позиций в порядок), но 8C4 = 70 способов иметь 4 головы и 4 хвоста. В случае подбрасывания монеты каждая из этих 70 комбинаций отображается в 4 головы / 4 хвоста, но в проблеме двоичных чисел каждый из этих 70 исходов отображается в уникальное целое число.

Черная сталь
источник
2

п(0)знак равноп(1)знак равно12

Ответ таков: есть две разные кодировки; 1) кодирование без потерь перестановок и 2) кодирование без потерь комбинаций.

Σязнак равно182я-1ИксяИксяяTчас28знак равно256, Затем, по совпадению, можно преобразовать эти двоичные цифры в базовые 10 чисел от 0 до 255 без потери уникальности, или в этом отношении можно переписать это число, используя любое другое кодирование без потерь (например, сжатые данные без потерь, Hex, Octal). Сам вопрос, однако, является бинарным. Каждая перестановка в равной степени вероятна, поскольку существует только один способ создания каждой уникальной последовательности кодирования, и мы предположили, что появление 1 или 0 одинаково вероятно в любом месте этой строки, так что каждая перестановка одинаково вероятна.

Σязнак равно1820ИксяС(8,Σязнак равно18Икся)Σязнак равно18ИксяС(8,4)

Примечание. В настоящее время приведенный выше ответ является единственным ответом, содержащим явное вычислительное сравнение двух кодировок, и единственным ответом, в котором даже упоминается концепция кодирования. Потребовалось некоторое время, чтобы понять это правильно, поэтому этот ответ исторически был отвергнут. Если есть какие-либо нерешенные жалобы, оставьте комментарий.

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

С(8,N)-1N069256-9знак равно247

деревенщина
источник
2
Использование обычного способа именования чисел - путем исключения всех ссылок на предшествующие нули - потенциально может привести к путанице в этом объяснении. Не думаете ли вы, что ситуация станет намного яснее, если вы0как 00000000,1(который вы случайно не указали) как 00000001и так далее?
whuber
16
Честно говоря, это все правильно, насколько это возможно, но это не решает вопрос . Вы хорошо показали, как восемь упорядоченных битов могут представлять числа в диапазоне, но не объяснили, почему выбор этих битов случайным образом дает равномерное распределение (что, по общему признанию, настолько простое, что для его объяснения явно требуются некоторые тонкость).
dmckee
9
Не проще ли сказать, что 8 (независимо) случайных бит равномерно распределены на [00000000, 11111111] по той же причине, что 3 случайных цифры равномерно распределены на [000, 999]? Побочные заявления о том, как / почему компьютеры используют двоичные и дробные базы, совершенно не нужны и не связаны. Я имею в виду, тот факт, что двоичный файл использует только символы 0 и 1, является просто неотъемлемым свойством базы 2 ... объяснять это не нужно. Если бы вы хотели сохранить там подобные объяснения, возможно, было бы более полезно объяснить, как работают основы в целом, но это все равно не относится к делу.
Блэкхок
3
Я рад видеть, насколько этот ответ улучшился. Тем не менее, мне трудно понять, как представления base-10 имеют отношение к этому вопросу (разве base-3 или base-17 не будут работать так же хорошо?), И я не вижу, что может быть особенного в 8 битах, которые тоже не обобщать на любое конечное число бит. Это говорит о том, что большинство соображений в этом ответе касательно или не имеет значения.
whuber
3
И я хотел бы поблагодарить вас за эту удачную характеристику путаницы, выраженной в вопросе: кодирование «с потерями» и «без потерь». Он запоминающийся, немного отличается от других точек зрения, проницателен и потенциально может быстро устранить эту путаницу.
whuber
1

Я хотел бы немного подробнее остановиться на идее зависимости порядка от независимости.

В задаче вычисления ожидаемого числа голов при подбрасывании 8 монет мы суммируем значения из 8 одинаковых распределений, каждое из которых является распределением Бернулли [; B(1, 0.5) ;](другими словами, 50% шанс 0, 50% шанс 1). Распределением суммы является биномиальное распределение [; B(8, 0.5) ;], которое имеет знакомую форму горба с большей вероятностью, сосредоточенной вокруг 4.

В задаче вычисления ожидаемого значения байта, состоящего из 8 случайных битов, каждый бит имеет свое значение, которое он вносит в байт, поэтому мы суммируем значения из 8 различных распределений. Первое [; B(1, 0.5) ;], второе [; 2 B(1, 0.5) ;], третье [; 4 B(1, 0.5) ;], и так до восьмого [; 128 B(1, 0.5) ;]. Распределение этой суммы по понятным причинам сильно отличается от первого.

Если вы хотите доказать, что это последнее распределение является равномерным, я думаю, вы могли бы сделать это индуктивно - распределение младшего бита является равномерным с диапазоном 1 по предположению, поэтому вы хотели бы показать, что если распределение младших [; n ;]битов является однородным с диапазоном, [; 2^n - 1} ;]то добавление первого [; n+1 ;]бита делает распределение младших [; n + 1 ;]битов равномерным с диапазоном [; 2^{n+1} - 1 ;], обеспечивая доказательство для всех положительных[; n ;], Но интуитивный путь, вероятно, является полной противоположностью. Если вы начнете с старшего бита и выберете значения по одному до младшего бита, каждый бит делит пространство возможных результатов ровно пополам, и каждая половина выбирается с равной вероятностью, поэтому к тому времени, когда вы доберетесь до внизу, каждое отдельное значение должно иметь одинаковую вероятность выбора.

Hobbs
источник
Это не сплошная униформа. Бит либо 0, либо 1 и ничего между ними.
Майкл Р. Черник
@MichaelChernick Конечно, мы имеем дело только с дискретными дистрибутивами.
Хоббс
ОП сказал, что биты только 1 или 0 и ничего между ними.
Майкл Р. Черник
1
@MichaelChernick правильно.
Хоббс
1

Если вы выполняете двоичный поиск, сравнивая каждый бит, то вам нужно одинаковое количество шагов для каждого 8-битного числа, от 0000 0000 до 1111 1111, они оба имеют длину 8 бит. На каждом шаге бинарного поиска обе стороны имеют вероятность 50/50, поэтому, в конце концов, поскольку каждое число имеет одинаковую глубину и одинаковую вероятность, без какого-либо реального выбора каждое число должно иметь одинаковый вес. Таким образом, распределение должно быть равномерным, даже если каждый отдельный бит определяется бросками монет.

Тем не менее, цифровая сумма чисел не является одинаковой и будет равна распределению 8 подбрасывания монет.

HopefullyHelpful
источник
1

Есть только одна последовательность с восемью нулями. Есть семьдесят последовательностей с четырьмя нулями и четырьмя.

Следовательно, в то время как 0 имеет вероятность 0,39%, а 15 [00001111] также имеет вероятность 0,39%, а 23 [00010111] имеет вероятность 0,39% и т. Д., Если сложить все семьдесят из вероятностей 0,39% вы получите 27,3%, что составляет вероятность наличия четырех. Вероятность каждого отдельного результата «четыре-четыре» не должна быть выше 0,39%, чтобы это работало.

Random832
источник
Это не меняет того факта, что все 256 последовательностей одинаково вероятны.
Михаил Р. Черник
@MichaelChernick Я не сказал, что сделал, я прямо сказал, что у них всех есть вероятность 0.39%, я обращаюсь к предположениям OP.
Random832
Вы правы. Это еще один способ сказать то, что я сказал в своем ответе. Некоторые другие ответы неверны.
Михаил Р. Черник
1

Рассмотреть кости

Подумайте о том, чтобы бросить пару кубиков, типичный пример неравномерного распределения. Ради математики представьте, что кости пронумерованы от 0 до 5 вместо традиционных от 1 до 6. Причина, по которой распределение не является равномерным, заключается в том, что вы смотрите на сумму бросков костей, где несколько комбинаций могут дать такое же общее количество, как {5, 0}, {0, 5}, {4, 1} и т. д., все генерируют 5.

Однако, если вы должны были интерпретировать бросок костей как двузначное случайное число в базе 6, каждая возможная комбинация костей уникальна. {5, 0} будет 50 (база 6), что будет 5 * (61) + 0 * (60) = 30 (основание 10). {0, 5} будет 5 (база 6), что будет 5 * (60) = 5 (основание 10). Итак, вы можете видеть, что есть сопоставление 1 к 1 возможных бросков костей, интерпретируемых как числа в базе 6, против сопоставления много к 1 для суммы двух костей в каждом броске.

Как указывают @Sycorax и @Blacksteel, это различие действительно сводится к вопросу о порядке.

Черный ястреб
источник
0

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

  • 50% вероятности будет 1

а также

  • 50% вероятности будет 0.

Это также относится ко второму биту, третьему биту и т. Д., Так что вы получите так для каждой возможной комбинации битов, чтобы сделать ваш байт у вас есть (12)8 знак равно 1256 вероятность того, что это уникальное 8-битное целое число происходит.

Ahemone
источник
Все эти утверждения верны, но это не касается того, почему броски монет, которые также являются справедливыми и независимыми, имеют только 9 различных результатов, когда результат определяется как количество голов и хвостов.
Sycorax сообщает восстановить Monica
Это только результат размещения результатов в упорядоченной системе после их выбора. Такое же распределение будет достигнуто, даже если случайные биты будут размещены в случайных позициях в байте. Вы также получите такое же распределение по броскам монет, когда вы задаете вопрос, чтобы найти шанс получить определенную комбинацию голов и хвостов, такую ​​как HHTHTTTH. У вас будет шанс 1/256 получить точную последовательность бросков монет для 8 бросков монет, выполняемых каждый раз.
Ahemone
Это хорошая информация для включения в ответ. Мой комментарий не имеет отношения к тому, что вы сказали, а к упущению прямого адреса источника путаницы ОП: взаимосвязи между битами и монетами.
Sycorax сообщает восстановить Monica
Я также должен сказать, что для достижения ожидаемого значения OP 4 они пытаются найти вероятность n много 1 или n много 0 в данном байте. Эта постановка вопроса дала бы биномиальное распределение, которое они ожидали в уме, а не равномерное распределение вероятности получения определенного значения из этих случайных битов.
Ahemone