Max Home IndustryОкружной суд США вынес решение о значении слова «строго случайный» и вынес математическое решение.
Если бы вас попросили реализовать случайный алгоритм, я надеюсь, вы бы знали, как это сделать, хотя мелкие детали могут оказаться сложными, даже если вы думаете, что понимаете.
Ранее в этом году возникла проблема с розыгрышем зеленых карт США, и через две недели после розыгрыша результаты были аннулированы. Система «Зеленая карта» — это лотерея, которая позволяет людям выиграть ПМЖ США, и слово «лотерея» должно дать вам представление о требованиях программы, которая ее реализует.
Проблема заключалась в том, что розыгрыш не был случайным ни в каком разумном смысле.
Подали заявки более 19 миллионов человек, и когда в мае 2011 года были объявлены результаты, стало ясно, что более 90% победителей подали заявки в первые два дня 30-дневного периода подачи заявок. Это не может быть случайным в обычном понимании этого слова, поэтому лотерея была признана недействительной.
Конечно, людям, которые выиграли, не понравилась идея, что они сначала выиграли, а потом нет, и поэтому они подали иск в федеральный суд. Их аргумент заключался в том, что, хотя выборка была предвзятой, модель не была идеальной, поскольку около 2% были выбраны из других времен входа. Кроме того, процесс отбора был в некотором смысле «произвольным» и, следовательно, снова следовал принципу «случайности».
Другой замечательный аргумент заключался в том, что, поскольку список был составлен из-за «компьютерной ошибки», он действительно был «случайным». Чтобы быть более точным, они утверждали, что:
«компьютерная ошибка … не может быть приравнена к неслучайности … если компьютерная ошибка приводит к появлению списка имен — любых имен — тогда список должен быть случайным, поскольку он был« бессмысленным »и« случайным ».
Суд, похоже, долго и тщательно обдумывал значение слова «случайный» и пришел к выводу, что любой процесс, в результате которого было выбрано 90% заявок в первые два дня, не может быть случайным, и поэтому отклонил иски.
«Более того, Суд не считает, что решение Департамента отменить лотерею, которая не соответствовала единственному наиболее важному критерию розыгрыша: случайный выбор, было произвольным или капризным».
Но как все это произошло. По данным Госдепартамента:
«Государственный департамент использовал новую программу рандомизатора для лотереи DV 2012 года, которая, как выяснилось, содержала ошибку в процессе, которая« сделала программу рандомизатора неэффективной ». Вместо того, чтобы указывать компьютеру выбрать победителей, поскольку они были переупорядочены и рандомизированы на втором этапе, компьютер просто выбрал записи в том порядке, в котором они были изначально пронумерованы ».
То есть настоящая ошибка!
Следующий вопрос, который возникает у любого программиста, — почему тогда в выборку не вошли все люди, которые подали заявку первыми. То есть, почему это не был отбор строго в порядке очереди? Ответ немного странный:
«Программа базы данных затем сохраняла петиции в физическом месте на жестких дисках, по большей части в том порядке, в котором они были получены. Однако из-за большого количества полученных петиций для лотереи — более одной петиции в секунду — база данных не могла сохранить петиции в том последовательном порядке, в котором они были поданы, со 100% точностью. В некоторых случаях программа «записывала петицию в удаленном месте на жестком диске и временно оставляла пустое место или разрыв на жестком диске рядом с тем местом, где была записана предыдущая петиция.
Программа базы данных позже заполнила пробелы петициями, поданными позже, чем предполагалось в противном случае их числовое размещение в базе данных ».
Нет, в этом нет большого смысла. Хранение вещей в базе данных обычно не влияет на результат какого-либо процесса — если только это не Госдепартамент, использующий систему перфокарт …
Итак, фиаско было вызвано какой-то неопределенной ошибкой, которая каким-то образом теряла случайную функцию в процессе выбора.
Больше мультфильмов на xkcd
Интересно то, что есть проблема — уж точно случайность или, по крайней мере, псевдослучайность настолько очевидна, что решение суда не требуется?
Если вы так думаете, попробуйте решить, будет ли следующий алгоритм законным.
Проиндексируйте все записи последовательно по мере их поступления.
Перемешайте всю базу данных в случайном порядке, используя: сканирование всей базы данных и замена каждой записи произвольной записью, выбранной из всей базы данных.
Теперь возьмите первые N записей в качестве выбранного набора.
То есть в коде — при условии, что есть M записей:
for (int i = 0; i