Об одной распространённой ошибке
Feb. 26th, 2018 09:00 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
a_shenОб одной распространённой ошибке при интерпретации результатов работы вероятностных алгоритмов.
Один мой знакомый (весьма уважаемый экономист) опубликовал запись, в которой рассказал, что ему прислали на день рожденья число, которое, будучи записанным цифрами в прямоугольнике, выглядит как его портрет (за счёт того, что одни цифры темнее, а другие светлее), и написал, что простота этого числа проверена вероятностным алгоритмом, с помощью которого установлено, что это число является простым с вероятностью не менее 1-eps (при очень малом eps), и потому с практической точки зрения его можно считать простым.
В чём тут ошибка? Формально можно сказать, что вообще некорректно говорить о том, что данное число является простым с такой-то вероятностью: оно либо является, либо не является, и никакого вероятностного пространства тут нет. Свойство же алгоритма (который получает на вход проверяемое число и использует случайные биты) состоит в другом: что на любом простом числе он всегда даёт ответ "простое", а на любом составном числе даёт ответ "составное" с вероятностью не менее 1-eps. Вероятность тут означает долю последовательностей случайных битов, дающих соответствующий ответ.
Можно было бы считать сказанное моим знакомым допустимой вольностью речи, но это не так - в этом рассуждении есть ошибка по существу (весьма распространённая, американское статистическое общество даже публиковало специальное разъяснение по аналогичному поводу, http://amstat.tandfonline.com/…/10.10…/00031305.2016.1154108). Чтобы объяснить, в чём она состоит, сделаем дополнительные предположения (не противоречащие сказанному):
(а) используемый вероятностный алгоритм на любом составном числе говорит "составное" с вероятностью равно 1-eps (и говорит "простое" с вероятностью eps; вероятность берётся по внутренним случайным битам).
(б) программа генерации картинки перебирает картинки из нужного класса (дающие при печати в прямоугольнике искомый портрет) и для каждой запускает алгоритм проверки простоты, пока не найдёт такую, где алгоритм даст ответ "простое"
(в) по каким-то таинственным законам теории чисел все картинки из нужного класса (соответствующие числа) оказываются составными.
Тогда программа, сделав в среднем 1/eps проб, выдаст картинку нужного класса, на которой алгоритм дал ответ "простое". Тем не менее соответствующее число будет гарантированно составным. (Конец объяснения ошибки.)
Другое дело, если бы именинник, получив такой подарок, собственноручно запустил бы на нём вероятностный алгоритм проверки, при этом бы ещё использовал не псевдослучайные биты от генератора, а собственнноручно бросал монету. Тогда с практической точки зрения вывод "можно считать простым" был бы корректным.
В заключение прошу прощения за занудство, но такая ошибка представляется мне распространённой и опасной, и пройти мимо удачной иллюстрации я не смог.
Один мой знакомый (весьма уважаемый экономист) опубликовал запись, в которой рассказал, что ему прислали на день рожденья число, которое, будучи записанным цифрами в прямоугольнике, выглядит как его портрет (за счёт того, что одни цифры темнее, а другие светлее), и написал, что простота этого числа проверена вероятностным алгоритмом, с помощью которого установлено, что это число является простым с вероятностью не менее 1-eps (при очень малом eps), и потому с практической точки зрения его можно считать простым.
В чём тут ошибка? Формально можно сказать, что вообще некорректно говорить о том, что данное число является простым с такой-то вероятностью: оно либо является, либо не является, и никакого вероятностного пространства тут нет. Свойство же алгоритма (который получает на вход проверяемое число и использует случайные биты) состоит в другом: что на любом простом числе он всегда даёт ответ "простое", а на любом составном числе даёт ответ "составное" с вероятностью не менее 1-eps. Вероятность тут означает долю последовательностей случайных битов, дающих соответствующий ответ.
Можно было бы считать сказанное моим знакомым допустимой вольностью речи, но это не так - в этом рассуждении есть ошибка по существу (весьма распространённая, американское статистическое общество даже публиковало специальное разъяснение по аналогичному поводу, http://amstat.tandfonline.com/…/10.10…/00031305.2016.1154108). Чтобы объяснить, в чём она состоит, сделаем дополнительные предположения (не противоречащие сказанному):
(а) используемый вероятностный алгоритм на любом составном числе говорит "составное" с вероятностью равно 1-eps (и говорит "простое" с вероятностью eps; вероятность берётся по внутренним случайным битам).
(б) программа генерации картинки перебирает картинки из нужного класса (дающие при печати в прямоугольнике искомый портрет) и для каждой запускает алгоритм проверки простоты, пока не найдёт такую, где алгоритм даст ответ "простое"
(в) по каким-то таинственным законам теории чисел все картинки из нужного класса (соответствующие числа) оказываются составными.
Тогда программа, сделав в среднем 1/eps проб, выдаст картинку нужного класса, на которой алгоритм дал ответ "простое". Тем не менее соответствующее число будет гарантированно составным. (Конец объяснения ошибки.)
Другое дело, если бы именинник, получив такой подарок, собственноручно запустил бы на нём вероятностный алгоритм проверки, при этом бы ещё использовал не псевдослучайные биты от генератора, а собственнноручно бросал монету. Тогда с практической точки зрения вывод "можно считать простым" был бы корректным.
В заключение прошу прощения за занудство, но такая ошибка представляется мне распространённой и опасной, и пройти мимо удачной иллюстрации я не смог.
можно ещё исходить из честности
Date: 2018-02-26 08:38 pm (UTC)Мне кажется, вопросы, что считать "доказанным с практической точки зрения", и можно ли рассуждать о вероятности фактов (с какой вероятностью число 6 простое, или с какой вероятность Наполеон был левшой), -- это разные вопросы.