The simplest flows are Markov processes and solution chains. Elements of queuing theory. Modeling of this process

where is one of the possible state spaces.

Probability of transition at m-step (conditional probability):

Thus, to calculate the joint probabilities Р(Q 0 , ..,Q n) it is necessary to set the initial state of the system and indicate the physical mechanism for the change of states, which allows one to calculate the transition probabilities.

1. A special (degenerate) case of a Markov chain. The change of all states occurs independently, that is, the probability of any state at the mth step does not depend on what states the system was in at previous times.

– sequence of independent tests.

2. Probability of the phase state of the parameter Qn at a point in time tn depends only on the state the system was in at the immediately preceding point in time tn-1, and does not depend on what states the system was in at earlier times t 0 ,…,t n-2.

3. Markov chain of order, if the probability of a new state depends only on m states of the system immediately preceding it:

The time a system stays in a certain state can be either discrete or continuous. Depending on this, systems with discrete or continuous time are distinguished.

The simplest probabilistic characteristic of a random process is a set of state probabilities P 1 (t), P 2 (t), ... P n (t), Where P i (t)– probability of the system transitioning to the state S i at a point in time t. Normalization condition P 1 +P 2 +...+P n =1.

If during operation the system is in a state S i, then the probability of its transition to the state Sj in general it depends not only on the state S i, but also from the previous state.

A random process occurring in a system is called Markovsky(a process without aftereffect), if for any moment in time t 0 probability of the system state in the future (with t>t 0) depends only on the state in the present (with t=t 0) and does not depend on how and in what way the system came to this state (i.e. does not depend on the previous history).

Event Streams

The transition of the system to a certain state is event.

The sequence of system transitions to the state S i represents stream of events.

The stream of events is called ordinary, if the event in it occurs one at a time.

Time intervals t 1, t 2, ... t n ordinary flow can be the same or different, discrete or continuous, random or non-random.

If time intervals t 1, t 2, ... t n are non-random values, then the flow is called regular or deterministic, and this flow is described by specifying the values T 1 ,T 2 , ... T n.

If T 1 ,T 2 , ... T n are random, then the flow is called random and it is characterized by the law of distribution of quantities T 1 ,T 2 ,... T n.

In practice, there are often systems in which T i– continuous random variable. In these cases, the system can be described by the probability density f(t 1 , t 2 , ... t n), Where t i– specific value of a random variable T i.

The stream is called stationary, if its probabilistic characteristics do not change over time, i.e. probability of occurrence of a particular number of events m to a section of the time axis t¢+t depends only on the length of the segment t and does not depend on where on the time axis the segment is selected.

The intensity (density) of the flow of events (the average number of events per unit time) is constant.

If the time interval t i is a uniform random variable, then such a flow called aftereffect flow and its state is in probabilistic dependence on the previous state.

If random variables t i independent, then such a flow is called flow with limited aftereffect and the probability density of this flow is equal to the product of the probability densities:

f(t 1 ,t 2 , ...t n) = f 1 (t 1) f 2 (t 2) ... f n (t n)(6.5)

A flow with limited aftereffect can be stationary and uniform in time. In this case, all intervals between adjacent events have the same distribution law:

f i (t i) = f (t i)(6.6)

A flow without aftereffect is called a random flow if, for any non-overlapping time segments, the number of events falling on one of them does not depend on how many events fall on other segments.

Poisson flow

Streams of random events are called Poisson, if the number of thread events m, falling on any area t, distributed according to Poisson's law

P m = e - a , (6.7)

Where A– average number of events located in the area t.

A Poisson flow is stationary if the event density l is constant, then the average number of events is lt, otherwise the flow will be unsteady.

A random flow of events, which has the property of stationarity, ordinaryness and has no aftereffect, is called the simplest and is stationary Poisson flow.

Sifted streams

The process of transitions of a system with discrete operating time can be considered as the impact of a discrete flow of events, which is characterized by the fact that at times t 1, t 2, ..., t n events occur with probability P i. The distribution function of such a flow is:

Sifting through the flow of events S 1, S 2, ... S n, which occur at certain points in time with probabilities p 1 , p 2 , ... p n, means transforming these probabilities into , , ..., . If the flow is stationary, then these probabilities are equal: = =...=1-p.

In this case, p is a sifting constant, which is determined either by the influence of some destabilizing factor, or is determined by the exclusion of any events from the set of states of the system.

Examples of streams with limited aftereffect are Erlang streams. They are formed by regular sifting of the simplest flow, while regular sifting is understood as a procedure that results in the exclusion of several subsequent events in the original flow. If every odd event is eliminated in the simplest flow, then the remaining events form a second-order Erlang flow. The time interval between neighboring events in such a flow is the sum of independent random variables and , distributed according to the exponential law ( = + ).

If in the simplest flow only every third event is stored, then we get an Erlang flow of the third order, etc. In general, Erlang stream k- about the simplest stream produced by an exception is called (k- 1) events and saving k-th event.

Discrete Markov chains

A Markov random process with discrete states and discrete operating time describes the system S with a finite number of states. In this case, transitions are possible at fixed times t 1 , t 2 , ..., t k. The process occurring in this system can be represented as a chain of random events

S 1 (0) ® S 2 (1) ® ... ® S i (n) ® ... ® S n (k).

This sequence is called a discrete Markov chain if for each step n=1,2, ... k probability of transitions from any state (S i ®S j) does not depend on how the system arrived at the state S i. Each transition of the system corresponds to a conditional probability

P. (6.9)

For each step number n possible transitions form full group of events.

homogeneous, if the transition probabilities do not depend on the step number. A complete description of such a chain can be a square matrix of transition probabilities

and the vector of the initial probability distribution for all states at time t=0.

= . (6.10)

The transition probabilities corresponding to impossible transitions are equal to 0, and the probabilities along the main diagonal correspond to the fact that the system has not changed its state.

