Докажите, что произвольно сгенерированное число равномерно распределено

Ответ 1

Чтобы доказать, вам нужно знать используемый алгоритм и показать в терминах графа, что множество всех состояний представляет собой цикл, что нет подциклов и что мощность состояния пространство по модулю N равно нулю, так что не существует множества состояний, которые встречаются чаще/реже других. Так мы знаем, что Мерсенн Твистер, например, равномерно распределен, хотя версия с 64-разрядными версиями имеет длину цикла 2 ¹⁹⁹³⁷ -1 и никогда не может быть перечислина в течение всего времени жизни юниверса.

В противном случае вы используете статистические тесты для проверки гипотезы однородности. Статистика не может доказать результат, она не может опровергнуть гипотезу. Чем больше размер выборки, тем более убедительным является отказ от опровержения гипотезы, но это никогда не является доказательством. (Эта перспектива вызывает больше проблем со связью с нестатистиками/не учеными, чем что-либо еще, что я знаю). Существует множество тестов на единообразие, включая хи-квадратные тесты, Андерсон-Дарлинг и Колмогоров-Смирнов, чтобы назвать лишь некоторые из них.

Все тесты однородности пройдут последовательности значений, таких как 0,1,2,..., N-1,0,1,... поэтому однородности недостаточно, чтобы сказать, что у вас хороший генератор. Вы также должны тестировать последовательную корреляцию с такими тестами, как тесты расстояний, прогоны/проезды, пробеги выше/ниже среднего, тесты "день рождения" и т.д.

Довольно всеобъемлющий набор тестов для единообразия и последовательной корреляции был создан Джорджем Марсалья в течение его карьеры и опубликован в 1995 году как то, что он в шутку назвал "Diehard tests" (потому что это тяжелая батарея тестов).

Ответ 2

Для тестирования черного ящика (у вас нет доступа к исходному коду) вы не можете доказать, что он равномерно распределен (UD). Тем не менее, вы можете выполнить статистические тесты, чтобы найти вероятность того, что это UD. Запустите генератор много раз (скажем, N * X раз), и каждое число между 0 и N должно появиться вокруг X раз.

Это полностью игнорирует, являются ли это случайные числа или нет, он просто фокусируется на единообразии. Тем не менее, это только докажет, что генератор был равномерно распределен, если бы вы запускали бесконечные тесты. В лучшем случае у вас есть вероятность того, что генератор будет однородным во время первых итераций N * X, но его просто и легко реализовать.

Ответ 3

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

Ответ 4

Поскольку это интервью, реальная проблема заключается не в том, чтобы доказать равномерное распределение, а в реальной задаче выбрать выбранную для работы. Я бы предложил подход, в котором вы быстро решаете, ищет ли интервьюер интересное обсуждение передовой математики или тестирует ваше практическое мышление. Я предполагаю, что есть хороший шанс, что интервьюер будет искать последнего. Хороший ответ на интервью может быть следующим: "Все зависит от того, для чего нужен генератор случайных чисел. Если он служит для функции тасования на музыкальном проигрывателе, я бы позволил ему сгенерировать 100 номеров, проверьте, если среднее примерно равно N/2, затем кратко просмотрите цифры и может быть удовлетворен в этой точке.Если цель будет связана с шифрованием, это будет другая история, я бы начал заниматься исследованиями, но, вероятно, в конечном итоге не докажу ее сам, но полагаюсь на существующем, независимом доказательстве".

Ответ 5

Просто одно число из генератора или сколько угодно? Если только один, вы ничего не можете сказать об однородности. Пока 0 & le; число < N, это нормально.

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

