|
"Золотое правило искателя - пока не рассеется туман, надо быть осмотрительным и
беречь силы."
Кобо Абэ "Тайное свидание"
|
Здравствуйте, уважаемые читатели!
Возможно вы обратили внимание, на несколько странную нумерацию последнего выпуска -
это объясняется тем, что он был как-бы новостным, а вот он настоящий 18-ый :)
Согласитесь, что для того, чтобы быть уверенными в результатах статистического моделирования, мы должны быть уверены
в случайности применяемой последовательности "случайных" чисел.
Как же проверить качество ГСЧ(Генераторов Случайных Чисел (Random Number Generator) (RNG)) или
Генераторов Псевдослучайных Чисел(Pseudorandom Number Generator (PRNG))?
вместо Pseudorandom очень хочется поставить Poor random :-)
Такую проверку проводят по ряду количественных критериев, которые нам даёт статистическая теория.
Ниже приводятся некоторые наиболее распространённые тесты:
1. Критерий "хи-квадрат" (пишется греческая буква хи, возведённая в квадрат)
2. Проверка по моментам распределения.
3. Проверка на равномерность.
4. Проверка независимости элементов последовательности.
5. etc.
Ниже рассмотрена сущность второго и третьего тестов:
Проверка по моментам распределения.
Note:МОМЕНТ
(от лат. momentum - движущая сила, толчок), понятие теории вероятностей;
характеристика распределения значений случайной величины Х. В простейшем случае,
когда Х может принимать лишь конечное число значений
x1, x2,..., xn
с вероятностями
p1, p2,..., pn,
моментом порядка k величины Х называется выражение:
k k k
x1 p1+x2 p2+ ... +xn pn
Момент 1-го порядка а - математическое ожидание, момент 2-го порядка -
дисперсия (если а = 0).
// СЭС,1985
Я конечно рассчитываю, что вам знакомы такие понятия из теории вероятностей, как математическое ожидание и
дисперсия, но до кучи :) приведу формулы и для них.
Математическое ожидание:
Если X принимает значения xi с вероятностями pi
Тогда математическое ожидание запишется:
n
--
MX= \ (xipi)
/
--
i
Математическое ожидание имеет смысл среднего значения случайной величины.
Для непрерывной величины сумма заменяется на интеграл.
Дисперсия:
2
DX=M(X-MX)
Дисперсия даёт разброс случайной величины вокруг среднего значения.
Именно смысл дисперсии имеют величины в принципе неопределённости Гейзенберга.
|
Т.о. проверка по моментам распределения последовательности случайных чисел x1,x2, ... ,xN заключается в подсчёте математического ожидания (сиречь среднего) и
дисперии. Если числа близки к равномерной случайной последовательности [0,1], то при достаточно больших N(число выборок)
Mx~0,5
Dx~1/12
Эти числа получаются, если в интегральные формулы для мат. ожидания и дисперсии подставить функцию плотности распределения, описывающую
равномерное распределение в интервале [0,1].
Проверка на равномерность.
Для проверки на равномерность нужно интревал распределения случайной величины (например отрезок [0,1]) разбить
на n равных частей. Тогда каждое из чисел xi попадёт в один из
интервалов.
Пусть M1 - число чисел, попавших в первый интервал M2 - во второй и т.д. При этом
M1+M2+ ... +Mn=N
Тогда относительные частоты попадания случайных чисел в каждый из n интервалов:
p1=M1/N ,p2=M2/N , ... ,pn=Mn/N ,
Далее строится гистограмма(pi от xi).
Если числа равномерные, то при большом N гистограмма должна приближаться к теоретической прямой 1/n.
Число разбиений обычно берётся 10-20.
Очередной выпуск подошёл к концу и я прошу прощения за его задержку - он должен был
появиться раньше, но непредвиденные обстоятельства в виде ОЧЕНЬ интересных книг и новой
Civilization III - Conquests :)) отсрочили его появление.
Счастливо!
|