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

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

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

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

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

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

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

Page 1 of 3 << [1] [2] [3] >>

Flat | Top-Level Comments Only

From:

dmytro kharchenko (from livejournal.com)

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

From:

vzaliva.livejournal.com

я тоже сразу про это подумал.

From:

amarao-san.livejournal.com

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

From:

gaz-v-pol.livejournal.com

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

From:

vodianoj.livejournal.com

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

(...)

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

Page Summary

Style Credit

Expand Cut Tags