|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 31 Jan 2002 12:30:33
To : Andrew Plyako
Subject : распределения
--------------------------------------------------------------------------------
Wed Jan 30 2002 10:18, Andrew Plyako wrote to Evgenij Masherov:
EN>>>> Берешь N равномерно распределенных чисел, суммируешь их и делишь
EN>>>> сумму на N (для прличной точности N должно быть не меньше 15-20,
EN>>>> я раньше 100 брал).
AP>>> Отвратительный способ.
AP>>> Одну величину ты, конечно, создашь. Hо уже 100 величин,
AP>>> построенных таким образом, не будут независимыми нормальными
AP>>> величинами; точнее, они "не пройдут" статистической проверки на
AP>>> независимость.
AP>>> Hехорошо такие советы давать.
EM>> Вы не правы. Если исходный генератор хорош - работает превосходно.
AP> Что значит "хорош"? Практически все генераторы обладают свойством
AP> кластерности. Это значит, что если брать группы по (к примеру) 17
AP> случайных величин (равномерно распределенных в [0,1]) полученных таким
AP> генератором, и рассматривать их как точку в 17-ти мерном пространстве, то
AP> набор таких "точек" (таких блоков из 17-ти сл.чисел) будет распределен не
AP> равномерно; эти точки образуют в 17-ти мерном кубике т.н. кластер -- как
AP> бы облако.
AP> Хотя сама исходная последовательность вполне удовлетворяет критериям на
AP> независимость.
AP> Вот именно по этому попытка воспользоваться ЦПТ крайне не удачна. Уж во
AP> всяком случае, предложенный мной способ заведомо лучше.
1. Практический опыт мой показывает, что полученные нормальные значения
достаточно хороши. Хотя проверка ограничивалась
а. Хи-квадрат
б. Колмогоров-Смирнов
в. Корреляции до 20 порядка (при 12 слагаемых)
г. Спектр.
Если Вы укажете тест, который выявит недостаток подобного датчика - буду
благодарен.
2. Если исходный ГСЧ обладает подобным недостатком, то и предлагаемый Вами
способ будет им обладать. А также всякий иной способ.
3. Если "период кластеризации" взаимно прост с числом слагаемых - то
полученные нормальные случайные числа будут ЛУЧШЕ в этом плане, чем исходные
равномерные.
4. В ряде приложений такой (ЦПТ) датчик вполне удовлетворителен, но возможно
существование и таких, для которых он будет плох. В этом случае можно:
а. Использовать вместо 12 вызовов одного ГСЧ вызовы 12 разных, причем можно
добиться как взаимной простоты их периодов (получая генератор
последовательности с колоссальным периодом), так и взаимной простоты "периодов
кластеризации".
б. Обрабатывать полученную последовательность дополнительным ГСЧ (например, на
основе сдвигового регистра - меняя в зависимости от бита знак).
в. Перетасовывать полученную последовательность в случайном порядке (при
помощи дополнительного ГСЧ).
5. Основной недостаток такого подхода, на мой взгляд - его вычислительная
сложность, и теперь, когда стоимость вычисления функций упала, он может
обходится дороже полярного метода.
do {
x1=random(-1,1);
x2=random(-1,1);
S=x1*x1+x2*x2;
} until (S>1);
S=sqrt(-2*ln(S)/S);
n1=x1*S;
n2=x2*S;
(Кнут, т.2...)
Так что ЦПТ скорее полезен для микропроцессорных приложений, где все еще
умножение дорого, а деления вовсе нет...
6. Hекогда пытался я сделать ЦПТ-генератор с низкой стоимостью.
Состоял:
а. 12 вычислений равномерных СЧ (линейный конгруэнтный датчик; взаимно простын
периоды).
б. Они перетасовываются в соответствии со вспомогательным датчиком СЧ
(модифицированный метод середины квадрата; период во всех датчиках взаимно
прост с имеющимися).
в. Им меняются знаки по датчику СЧ на основе сдвигового регистра.
г. Hад ними производится Фурье для 12 точек (описано у Хэмминга, "Численные
методы для научных работников и инженеров"; остальное из Кнута). Поскольку
Фурье преобразование ортогональное - из 12 независимых СЧ получаем 12
независимых, близких к нормальному.
д. Обрабатываем полиномом Тейчроева (там же).
е. Меняем знаки другим сдвиговым регистром.
ж. Перетасовываем (уже Фибоначчиев ГСЧ).
з. По запросу выдаем очередное число, раз в 12 попыток повторяем генерацию.
Скорость весьма приличная, и все имеющиеся тесты прошло прекрасно (к названным
- еще искалась корреляционная матрица и вычислялись ея собственные значения)
С уважением
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
