генератор случайного вектора на сфере

[AndreyL]

Дамы и Господа!

Понадобился генератор $n$-мерного случайного вектора, равномерно распределенного на гиперсфере радиуса 1. Два вопроса:
1. Насколько корректен такой генератор - генерируем случайный вектор $t$ из $n$-мерного нормального распределения с нулевым центром и единичной ковариационной матрицей и делим его на его собственную евклидову норму? Какие еще есть генераторы?
2. Как проверить, что выборка взята именно из равномерного распределения на гиперсфере, ведь компоненты вектора зависимы?

[ewert]

Самый дешёвый способ -- генерировать векторы, равномерно распределённые в кубе, отбраковывать их по попаданию в шар (и, на всякий случай, по непопаданию в маленький шарик в центре), затем нормировать. Конечно, с ростом размерности эффективность быстро снижается (при $n=10$ будет примерно $\frac1{400}$). Однако при не слишком больших $n$ вряд ли можно придумать что-нибудь лучшее.

[ozheredov]

ewert
Вопрос вроде был про корректность предложенного генератора(который в вычислительном плане тоже весьма недорог), не?

AndreyL в сообщении #1563198 писал(а):

Как проверить,

Навскидку: берете кучу случайных гауссовых векторов (ненормированных). И берете огромную выборку из Вашего "сферического" распределения. Для каждого вектора положительных и отрицательных скалярных произведений с выборкой должно быть примерно одинаково

[ewert]

ozheredov в сообщении #1563203 писал(а):

корректность предложенного генератора(который в вычислительном плане тоже весьма недорог)

С корректностью того метода проблем, естественно, нет (при условии, конечно, что корректен сам генератор нормального распределения). Проблема в том, что нормальное распределение генерируется гораздо дольше, чем равномерное (которое в простейших случаях реализуется вообще за две целочисленные арифметические операции). И если эффективность отбраковки не слишком мала (округлённо $75\%$ при $n=2$, $50\%$ при $n=3$, $30\%$ при $n=4$), то метод с отбраковкой явно выгоднее. А вот при $n=10$ уже явно наоборот.

[AndreyL]

ewert в сообщении #1563201 писал(а):

Самый дешёвый способ -- генерировать векторы, равномерно распределённые в кубе, отбраковывать их по попаданию в шар ...

Да, я слышал о таком методе, но меня смутила проверка на попадание в шар, думал долго будет. На самом деле это значительно быстрее, чем генерировать нормальные векторы, а если организовать в цикле, то и код компактный получается, спасибо за подсказку о скорости генерации равномерного.

Про проверку не очень понял - объемы выборок должны быть одинаковые, или делать умножение каждого вектора моей выборки с каждым вектором нормального распределения?

[ozheredov]

ewert в сообщении #1563205 писал(а):

Проблема в том, что нормальное распределение генерируется гораздо дольше, чем равномерное

Согласен, но современные пакеты без труда генерируют нормалки миллиардами (под дешевизной я это имел в виду).

AndreyL в сообщении #1563207 писал(а):

Про проверку не очень понял - объемы выборок должны быть одинаковые, или делать умножение каждого вектора моей выборки с каждым вектором нормального распределения?

Предположим, у Вас уже есть куча сгенерированных "сферических" векторов RANDN. Далее, Вы делаете множество ненормированных нормально распределенных тестовых векторов TEST. Оно может быть не очень большим. Теперь для каждого вектора TEST Вы считаете знаки скалярных произведений со всеми векторами RANDN. Если во всех случаях знаков примерно поровну, то все хорошо.

Потом можно слегка усложнить, беря в качестве TEST рандомные ортонормированные базисы (полученные, например, из собственных векторов матрицы $A^TA$, где $A$ составлена из равномерных рандомов). Знаки скалярных произведений будут образовывать последовательности, каждая из которых должна встречаться примерно одно и то же количество раз.

[AndreyL]

ozheredov в сообщении #1563212 писал(а):

Предположим, у Вас уже есть куча сгенерированных "сферических" векторов RANDN. Далее, Вы делаете множество ненормированных нормально распределенных тестовых векторов TEST. Оно может быть не очень большим. Теперь для каждого вектора TEST Вы считаете знаки скалярных произведений со всеми векторами RANDN. Если во всех случаях знаков примерно поровну, то все хорошо

Так, наверное, можно построить критерий - посчитать. каких знаков меньше и определить вероятность того, что знаков будет еще меньше по биномиальному распределению (вероятность знака 1/2) - это и будет p-value или "достижимый уровень значимости". Кстати. как в этом случае правильно, считать вероятность строго меньше найденного значения или меньше-равно? Не часто работаю с дискретными критериями.

[ozheredov]

AndreyL в сообщении #1563214 писал(а):

Так, наверное, можно построить критерий - посчитать. каких знаков меньше и определить вероятность того, что знаков будет еще меньше по биномиальному распределению (вероятность знака 1/2) - это и будет p-value

Именно!

AndreyL в сообщении #1563214 писал(а):

Кстати. как в этом случае правильно, считать вероятность строго меньше найденного значения или меньше-равно?

Я бы рассмотрел гипотезу распределения $[0.5; 0.5]$ при уровне значимости 0.01. Если для всех векторов из TEST эта гипотеза прокатывает, то ладушки. И не надо считать вероятность )

[AndreyL]

Имеется ввиду, то для любого целого критического значения при больших объемах выборки вероятность будет иметь очень много знаков после запятой, т.е. для любого разумного уровня значимости нет целого критического значения? Или как-то не так? Если так, то можно считать вероятность строго меньше и говорить. что p-value не меньше. Это для принятия гипотезы о равномерности, для отвержения наоборот. По p-value сразу видно, не нужно заранее задавать уровни значимости и считать критические значения: если p-value больше, например, 5% (а лучше 20%), то принимаем гипотезу, если меньше, например, 1% (лучше 0.1% или 0.01%), то отвергаем, если между - то думаем.

[zykov]

ewert в сообщении #1563205 писал(а):

Проблема в том, что нормальное распределение генерируется гораздо дольше, чем равномерное

Ну не гораздо.
Из равномерного легко получается нормальное: Generating values from normal distribution.

[AndreyL]

zykov в сообщении #1563219 писал(а):

Из равномерного легко получается нормальное: Generating values from normal distribution.

Согласен, но проверка квадрата длины вектора (его все равно считать) на "меньше единицы" делается быстрее, чем взятие функции ошибок. Но согласен и с тем, что на современных машинах миллионные выборки нормального распределения генерируются секунды, поэтому так и делал.

[zykov]

AndreyL в сообщении #1563220 писал(а):

на современных машинах миллионные выборки нормального распределения генерируются секунды

Вот Octave (свободный аналог Matlab) сгенерировал миллион значений за 15 миллисекунд (для равномерного распределения было 8.5 миллисекунд).

Используется синтаксис Matlab M

>> t1=time;x=randn(1000,1000);time-t1
ans =  0.015062
>> t1=time;x=rand(1000,1000);time-t1
ans =  0.0084100

(А 100 миллионов за 1.5 секунды.)