Алгоритм генерации случайных чисел для человеческого мозга? [закрыто]

37

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

Спросил это на SO, но это не вызвало особого интереса. Может быть, это лучше подходит для программистов.

Магнус Вольффелт
источник
7
@ S.Lott Не думаю, что это абсурд. Непрактично? Почему конечно. Абсурд? Конечно, нет. И даже если бы это было так, абсурд может проложить путь для новых полезных мыслей.
Бизиклоп
21
9 .... 9 .... 9 .... 9 - Вы не можете доказать это не случайно.
13
С.Лотт: Идея простого вычисления генератора псевдослучайных чисел вовсе не абсурдна. Я думаю, что ОП хочет избежать человеческой предвзятости здесь ...
Jens
8
Я нахожу забавным (и в то же время немного удручающим), что многие люди, похоже, ценят аргумент невежества. «Я не могу себе это представить, поэтому оно не может существовать» или ответы, в которых полностью отсутствует смысл.
biziclop
4
Этот вопрос, кажется, не по теме, потому что он касается когнитивных способностей человека, а не программирования.

Ответы:

36

Вот алгоритм от Джорджа Марсалья :

Выберите двузначное число, скажем, 23, ваше «семя».

Сформируйте новый 2-значный номер: 10-значный плюс 6 раз цифры единицы.

Пример последовательности: 23 -> 20 -> 02 -> 12 -> 13 -> 19 -> 55 -> 35 -> ...

и период равен порядку множителя 6 в группе вычетов, относительно простых к модулю 10. (в данном случае 59).

«Случайные цифры» - это единицы измерения двухзначных чисел, т. Е. 3,0,2,2,3,9,5, ... мод последовательности 10. Арифметика достаточно проста для выполнения в вашем голова.

Davo
источник
Это звучит действительно хорошо.
biziclop
4
Это не может быть проблемой для потребностей конкретного человека, но это дает вам только 90 различных потоков.
Compman
5
79, 79, 79, 79, 79, 79, 79, 79, 79, 79, о нет! Я предполагаю, что вы должны остаться <= 60, что хорошо работает, потому что вы можете использовать часы для семян, если у вас их нет.
Ред.
4
@eds Гм, что? 79 -> 61 -> 15 -> ...
Изката
1
Возможно, @eds означало 59. Все числа от 1 до 58 выглядят как честная игра.
Эрханнис
26

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

Отказ от ответственности: я сам не пробовал; когда мне нужно достаточно случайное число, я либо получаю какой-то вывод /dev/random, использую его randна любом удобном для меня языке, либо бросаю свой верный d20.

Если вы вундеркинд, метод средних квадратов является довольно вычислительным, хотя и ненадежным методом.

Inaimathi
источник
3
+1 Я думаю, что это первый серьезный ответ на этот вопрос. Немного грустный.
Jens
@Magnus Wolffelt - я вспомнил, что он упоминался в выступлении Рона Эглаша на TED о культурном значении фрактальной геометрии в Африке; "Гадание на песке Бамана". Это довольно интересно, хотя я до сих пор понятия не имею, для чего вы сейчас будете использовать эту технику, поскольку нам больше не нужны предсказатели. ted.com/talks/ron_eglash_on_african_fractals.html
Инамати,
1
Насколько я вижу, этот геомантический метод просто позволяет вам «улучшить» (я полагаю, что «debias» будет лучше) источник случайности. Не для чихания, но не для того, что ищет ОП. Который не должен сказать, что это не симпатично ....
Норман Грей
@Norman Grey - человеческий мозг может придумать произвольные числа по умолчанию.
Инамати
@Inaimathi Точно: именно поэтому смещение чисел будет важно, и почему метод, на который вы указали, полезен. Или я вас неправильно понимаю.
Норман Грей
10

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

Затем вы должны выбрать довольно случайную его часть, максимально исключив неосознанную предвзятость. Например, для этого можно выбрать песню, выбрать число kот 10 до 20, а затем найти kбукву th в ее тексте.

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

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

biziclop
источник
Даже тогда я ожидаю, что вы будете предвзяты по нескольким тонким причинам. (IE стремится выбрать одну и ту же группу песен)
Zachary K
@ Zachary K Без сомнения, но тогда вам также нужно будет выбрать число, которое немного распространяет его. Хотя предвзятость никогда не удастся устранить, этот метод почти наверняка не позволит вам узнать, какую букву вы выберете (хотя со временем вам придется запомнить некоторые из них).
Бизиклоп
Эйни мини минь мо, как мы привыкли делать в детстве.
Захари К
2
«выберите число k от 10 до 20». 17. Наименьшее случайное число.
S.Lott
@ S.Lott Неважно, насколько случайным является это число. Единственная причина, по которой вам это нужно, - это то, что вам легче запомнить первые несколько букв вещей.
Бизиклоп
9

