Что такое случайность

23

Я студентка факультета компьютерных наук и в настоящее время обучаюсь на курсе по системному моделированию и моделированию. Он включает в себя взаимодействие с повседневными системами вокруг нас и моделирование их в различных сценариях путем генерации случайных чисел в различных кривых распределения, таких как, например, IID, Gaussian и т. Д. Я работал над проектом boids, и меня просто поразил вопрос, что же на самом деле является «случайным»? Я имею в виду, например, что каждое случайное число, которое мы генерируем, даже в наших языках программирования, например, с помощью Math.random()метода в Java, по существу генерируется по «алгоритму».

Откуда мы на самом деле знаем, что последовательность чисел, которую мы производим, является на самом деле случайной и поможет ли нам, как можно точнее, смоделировать определенную модель?

mak7
источник

Ответы:

18

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

Вот интуитивный пример, который действительно мешал людям в тот день. Рассмотрим последовательность бросков монет. Результатом одного броска является либо голова ( ), либо хвост ( T ). Скажем, мы делаем два эксперимента, где мы подбрасываем монету 10 раз. Первый эксперимент E 1 дает нам Н , Н , Н , Н , Н , Н , Н , Н , Н , Н . Второй эксперимент E 2 дает нам T , T , H , T , H ,HTE1H,H,H,H,H,H,H,H,H,HE2 . Посмотрев на результат, вы можете испытать искушение заявить, что с монетой в E 1 что-то не так , или, по крайней мере, по какой-то странной причине то, что вы получили, не случайно. Но если предположитькак H и T являются вероятным (монета является справедливым), вероятность получения либо Е 1 или Е 2 равно ( 1 / 2 ) 10 . Фактически, получениелюбойопределенной последовательности так же вероятно, как и любой! Тем не менее, E 2 чувствуетT,T,H,T,H,T,T,H,T,HE1HTE1E2(1/2)10E2 случайный, а нет.E1

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

Юхо
источник
Для бесконечных последовательностей у нас есть намного больше инструментов для определения случайности, например, нормальности.
Денис
1
@dkuper Обратите внимание, что все бесконечные последовательности, начальные сегменты которых являются случайными в соответствии с определением сложности Колмогорова, будут нормальными, но их нормальности недостаточно для того, что можно считать действительно случайным. Например, существуют нормальные числа, у всех начальных сегментов которых больше 1, чем 0.
Куинн Калвер
@Quinn Culver Да, я согласен, нормальность была лишь примером дополнительного инструмента, который мы имеем (среди прочих) для бесконечных последовательностей. Колмогоровская сложность и другие по-прежнему полезны.
Денис
8

