Квази-случайность
Jun. 25th, 2014 03:39 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kaipaПо следам содержательного разговора с ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
antilamer на тему использования квази-случайных последовательностей решил написать небольшую заметку. Почему-то статьи по этой теме есть в английской википедии, но не в русской, хотя один из авторитетов в этой области -- И. М. Соболь -- наш советский и российский математик (вот список его статей, многие весьма интересны).
Сначала пара определений.
Случайная последовательность здесь и дальше -- это выборка из равномерного распределения в ограниченной конечномерной области (для простоты можно считать область сферой или кубом в Rn).
Псевдо-случайные последовательности -- это сгенерированные имитации случайных последовательностей. Они являются строго детерминированными (программисты знают, что random можно перезапустить с исходной или заданной "позиции"), но при этом похожи на случайные.
Квази-случайные последовательности -- это тоже сгенерированные последовательности, имеющие некоторые сходства со случайными, но и существенные отличия.
Лучше всего сходства и отличия проиллюстрирует картинка с википедии, которая показывает разницу в расположении случайных и квази-случайных точек для размера выборки из 10, 100, 1000 и 10000. Видно, что квази-случайная выборка более "равномерно" покрывает область. Хотя в смысле настоящей случайности это квази-равномерность. Именно это свойство делает ее полезной для квази-случайного метода Монте-Карло, который используется для задач оптимизации, вычисления интегралов и др.
Однако, при использовании квази-случайных последовательной есть одна неочевидная проблема, о которой я и пытался рассказать Жене. Суть в том, что для квази-случайной последовательности нарушается свойство равномерности в смысле распределения, то есть вероятность попадания в определенную область даже если и стремится в пределе к правильной вероятности, то делает это "неправильным" образом. На третьей сверху картинке это хорошо видно.
Чем и для каких задач это плохо? Наиболее сильно это может проявляться в нелинейных задачах аппроксимации, которая возникает во многих практических приложения теории оптимального управления. Дело в том, что в таких задачах по выборке вычисляется функция в каком-то другом пространстве, и свойство квази-равномерности в исходном пространстве не имеет большого значения, так как в пространстве образа оно в силу нелинейности может полностью нарушаться. За то имеет значение свойство равномерности, так как позволяет строить теоретические оценки полноты и надежности покрытия образа. Это реальная проблема, поэтому квази-случайные распределения в таких задачах не используют.
Другая проблема теоретического и методологического характера состоит в том, что для квази-случайных последовательностей и методов Монте-Карло в принципе не очень хорошо обстоит дело со статистическими оценками. То есть, насколько я понимаю, есть большие трудности в доказательстве того, что квази-случайный метод на конкретной задаче оптимизации или интегрирования будет работать лучше, чем случайный. Вычислительный эксперимент, возможно, покажет, что это так, а теоретически доказать можно (если можно) не всегда.
Наверное, не-математики меня заклюют, что ничего не понятно, а математики за нестрогость, но подробнее написать времени, увы, нет.
antilamer на тему использования квази-случайных последовательностей решил написать небольшую заметку. Почему-то статьи по этой теме есть в английской википедии, но не в русской, хотя один из авторитетов в этой области -- И. М. Соболь -- наш советский и российский математик (вот список его статей, многие весьма интересны).Сначала пара определений.
Случайная последовательность здесь и дальше -- это выборка из равномерного распределения в ограниченной конечномерной области (для простоты можно считать область сферой или кубом в Rn).
Псевдо-случайные последовательности -- это сгенерированные имитации случайных последовательностей. Они являются строго детерминированными (программисты знают, что random можно перезапустить с исходной или заданной "позиции"), но при этом похожи на случайные.
Квази-случайные последовательности -- это тоже сгенерированные последовательности, имеющие некоторые сходства со случайными, но и существенные отличия.
Лучше всего сходства и отличия проиллюстрирует картинка с википедии, которая показывает разницу в расположении случайных и квази-случайных точек для размера выборки из 10, 100, 1000 и 10000. Видно, что квази-случайная выборка более "равномерно" покрывает область. Хотя в смысле настоящей случайности это квази-равномерность. Именно это свойство делает ее полезной для квази-случайного метода Монте-Карло, который используется для задач оптимизации, вычисления интегралов и др.Однако, при использовании квази-случайных последовательной есть одна неочевидная проблема, о которой я и пытался рассказать Жене. Суть в том, что для квази-случайной последовательности нарушается свойство равномерности в смысле распределения, то есть вероятность попадания в определенную область даже если и стремится в пределе к правильной вероятности, то делает это "неправильным" образом. На третьей сверху картинке это хорошо видно.
Чем и для каких задач это плохо? Наиболее сильно это может проявляться в нелинейных задачах аппроксимации, которая возникает во многих практических приложения теории оптимального управления. Дело в том, что в таких задачах по выборке вычисляется функция в каком-то другом пространстве, и свойство квази-равномерности в исходном пространстве не имеет большого значения, так как в пространстве образа оно в силу нелинейности может полностью нарушаться. За то имеет значение свойство равномерности, так как позволяет строить теоретические оценки полноты и надежности покрытия образа. Это реальная проблема, поэтому квази-случайные распределения в таких задачах не используют.
Другая проблема теоретического и методологического характера состоит в том, что для квази-случайных последовательностей и методов Монте-Карло в принципе не очень хорошо обстоит дело со статистическими оценками. То есть, насколько я понимаю, есть большие трудности в доказательстве того, что квази-случайный метод на конкретной задаче оптимизации или интегрирования будет работать лучше, чем случайный. Вычислительный эксперимент, возможно, покажет, что это так, а теоретически доказать можно (если можно) не всегда.
Наверное, не-математики меня заклюют, что ничего не понятно, а математики за нестрогость, но подробнее написать времени, увы, нет.
