Математические основы моделирования дискретных систем

Введение

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

В настоящем пособии рассматриваются математические основы моделирования стохастических ДС. В первом разделе приводятся необходимые сведения из теории вероятностей, описываются основные законы распределения случайных величин и рассматриваются наиболее важные числовые характеристики. Второй раздел посвящен рассмотрению такого класса случайных процессов, как Марковские случайные процессы, как с дискретным, так и с непрерывным временем. При этом особое внимание уделяется частному случаю Марковских случайных процессов в виде процессов размножения и гибели, которые тем не менее находят широкое применение при анализе ДС со стохастическим характером функционирования.

Необходимые сведения теории вероятностей подробно приводятся в работах [1,2]. С наиболее доступным полным изложением задач и методов теории Марковских случайных процессов можно ознакомится в литературе [3,4,5]. Кроме того, в работах [4,5] подробно рассматриваются вопросы применения Марковских случайных процессов в качестве моделей стохастических систем различной организации.

Раздел 1 Элементы теории вероятностей

1.1. Понятие вероятности и случайной величины.

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

Предположим, что рассматривается некоторый опыт или явление, в котором в зависимости от случая происходит или не происходит некоторое событие А. Если условия опыта могут быть воспроизведены многократно, так что в принципе будет осуществима целая серия одинаковых и независимых друг от друга испытаний, то вероятность событияА, обозначаемая через Рr[A], может быть вычислена по формуле:

Рr[A]= n/N,

где N - общее число взаимно исключающих друг друга исходов;n- число исходов, которые приводят к наступлению событияA.

Вероятность любого события А должна удовлетворять условию:

0Pr[A]1.

Если Рr[А]=0, то событиеАназывается невозможным или нулевым (0) событием, а событие, для которого Рr[А]=1, называется достоверным.

Множество событий {А₁, А₂ ,..., А_n} образует полную группу событий, если в результате опыта должно непременно появиться хотя бы одно из них. Для полной группы событий справедливо условие:

Рr[A₁]+Рr[A₂]+...+Рr[A_n]=1.

События АиВназываются несовместными или взаимоисключающими, если в результате опыта они не могут появиться одновременно (вместе), и для таких событий справедливо:

Рr[АВ]=Рr[0]=0 и Pr[AB]=Pr[A]+Pr[B] .

События АиВназываются независимыми, если появление одного из них не зависит имело место или нет другое событие. Для таких событий

Pr[AB]=Pr[A]Pr[B].

Такое равенство в виде произведения справедливо и для большего количества независимых событий.

У

(1.1)

словная вероятность событияА, если известно, что наступило событиеВ, обозначаемая черезPr[A|B], определяется как

Pr[A|B]=Pr[AB]/Pr[B], если Pr[B]0.

Пусть {A₁, A₂, ..., A_n} - множество несовместных событий, образующее полную группу событий. Теорема о полной вероятности связывает вероятность событияВс данным множеством:

Pr[B]=

это означает, что событиеВнаступает совместно точно с одним из взаимно несовместных исчерпывающих событийA_i,i=1,n. Однако из определения условной вероятности можно написать

Pr[A_iB]=Pr[A_i|B]Pr[B]=Pr[B|A_i]Pr[A_i];

это дает вторую важную форму теоремы о полной вероятности, а именно:

Pr[B]= .

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

1. дискретные случайные величины (ДСВ), принимающие только отдельные друг от друга значения из дискретного (конечного или счетного) множества;

2. непрерывные случайные величины (НСВ), которые могут принимать любые значения из некоторого промежутка.

Примерами ДСВ являются: число покупателей в магазине, количество обращений к серверу, число процессорных операций при выполнении программы и т.д.

Примерами НСВ являются: время выполнения программы, интервалы прихода покупателей в магазин; значение температуры в течение дня и т.д.

Случайные величины часто обозначают большими буквами (например X), а их возможные значения - соответствующими малыми буквами:x₁, x₂, ..., x_n.