Второй тест немного сложнее, так как вы можете получать шаблоны 2, 3 или даже 4 или более номера. Один тест, который я видел для триплетов, заключается в построении результатов в группах по три, в сферических координатах (сначала азимут, второй - высота, а третий - радиус). Я не помню подробностей, но IIRC вы должны видеть равномерно заполненную сферу или что-то в этом роде. Вероятно, существует формальный термин для этого теста, но в нижней строке есть ряд тестов, чтобы увидеть, что делает RNG, так что следующий номерный номер трудно предсказать из последнего номера (без видимого шаблона).

Ответ 6

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

Да, выполнение всеобъемлющего набора статистических тестов приятно, если вы хотите быть основательным. Но это может занять несколько дней или недель. В некоторых ситуациях вопрос может быть задан на встрече с кучей людей, которые хотят получить ответ сразу, и лучшим ответом может быть просто использование google прямо там на собрании, чтобы узнать, достаточно ли генератор "хорошо" в соответствии с других пользователей. Существует целый спектр ответов между "быстрым Google" и "всесторонними тестами".

Бонусные баллы за упоминание о том, что в РЕАЛИСТИЧЕСКИ вы не можете доказать, что генератор на 100% равномерен во всех ситуациях. Случаи:

1) Вы не можете посмотреть исходный код. Поэтому, даже если вы генерируете N случайных чисел, которые выглядят единообразно, нет никакого способа узнать, что каждое число из N + 1 включено 10 (например), не генерируя больше чисел. Независимо от того, где вы остановились, вы не можете предъявлять никаких претензий к номерам, которые вы еще не создали.

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

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

Ответ 7

Там доступно обсуждение этого вопроса в Принстонский компаньон по математике

Как, однако, используется детерминированный компьютер для выберите десять тысяч случайных чисел от 10 до 30 10 31? Ответ заключается в том, что на самом деле этого не нужно: он почти всегда достаточно хорош, чтобы вместо этого использовать псевдослучайный выбор....

Когда мы должны рассматривать такую ​​последовательность как "случайную"? Опять же, было предложено много разных ответов. Одна из идей - рассмотреть простые статистические тесты: мы ожидал бы, что в конечном счете частота нулей должен быть примерно таким же, как у единиц, и более как правило, любая небольшая подпоследовательность, такая как 00110 должен появиться с "правильной" частотой (которая для эта последовательность 1/32 будет, так как она имеет длину 5).

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

По этой причине фон Мизес предложил в 1919 году, что последовательность нулей и единиц следует называть случайными, если это не только случай, когда предел частоты единиц равен 1/2, но также и то, что то же самое верно для любой подпоследовательности, которая может быть извлечена "с помощью разумной процедуры". В 1940 году Церковь сделала это более точным, переведя "с помощью разумной процедуры" в "с помощью рекурсивной функции". Однако даже это условие слишком слабое: существуют такие последовательности, что не удовлетворяют "закону повторного логарифма" (то, что удовлетворяет случайная последовательность). В данный момент, так называемая тезис Мартина-Лёфа, сформулированный в 1966 году, одно из наиболее часто используемых определений случайно- n: случайная последовательность - последовательность, которая удовлетворяет всем "эффективные статистические последовательные тесты", понятие, которое мы не можем сформулировать именно здесь, но которое использует в существенным образом определяется понятие рекурсивной функции. От контрастирует с тезисами Церкви, с которыми почти каждый математик согласен, тезис Мартина-Лёфа все еще очень обсуждается.

Ответ 8

Это немного жестокий вопрос для интервью (если только это не была исследовательская позиция), но интересный для форума. 20 лет назад, после окончания моей математической степени, я бы весело представил случайный генератор, написанный мною, с математическим доказательством того, что он был случайным. Теперь, глядя на этот код, мне трудно поверить, что я его написал. В наши дни я делаю то, что сделал бы любой практический программист, и использовал алгоритм, реализованный NAG, numpy, matlab или каким-либо другим хорошо уважаемым пакетом (я доверяю NAG) и, возможно, сделаю простой статистический анализ, чтобы проверить, было ли распределение критичным по тем или иным причинам.

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