­
­

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

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

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

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


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

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

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

Предыдущие записи блогера :
Архив записей в блогах:
Это письмо так называлось. И я решила взять его отдельно, мне кажется, здесь есть о чем поговорить. "Привет, Катя. Вдохновилась постом "Женсовет", но немного негодую. Хочу развеять представление о мини и чем-то неординарном своими луками, кому за 30. Мне как раз 32, и я вовсю ношу ...
Гиперэпиграф: Николай Заболоцкий Аналогом Satisfactory чаще всего называют Factorio, но это не совсем так. Во-первых, заводостроительство – это уже целый субжанр, таких игр много, они попадаются даже на мобильных платформах. Во-вторых, Satisfactory полностью трехмерна и с видом от ...
Знаете, какое самое частое обвинение слышу я в свой адрес на просторах тырнета? Нет, как ни странно, не бл..ь. Тролль!!! Вначале, я не могла понять, какое отношение имею я, вся такая девочка-ромашка, к этим злым огромным гоблинам. В общем, первые ...
Есть такая поговорка: лучшим средством противовоздушной обороны являются свои танки на вражеском аэродроме. Впервые немцам советскую ПВО пришлось ощутить еще в 1941 году, а потом была станица Тацинская и много где еще. Ну а дальше была 1945 года. Там уже "всем спасибо, все свободны" ...
Здравствуйте, меня зовут Наталья и я приглашаю вас провести 4 мая в прекрасном горном городе Далате (тэга для города, к сожалению, не нашла), во Вьетнаме, со мной и моим молодым человеком, вместе с нами посетить несколько храмов, выпить ароматного кофе, закупиться на местном рынке и просто ...