Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

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

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

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

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

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 150 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →