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

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

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

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

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


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

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

Оставить комментарий

Популярные посты:

• Ранее
• Архив