A discrete Markov chain is called heterogeneous, if the transition probabilities change with the step number. To describe such circuits it is necessary to set k transition probability matrices P ij (k– number of considered steps). The main task of the analysis of Markov processes is to determine the probability of all states of the system after any number of steps. Moreover, if the matrix of transition probabilities and the vector of the initial distribution are known, then the probabilities of the system states after each step are determined by the total probability formula:

P(A) = P(B i)*P(A/B i)(6.11)

After the first step the probability P i can be defined as follows:

P i (1) = P j (0)P ji , (6.12)

Where Pj(0) – vector of initial states,

P ji– row of the matrix of conditional probabilities.

P i (2) = P j (1)P ji = P j (0)P ji (1)(6.13)

After k steps:

P i (k) = P j (k-1)P ji = P j (0)P ji (k),(6.14)

Where Pji(k)– probabilities of system transitions from the state S i V Sj behind k steps.

If a transition from the state is possible S i in a state Sj behind k steps, then the value P ji (k)>0. If the reverse transition is possible in the same number of steps, then the state S i called returnable. The probability that the system will go out of state S i and for k steps will return to it, equal to 1 for return states.

State S i - irrevocable, if this probability is different from 1.

States S i And Sj are called communicating, if transition is possible S i ®S j in a finite number of steps.

In previous lectures we learned how to simulate the occurrence of random events. That is, we can play which of possible events will occur and in which quantity. To determine this, you need to know the statistical characteristics of the occurrence of events, for example, such a value could be the probability of an event occurring, or the probability distribution of different events, if there are infinitely many types of these events.

But often it is also important to know When this or that event will specifically occur in time.

When there are many events and they follow each other, they form flow. Note that the events must be homogeneous, that is, somewhat similar to each other. For example, the appearance of drivers at gas stations wanting to refuel their car. That is, homogeneous events form a certain series. In this case, it is assumed that the statistical characteristic of this phenomenon (the intensity of the flow of events) is given. The intensity of the event flow indicates how many average such events occur per unit of time. But exactly when each specific event will occur must be determined using modeling methods. It is important that when we generate, for example, 1000 events in 200 hours, their number will be approximately equal to the average intensity of occurrence of events 1000/200 = 5 events per hour, which is a statistical value characterizing this flow as a whole.

The flow intensity in a sense is the mathematical expectation of the number of events per unit time. But in reality it may turn out that 4 events appear in one hour, 6 in another, although on average there are 5 events per hour, so one value is not enough to characterize the flow. The second quantity characterizing how large the spread of events is relative to the mathematical expectation is, as before, dispersion. Actually, it is this value that determines the randomness of the occurrence of an event, the weak predictability of the moment of its occurrence. We will talk about this value in the next lecture.

A stream of events is a sequence of homogeneous events occurring one after another at random intervals. On the time axis, these events look like shown in Fig. 28.1.

An example of a flow of events is the sequence of moments when planes arriving at an airport touch down on the runway.

Flow intensity λ this is the average number of events per unit of time. The flow intensity can be calculated experimentally using the formula: λ = N/T n, Where N number of events that occurred during observation T n.

If the interval between events τ j equal to a constant or defined by some formula in the form: t j = f(t j 1), then the flow is called deterministic. Otherwise the flow is called random.

There are random streams:

• ordinary: the probability of the simultaneous occurrence of two or more events is zero;
• stationary: frequency of occurrence of events λ (t) = const( t) ;
• without aftereffect: the probability of a random event occurring does not depend on the moment of occurrence of previous events.

Poisson flow

It is customary to take the Poisson flow as the flow standard in modeling..

Poisson flow this is an ordinary flow without aftereffect.

As previously stated, the probability that during a time interval (t 0 , t 0 + τ ) will happen m events is determined from Poisson's law:

Where a Poisson parameter.

If λ (t) = const( t) , that is stationary Poisson flow(simplest). In this case a = λ · t . If λ = var( t) , that is unsteady Poisson flow.

For the simplest flow, the probability of occurrence m events during τ is equal to:

The probability of non-occurrence (that is, none, m= 0 ) events over time τ is equal to:

Rice. 28.2 illustrates the dependency P 0 from time. Obviously, the longer the observation time, the less likely it is that no event will occur. Moreover, the higher the value λ , the steeper the graph goes, that is, the faster the probability decreases. This corresponds to the fact that if the intensity of the occurrence of events is high, then the probability of the event not occurring quickly decreases with observation time.

The probability of at least one event occurring ( PХБ1С) is calculated as follows:

because P HB1S + P 0 = 1 (either at least one event will appear, or none will appear, the other is not given).

From the graph in Fig. 28.3 it is clear that the probability of the occurrence of at least one event tends to unity over time, that is, with a corresponding long-term observation of the event, it will definitely happen sooner or later. The longer we observe an event (the more t), the greater the probability that the event will occur; the graph of the function increases monotonically.

The greater the intensity of the occurrence of the event (the more λ ), the faster this event occurs, and the faster the function tends to unity. Parameter on the chart λ represented by the steepness of the line (slope of the tangent).

If you increase λ , then when observing an event during the same time τ , the probability of an event occurring increases (see Fig. 28.4). Obviously, the graph starts from 0, since if the observation time is infinitesimal, then the probability that the event will occur during this time is negligible. And vice versa, if the observation time is infinitely long, then the event will definitely occur at least once, which means that the graph tends to a probability value equal to 1.

