Понимание "случайности"

Question

Я не могу разобраться с этим, что является более случайным?

rand()

ИЛИ

rand() * rand()

Я считаю, что это настоящая головоломка для мозга, не могли бы вы помочь?меня?

РЕДАКТИРОВАТЬ:

Интуитивно я знаю, что математическим ответом будет то, что они одинаково случайны, но я не могу не думать, что если вы "Запустите алгоритм случайных чисел "дважды, когда вы умножите их вдвоем, вы создадите нечто более случайное, чем просто один раз.

Answer 1

Понятие, которое вы ищете, это «энтропия», «степень» беспорядка цепочки битов.Идея наиболее проста для понимания с точки зрения понятия «максимальная энтропия».

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

Итак, если вы хотите сделать случайное число из двух случайных выборок, которое «вдвое» случайнее, вы бы конкатенировали две битовые строки вместе.На практике вы просто помещаете сэмплы в верхнюю и нижнюю половинки слова двойной длины.

На более практической ноте, если вы окажетесь обремененным дерьмовым рэндом (), иногда это может помочьxor пару сэмплов вместе - хотя, если это действительно сломано, даже эта процедура не поможет.

Answer 2

Принятый ответ довольно милый, но есть и другой способ ответить на ваш вопрос. Ответ PachydermPuncher уже использует этот альтернативный подход, и я просто собираюсь его немного расширить.

Самый простой способ подумать о теории информации - это наименьшая единица информации, один бит.

В стандартной библиотеке C rand() возвращает целое число в диапазоне от 0 до RAND_MAX, предел, который может быть определен по-разному в зависимости от платформы.Предположим, что RAND_MAX определено как 2^n - 1, где n - некоторое целое число (это имеет место в реализации Microsoft, где n равно 15).Тогда мы бы сказали, что хорошая реализация вернула бы n битов информации.

Представьте, что rand() создает случайные числа, подбрасывая монету, чтобы найти значение одного бита, и затем повторяя, пока не получитпартия 15 бит.Тогда биты являются независимыми (значение любого одного бита не влияет на вероятность того, что другие биты в той же партии имеют определенное значение).Таким образом, каждый бит, рассматриваемый независимо, подобен случайному числу от 0 до 1 включительно и «равномерно распределен» по этому диапазону (с вероятностью 0 к 1).

Независимость битов гарантирует, что числапредставленные пакетами битов также будут равномерно распределены по их диапазону.Это интуитивно очевидно: если имеется 15 битов, допустимый диапазон от нуля до 2^15 - 1 = 32767. Каждое число в этом диапазоне является уникальным шаблоном битов, например:

010110101110010

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

Так что думайте о rand() как о производственной линии для создания битов, которая просто служитих в партиях произвольного размера.Если вам не нравится размер, разбейте партии на отдельные биты, а затем соедините их вместе в любых количествах, которые вам нравятся (хотя, если вам нужен определенный диапазон, который не является степенью 2, вам нужно уменьшить свои числаи, безусловно, самый простой способ сделать это - преобразовать в число с плавающей запятой).

Возвращаясь к исходному предложению, предположим, что вы хотите перейти от партий 15 к партиям 30, попросите rand() длясначала число сдвиньте на 15 позиций, затем добавьте к нему еще rand().Это способ объединить два вызова на rand(), не нарушая равномерное распределение.Это работает просто потому, что нет никакого перекрытия между местами, где вы размещаете биты информации.

Это очень отличается от «растяжения» диапазона rand() путем умножения на константу.Например, если вы хотите удвоить диапазон rand(), вы можете умножить на два - но теперь вы будете получать только четные числа, а не нечетные!Это не совсем гладкое распределение и может быть серьезной проблемой в зависимости от приложения, например, игра в рулетку, якобы допускающая нечетные / четные ставки.(Думая в терминах битов, вы избежите этой ошибки интуитивно, потому что вы поймете, что умножение на два - это то же самое, что смещение битов влево (большее значение) на одно место и заполнение пробела нулем.Поэтому очевидно, что объем информации одинаков - он просто немного сдвинулся.)

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

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

Но, по крайней мере, если вы считаете это кусочками, ваша интуиция может продвинуть вас немного дальше. Биты действительно легки - даже компьютеры могут их понять.

Answer 3

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

