о случайности

[avva]

В блоге о теории сложности Билл Гасарк недавно рассказал забавную историю (англ.), которую я перескажу.

Лектор дал студентам домашнее задание: подбросить монету 600 раз и записать последовательность О и Р (орлов и решек). Он предупредил их также, что если они попробуют просто написать случайную последовательность сами из головы, не подбрасывая, он это обнаружит. И действительно, в тех заданиях, что он собрал у студентов, в двух из них не было ни разу подряд шесть орлов или шесть решек - надежный знак того, что последовательность не случайная. Лектор вызывает к себе этих двоих студентов. Первый признается, что он действительно просто записал О и Р, как ему казалось случайным. Зато второй утверждает, что он на самом деле подбрасывал монету 600 раз и записывал за ней, но когда он увидел шесть орлов подряд, то подправил результат, потому что подумал, что учитель увидит эти шесть орлов подряд и решит, что последовательность не случайна.

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

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


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

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

Comments

[dmytro kharchenko (from livejournal.com)]

Шестигранный карандаш отлично заменяет собой кубик d6.

[amarao-san.livejournal.com]

чётные/нечётные номера (буквы по порядку алфавита) на купюрах.

[gaz-v-pol.livejournal.com]

Я бы попробовал вычислять sqrt(2) в надежде, что его цифры случайны (это, насколько я понимаю, не доказано). И добавил бы к каждой цифре последнюю секунду того времени, в которое я её вычислил. Это уж точно случайно.

[nechaman]

Я думала смотреть на улицу и смотреть кто пересекает какую-нибудь условную линию. Мужчина - 0, женщина - 1. (Или наоборот)
Недостаток, что число мужчин и женщин на улице может быть изначально не одинаково по какой-то социальной причине. Но проще, чем ваш способ.

[murchik007.livejournal.com]

Просто взять меню и просмотреть цены сверху вниз.

Четная цифра - ноль, нечетная - единица, ну или наоборот.

Неутомительно и довольно рандомально.

[vodianoj.livejournal.com]

Да, мне тоже именно это пришло в голову, но тут проблема, что это кажется мне очень медленным и трудоёмким методом. Вот тут автор подсчитывет Пи с точностью до 14 знаков: http://www.cygnus-software.com/misc/pidigits.htm

[vodianoj.livejournal.com]

Боюсь, что не будет рандомально. Цены в меню часто красивые.

[p_govorun.livejournal.com]

Классическая история из Перельмана: двое пытаются именно так определить случайность -- и тут проходит рота солдат.

[r-l.livejournal.com]

Несколько стихотворений, которые Вы помните наизусть - чет/нечет (кол-во букв в словах). Для надежности - строчки стихов разных размеров вперемежку (можно просто по строчке из разных текстов вспоминать). Должно быть вполне себе рандомальненько. (Правда, довольно долго. Можно было бы брать гласные/согласные первых слов, но русский язык тут будет давить.)

[timur0.livejournal.com]

если есть тетрадь и карандаш, то без проблем. для простоты считаем, что тетрадь в клеточку - шахматная раскраска даст 0 и 1. теперь держим карандаш под углом 45 градусов к плоскости стола, острие сверху, под ним - тетрадь. отпускаем карандаш - он падает на стол незаточенным концом, отскакивает и острие карандаша попадает на тетрадь и делает там отметку. осталось только взять цифру из той клетки, куда попал карандаш.
плюсы способа - достаточно случайно, легко реализуемо.
минусы - карандаш может сломаться, окружающие посмотрят как на идиота.

[r-l.livejournal.com]

Угу.

[murchik007.livejournal.com]

Красиво - понятие относительное

[irene221b.livejournal.com]

Нет, цены в меню совершенно не рандомальны. Там кластеры, корреляции, х.99 и т.п.

[bsivko.livejournal.com]

См. закон Бенфорда.

[p_govorun.livejournal.com]

Пусть тетрадь у нас будет в клетку. Тогда рисуем произвольную закорюку. Берём вертикальную линию сетки, разбиваем интервалы сетки на ней на пары. Берём только те пары, которые закорюка пересекает ровно один раз. Если она пересекает верхнюю клетку пары -- 1, нижнюю -- 0.

(Разлиновать клетку можно и самому. Точности не требуется.)

[vels.livejournal.com]

А почему просто не разорвать листочки из тетради на много квадратиков, на половине написать 0, на другой - 1. Все хорошо перемешать,после чего вытаскивать квадратик, проверять бит и замешивать его обратно.

Слишком банально ? )

[janatem.livejournal.com]

Цифровые часы, которые показывают секунды, — достаточно эффективный ГСЧ, если не пользоваться ими слишком часто. Еще бывают часы с секундомером, который показывает в миллисекундах, это еще удобней.

[dzz.livejournal.com]

Расчерчиваем лист бумаги на небольшие клетки и объявляем их "чёрными" и "белыми" по принципу шахматной доски. Далее не глядя тыкаем в произвольное место листка карандашом, смотрим на результат.

[p_govorun.livejournal.com]

Цифры sqrt(2) не случайны, в том смысле, что они составляют sqrt(2). Думаю, что это противоречит условию задачи.

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

[nameless--one.livejournal.com]

с миллисекундами - лучший метод пожалуй из всех вышепредложенных

[amarao-san.livejournal.com]

Когда нас на первом курсе учили методологии измерения и заставляли записывать милисекунды результата измерения (соседняя группа записывала точную частоту, выставляемую аналоговым генератором с ручкой), всё закончилось тем, что народ приловчился выставлять желаемое значение. Да-да, милисекунды. Точнее, десятки милисекунд (на часах было два знака).

[phoonzang.livejournal.com]

итерировать логистическое отображение (http://en.wikipedia.org/wiki/Logistic_map) для значения парамететра из хаотического режима и брать четность, скажем, третьей цифры после запятой

[phoonzang.livejournal.com]

ну или tent map (http://en.wikipedia.org/wiki/Tent_map), если не хочется выполнять умножения

[nameless--one.livejournal.com]

я не говорю что идеально рэндомный

а на каком отрезке народ это значение выставлял? вряд ли на десятке секунд

[iisus.livejournal.com]

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