Alg i metodi vichisl / Teorija / lek_num_met

M[τ]=1/λ

Рисунок 11.2 Экспоненциальная плотность вероятностей с разными значениями параметра

Экспоненциальному распределению, как правило, подчиняется случайный интервал времени τ между поступлениями заявок в систему массового обслуживания. Поэтому весьма важно уметь моделировать потоки заявок разной интенсивности.

Напомним, что математическое М[τ] ожидание экспоненциально распределенной случайной величины τ равно

а дисперсия

D[τ ]= 1/ λ2

Чтобы найти алгоритм имитации экспоненциально распределенных чисел τ, применим метод инверсии:

	∫τ	λe−λx = R					(11.14)
	0
		1−e−λτ = R					(11.15)
	откуда		1
	τ	= −			ln(1− R)		(11.16)
			λ
	но, поскольку случайная величина (1 - R) распределена точно так же, как R, и находится в том же интервале
	(0,1), то (11.16) можно заменить на более удобную формулу:
	τ	= −			1	ln R	(11.17)
					λ

что дает искомый ответ.

§3. Генерация случайных чисел с равномерным законом распределения на отрезке (a,b).

Предположим, что нам необходимо составить программу для моделирования входного потока заявок распределенного по равномерному закону в интервале (а,b). Уравнение метода инверсии для рассматриваемого случая выглядит так

y	b dy− a = R
∫a

где R – равномерно распределенное случайное число на (0,1), т.е. базовое число. Это интегральное уравнение решается легко и ответ ясен:

y − a = R b − a

Отсюда мы имеем явное выражение для y:

y =a+R(b−a)

где R – базовое случайное число.

§4. Генерация случайных чисел с распределением Пуассона.

Распределение Пуассона моделирует случайную величину, равную числу событий, произошедших за фиксированное время, при условии, что данные события происходят с некоторой фиксированной средней интенсивностью и независимо друг от друга.

Распределение Пуассона - это дискретное распределение, являющееся одним из важных предельных случаев биномиального распределения. При росте n и зафиксированном значении произведения np=λ > 0 биномиальное распределение B(n,p) сходится к распределению Пуассона. Таким образом, случайная величина, имеющая распределение Пуассона с параметром λ, принимает неотрицательные целые значения с вероятностью P.

Выберем фиксированное число λ > 0 и определим дискретное распределение, задаваемое следующей функцией вероятности:

pn = P(ξ = n) = λnn! e−λ

Функция распределения равна

F (x) = e −λ ∑x λn

n=0 n!

Параметр λ является одновременно и математическим ожиданием, и дисперсией случайной величины, имеющей распределение Пуассона. Часто параметр называется интенсивностью.

Производящая функция моментов распределения Пуассона имеет вид:

M y (t) = eλ(et −1) ,

откуда

,

.

Классическим примером случайной величины, распределенной по Пуассону, является количество машин, проезжающих через какой-либо участок дороги за заданный период времен. Также можно отметить такие примеры, как количество звезд на участке неба заданной величины, количество ошибок в тексте заданной длины, количество телефонных звонков в call-центре или количество обращений к веб-серверу за заданный период времени.

Биномиальное распределение B(n,p) - это распределение числа успехов в серии из n экспериментов, каждый из которых завершается успехом с вероятностью p. Важными предельными случаями биномиального распределения являются распределение Пуассона и нормальное распределение.

Если X - биномиальная случайная величина, то

P(X = k) = n pk (1− p)n−kk

P(X ≤ k) = l1−p (n −k,k +1)

§5. Генерация случайных чисел с показательным законом распределения.

Определение. Показательным (экспоненциальным) называется распределение вероятностей непрерывной случайной величины Х, которое описывается плотностью

0,приx < 0 f (x) = λe−λx ,приx ≥ 0

где λ - положительное число. Найдем закон распределения.

F (x) = ∫x	f (x)dx = ∫0 0dx + λ∫x e −λx dx = 1 − e −λx
−∞	−∞	0

0,приx<0 F(x) = 1−e−λx ,приx≥0

Графики функции распределения(рисунок 11.3) и плотности распределения(рисунок 11.4):

f(x)

F(x)

0	x	0	x
Рисунок 11.3			Рисунок 11.4

Найдем математическое ожидание случайной величины, подчиненной показательному распределению.

mx = ∞∫xf (x)dx

−∞

∞		−λx
	u = x,e			dx = dv,