By studying the law, you can determine that: m x = 1/λ , σ = 1/λ , that is, for the simplest flow m x = σ . The equality of the mathematical expectation to the standard deviation means that this flow is a flow without aftereffect. The dispersion (more precisely, the standard deviation) of such a flow is large. Physically, this means that the time of occurrence of an event (the distance between events) is poorly predictable, random, and lies in the interval m x – σ < τ j < m x + σ . Although it is clear that on average it is approximately equal to: τ j = m x = T n/ N . An event can occur at any time, but within the range of this moment τ j relatively m x to [ σ ; +σ ] (the magnitude of the aftereffect). In Fig. Figure 28.5 shows the possible positions of event 2 relative to the time axis for a given σ . In this case, they say that the first event does not affect the second, the second does not affect the third, and so on, that is, there is no aftereffect.

Within the meaning of P equals r(see lecture 23. Modeling a random event. Modeling a complete group of incompatible events), therefore, expressing τ from the formula (*) , finally, to determine the intervals between two random events we have:

τ = 1/ λ Ln( r) ,

Where r a random number uniformly distributed from 0 to 1, which is taken from the RNG, τ interval between random events (random variable τ j ).

Example 1. Let's consider the flow of products arriving at a technological operation. Products arrive randomly on average eight pieces per day (flow rate λ = 8/24 [units/hour]). It is necessary to simulate this process within T n = 100 hours. m = 1/λ = 24/8 = 3 , that is, on average, one part per three hours. notice, that σ = 3 . In Fig. Figure 28.6 presents an algorithm that generates a stream of random events.

In Fig. Figure 28.7 shows the result of the algorithm: the moments in time when the parts arrived for the operation. As can be seen, in just the period T n = 100 production unit processed N= 33 products. If we run the algorithm again, then N may turn out to be equal, for example, 34, 35 or 32. But on average, for K algorithm runs N will be equal to 33.33 If you calculate the distances between events t With i and time points defined as 3 i, then on average the value will be equal to σ = 3 .

Modeling extraordinary flows of events

If it is known that the flow is not ordinary, then it is necessary to model, in addition to the moment of occurrence of the event, also the number of events that could appear at this moment. For example, cars arrive at a railway station as part of a train at random times (regular train flow). But at the same time, a train may have a different (random) number of cars. In this case, the flow of carriages is spoken of as a flow of extraordinary events.

Let's assume that M k = 10 , σ = 4 (that is, on average, in 68 cases out of 100, there are from 6 to 14 cars in the train) and their number is distributed according to the normal law. In the place marked (*) in the previous algorithm (see Fig. 28.6), you need to insert the fragment shown in Fig. 28.8.

Example 2. The solution to the following problem is very useful in production. What is the average daily downtime of the equipment of a technological node if the node processes each product for a random time specified by the intensity of the flow of random events λ 2? At the same time, it has been experimentally established that products are also brought for processing at random times specified by the flow λ 1 in batches of 8 pieces, and the batch size fluctuates randomly according to the normal law with m = 8 , σ = 2 (see lecture 25). Before modeling T= 0 there were no products in stock. It is necessary to simulate this process within T n = 100 hours.

In Fig. Figure 28.9 presents an algorithm that randomly generates a flow of arrivals of batches of products for processing and a flow of random events exit of batches of products from processing.

In Fig. Figure 28.10 shows the result of the algorithm: the moments in time when parts arrived at the operation, and the moments in time when parts left the operation. The third line shows how many parts were in the queue for processing (lying in the node’s warehouse) at different points in time.

By noting for the processing node the times when it was idle waiting for the next part (see in Fig. 28.10 the time sections highlighted in red), we can calculate the total downtime of the node for the entire observation time, and then calculate the average downtime during the day. For this implementation, this time is calculated as follows:

T etc. Wed. = 24 · ( t 1 ave. + t 2 ave. + t 3 ave. + t 4 ave + + t N etc.)/ T n.

Exercise 1 . Changing the value σ , install dependency T etc. Wed. ( σ ) . Setting the cost for node downtime at 100 euros/hour, determine the enterprise’s annual losses from irregularity in the work of suppliers. Suggest the wording of the clause of the enterprise’s contract with suppliers “The amount of the fine for delay in delivery of products.”

Task 2. By changing the amount of initial warehouse filling, determine how the enterprise's annual losses from irregularity in the work of suppliers will change, depending on the amount of inventory accepted at the enterprise.

Simulation of non-stationary event streams

In some cases, the flow intensity may change over time λ (t) . Such a flow is called unsteady. For example, the average number of ambulances per hour leaving the station in response to calls from the population of a large city may vary throughout the day. It is known, for example, that the largest number of calls falls on the intervals from 23 to 01 am and from 05 to 07 am, while in other hours it is half as much (see Fig. 28.11).

In this case, the distribution λ (t) can be specified either by a graph, a formula, or a table. And in the algorithm shown in Fig. 28.6, in the place marked (**), you will need to insert the fragment shown in Fig. 28.12.

Transcript