Попробуйте ваши часы.

Я делаю это, если мне нужно случайное число с коэффициентом 60 (секунд). Возьмите соответствующий модуль по времени. 4:17:23 вечера, имитируя бросок кубика, становится 5.

Марк Канлас
источник
И за большое количество в минуту?
Гэри Роу
Не уверен, что я следую. Вы говорите, что сделать пул чисел 3600, включая минуты? Я думаю, но чем больше число, тем менее случайным оно будет? Как будто вы не могли быстро взять образцы так же легко.
Марк Канлас
1
Боюсь, этот критерий должен быть отменен просто потому, что независимо от используемого метода, человеческий мозг просто слишком медленный.
Бизиклоп
Извините, мне просто интересно, как работает ваш подход, если вам нужно более 60 номеров в минуту. Оглядываясь назад, просьба о том, чтобы человеческий мозг производил такое количество цифр в минуту, в любом случае доведет его до максимума, так что не беспокойтесь об этом.
Гэри Роу
@biziclop Нет проблем. Похоже, я столкнулся с комментарием при рассмотрении ситуации с подходом @ Mark.
Гэри Роу
5

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

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

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

Конрад Рудольф
источник
Мне кажется, важно, чтобы подсчет выполнялся быстро - подсчитывающий должен следить за тем, чтобы не считать ритмично, всего около 1 или 2 шагов в секунду. Потому что должно быть значительное количество циклов (интуитивно ≥4) через все числа, чтобы достичь достаточной энтропии.
Аарон Тома
Предложение по улучшению для лучшей случайности : подсчитывающий выбирает секретное случайное зерно X₀ между 0 и модулем первым; в сочетании с подсчетом это должно обеспечить приличную случайность при минимальных усилиях мышления (даже при подсчете медленно, относительно продолжительности подсчета; т.е. малое количество циклов - интуитивно ≥2 будет хорошо; <2 будет в порядке).
Аарон Тома
4

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

Во-первых, мы должны спросить «что такое настоящая случайность»? Такие дискуссии быстро вырождаются в философские воды, но суть в том, что «вселенная действительно случайна»? Другими словами, если вы квантоваете время и материю, можете ли вы вычислить следующее состояние вселенной из текущего? Если да, то вселенная детерминирована и в ней нет случайности (понимаете, что я имею в виду под «философским»?)

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

Простейшим генератором псевдослучайных чисел было бы что-то вроде знаменитого алгоритма Дилберта «9 .. 9 .. 9 ..». Но интуитивно это не кажется очень хорошим (что, конечно, шутка). Статистики разработали целый ряд тестов, чтобы сказать, является ли последовательность предположительно случайных выходных данных «хорошей». Начните со страницы Википедии для «теста хи-квадрат», и вы можете провести день, просто читая об этих тестах.

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

Следующим шагом в «доброте» является «криптографически сильная случайность», что означает, что при заданной последовательности a1, a2, ... вы не можете предсказать следующее число в последовательности с «разумной вероятностью», если не будете использовать много вычислений. Эти числа иногда называют «вычислительно псевдослучайными». Один из распространенных способов получения такой последовательности - через «хэш-цепочку», подобную этой: a1 = SHA512 (a2), a2 = SHA512 (a3), ... Поскольку мы считаем (основываясь на опыте, а не математическим доказательством), что SHA512 вычислительно трудно инвертировать, мы считаем, что a2 «невозможно» предсказать, учитывая только a1.

Итак, теперь возникает вопрос: что лучше всего делать людям по правилам, изложенным в вашем вопросе? Люди, как известно, плохо генерируют случайность; раньше был веб-сайт, на котором вы пытались бы генерировать броски монет, «случайным образом» печатая H, T, T, H, H, T, T и т. д., как если бы вы подбрасывали монету (но вы делаете это в твоя голова). Через некоторое время веб-сайт начнет предсказывать ваши сальто лучше, чем в 50% случаев (используя скрытую марковскую модель). Мы просто плохи в этом.

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

Fixee
источник
1
Хотя вопрос о том, существует ли действительно случайный физический процесс, является предметом споров (хотя эксперименты с парадоксом ЭПР предполагают положительный ответ), теоретическое определение случайной последовательности существует, основываясь на сложности Колмогорова.
Бизиклоп
3

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

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

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

