Кафедра "АСОИиУ"
Лабораторная работа №1
На тему: Исследование статистических характеристик
случайной последовательности
Душанбе-2010
I. Цель работы
Целью работы является:
1. Исследование свойств базой случайной последовательности;
2. Освоение методов оценки вероятностных характеристик случайной последовательности: математического ожидания, дисперсии, среднеквадратического отклонения и автокорреляционной функции;
3. Освоение метода проверки гипотезы о законе распределения по критерию согласия хи-квадрат Пирсона.
II. Теоретические сведения.
1. Имитация случайных последовательностей
При моделировании сложных систем одной из важнейших частей является имитация случайных воздействий, действующих на исследуемую систему.
Существует два основных метода имитации случайных воздействий:
1. Моделирование на натурных, экспериментальных данных
2. Моделирование с помощью алгоритмических датчиков.
При реализации первого способа приходиться сталкиваться с трудностями последовательного ввода в оперативную память ЭВМ больших массивов информации и изменения параметров случайных воздействий. Свободным от этих недостатков, более предпочтительным является второй способ, позволяющий программно реализовать случайные воздействия на ЭВМ и легко изменять их характеристики. В основе этого метода положена генерация некоторых стандартных объектов, назваными базовыми случайными воздействиями и последующее их функциональное преобразование. Таким базовым случайным воздействием является последовательность чисел x1,x2,……,xn, представляющих собой реализацию независимых равномерно распределенных в интервале [0,1] случайных воздействий.
В данной работе в качестве базовой случайной последовательности x1,x2,……,xm рассматривается М-последовательность, вырабатываемая генератором псевдослучайных чисел. Генератор строится на базе регистра, состоящего из n ячеек хi﴾i=1,n﴿, в которых записываются целые числа от 0 до ﴾q-1 ﴿, где q-основание системы исчисления ﴾Рис1.﴿ Случайные числа М- последовательности снимаются с последнего элемента регистра Хn. Числа записанные в ячейках Хm и Хn складываются по модулю q т.е.
R=Xm+Xn(1)
где "+"- знак сложения по модулю q.
Сложение по модулю q означает, что сумма R не должна превышать и быть равной q. В противном случае
R=R-q(2)
затем производится сдвиг чисел в регистре:
Хi
:=Хi
-1
-1 (i=n,2) (3)
В первую ячейку записывается содержимое сумматора:
Х1
:=R(4)
Такая процедура повторяется М раз:
M=qn
-1 (5)
где М- общее количество случайных чисел, вырабатываемых генератором.
q- основание системы исчисления
n- количество разрядов в регистре генератора.
В результате проведения повторяющихся циклов получается базовая псевдослучайная последовательность x1,x2,……,xm
Рис1. Генератор псевдослучайных чисел
2. Оценка вероятностных характеристик случайной последовательности
Для полученной случайной последовательности x1,x2,……,xМ производится оценка ее вероятностных характеристик. В качестве основных вероятностных характеристик рассматриваются:
- математическое ожидание;
-среднеквадратическое отклонение;
-дисперсия;
- автокорреляционная функция.
Математическим ожиданием случайной величины х называется сумма произведений случайной величины на ее вероятность, т.е.
mx
=M[x]= Xi
*
Pi (6)
Но, так как вероятности случайной величины Хi неизвестны, то оценка математического ожидания для случайной последовательности производится по формуле:
mX
*
=Xi
(7)
Дисперсией называется математическое ожидание квадрата отклонения случайной величины от ее математического ожидания, т.е.
DX
=M [Xi
-mX
]2
= [Xi
-mX
]2
*Pi
(8)
Так как вероятности Pi
неизвестны, то оценка дисперсии производится:
DX
*
=[Xi
-m*
X
]2
(9)
Среднеквадратическим отклонением называется корень квадратный из дисперсии, т.е.
X=(10)
Ее оценка производится по этой же формуле.
Автокорреляционной функцией называется математическое ожидание произведения отклонений случайной величины от ее математического ожидания, зависящих от величины сдвига r, как от аргумента:
K(r)=M [(Xi
-mX
)(Xi+r
-mX
)]=(Xi
-mX
)(Xi+r
-mX
)Pi
(11)
Оценка автокорреляционной функции производится по формуле:
K*
(r)= ( Xi
-m*
X
)(Xi+r
-m*
X
) (12)
(r=1,M-r)
Для получения нормированной автокорреляционной функции необходимо все значения K*
(r) поделить на оценку дисперсии DX
*
.
Для случайной последовательности с равномерным законом распределения нормированная автокорреляционная функция K*
(r) имеет вид (Рис 2.)
Рис2. Нормированная автокорреляционная функция случайной последовательности с равномерным законом распределения
3. Оценка закона распределения
Оценка закона распределения при большом объеме случайной последовательности производится по статистическому ряду, графическое изображение которого называется гистограммой. Для построения гистограммы диапазон возможных значений случайной последовательности разбивается на L участков точками U1,U2,…UL-1 (Рис 3.)
Крайние точки U1 и UL в общем случае могут быть бесконечными. Длины участков U могут быть не обязательно одинаковыми. Если они различные, то чаще всего они выбираются так, чтобы вероятности попаданий во всех участках были одинаковы или близки друг к другу. В связи с тем, что моделируемый генератор М-последовательности вырабатывает целые случайные числа от 0 до ﴾q-1 ﴿,то участки выделяются точками U1=1, U2=2,….Uq=q.
Статистический ряд представляет совокупность чисел V1,V2,…VL, где Vj-количество элементов последовательности попавших в j-тый участок и удовлетворяющий неравенству
Uj
-1
Xj
<Uj
(j=1,L) (13)
Графическое представление статистического ряда, то есть гистограмму, удобно строить в относительных величинах. Поэтому производится нормирование, чтобы:
=1 (14)
Статистическая (выборочная, эмпирическая) функция распределения для равномерного закона F(x) является оценкой для интегральной функции распределения и вычисляется по формуле:
F(x)=
Где Хк-к-тый элемент статистического ряда, в котором элементы расположены в порядке возрастания их числовых значений.
Графическое представление интегральной функции распределения показано на Рис4.
Рис3.Гистограмма
Рис4. Интегральная функция распределения
4. Проверка гипотезы о законе распределения
Гипотеза о законе распределения элементов последовательности задается названием закона и численным значением его параметров. Она может быть задана плотностью вероятности в виде формулы или графика статистического ряда (Рис3). Иногда может быть задана интегральная функция распределения (Рис4). Тогда зная эту функцию распределения F(x), можно всегда найти плотность вероятности как
f (x)= F’(x) (16)
Для проверки гипотезы о законе распределения при большом объеме последовательности (M>100) пользуются критерием X2
Пирсона. По построенному статистическому ряду (гистограмме) вычисляется статистика X2
(∆)
∆=X2
=(Vj-NPj)/NPj(17)
Где Рj- вероятность попадания элемента последовательности в j – тый участок
Vj- j-тый член статистического ряда, то есть количество элементов последовательности, попавших в j тый участок
N – общее количество элементов последовательности
Распределение X2
зависит от параметра r, называемого числом "степеней свободы".
Число степеней свободы r равно числу участков L минус число независимых условий k, наложенных на закон распределения:
r=L-k(18)
Для равномерного закона распределения k= 1. Поэтому число степеней свободы равно:
r=L-1 (19)
Если для теоретического распределения задается математическое ожидание, дисперсия и другие параметры, то число степеней свободы уменьшается на число таких параметров k.
Для распределения X2
имеются специальные таблицы ( таблица1) , по значениям которых и числу степеней свободы r можно найти вероятность Р( уровень значимости) того, что мера расхождения теоретического и статистического распределения будет не меньше, чем фактически наблюдаемое в в данной серии опытов значение X2
.Если эта вероятность L весьма мала, то результаты опытов следует считать противоречащим гипотезе о том, что закон распределения величины X2
есть функция F(x). Поэтому эту гипотезу следует отнести как неправдоподобную.
Напротив, если вероятность Р сравнительно велика ( близка к 1), то можно считать, что расхождения между теоретическим и статистическим распределением несущественно. Поэтому гипотезу о том, что величина X2
распределена по закону F(x) можно считать правдоподобной или не противоречащей опытным данным. На практике, если Р оказывается меньше, чем 0.1, то рекомендуется проверить и по возможности повторить эксперимент. В случае, если опять появятся заметные расхождения, то следует изменить параметры исследуемого генератора случайных чисел или подобрать более подходящий для описания статистических данных закон распределения.
III. Содержание исследования
В состав исследования, проводимого в данной лабораторной работе входит:
1. Программная реализация базовой псевдослучайной последовательности, вырабатываемой генератором случайных чисел при заданных преподавателем параметрах Таблица2: n, m, q,xi(i=1,n)
2. Определение оценок математического ожидания, дисперсии, среднеквадратического отклонения и q коэффициентов корреляции K (r) для r=1,q.
3. Построение гистограммы распределения для последовательности, полученной генератором случайных чисел.
4. Вычисление отклонений по критерию X2
Пирсона
5. Проверка гипотезы о равномерном распределении чисел, полученных генератором случайных чисел.
IV. Порядок проведения работы
Проведение работы включает следующие пункты
1. Получить у преподавателя исходные данные для моделирования генератора случайных чисел n, m, q, xi
2. Разработать блок-схему алгоритма исследования (моделирующий алгоритм) в соответствии с содержанием проводимого исследования
3. Составить программу на одном из языков программирования, предусмотрев вывод на печать всех результатов вычислений и соответствующих графиков
4. Отладить программу и решить задачу на ПЭВМ
5. Оформить отчет
V. Оформление отчета
Отчет по лабораторной работе должен содержать:
· Титульный лист
· Цель работы
· Краткое изложение теоретического материала и содержание исследования
· Блок-схему алгоритма исследования
· Листинг программы
· Результаты исследован
· Выводы о качестве генератора случайных чисел и его пригодность для моделирования.
Таблица1Критические точки распределения
| Число степеней свободы r | Уровень значимости ά | |||||
| 0.01 | 0.025 | 0.05 | 0.95 | 0.975 | 0.99 | |
| 1 | 6.6 | 5.0 | 3.8 | 0.0039 | 0.00089 | 0.00016 |
| 2 | 9.2 | 7,4 | 6,0 | 0,103 | 0.051 | 0.20 |
| 3 | 11.3 | 9,4 | 7,8 | 0,352 | 0,216 | 0,115 |
| 4 | 13,3 | 11,1 | 9,5 | 0,711 | 0,484 | 0,297 |
| 5 | 15,1 | 12,8 | 11,1 | 0,115 | 0,831 | 0,554 |
| 6 | 16,8 | 14,4 | 12,6 | 0,164 | 1,24 | 0,872 |
| 7 | 18,5 | 16,0 | 14,1 | 0,217 | 1,69 | 1,24 |
| 8 | 20,1 | 17,5 | 15,5 | 2,73 | 2,18 | 1,65 |
| 9 | 21,7 | 19,0 | 16,9 | 3,33 | 2,70 | 2,09 |
| 10 | 23,2 | 20,5 | 18,3 | 3,94 | 3,21 | 2,56 |
| 11 | 24,7 | 21,9 | 19,7 | 4,57 | 3,82 | 3,05 |
| 12 | 26,2 | 23,3 | 20,0 | 5,23 | 4,40 | 3,57 |
| 13 | 27,7 | 24,7 | 22,4 | 5,89 | 5,01 | 4,11 |
| 14 | 29,1 | 26,1 | 23,7 | 6,57 | 5,63 | 4,66 |
| 15 | 30,6 | 27,5 | 25,0 | 7,26 | 6,26 | 5,23 |
| 16 | 32,0 | 28,8 | 26,3 | 7,96 | 6,91 | 5,81 |
| 17 | 33,4 | 30,2 | 27,6 | 8,67 | 7,56 | 6,41 |
| 18 | 34,8 | 31,5 | 28,9 | 9,39 | 8,23 | 7,01 |
| 19 | 36,2 | 32,9 | 30,1 | 10,1 | 8,91 | 7,63 |
| 20 | 37,6 | 34,2 | 31,4 | 10,9 | 9,59 | 8,26 |
| 21 | 38,9 | 35,5 | 32,7 | 11,6 | 10,3 | 8,90 |
| 22 | 40,3 | 36,8 | 33,9 | 12,3 | 11,0 | 9,54 |
| 23 | 41,6 | 38,1 | 35,2 | 13,1 | 11,7 | 10,2 |
| 24 | 43,0 | 39,4 | 36,4 | 13,8 | 12,4 | 10,9 |
| 25 | 44,3 | 40,6 | 37,7 | 14,6 | 13,1 | 11,5 |
| 26 | 45,6 | 41,9 | 38,9 | 15,4 | 13,8 | 12,2 |
| 27 | 47,0 | 43,2 | 40,1 | 16,2 | 14,6 | 12,9 |
| 28 | 48,3 | 44,5 | 41,3 | 16,9 | 15,3 | 13,6 |
| 29 | 49,6 | 45,7 | 42,6 | 17,7 | 16,02 | 14,3 |
| 30 | 50,9 | 47,0 | 43,8 | 18,5 | 16,8 | 15,0 |
Таблица 2 Варианты заданий к лабораторной работе
| q | m | n | x1 | x2 | x3 | x4 | x5 | x6 | x7 | |
| 1 | 3 | 3 | 5 | 0 | 1 | 2 | 1 | 1 | - | - |
| 2 | 2 | 3 | 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 2 | 5 | 7 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 4 | 3 | 2 | 5 | 1 | 1 | 1 | 1 | 1 | - | - |
| 5 | 2 | 4 | 7 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 6 | 3 | 3 | 5 | 0 | 0 | 0 | 1 | 1 | - | - |
| 7 | 3 | 3 | 6 | 0 | 1 | 2 | 1 | 2 | 0 | - |
| 8 | 3 | 4 | 6 | 1 | 1 | 1 | 2 | 2 | 2 | - |
| 9 | 3 | 5 | 6 | 1 | 1 | 1 | 0 | 0 | 2 | - |
| 10 | 2 | 3 | 7 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 11 | 2 | 6 | 7 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 12 | 2 | 2 | 7 | 0 | 1 | 0 | 1 | 0 | 2 | 0 |
| 13 | 3 | 3 | 5 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 14 | 2 | 2 | 6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 15 | 3 | 4 | 5 | 1 | 2 | 1 | 0 | 1 | 2 | 2 |
Интерфейс программы:
Листингпрограммы:
Private Sub generator_Click()
Dim q, m, n, R, m3 As Integer
Dim mx, dx, qx, rk, f2 As Variant
Dim y(7) As Integer
Dim z() As Integer
Dim p() As Integer
List1.Clear
' ввод данных
q = Val(q1.Text)
m = Val(m1.Text)
n = Val(n1.Text)
y(1) = Val(x1.Text)
y(2) = Val(x2.Text)
y(3) = Val(x3.Text)
y(4) = Val(x4.Text)
y(5) = Val(x5.Text)
y(6) = Val(x6.Text)
y(7) = Val(x7.Text)
m3 = q ^ n - 1
m2.Text = Str(m3)
ReDim z(m3) As Integer
ReDim p(q) As Integer
'операторы для визуализации
Ifq = 2 Then
r3.Visible = 0
r4.Visible = 0
Label17.Visible = 0
Label18.Visible = 0
Else
r3.Visible = 1
Label17.Visible = 1
End If
If q = 3 Then
r4.Visible = 0
Label18.Visible = 0
Else
If q = 4 Then
r4.Visible = 1
Label18.Visible = 1
End If
EndIf
' вывод начальных чисел регистра
For i = 1 To n
h = h + Str(y(i))
Next i
List1.AddItem (h)
' генерирование новых чисел регистра и их вывод
For i = 1 To m3
R = y(m) + y(n)
If R >= q Then R = R - q
z(i) = y(n)
List1.AddItem ("R=" + Str(R) + " " + "y(" + Str(i) + ")=" + Str(z(i)))
For k = n To 2 Step -1
y(k) = y(k - 1)
Next k
p(R) = p(R) + 1
y(1) = R
f = ""
For b = 1 To n
f = f + Str(y(b))
Next b
List1.AddItem ("генератор : " + f)
Next i
For i = 0 To q - 1
List1.AddItem ("p(" + Str(i) + ")= " + Str(p(i)))
Nexti
' нахождение ма ожидания
For i = 1 To m3
mx = mx + z(i)
Next i
mx = mx / m3
mx1.Text = Str(mx)
' нахождение дисперсии
Fori = 1 Tom3
dx = dx + (z(i) - mx) ^ 2
Next i
dx = dx / (m3 - 1)
dx1.Text = Str(dx)
' нахождение средеквадратичного отклонения
qx = Sqr(dx)
qx1.Text = Str(qx)
'нахождение автокорреляционной функции
For rk = 1 To q
kr = 0
For i = 1 To m3 - rk
kr = kr + (z(i) - mx) * (z(i + rk) - mx)
Next i
kr = kr / (m3 - rk - 1)
Select Case rk
Case 1
r1.Text = Str(kr)
Case 2
r2.Text = Str(kr)
Case 3
r3.Text = Str(kr)
Case 4
r4.Text = Str(kr)
EndSelect
Nextrk
'нахожение по критерии Пирсона
For i = 1 To q
f2 = f2 + (1 / q - p(i) / m3) ^ 2
Next i
f2 = 1 / q * f2
Text1.Text = Str(f2)
End Sub
Список используемой литературы
1. Ли. И.Т., Моделирование экономических процессов, Душанбе, 2008 год