1 AN Moiseev AA Nazarov Asymptotic analysis of a high-intensity semi-Markov flow 9 UDC 5987 AN Moiseev AA Nazarov Asymptotic analysis of a high-intensity semi-Markov flow of events A study of a high-intensity semi-Markov flow of events is presented. It is shown that for the flow under consideration, the probability distribution of the number of events occurring over a fixed time interval, subject to an unlimited increase in the intensity of the flow, can be approximated by a normal distribution. The parameters of this distribution are obtained in the work. Key words: high-intensity flow of events, semi-Markov flow, asymptotic analysis. One of the basic elements of queuing systems and networks is the incoming flow of requests. Modern telecommunication networks and distributed information processing systems require high throughput of information transmission channels. Thus in these systems, the number of data packets arriving for processing per unit of time is very high. In terms of queuing theory, in such cases they speak of a high intensity of the incoming flow. In particular, in the work, the high-intensity flow model is used to simulate the flow of incoming messages of a multiphase distributed data processing system. The works were studied properties of high-intensity recurrent MMPP- and MAP-flows This paper presents an analysis of the properties of a high-intensity semi-Markovian (Semi-Markovian or SM-) flow as the most general model of event flows Mathematical model Consider a semi-Markov flow of homogeneous events specified as follows Let (ξ n τ n ) stationary two-dimensional Markov process with discrete time Here ξ n is a discrete component taking values ​​from to K τ n is a continuous component taking non-negative values. We will assume that the evolution of the process is determined by the elements of the so-called semi-Markov matrix A (x) = ( Ak ν ) k ν= as follows K: x Akν (x) = P ξ n+ =ν τ n+< ξ n = k N Здесь N некоторая большая величина которая введена искусственно чтобы явным образом подчеркнуть малость величин τ n В теоретических исследованиях будем полагать N и таким образом τ n На практике полученные результаты можно использовать для аппроксимации соответствующих величин при достаточно больших значениях N (в условии высокой интенсивности потока) Пусть в момент времени t = произошло изменение состояния процесса {ξ n τ n } Последовательность моментов времени t n определяемая рекуррентным выражением tn+ = tn+τ n+ для n = называется полумарковским потоком случайных событий определяемым полумарковской матрицей A(x) Процесс ξ n =ξ(t n) называют вложенной в полумарковский поток цепью Маркова Поскольку средняя длина интервалов τ n обратно пропорциональна N то при N интенсивность наступления событий в таком потоке будет неограниченно расти Такой поток событий будем называть высокоинтенсивным полумарковским или HISM-потоком (от High-Intensive Semi- Markovian) Ставится задача нахождения числа событий m(t) наступивших в этом потоке в течение интервала времени (t) Вывод уравнений Колмогорова Пусть z(t) длина интервала времени от момента t до момента наступления следующего события в потоке; k(t) случайный процесс значения которого на каждом из интервалов = () Отсюда получаем матричное дифференциальное уравнение относительно функции R(z): R (z) = R ()[ I A (z) ] (3) граничное условие для которого при z имеет вид R () = λr (4) где λ некоторый коэффициент вектор-строка r есть стационарное распределение состояний вложенной цепи Маркова Этот вектор является решением уравнения Колмогорова r= r P где P= lim A (z) есть стохастическая матрица определяющая вероятности переходов вложенной цепи z Маркова Таким образом решение уравнения (3) имеет вид z R() z = R ()[ I A () x ] dx (5) Пусть R= R () есть стационарное распределение значений полумарковского процесса k(t) тогда при z из (5) получаем R= R ()[ I A(x) ] dx=λ r[ I A(x) ] dx=λr [ P A(x) ] dx=λra (6) где A матрица с элементами Akν = [ Pkν Akν(x) ] dx Умножая левую и правую части равенства (6) на единичный вектор-столбец E получим RE = =λrae откуда находим значение коэффициента λ: λ= (7) rae Доклады ТУСУРа 3 (9) сентябрь 3

3 AN Moiseev AA Nazarov Asymptotic analysis of high-intensity semi-Markov flow jum Let us introduce the notation Hkuzt () = e Pkmzt () where j = imaginary unit and u is some variable Multiplying () by e jum and summing over m from to we obtain m= Hkuzt () Hkuzt ( ) Hku (t) K ju Hku (t) = + e Aν k (z) N ν= Taking into account the row vector notation H(u z t) = (H(u z t) H(K u z t)), this equation takes the form H(uzt) H(uzt) H(u t) ju = + e A(z) I (8) N We will solve the differential matrix equation (8) asymptotically by the method under the condition of unlimitedly increasing intensity λn of the semi-Markov flow under consideration as N First-order asymptotics Let us introduce the notation N =ε u= ε w H(uzt) = F (wzt ε) From (8) we obtain F(wzt ε) F(wzt ε) F(w t ε) jwε ε = + e A(z) I ( 9) Theorem The asymptotic solution F(wzt) = lim F (wzt ε) of equation (9) has the form ε () () jw λ F wzt = R ze t () where R(z) is determined by the expression (5) Proof Let’s do it in (9) passing to the limit ε we obtain the equation F(wzt) F(w t) = + [ A(z) I ] which has the form similar to () Therefore, the function F (w z t) can be represented as F(wzt) = R (z) Φ(wt) () where Φ (w t) is some scalar function. Let us pass to the limit z in (9) and sum up all the components of this equation (to do this, we multiply both sides on the right by the unit column vector E) We obtain F(w t ε) F (w t ε) ε E= e P I E Substitute here the expression () use the expansion e = + jε w+ O(ε) divide both sides by ε and pass to the limit ε: Φ(wt) RE = jwr () PE Φ(wt) from where, taking into account (4), we obtain a differential equation for the function Φ (w t): Φ(wt) = jwλφ (wt) Solving this equation under the initial condition Φ (w) = we obtain the solution jwλt Φ (wt) = e Substitute this expression in ( ) we obtain () The theorem is proven ju Nt Second-order asymptotics Let us make the replacement H(uzt) = H (uzte) λ in (8): H(uzt) H(uzt) H(u t) ju + juλ H(u z t) = + e A(z) I () N Let us introduce the notation N =ε u= ε w H(uzt) = F (wzt ε) (3) TUSUR Reports 3 (9) September 3