Kramii Восстановить Монику
источник
1
И эти физические устройства действительно имеют непредсказуемую природу, поэтому в некотором смысле они более случайны, чем лучшие компьютерные алгоритмы.
Омега Центавра
( @OmegaCentauri: Естественно, я вижу, что ты там делал; о) (Не уверен, что каламбур был задуман, но мне это нравится. :)) )
Аарон Тома,
3

Высоко рандомизированное, большое количество в минуту и ​​генерируется людьми? Не случится

Основные проблемы, с которыми вы столкнетесь:

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

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

Не по теме, но интересно

Хотя это не механизм для генерации случайных чисел в голове, то алгоритм Solitaire (как изображается в Нил Стивенсон Криптономикона ) демонстрирует , насколько трудно использовать случайные числа для криптографических целей. Для создания достаточно безопасного выхода требуется только колода обычных игральных карт, но метод достаточно сложный.

Гэри Роу
источник
1
Я думаю, что это не отвечает на вопрос. 4 пункта вашего ответа применимы, только если люди пытались найти случайные числа без алгоритма. Я думаю, что ОП знает об этом, и именно поэтому он спрашивает алгоритм, который люди могут сделать в своей голове и дать хорошие результаты, т.е. не страдают от проблем, упомянутых в вашем ответе.
FabianB
2

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

Пожалуйста, отойдите от стола и отправляйтесь в Лас-Вегас.

Человечество имеет десятки рандомизированных процедур. Вы можете увидеть их все в Лас-Вегасе.

У вас есть вращающиеся круги. У вас есть кувыркающиеся кубики. И вы перетасовали токены. Все они работают на удивление хорошо.

Кубики, пожалуй, самые старые. Очевидно, в одной точке использовались удлиненные 4-сторонние палки. Симметричные кубические суставы овец были популярны в течение тысячелетий. Мы использовали такие рандомизаторы с тех пор, возможно, в то же время, когда разрабатывали язык.

http://itunes.apple.com/us/app/motionx-dice/id287509231?mt=8

«Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха»

--- Джон фон Нейман

С. Лотт
источник
7
Пониженное голосование - меня не интересуют внешние инструменты для генерации случайных чисел, а скорее встроенные алгоритмы, которые могут полагаться на память или стимул для генерации действительно случайных чисел.
Магнус Вольффелт
3
Вы не можете бросать кости в своей голове
JK.
2
@ jk01: правильно. Вы не можете делать случайные в своей голове, либо.
S.Lott
@ S.Lott - Я думаю, что вы хотите сказать: «Типичный человек не может генерировать последовательно случайные числа в своей голове с высокой скоростью, используя наивный метод и никакие внешние инструменты».
Инамати
1
@Inaimathi. Нет, я говорю что-то гораздо более сильное. Вы не можете сделать случайным в своей голове. Ваш мозг полон уклонов, поэтому вам нужен алгоритм. Конечный, эффективный, детерминированный алгоритм не является случайным. Вы просто не можете этого сделать. Ни один достаточно простой алгоритм не является даже псевдослучайным, поэтому вы не можете приблизить случайный. Кости маленькие, удобные и имеют долгую и долгую историю использования.
S.Lott
1

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

Если мне нужны случайные числа, я обычно бросаю кости.

Захари К
источник
0

Вы просите LCM, который вы можете сделать в своей голове? Обратите внимание, что идея, что это лучше, чем игра в кости, остается абсурдной.

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

http://www.vias.org/simulations/simusoft_lincong.html

http://www1.i2r.a-star.edu.sg/~knandakumar/nrg/Tms/Probability/Probgenerator.htm

U_ {k + 1} = (a \ times U_k + b) mod (m + 1).

Легче увидеть, что это делает, если мы выберем маленькие значения a = 5, b = 1 и m = 7. Вы должны быть в состоянии сделать это в своей голове.

С. Лотт
источник
Интересно, есть ли прилично случайная версия этого ( линейный конгруэнтный генератор (LCG) ), который действительно легко сделать в голове? а = 1 в идеале, а = 2 в идеале. (Мои мысли об этом пока в следующем комментарии.)
Аарон Тома
(( Я думал, что a = 1, b простое, b умно выбранное, может быть более приемлемой альтернативой для больших m, что все равно будет работать хорошо. Тогда я заметил, что, вероятно, это не так: для b≈0 или b≈m это будет проходите довольно последовательно по номерам, поэтому я подумал, что b≈m / 2 - это ответ, но потом я заметил, что он также может быть последовательным (для малых | b – m / 2 | / m), только в двух положениях поочередно. b≈m / 3, он может быть последовательным, чередуясь между 3 позициями, для b≈m / 99 проблема больше не будет в чередующейся форме, но для циклического обхода одного вычитания по модулю потребуется ~ 99 шагов. ))
Аарон Тома