Предположим, вы играли в игру в кости.У вас есть совершенно честные, случайные кости.Будут ли броски кубиков "более случайными", если перед каждым броском кубиков вы сначала кладете две кубики в миску, встряхиваете их, выбираете одну из кубиков наугад, а затем бросаете ее?Понятно, что это не имеет значения.Если оба кубика дают случайные числа, то случайный выбор одного из двух кубиков не будет иметь значения.В любом случае вы получите случайное число от 1 до 6 с равномерным распределением по достаточному количеству бросков.

Полагаю, в реальной жизни такая процедура может быть полезна, если вы подозреваете, что игра в кости НЕ будет справедливой,Если, скажем, игральные кости слегка несбалансированы, так что один имеет тенденцию давать 1 чаще, чем 1/6 времени, а другой имеет тенденцию давать 6 необычно часто, то случайный выбор между ними будет иметь тенденцию скрывать смещение.(Хотя в этом случае 1 и 6 все равно бывают больше, чем 2, 3, 4 и 5. Ну, я думаю, в зависимости от характера дисбаланса.)

Существует много определений случайности.Одно из определений случайного ряда состоит в том, что это ряд чисел, созданный случайным процессом.По этому определению, если я брошу честный кубик 5 раз и получу числа 2, 4, 3, 2, 5, то это случайный ряд.Если я затем брошу тот же самый умный кубик еще 5 раз и получу 1, 1, 1, 1, 1, то это тоже случайный ряд.

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

РЕДАКТИРОВАТЬ

Не думаю, что смогу ответить на Монти Холлпроблема в комментарии, поэтому я обновлю свой ответ.

Для тех, кто не читал ссылку Велисария, суть в том, что участнику игрового шоу предоставляется выбор из 3 дверей.За одним стоит ценный приз, за ​​остальными - что-то бесполезное.Он выбирает дверь № 1.Прежде чем показать, является ли он победителем или проигравшим, хозяин открывает дверь № 3, чтобы показать, что он проигравший.Затем он дает участнику возможность перейти к двери № 2.Должен ли участник сделать это или нет?

Ответ, который оскорбляет интуицию многих людей, заключается в том, что он должен поменяться.Вероятность того, что его исходный выбор был победителем, равна 1/3, а другая дверь - победителем - 2/3.Моя первоначальная интуиция, как и у многих других людей, заключается в том, что при переключении не было бы никакой выгоды, что шансы только что были изменены на 50: 50.

В конце концов, предположим, что кто-то включил телевизорСразу после того, как хозяин открыл проигрышную дверь.Этот человек увидит две оставшиеся закрытые двери.Предполагая, что он знает природу игры, он сказал бы, что есть шанс 1/2, что каждая дверь скрывает приз.Как шансы для зрителя могут быть 1/2: 1/2, а шансы для участника - 1/3: 2/3?

Мне действительно нужно было подумать об этом, чтобы превратить мою интуицию в форму.Чтобы разобраться с этим, поймите, что когда мы говорим о вероятностях в такой проблеме, мы имеем в виду вероятность, которую вы назначаете с учетом доступной информации.Для члена команды, который поставил приз, скажем, за дверью № 1, вероятность того, что приз находится за дверью № 1, составляет 100%, а вероятность того, что он находится за любой из двух других дверей, равна нулю.

Шансы члена команды отличаются от шансов участника, потому что он знает то, чего не знает участник, а именно, за какой дверью он поставил приз.Аналогично, шансы претендента отличаются от шансов зрителя, потому что он знает то, чего не знает зритель, а именно, какую дверь он первоначально выбрал.Это не имеет значения, потому что выбор хозяина, какую дверь открыть, не случаен.Он не откроет дверь, которую выбрал участник, и не откроет дверь, которая скрывает приз.Если это одна и та же дверь, это оставляет ему два выбора.Если это разные двери, то остается только одна.

Итак, как мы можем придумать 1/3 и 2/3?Когда участник первоначально выбрал дверь, он имел 1/3 шанса выбрать победителя.Я думаю, что многое очевидно.Это означает, что был шанс 2/3, что одна из других дверей станет победителем.Если хозяин игры ему предоставит возможность переключаться без предоставления какой-либо дополнительной информации, выигрыша не будет.Опять же, это должно быть очевидно.Но один из способов взглянуть на это - сказать, что есть шанс 2/3, что он выиграет, переключившись.Но у него есть 2 альтернативы.Таким образом, у каждого есть только 2/3, деленное на 2 = 1/3 шанса стать победителем, что не лучше, чем его первоначальный выбор.Конечно, мы уже знали окончательный результат, он просто вычисляет его по-другому.