4 MANAGEMENT COMPUTER ENGINEERING AND INFORMATION SCIENCE Then () will be rewritten as F(wzt ε) F(wzt ε) F(w t ε) ε + λf (wzt ε) = + e A(z) I (4) Theorem Asymptotic solution F( wzt) = lim F (wzt ε) equation (4) has the form ε (jw) F (wzt) = R (z)exp (λ+κ) t (5) where R(z) is determined by the expression (5) κ= fe (6) row vector f satisfies a system of linear algebraic equations f I P =λ rp R λ a (7) f AE= a = rae A = x da (x) Proof Let us pass to the limit ε in (4) we obtain the equation F( wzt) F(w t) = + [ A(z) I ] which has the form similar to () Therefore, the function F (w z t) can be represented as F(wzt) = R (z) Φ(wt) (8) where Φ ( w t) some scalar function The solution to equation (4) will be sought in the form of expansion F(wzt ε) =Φ (wt) R(z) + jε wf (z) + O(ε) (9) where f(z) is some vector -function (string) Substituting this expression into (4) and applying the expansion e = + jε w+ O(ε) after some transformations we obtain ( ) λφ (wt) R() z=φ (wt) R() z+ f () z+ R() A() z I + R() A() z+ f () A() z I+ A () z + O(ε) Taking into account (3) (4) dividing both sides by jεw and canceling Φ ( w t) we obtain λ R(z) = f (z) + λ ra(z) + f ()[ A(z) I ] + O(ε) From here, for ε, we obtain a differential equation for the unknown vector function f(z) f ( z) = f ()[ I A(z) ] λ[ ra(z) R (z) ] integrating which under the initial condition f() = we obtain the expression z f(z) = ( f ()[ I A(x) ] λ [ ra(x) R (x) ]) dx () We will look for f(z) in the class of functions satisfying the condition lim ( f ()[ I A(x) ] λ[ ra(x) R (x) ]) = x From here we obtain f ()[ I P] λ[ rp R ] = () Subtracting the left side of this equality from the integrand () taking into account (6) we obtain f() = f () A+λrA λ [ R R (x) ] dx () It can be shown that [ R R (x) ] dx= λ ra where A = x da (x) Taking this into account, multiplying both sides () on the right by the unit vector E we obtain TUSUR Reports 3 (9) September 3

5 AN Moiseev AA Nazarov Asymptotic analysis of high-intensity semi-Markov flow 3 λ a [ f () A f()] E = (3) where a = rae Assuming that f() E = and denoting f = f () from () and ( 3) we obtain the system of equations (7) Let us pass to the limit z in (4) and multiply both sides of the equation by E on the right, we obtain F(w t ε) F(w t ε) jw (w t) jw jw (w t) ε ε e F ε ε E+ ε λf ε E= P I E= E (e) () 3 Substitute here (9) and apply the expansion e = + jε w+ + O(ε) we obtain Φ(wt) (jεw) 3 ε RE+ λφ (wt) RE = Φ (wt)[ R () + f ()] E jw ε + + O(ε) Reducing similar reductions by ε using notation (6) and passing to the limit at ε we obtain the following differential equation for the unknown function Φ (w t): Φ(wt) (jw) = Φ(wt) (λ+κ) (jw) solving which under the initial condition Φ (w) = we obtain Φ (wt) = exp (λ+κ) t Substituting this expression in (8) we obtain (5) The theorem is proven Approximation of the distribution of the number of events occurring in the HISM flow Making changes in (5) inverse to (3) and returning to the function H(u z t) we obtain (ju) H(u z t) R (z)exp juλ Nt + (λ+κ) Nt Thus, the characteristic function of the number of events occurring in a high-intensity semi-Markov flow during time t satisfies the relation (ju) hut () = H(u t) E exp juλ Nt+ (λ+κ) Nt That is, for sufficiently large values N distribution of the number of events occurring in a HISM flow during time t can be approximated by a normal distribution with mathematical expectation λnt and variance (λ + κ)nt where λ and κ are determined by expressions (7) and (6) Numerical results As an example for numerical calculations Let's consider the problem of modeling events in a high-intensity semi-Markov flow specified by a third-order semi-Markov matrix A(x) written in the form A(x) = P * G(x) where P is a stochastic matrix; G(x) is a matrix composed of some distribution functions; operation * Hadamard product of matrices We will consider an example when the elements of the matrix G(x) correspond to gamma distribution functions with parameters of shape α kν and scale β kν k ν = 3, which we will represent in the form of matrices α and β, respectively. We will choose the following specific parameter values: P = 3 5 α = 5 4 β = As a result of the calculations, the following parameter values ​​were obtained: λ 99; κ 96 For this problem, flow simulation was performed for values ​​N = 3 and empirical distributions of the number of events in intervals of length t = were constructed. Series of distributions of empirical data and corresponding approximations for N = and N = are presented graphically in Fig. (for other values ​​of N, the graphs are almost coincide and become indistinguishable in the figure) TUSUR reports 3 (9) September 3

6 4 4 MANAGEMENT COMPUTER ENGINEERING AND INFORMATION SCIENCE 5 8 N = N = Fig Comparison of the polygon of relative frequencies of the empirical distribution () and the approximating distribution series () To assess the accuracy of the approximation of the distribution, we will use the Kolmogorov distance Dq = sup Fq(x) F(x) Here F q (x) empirical distribution function F(x) function x of the distribution of a normal random variable with the characteristics found above The table shows the dependence of the quality of approximation on the value N N δ relative errors in calculating the mathematical a δ D D q 8% 6% 464 expectations δ a and variance δ D as well as the Kolmogorov distance D q for the considered cases 9% 7% % 5% Figure shows a graph showing % 4% 44 the decrease in the Kolmogorov distance between the empirical and 8% % analytical (normal) distributions with increasing values ​​of N D q You can notice that already at 5 N > 3, a sufficiently high quality of Gaussian approximation of the number of events in the considered high-intensity semi-Markov flow is achieved (the Kolmogorov distance does not exceed) 3 Fig. Change in the Kolmogorov distance D q depending on the flow intensity (logarithmic scale in N) N Conclusion The work presents study of a high-intensity semi-Markov stream of events It is shown that, under the condition of unlimited growth of its intensity, the distribution of the number of events occurring in a given stream during a time interval of a fixed length can be approximated by a normal distribution. The parameters of this distribution are obtained in the work. The considered numerical examples demonstrate the applicability of the obtained asymptotic results for HISM-streams of events Similar results were obtained earlier for other types of high-intensity flows: recurrent MMPP MAP TUSUR Reports 3 (9) September 3