В случае Java (или аналогичных языков) мы знаем алгоритм, используемый для создания случайных чисел. Если он начинается с одного начального числа, числа вовсе не случайны, т. Е. Если мы знаем в последовательности a 0 , , a n , мы знаем a i + 1 или задаем как условную вероятность: k , l , i : P ( a i + 1 = k a i = l ) { 0 ,aia0,,anai+1

k,l,i:P(ai+1=kai=l){0,1}

Тем не менее, эти ряды могут соответствовать свойствам (см., Например, WP: Автокорреляция ), которым соответствуют случайные числа, и этих свойств часто достаточно для выполнения задач, где мы хотели бы использовать «реальные» (например, сгенерированные каким-либо физическим процессом) случайные числа, но можем: Усилие их.

frafl
источник
3

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

(μ=0,σ=1)1

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

Джонатан
источник
3

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

AA

  • все машины Тьюринга, которые всегда останавливаются
  • все семейства схем полиномиального размера
  • все машины Тьюринга за полиномиальное время
  • все машины Тьюринга

A(Xn)Xn{0,1}nϵAAA

|Pr[A(Xn)=1]Pr[A(Un)=1]|ϵ,
{ 0 , 1 } nUn{0,1}n

Эта идея стоит за любым современным формальным понятием псевдослучайности.

Сашо Николов
источник
2

Вот еще два цента.

Один из способов думать о рандомизированных алгоритмах состоит в том, чтобы изобразить блок, который принимает некоторые входные данные, делает загадочные вещи с этим входным сигналом и производит некоторые («непредсказуемые») выходные данные.

Но вместо этого было бы полезно думать о них как о детерминированных алгоритмах, которые принимают два входа: «истинный» вход и некоторые «случайные» входные данные, которые мы получаем из функций, подобных Math.Random().

[0,1]nlogn

[0,1]nlogn

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

усул
источник
-2

Мы не можем генерировать действительно случайные числа. Существуют разные способы генерации псевдослучайных чисел с использованием заданного уравнения и конкретного начального значения. Таким образом, случайная последовательность чисел зависит от начального значения. Как только мы узнаем начальное значение, мы можем предсказать, какой будет последовательность. Помимо этого есть другие методы для генерации случайных чисел. Сейчас люди используют некоторые методы для генерации истинных случайных чисел, например, время движения головки диска и другие физические методы, которые можно встроить в компьютер. См. Http://en.wikipedia.org/wiki/Random_number_generation#Generation_methods.

user2447174
источник
lavarnd.org
Джефф
-3

с помощью данного метода, как вы сказали
Math.random () в Java
Randomize; Случайная (п); в Дельфи

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

Спасибо.

кличка
источник
2
Как это отвечает на вопрос «откуда знать, что последовательность случайна»?
Юхо
как я уже сказал. просто ... где "случайный" можно рассматривать как мошенничество, но это не влияет на его случайный эффект. Затем заставьте его гордиться и постройте свою логику. Просто.
ник
-4

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

  • «истинная / реальная случайность» происходит с физическими процессами низкого уровня и «шумом», таким как в стабилитронах, квантовой механике и т. д., которые могут использоваться в аппаратных ГСЧ

  • другие числа, генерируемые в компьютерной сфере, - это то, что известно как «псевдослучайный», который имитируется и никогда не может совпадать с «истинной случайностью». это так называемые PRNG

  • существует важный смысл «криптографической стойкости генераторов случайных чисел», который в некотором смысле измеряет их «качество» или «безопасность», см., например, криптографически безопасный PRNG . в основном, «слабый» генератор не имеет такой сложной вычислительной сложности, как «жесткий» генератор, а «слабый» генератор легче сломать.

  • O(n)O(n2)=?Доказательство NP должно иметь определенную «сложность», в противном случае тот же метод анализа может быть использован для взлома PRNG, и, более того, несколько удивительно, что большинство или, возможно, все разделения / методы класса сложности, известные на эту дату (или, возможно, даже впоследствии, на сегодняшний день ), делают не имеют достаточной сложности.

  • Важной темой исследования в TCS являются рандомизированные и дерандомизированные алгоритмы . идея состоит в том, чтобы примерно изучить, насколько сильно алгоритм изменяется путем замены «истинной случайности» на PRNG, и существуют различные глубокие теоремы на эту тему. Вот высокоуровневый вопрос cstheory.se, который дает некоторое представление об исследованиях в этой области: эффективные и простые рандомизированные алгоритмы, где детерминизм труден

  • Еще одна ключевая тема в TCS - информационная энтропия - изначально введенная в физике - которая изучает тесно связанную концепцию «информационного дисупорядочения» и, как и некоторые другие важные концепции в (T) CS, представляется одной из ключевых идей, которые пересекаются Граница между прикладным и теоретическим анализом даже по некоторым формулам совпадает .

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

ВЗН
источник
И не только программисты, конечно, заинтересованы в «случайности». Вероятно, это нестареющий вопрос, рассматриваемый также с религиозной и философской точек зрения.
Юхо
согласен, также в физике это ключевая концепция при изобретении QM и дебатов Бора-Эйнштейна , Bells thm , и до сих пор мотивирует «теории скрытых переменных» снова активной областью исследования. так что, как вы говорите, возможно, никто не знает, что это такое, но многие все еще работают над поиском более точного ответа, пока мы говорим.
vzn
более подробно об актуальности случайности для угла P против NP, она проявляется в «точке перехода» удовлетворяемости и клики, например, как в этой статье «Монотонная сложность k-клики на случайных графах » Россмана
vzn
перерыв
обзор случайности в CS от Wigderson RANDOMNESS И PSEUDORANDOMNESS
vzn