= ∫xλe−λx dx =				e−λx				=
0	du = dx,−						= v,
				λ
	∞		e−λx					1
	= ∫e−λx dx = −						0∞ =
								λ
	0			λ

		xe−λx ∞ ∞ e−λx
	−		∫	+ ∫			=
λ		λ			λ	dx
			0	0

Результат получен с использованием того факта, что

∞	x			По	правилу		1
xe −λx ∫= lim		− 0				= lim			= 0
			=
	λx			Лопиталя			− λe	λx
0 x→∞	e					ч→∞

Для нахождения дисперсии найдем величину М(Х2).

∞∞

M ( X 2 ) = ∫ x 2 f (x)dx = ∫λx 2 e −λx dx

−∞

0

Дважды интегрируя по частям, аналогично рассмотренному случаю, получим:

M (X 2 ) = λ22

D(X ) = M (X 2 ) −[M (X )]2 = λ12

Тогда

M (X ) = λ1 ; D(X ) = λ12 ;σ x = λ1

Итого:

Видно, что в случае показательного распределения математическое ожидание и среднее квадратическое отклонение равны.

Также легко определить и вероятность попадания случайной величины, подчиненной показательному закону распределения, в заданный интервал.

P(a < x <b) = F(b)−F(a) =e−λa −e−λb

Показательное распределение широко используется в теории надежности.

Допустим, некоторое устройство начинает работать в момент времени t0=0, а через какое– то время t происходит отказ устройства.

Обозначим Т непрерывную случайную величину – длительность безотказной работы устройства.

Таким образом, функция распределения F(t) = P(T<t) определяет вероятность отказа за время длительностью t. Вероятность противоположного события (безотказная работа в течение времени t) равна R(t)=P(T>t) = 1–F(t).

§6. Примеры программ генераторов случайных чисел.

AP.cs

Алгоритмы

Библиотека AP для С# содержит базовый набор математических функций и классов, которые требуются для работы программ.

HQRND.cs

Алгоритмы В состав модуля входят два типа подпрограмм: подпрограммы для работы с низкоуровневым генератором и

для его настройки, и высокоуровневые подпрограммы, реализованные на базе низкоуровневого генератора. К первой категории относятся подпрограммы RndIntegerBase, RndIntegerMax и RndInitialize. Первая подпрограмма возвращает случайное число в диапазоне от 0 (не включительно) до границы, возвращаемой подпрограммой RndIntegerMax. Эта подпрограмма является основой для всех генераторов случайных чисел в этом модуле. Подпрограмма RndInitialize служит для инициализации генератора и является аналогом подпрограммы randomize, с тем отличием, что она принимает не одно значение seed-переменной, а два.

Ко второй категории относится целый ряд подпрограмм. Для получения случайных целых чисел, расположенных в указанном диапазоне, может использоваться подпрограмма RndUniformI. Подпрограмма RndUniformR возвращает вещественные числа в диапазоне (0, 1). Подпрограммы RndNormal и RndNormal2 служат для генерации нормально распределенных случайных чисел. Первая из них генерирует одно нормально распределенное случайное число, вторая - пару независимых чисел (при этом по трудоемкости обе подпрограммы одинаковы, поэтому для генерации больших количеств случайных чисел стоит пользоваться второй подпрограммой). Подпрограмма RndExponential служит для генерации экспоненциально распределенных случайных чисел.

POISSONDISTR.cs

Алгоритмы

Подпрограммы PoissonDistribution и PoissonCDistribution предназначены для вычисления площади под левым и под правым хвостами графика (т.е. для вычисления интегральной функции вероятности и её дополнения). Подпрограмма InvPoissonDistribution вычисляет функцию, обратную к интегральной функции вероятности (подбирает такое значение параметра λ, что Fλ (x)=y).

NORMALDISTR.cs

Алгоритмы

Нормальное распределение, функции erf и erfc. Нормальное распределение, также известное, как распределение Гаусса, является одним из наиболее известных непрерывных распределений. Строго говоря, существует целое семейство нормальных распределений, различающихся лишь масштабом и смещением. Здесь и далее под нормальным распределением подразумевается т.н. стандартное нормальное распределение - нормальное распределение с нулевым математическим ожиданием и единичным стандартным отклонением.

Подпрограммы Erf и ErfC служат для вычисления значения специальной функции erf(x) и её дополнения до единицы. Функция, обратная к erf(x) вычисляется подпрограммой InvErf.

Интегральная функция вероятности нормального распределения вычисляется подпрограммой NormalDistribution. Функция, обратная к интегральной функции распределения, вычисляется подпрограммой

InvNormalDistribution.