7 AN Moiseev AA Nazarov Asymptotic analysis of high-intensity semi-Markov flow 5 References Gnedenko BV Introduction to the theory of queuing / BV Gnedenko IN Kovalenko 4th ed. revision M: Publishing house LKI 7 4 s Grachev VV Multiphase queuing model of a distributed data processing system / VV Grachev AN Moiseev AA Nazarov VZ Yampolsky // TUSUR reports (6) h C Moiseev A Investigation of High Intensive General Flow / A Moiseev A Nazarov // Proc of the IV International Conference “Problems of Cybernetics and Informatics” (PCI) Baku: IEEE P Moiseev A Investigation of the High Intensive Markov-Modulated Poisson Process / A Moiseev A Nazarov // Proc Of The International Conference On Application Of Information And Communication Technology And Statistics In Economy And Education (ICAICTSEE-) Sofia: University Of National And World Economy P Moiseev AN Study of high-intensity MAP flow / AN Moiseev AA Nazarov // Izv. Tom Polytechnic University 3 T 3 S Korolyuk VS Stochastic models of systems Kiev: Nauk Dumka s 7 Nazarov AA Theory of probability and random processes: textbook / AA Nazarov AF Terpugov-e izd ispr Tomsk: NTL Publishing House 4 p 8 Nazarov AA Method of asymptotic analysis in queuing theory / AA Nazarov SP Moiseeva Tomsk: NTL Publishing House 6 p 9 Korn G Handbook of mathematics for scientists and engineers / G Korn T Korn M: Science with Rykov VV Mathematical statistics and experimental planning: textbook / VV Rykov VY Itkin M: MAKS Press 38 with Moiseev Alexander Nikolaevich Candidate of Technical Sciences Associate Professor, Department of Software Engineering, Tomsk State University (TSU) Tel: 8 (38-) Email: Nazarov Anatoly Andreevich Doctor of Technical Sciences Professor Head of the Department of Probability Theory and Mathematical Statistics TSU Tel: 8 (38-) Email: Moiseev AN Nazarov AA Asymptotic analysis of the high-intensive semi-Markovian arrival process Investigation of the high -intensive semi-Markovian arrival process is presented in the paper It is shown that a distribution of the number of arrivals in the process during some period under asymptotic condition of an infinite growth of the process rate can be approximated by normal distribution The characteristics of the approximation are obtained as well The analytical results are supported by numeric examples Keywords: high-intensive arrival process semi-markovian process asymptotic analysis TUSUR Reports 3 (9) September 3

BIBLIOGRAPHY. Balasanyan S.Sh. Stratified model for assessing and analyzing the efficiency of functioning of complex technological systems with many states // News of the Tomsk Polytechnic

ASYMPTOTIC ANALYSIS OF AN OPEN LOOP NON-MARKOV QUESTION NETWORK HIMMPP (GI) K A. Nazarov, A. Moiseev Tomsk State University Tomsk, Russia [email protected] The work presents

BULLETIN OF TOMSK STATE UNIVERSITY 2008 Department of Computer Science and Information Science 3(4) UDC 6239; 592 SV Lopukhova RESEARCH OF MMR FLOW BY THE ASYMPTOTIC METHOD OF THE TH ​​ORDER The work considers

S.A. Matveev, A.N. Moiseev, A.A. Nazarov. Application of the method of initial moments 9 UDC 59.87 S.A. Matveev, A.N. Moiseev, A.A. Nazarov Application of the method of initial moments to study a multiphase system

BULLETIN OF TOMSK STATE UNIVERSITY 7 Management of computer technology and information science UDC 5987 TA Karlykhanova SIFT FLOW METHOD FOR STUDYING THE GI/GI/ SYSTEM For a queuing system

UDC 6.39.; 59. S.V. Lopukhova A.A. Nazarov STUDY OF MAR-FLOW BY THE METHOD OF ASYMPTOTIC ANALYSIS OF THE NTH ORDER The MAR-flow is considered. This flow has been studied using the asymptotic method.

BULLETIN OF TOMSK STATE UNIVERSITY 8 Management of computer technology and information science 4(5) MATHEMATICAL MODELING UDC 59.87 V.A. Vavilov A.A. Nazarov MATHEMATICAL MODELING OF UNSTABLE

Branch of Kemerovo State University in Anzhero-Sudzhensk National Research Tomsk State University Kemerovo State University Institute of Management Problems

BULLETIN OF TOMSK STATE UNIVERSITY Management of computer technology and information science 3() UDC 59.87 I.A. Ivanovskaya S.P. Moiseeva RESEARCH OF A MODEL OF PARALLEL SERVICE OF MULTIPLE ORDERS

BULLETIN OF TOMSK STATE UNIVERSITY 2011 Management, computer technology and information science 3(16) INFORMATION PROCESSING UDC 519.872 I.L. Lapatin, A.A. Nazarov CHARACTERISTICS OF MARKOV SYSTEMS

A.A. Nazarov I.A. Semenov. Comparison of asymptotic and prelimit characteristics 187 UDC 4.94:519.872 A.A. Nazarov I.A. Semenova Comparison of asymptotic and prelimit characteristics of the MAP/M/ system

Branch of Kemerovo State University in Anzhero-Sudzhensk National Research Tomsk State University Kemerovo State University Institute of Management Problems

Statistical radiophysics and information theory Lecture 7 8. Continuous-time Markov chains Continuous-time Markov chains are a Markov random process X t, consisting of

BULLETIN OF TOMSK STATE UNIVERSITY 9 Management of computer technology and information science (7) MATHEMATICAL MODELING UDC 5987 VA Vavilov MATHEMATICAL MODELING UNSTABLE RANDOM NETWORKS