Но теперь хозяин показывает, что один из этих двух вариантов не является победителем.Так что из 2/3 шансов, что дверь, которую он не выбрал, является победителем, он теперь знает, что 1 из 2 альтернатив не так.Другой может или не может быть.Таким образом, у него больше нет 2/3, деленного на 2. У него есть ноль для открытой двери и 2/3 для закрытой двери.

Answer 4

Представьте, что у вас есть простая проблема с подбрасыванием монеты, когда четные считаются головами, а нечетные - хвостами. Логическая реализация:

rand() mod 2

При достаточно большом распределении число четных чисел должно равняться количеству нечетных чисел.

Теперь рассмотрим небольшой твик:

rand() * rand() mod 2

Если один из результатов четный, то весь результат должен быть четным. Рассмотрим 4 возможных результата (четное * четное = четное, четное * нечетное = четное, нечетное * четное = четное, нечетное * нечетное = нечетное). Теперь при достаточно большом распределении ответ должен быть даже 75% времени.

Я бы поставил головы на твоем месте.

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

Answer 5

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

В ситуации ОП он хочет знать, каков результат X * X = X ^ 2, где X - случайная величина, распределенная вдоль Униформы [0,1]. Мы будем использовать технику CDF, так как это только однозначное сопоставление.

Так как X ~ Uniform [0,1], это cdf: f _X (x) = 1 Мы хотим преобразование Y <- X ^ 2, таким образом, у = х ^ 2 Найдите обратное x (y): sqrt (y) = x, это дает нам x как функцию от y. Затем найдите производную dx / dy: d / dy (sqrt (y)) = 1 / (2 sqrt (y)) </p>

Распределение Y задается как: f _Y (y) = f _X (x (y)) | dx / dy | = 1 / (2 кв. (У))

Мы еще не закончили, нам нужно получить домен Y. так как 0 <= x <1, 0 <= x ^ 2 <1 поэтому Y находится в диапазоне [0, 1). Если вы хотите проверить, действительно ли pdf-файл Y является pdf, интегрируйте его в домен: <a href="http://www.wolframalpha.com/input/?i=integrate+1/(2+sqrt(y))+from+0+to+1" rel="noreferrer"> Интегрируйте 1 / (2 sqrt (y)) от 0 до 1 и, действительно, он появится как 1. Также Обратите внимание на то, что форма упомянутой функции выглядит так, как выглядело блаженно.

Что касается таких вещей, как X ₁ + X ₂ + ... + X _n , (где X _i ~ Uniform [0,1]) мы можем просто обратиться к центральной предельной теореме, которая работает для любого распределения, моменты которого существуют. Вот почему Z-тест существует на самом деле.

Другие методы определения результирующего pdf включают преобразование Якоби (которое является обобщенной версией метода cdf) и метод MGF.

РЕДАКТИРОВАТЬ: В качестве пояснения, обратите внимание, что я говорю о распределение результирующего преобразования, а не его случайность . Это на самом деле для отдельного обсуждения. Также то, что я на самом деле получил, было для (rand ()) ^ 2. Для rand () * rand () это намного сложнее, что, в любом случае, не приведет к равномерному распределению любого рода.

Answer 6

Это не совсем очевидно, но rand() обычно более случайный, чем rand()*rand().Важно то, что на самом деле это не очень важно для большинства применений.

Но, во-первых, они производят разные дистрибутивы. Это не проблема , если это то, что вы хотите, но это имеет значение.Если вам нужен конкретный дистрибутив, тогда проигнорируйте весь вопрос «который является более случайным».Так почему же rand() более случайный?

Суть того, почему rand() более случайный (при условии, что он генерирует случайные числа с плавающей запятой с диапазоном [0..1], чтоочень часто), когда вы умножаете два числа FP вместе с большим количеством информации в мантиссе, вы получаете некоторую потерю информации до конца;в поплавке двойной точности IEEE просто недостаточно битов, чтобы хранить всю информацию, которая была в двух поплавках двойной точности IEEE, равномерно случайным образом выбранную из [0..1], и эти дополнительные биты информации теряются.Конечно, это не имеет большого значения, так как вы (вероятно) не собирались использовать эту информацию, но потеря реальна.Также не имеет значения, какой дистрибутив вы производите (т. Е. Какую операцию вы используете для комбинации).Каждое из этих случайных чисел содержит (в лучшем случае) 52 бита случайной информации - это то, что может содержать двойник IEEE - и если вы объедините два или более в одно, вы все равно будете иметь не более 52 бит случайной информации.

