Преобразование Бокса-Мюллера

[green_fr]

На лекции написали по-быстренькому программу на Excel Монте-Карло для оценки опционов. В частности там понадобился генератор случайной переменной, подчиняющейся нормальному распределению. Я автоматом использую встроенную в Excel функцию (NORMSINV), на что преп говорит, что её использовать не надо, потому как она — медленная. Вместо её он предлагает написать самому функцию, которая берёт обычное случайное число (равномерное распределение между 0 и 1) и преобразовывает его в нужное нормальное.

Собственно, кроме как «хозяйке на заметку» (действительно, выходит на порядок быстрее), у меня вопрос — а почему в Excel такая медленная функция? Что мешает им использовать то же самое преобразование Бокса-Мюллера?
Варианты «Билл Гейтс — дурак, переходи на linux» не предлагать.

Comments

[alexnavfr.livejournal.com]

А кто ж тогда будет покупать более мощные компы?
Если в Excel Монте-Карло будет считаться одинаково быстро на пентиуме и на Dual Core.

[a_p]

возможно, в Экселе реализован симулятор физики подбрасывания монеты или чего-нибудь в этом духе. (смайл, уточню на всякий случай).

[insead-hec.livejournal.com]

Another method for generating Normal distributed random numbers is to run uniform random numbers 0 < x < 1 through the inverse Normal distribution. This method is particularly useful when using high dimensional low discrepancy sequences like Sobol, Hastons, Faure. These generators generate specific random numbers that can't be used to feed into the Box-Muller transform without losing their properties.

(источник: http://www.sitmo.com/doc/Generating_Normal_Distributed_Random_Numbers)

[green-fr.livejournal.com]

Если честно, я не понял, что именно теряется при такой генерации. Можешь объяснить?

[insead-hec.livejournal.com]

Если коротко - теряется псевдо-случайность и получаются толстые хвосты.

Откровенно говоря, я могу только спекулировать, поскольку в последний раз использовал генераторы превдо-случайных чисел для серьезных вычислений больше 20 лет назад, когда про Excel я даже не слышал. А в последние годы мне хватало выборок в 1000.

Судя по тому что я смутно помню и что быстро посмотрел в Google (http://en.wikipedia.org/wiki/Low-discrepancy_sequence или http://www.wpi.edu/Pubs/ETD/Available/etd-0113104-140925/unrestricted/krykova.pdf), фишка заключалась в том, что для того, чтобы преобразование Бокса-Мюллера работало хорошо (например, не создавало плохого куртозиса - "толстых хвостов"), нужен был хороший изначальный генератор псевдо-случайных чисел. Low-discrepancy это как раз и есть характеристика псевдо-случайной последовательности, которая делает ее хорошим заменителем случайной последовательности в таких операциях (если взять произвольное подмножество/подыинтервал исходного множеста/интервала, то число псевдослучайных чисел, попавших в это подмножество не должно превышать меры этого подмножества). Особенно это было важно, когда полученные числа использовались для вычисления многомерных интегралов.

Раньше в Excel'е генератор был слишком плох (относительно высокая автокоррелация олучаемой последовательности), поэтому хвосты получались слишком толстые при использовании Бокса Мюллера. А после Excel 2003 генератор вроде бы подновили.

[green-fr.livejournal.com]

Спасибо! Поговорю теперь с препом на эту же тему.
Меня смутило именно это — он (человек умный, математик, статьи, призы, премии, все дела) нам советует как на коленке написать лучше, чем фирма Microsoft.
В решении Excel явно должно быть что-то такое, что нам в данном контексте не нужно, а им выбросить нельзя, и оно тормозит их расчёты. Вот и нужно теперь понять, что именно это «ненужное». чтобы понимать, когда мы можем от него отказываться, а когда — нет.

[oldjackaroo.livejournal.com]

Так преобразование Бокса-Мюллера было открыто только в 1958 году, создатели Excel про него еще не знали! :)

[bgmt.livejournal.com]

Дело может быть в том, что у генератора случайных чисел есть КАЧЕСТВО. Это - не только длина последовательности, после которой повторяется, но это ещё и степень зануления всех моментов. Хороший генератор случайных числе (скажем, для Монте-Карло в теории поля на решётке или в твёрдом теле) - вещь крайне сложная, постоянно улучшаемая, и да, берущая время.
Что за генератор в Экселе, не знаю. Как он сравнивается с использованием NORMSINV, не знаю. Но тут может быть зарыта именно эта собака.

[kalvado.livejournal.com]

В каком-то из интеловских чипсетов (8хх вроде?) была реализована аппаратная функция генератора случайных чисел. Не прижилось..

[birdwatcher.livejournal.com]

Я думал, преобразование Бокса-Мюллера помогает генерировать нормальные случайные числа из равномерных, а функция NORMSINV - вычислять функцию, обратную к Ф. Определенная связь между этими операциями есть, но как можно сравнивать их скорости?

[green-fr.livejournal.com]

Ну так Ф^-1 от случайного равномерно распределённого числа — это случайное нормально распределённое число. Нет разве? То есть у тебя, получив случайное равномерное число, есть выбор, либо послать его стандартной Excel функции, либо провести через свою (Бокс-Мюллер).

Перечитал пост, действительно, не совсем внятно написал. Случайные числа тут вообще ни при чём, я просто так вышел на этот вопрос — обратная функция плотности нормального распределения.

[birdwatcher.livejournal.com]

Конечно, если у тебя есть равномерные числа, а ты хочешь нормальные, то гораздо быстрее будет подставлять их в Бокса-Мюллера, чем в Ф^-1.

Но Ф^-1 нужна вовсе не только для этого, а и для кучи других вещей, и я не слышал, чтобы в Экселе жила особенно медленная ее имплементация. Поэтому вопрос может быть разве что о том, почему в Экселе нет отдельно Бокса-Мюллера (ну, например, потому, что его тривиально сделать самому имеющимися средствами Эскела).

[green-fr.livejournal.com]

Слушай, да, кажется я понял. Ты абсолютно прав, спасибо :-)