CHAPTER 5. MARKOV PROCESSES WITH CONTINUOUS TIME AND A DISCRETE SET OF STATES As a result of studying this chapter, students should: know the definitions and properties of Markov processes with continuous

As a manuscript Zadiranova Lyubov Aleksandrovna RESEARCH OF MATHEMATICAL MODELS OF FLOW IN INFINITELY LINEAR QS WITH REPEATED MAINTENANCE OF REQUIREMENTS 05.13.18 Mathematical modeling, numerical

BULLETIN OF TOMSK STATE UNIVERSITY 7 Management of computer technology and information science UDC 59 NV Stepanova AF Terpugov PRICE MANAGEMENT IN THE SALE OF PERISHABLE PRODUCTS Management is considered

BULLETIN OF TOMSK STATE UNIVERSITY Management, computer technology and information science () UDC 59.865 K.I. Livshits, Ya.S. Bagel PROBABILITY OF RUIN OF AN INSURANCE COMPANY UNDER DOUBLE STOCHASTIC

UDC 6-5 Spectral characteristics of linear functionals and their applications to the analysis and synthesis of stochastic control systems K.A. Rybakov The article introduces the concept of spectral characteristics of linear

As a manuscript Lapatin Ivan Leonidovich RESEARCH OF MATHEMATICAL MODELS OF OUTPUT STREAM OF QUEUE SYSTEMS WITH AN UNLIMITED NUMBER OF DEVICES 05.13.18 Mathematical modeling, numerical

Contents Chapter Random processes Simple homogeneous Markov chain Markov equation Simple homogeneous Markov chain 4 Properties of the transition matrix 5 Numerical experiment: stabilization of the probability distribution

INSTITUTE OF COMPUTATIONAL MATHEMATICS AND MATHEMATICAL GEOPHYSICS SIBERIAN BRANCH OF THE RUSSIAN ACADEMY OF SCIENCES MARCHUKOV SCIENTIFIC READINGS 017 June 5 July 14, 017 Proceedings Editorial Board academician

STUDY OF RQ-SYSTEM M GI 1 BY ASYMPTOTIC ANALYSIS METHOD UNDER HEAVY LOAD CONDITIONS E. Moiseeva, A. Nazarov Tomsk State University Tomsk, Russia [email protected] The work considers

UDC 6-5:59 NS Demin SV Rozhkova OV Rozhkova FILTERING IN DYNAMIC SYSTEMS BY CONTINUOUS-DISCRETE OBSERVATIONS WITH MEMORY IN THE PRESENCE OF ANOMALIC INTERFERENCE II CONTINUOUS-DISCRETE OBSERVATIONS In this work

Numerical methods Topic 2 Interpolation V I Velikodny 2011 2012 academic year 1 The concept of interpolation Interpolation is a method of approximately or accurately finding any value from known individual values

Ukrainian Mathematical Journal Volume 5 (28), 3, 293 34 On boundary value problems for an ordinary differential operator with matrix coefficients Anna V Agibalova (Presented by M M Malamud) Abstract

Lecture 2. Statistics of the first type. Pointed estimates and their properties Bure V.M., Grauer L.V. ShAD St. Petersburg, 2013 Bure V.M., Grauer L.V. (SHAD) Lecture 2. Statistics of the first type. Dotted St. Petersburg,

Management of computer technology and information science UDC 6-5:59 RESEARCH OF THE EFFICIENCY OF A DISCRETE OBSERVATION CHANNEL WITH MEMORY IN THE EXTRAPOLATION PROBLEM NS Demin OV Rozhkova* Tomsk State University

Statistical radiophysics and information theory Lecture 6 7. Markov* random processes and Markov chains. *Markov Andrey Andreevich (born 1890) Russian mathematician, academician Markov random process

Siberian Mathematical Journal July August, 2003 Volume 44, 4 UDC 51921+5192195 ON THE COMPONENTS OF FACTORIZATION REPRESENTATION FOR THE Dwelling Time of SEMI-CONTINUOUS RANDOM WALKS IN THE BAND IN S Lugavów

As a manuscript Gorbatenko Anna Evgenievna RESEARCH OF QUEUE SYSTEMS WITH CORRELATE FLOWS UNDER SPECIAL LIMITING CONDITIONS 05.13.18 Mathematical modeling, numerical methods

Management of computer technology and information science UDC 59. INFORMATION ASPECT IN THE JOINT PROBLEM OF CONTINUOUS-DISCRETE FILTERING AND INTERPOLATION. ANALYSIS S.V. Rozhkova O.V. Rozhkova Tomsk Polytechnic

Siberian Mathematical Journal July August, 2005. Volume 46, 4 UDC 519.21 ON FACTORIZATION REPRESENTATIONS IN BOUNDARY PROBLEMS FOR RANDOM WALKS SPECIFIED ON A MARKOV CHAIN ​​V. I. Lotov, N. G. Orlova

Lecture 3 Stability of equilibrium and motion of a system When considering steady motions, we write the equations of perturbed motion in the form d dt A Y where the column vector is a square matrix of constant coefficients

Chapter 1 Differential equations 1.1 The concept of a differential equation 1.1.1 Problems leading to differential equations. In classical physics, each physical quantity is associated with

Lecture CHARACTERISTIC FUNCTION PURPOSE OF THE LECTURE: to construct a method for linearization of functions of random variables; introduce the concept of a complex random variable and obtain its numerical characteristics; determine characteristic

Modeling systems using Markov random processes Basic concepts of Markov processes The function X(t) is called random if its value for any argument t is a random variable.