В большинстве случаев использование случайных чисел не использует даже столько случайности, сколько фактически доступно в случайном источнике.Получите хороший PRNG и не беспокойтесь об этом.(Уровень «добродетели» зависит от того, что вы делаете с ним; вы должны быть осторожны при симуляции или криптографии Монте-Карло, но в противном случае вы, вероятно, можете использовать стандартный PRNG, поскольку он обычно намного быстрее.)

Answer 7

Плавающие случайные числа основаны, как правило, на алгоритме, который выдает целое число от нуля до определенного диапазона. Таким образом, используя rand () * rand (), вы, по сути, говорите int_rand () * int_rand () / rand_max ^ 2, то есть исключаете любое простое число / rand_max ^ 2.

Это значительно меняет рандомизированное распределение.

rand () равномерно распределен в большинстве систем, и его трудно предсказать, если правильно посеять. Используйте это, если у вас нет особой причины выполнять математические расчеты (т. Е. Формировать распределение для нужной кривой).

Answer 8

Умножение чисел может оказаться в меньшем диапазоне решений, в зависимости от архитектуры вашего компьютера.

Если на дисплее вашего компьютера отображается 16 цифр, то rand() будет означать, что 0,12344567890123 умножено на секунду rand(), 0,1234567890123, даст 0,0152415 то, что вы определенно найдете меньше решений, если будете повторять эксперимент 10 ^ 14 раз.

Answer 9

Большинство этих распределений происходит, потому что вы должны ограничить или нормализовать случайное число.

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

Другими словами, поскольку мы должны ограничить случайный вызов между 0 и X (X является пределом размера нашей переменной), у нас будет группа «случайных» чисел от 0 до X.

Теперь, когда вы добавляете случайное число к другому случайному числу, сумма будет где-то между 0 и 2X ... это отклоняет значения от краевых точек (вероятность сложения двух маленьких чисел вместе и двух больших чисел равна очень маленький, когда у вас есть два случайных числа в большом диапазоне).

Вспомните случай, когда у вас было число, близкое к нулю, и вы добавляете его к другому случайному числу, оно, безусловно, будет больше и будет отличаться от 0 (это будет справедливо для больших чисел, а также вряд ли два больших числа (числа, близкие к X), возвращаемые функцией Random дважды.

Теперь, если бы вы установили случайный метод с отрицательными числами и положительными числами (одинаково охватывающими нулевую ось), это больше не имело бы место.

Скажем, например, RandomReal({-x, x}, 50000, .01), тогда вы получите равномерное распределение чисел на отрицательной и положительной стороне, и если вы сложите случайные числа вместе, они сохранят свою "случайность".

Теперь я не уверен, что произойдет с Random() * Random() с диапазоном от отрицательного до положительного ... это было бы интересно увидеть ... но мне нужно вернуться к написанию кода сейчас. : -Р

Answer 10

1. Не существует такой вещи, как more random.Это либо случайно, либо нет.Случайный означает «трудно предсказать».Это не значит недетерминированный.Random () и random () * random () одинаково случайны, если random () является случайным.Распределение не имеет отношения к случайности.Если происходит неравномерное распределение, это просто означает, что некоторые значения более вероятны, чем другие;они все еще непредсказуемы.

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

3. Необходимые свойства случайных чисел важны: повторяемость и воспроизводимость, статистическая случайность, (обычно) равномерно распределенная, и большой периодНесколько.

4. Относительно преобразований случайных чисел: Как кто-то сказал, сумма двух или более равномерно распределенных приводит к нормальному распределению.Это аддитивная центральная предельная теорема.Он применяется независимо от исходного распределения, если все распределения независимы и идентичны.Мультипликативная центральная предельная теорема говорит, что произведение двух или более независимых и одинаково распределенных случайных величин является логнормальным.График, созданный кем-то еще, выглядит экспоненциально, но он действительно логнормален.Таким образом, random () * random () логнормально распределен (хотя он не может быть независимым, так как числа извлекаются из одного потока).Это может быть желательно в некоторых приложениях.Однако обычно лучше генерировать одно случайное число и преобразовывать его в логически нормальное число.Случайный () * случайный () может быть трудно анализировать.

Для получения дополнительной информации, обратитесь к моей книге на www.performorama.org.Книга находится в стадии разработки, но соответствующий материал есть.Обратите внимание, что номера глав и разделов могут меняться со временем.Глава 8 (теория вероятностей) - разделы 8.3.1 и 8.3.3, глава 10 (случайные числа).