1. FINITE HOMOGENEOUS MARKOV CHAINS Consider a sequence of random variables ξ n, n 0, 1,..., each of which is distributed discretely and takes values ​​from the same set (x 1,...,

Chapter 6 Fundamentals of Stability Theory Lecture Problem Statement Basic Concepts Previously, it was shown that the solution to the Cauchy problem for a normal system ODE = f, () continuously depends on the initial conditions at

Sin cos R Z cos ImZ cos sin sin The solutions found in this way form a fundamental system of solutions and therefore the general solution of the system has the form or, in more detail, sin cos cos sin cos cos cos sin sin

Structural reliability. Theory and practice Kashtanov V.A. STRUCTURE CONTROL IN QUEUE AND RELIABILITY MODELS Using controlled semi-Markov processes, the optimal

MATHEMATICAL MODEL OF AN INSURANCE COMPANY IN THE FORM OF A QUEU SERVICE SYSTEM M M I. Sinyakova, S. Moiseeva National Research Tomsk State University Tomsk, Russia [email protected]

UDC 59. SEPARATION THEOREM IN THE CASE OF OBSERVATIONS WITH MEMORY N.S. Demin, S.V. Rozhkova Tomsk State University Tomsk Polytechnic University E-mail: [email protected] Proof is given

By the conditions of the theorem L B (m Then, due to the linearity of the operator L, we have: m m m L L ] B [ Systems of linear differential equations with constant coefficients Eigenvalues ​​and eigenvectors

REFERENCES Kalashnikova TV Izvekov NU Integration of the demand orientation method into the pricing system of a retail chain // News of Tomsk Polytechnic University T 3 6 S 9 3 Fomin

INSTITUTE OF COMPUTATIONAL MATHEMATICS AND MATHEMATICAL GEOPHYSICS SIBERIAN BRANCH OF THE RUSSIAN ACADEMY OF SCIENCES MARCHUKOV SCIENTIFIC READINGS 217 June 25 July 14, 217 Proceedings Editorial Board academician

TOPIC 7. Random processes. The purpose of the content of topic 7 is to give initial concepts about random processes and Markov chains in particular; outline the range of economic problems that models use in their solution,

Lecture 4. Confidence intervals Bure V.M., Grauer L.V. ShAD St. Petersburg, 2013 Bure V.M., Grauer L.V. (SHAD) Lecture 4. Confidence intervals St. Petersburg, 2013 1 / 49 Contents Contents 1 Confidence intervals

Siberian Mathematical Journal January February, 2. Volume 41, 1 UDC 517.948 ASYMPTOTICS OF SOLUTIONS TO SINGULARLY PERTURBED NONLINEAR INTEGRODIFERENTIAL EQUATIONS M. K. Dauylbaev Abstract: Considered singularly

Lecture Modeling systems using Markov random processes Basic concepts of Markov processes A function X(t) is called random if its value for any argument t is random

7 (), 9 G. V. Boykova about the world of the world Abstract: for a second-order differential equation, a solution has been found that represents

NATURAL AND EXACT SCIENCES UDC 57977 ABOUT THE CONTROL OF LINEAR SINGULARLY PERTURBED SYSTEMS WITH SMALL DELAY Candidate of Physical and Mathematical Sciences Associate Professor KOPEYKINA T B GUSEINOVA A S Belarusian National Technical

Computer modeling. SMO. Lecture 2 1 Contents Chapter 2. Representation of a QS by a Markov random process... 1 I. Classification of QS according to Kendall... 1 II. Markov random process... 2 III. Markovsky

48 Vestnik RAU Series physical, mathematical and natural sciences, 1, 28, 48-59 UDC 68136 ASSESSMENT OF RELIABILITY CHARACTERISTICS OF DISTANCE LEARNING SYSTEMS PART 2 HV Kerobyan, NN Khublaryan, AG Oganesyan Russian-Armenian

Basic concepts of the theory of difference schemes. Examples of constructing difference schemes for initial-boundary value problems. A large number of problems in physics and technology lead to boundary value or initial boundary value problems for linear

4 (0) 00 Bayesian analysis when the estimated parameter is a random normal process The problem of Bayesian estimation of a sequence of unknown average values ​​q q... q... is considered

RUSSIAN TECHNOLOGICAL UNIVERSITY MIREA ADDITIONAL CHAPTERS OF HIGHER MATHEMATICS CHAPTER 3. SYSTEMS OF DIFFERENTIAL EQUATIONS The work is devoted to modeling dynamic systems using elements

SYSTEMS OF LINEAR DIFFERENTIAL EQUATIONS WITH CONSTANT COEFFICIENTS Reduction to one equation of the th order From a practical point of view, linear systems with constant coefficients are very important

1 Title of the document Ovsyannikov A.V. STATISTICAL INEQUALITIES IN SUPERREGULAR STATISTICAL EXPERIMENTS OF ESTIMATION THEORY // West National Academy of Sciences Belarus, 009. Ser fz-mat. navuk. P.106-110

UDC 59 EV Novitskaya AF Terpugov DETERMINATION OF THE OPTIMAL VOLUME OF A LOT OF PRODUCT AND THE RETAIL PRICE OF SALES OF CONTINUALLY PERISHABLE PRODUCTS The problem of determining the optimal volume of a batch of goods is considered

Moscow State Technical University named after NE Bauman Faculty of Fundamental Sciences Department of Mathematical Modeling A. K. K. K. K., A. K. REPLACEMENT

Math-Net.Ru All-Russian mathematical portal A. A. Nazarov, T. V. Lyubina, Non-Markov dynamic RQ system with an incoming MMP flow of requests, Avtomat. and telemekh., 213, issue 7, 89 11 Use

MINISTRY OF EDUCATION OF THE RUSSIAN FEDERATION KRASNOYARSK STATE UNIVERSITY UDC BBK Compiled by: N.A. Pinkina DEPARTMENT OF HIGHER MATHEMATICS Linear algebra. Solving typical examples. Test options

Lecture 2 Solving systems of linear equations. 1. Solving systems of 3 linear equations using the Cramer method. Definition. A system of 3 linear equations is a system of the form In this system, the required quantities are