QUEUE THEORY
Introduction
Queuing theory is an important branch of systems analysis and operations research. It is rich in a variety of applications: from tasks. related to the operation telephone networks, to the scientific organization of production. This theory is used where there are calls and clients, signals and mass-produced products, as well as where products are serviced, processed, transmitted.
Ideas and methods of theory queuing(TMO) are becoming increasingly widespread. Many problems in technology, economics, military affairs, and natural sciences can be posed and solved in terms of TMT.
TMO owes its emergence, first of all, to applied issues of telephony, in which, due to large number from independent or weakly dependent sources (telephone exchange subscribers), the flows of requests (calls) have a clearly defined random nature. Random oscillations (fluctuations) around a certain average are in this case not the result of some deviation from the norm, but a pattern inherent in the entire process. On the other hand, the stability of telephone exchanges and the possibility of obtaining good statistical data created the prerequisites for identifying the main characteristics inherent in a given service process.
For the first time, Danish A.K. drew attention to this and conducted research. Erlang. His main works in this area date back to 1908 - 1921. Since that time, interest in the problems put forward by Erlang has increased enormously. In 1927 - 1928, works by Molina and Frey appeared, later in 1930 - 1932 - interesting works by Pollacek, A.N. Kolmogorova, A.Ya. Khinchin.
It must be said that the first problems of TMT were quite simple and allowed obtaining final analytical dependencies. Oh, development went both along the line of increasing the scope of application of TMO, and along the line of complicating the tasks facing it. It turned out that problems like telephone calls arise in a wide variety of areas of research: in natural science. in technology, transport, military affairs, production organization, etc.
23. Queuing systems
In many areas of human practical activity, we are faced with the need to remain in a state of anticipation. Similar situations arise in queues at ticket offices, at large airports, when aircraft maintenance personnel are waiting for permission to take off or land, at telephone exchanges while waiting for the subscriber's line to become free, in repair shops while waiting for the repair of machines and equipment, in the warehouses of supply and distribution organizations in waiting for unloading or loading of vehicles. In all of the above cases, we are dealing with mass production and service. Queuing theory studies such situations.
Queuing theory– a field of applied mathematics that deals with the analysis of processes in production, service, and management systems in which homogeneous events are repeated many times, for example, in consumer service enterprises; in systems for receiving, processing and transmitting information; automatic production lines, etc.
The subject of queuing theory is to establish dependencies between the nature of the flow of requests, the number of service channels, the performance of an individual channel and effective service in order to find the best ways to manage these processes.
23.1. smo concept
In the theory of queuing systems (QS), the object being served is called a requirement. In general, a requirement is usually understood as a request to satisfy some need, for example, a conversation with a subscriber, landing a plane, buying a ticket, receiving materials from a warehouse.
The tools that serve the requirements are called service devices or service channels . For example, these include telephone communication channels, landing strips, repairmen, ticket cashiers, loading and unloading points at bases and warehouses.
A set of similar servicing devices is called queuing system . Such systems can be telephone exchanges, airfields, ticket offices, repair shops, warehouses and bases of supply and sales organizations, etc.
The main task of the QS theory is to study the operating mode of the servicing system and study the phenomena that arise during the servicing process. Thus, one of the characteristics of the servicing system is the time a request remains in the queue. Obviously, this time can be reduced by increasing the number of servicing devices. However, each additional device requires certain material costs, and the inactivity time of the servicing device increases due to the lack of maintenance requirements, which is also a negative phenomenon. Consequently, in QS theory, optimization problems arise: how to achieve a certain level of service (maximum reduction of queue or loss of requirements) with minimum costs associated with downtime of service devices.
Source. A source is defined as a device or set from which demands enter the system for service. A source is called infinite or finite depending on whether it contains an infinite or a finite number of requirements. We will always assume that the source generating requirements is inexhaustible. For example, although there is a finite number of subscribers to a certain telephone exchange, we assume that they form an infinite source.
Incoming flow. Requirements arriving from a source for service form an incoming flow. The requirement itself can be considered as a request to satisfy some need. There are many examples of incoming flows. This is the flow of information entering the computer for processing; flow of applications for automatic telephone exchange; the flow of clients coming to the studio, and patients to the clinic, the flow of ships arriving at the port; enemy aircraft and missiles flying at the target, etc.
Servicing system. The service system is understood as a set of technical means or production personnel (various types of installations, instruments, devices, tunnels, runways, communication lines, salespeople, teams of workers or employees, cashiers, etc.) performing service functions. All of the above, as already mentioned, is united by one name “service channel” (service device). The composition of the system is determined by the number of channels (devices, lines). Based on the number of channels, systems can be divided into single-channel and multi-channel.
Outgoing stream. The egress flow is the flow of demands leaving the system after servicing. This may include requirements that left the system without being serviced.
The incoming flow, the functioning of the service system as a result of service, and the outgoing flow are subject to quantitative description. In order to conduct a mathematical study of the queuing process, it is necessary to fully define the service system. Usually this means:
- specifying the incoming flow. Here we mean both the average intensity of receipt of requirements and the statistical model of their receipt (i.e., the law of distribution of the moments of receipt of requirements into the system);
- setting the service mechanism. This means specifying when service is acceptable, how many requests can be serviced at once, and how long the service lasts. The last property is usually characterized by the statistical distribution of service duration (service time distribution law);
- assignment of service discipline. This means indicating the method by which one request is selected from the queue (if there is one) for service. In its simplest form, service discipline is to serve requests in the order they are received (fair principle), but there are many other possibilities.
The specification of a system also presupposes a known description of the interaction between its individual parts.
When the system is sufficiently fully defined, there is a basis for constructing a mathematical model. If a mathematical model more or less adequately reflects a real system, then it allows one to obtain the main characteristics of the system’s functioning. Of course, the model greatly simplifies the practical situation, but this does not detract from the mathematical methods of queuing theory and the state of affairs is no different from the state of affairs in other areas of applied mathematics.
Types of queuing systems
Depending on how the application is handled if all channels are busy, there are:
QS with refusal to service an application and QS with waiting.
For a QS with a failure, it is typical that a request that finds all channels busy immediately leaves the system.
In a QS with waiting, a request that finds all channels busy does not leave the system, but is put in a queue and serviced when one of the channels becomes free. In a queued QS, the process of waiting for applications in a queue may or may not have any restrictions imposed on it. In the latter case, they say that they are dealing with a “pure” QS with expectation. If restrictions are imposed on the waiting process, then the QS is called a “system mixed type". In such systems, due to the restrictions imposed, there may be cases when a request is denied service, i.e. a mixed-type QS also exhibits signs of a QS with a failure.
In mixed-type systems, the following restrictions may be imposed:
a) the number of applications in the queue;
b) for the duration of the application’s stay in the queue;
c) on total time finding the application in the CMO.
In REU technology, mixed-type QS systems are most often encountered.
Mathematical description of QS with failure
Consider a queuing system with failure having P channels. Let us assume that the flow of requests entering the QS is the simplest and has density l. In addition, we will assume that the time for servicing requests is distributed according to an exponential law with the parameter
Where M(Tob) - mathematical expectation of the request service time.
Therefore, the service time distribution density
For the system under consideration it is possible following states:
x 0- all channels are free;
x 1 - one channel is busy;
x k -- busy k channels;
x n -- everyone is busy P channels.
The service system state data can be described differential equations Erlang. solving them allows one to obtain formulas for calculating probabilities that are constant for a steady state. This regime occurs when t® ¥.
The coefficient is determined as
Where M(Tob) - mathematical expectation of the service time for one request.
Erlang formulas were obtained for the case of exponential distribution of service time, but are also valid under any other law, as long as the flow of requests is simple.
The probability of a request not being serviced is defined as
q
The average proportion of time that the service system will be idle can be determined by the probability of the condition x 0 , those.
P idle = p(x 0) = p 0
Example. Let it go to the repair area technological equipment devices arrive from medium density l= 2 units/hour. The average service time for one piece of equipment is 24 minutes (0.4 hours). An application that finds all channels busy is denied service.
It is required to determine the characteristics of the QS assuming the presence of one workplace. In addition, it is necessary to establish how the characteristics of the QS change with the introduction of a second workplace.
Solution. According to the conditions of the problem, we have a QS with failure. We will assume that the flow of applications entering the QS is the simplest with an average density l.
1. Calculate the channel load factor or the reduced density of requests
2. Let’s find the characteristics of the QS for the number of channels n = 1. Probability of requests not being serviced:
Relative throughput q will determine how
q=1- P required = 1 – 0,44 = 0,56.
Consequently, approximately 56% of applications received by the CMO will be serviced.
Probability of channel downtime p 0
The theory of QS is devoted to the development of methods for analysis, design and rational organization of systems related to various fields of activity, such as communications, Computer Engineering, trade, transport, military affairs. Despite all their diversity, the above systems have a number of typical properties, namely.
- Queuing systems (queuing systems) are system models, in which applications (requirements) are received at random times from outside or inside. They must be served by the system in one way or another. The duration of service is most often random.
- QS is totality serving equipment And personnel with appropriate organization of the service process.
- To set a QMS means to set it structure and statistical characteristics of the sequence of requests received and the sequence of their servicing.
- indicators characterizing the system as a whole: number n busy service channels, number of serviced (λ b), pending service or rejected applications (λ c) per unit of time, etc.;
- probabilistic characteristics: probability that the request will be served ( P obs) or receive a denial of service ( P open) that all devices are free ( p 0) or a certain number of them are occupied ( p k), probability of a queue, etc.;
- economic indicators: the cost of losses associated with the departure of an application that was not serviced for one reason or another from the system, the economic effect obtained as a result of servicing the application, etc.
While doing homework test work The simplest QSs are studied. These are open-loop systems; an endless source of applications is not included in the system. The input flow of requests, service flows and expectations of these systems are the simplest. There are no priorities. Single-phase systems.
Multi-channel system with failures
The system consists of one service node containing n service channels, each of which can serve only one request.All service channels have the same performance and are indistinguishable for the system model. If a request enters the system and finds at least one channel free, it immediately begins to be serviced. If at the time of receipt of an application in the system all channels are busy, then the application leaves the system unserved.
Mixed systems
- System with limitation by queue length
.
Consists of a storage device (queue) and a service node. An application leaves the queue and leaves the system if there are already m applications in the storage by the time it appears (m is the maximum possible number of places in the queue). If a request has entered the system and finds at least one channel free, it immediately begins to be serviced. If at the time an application arrives in the system, all channels are busy, then the application does not leave the system, but takes a place in the queue. An application leaves the system unserved if, by the time it enters the system, all service channels and all places in the queue are occupied.
For each system, a queue discipline is determined. This is a system of rules that determine the order in which requests arrive from the queue to the service node. If all requests and service channels are equal, then most often the rule “who comes first is served first” applies. - System with limitation for the duration of the application's stay in the queue.
Consists of a storage device (queue) and a service node. It differs from the previous system in that a request received in the storage (queue) can wait for service to begin for only a limited time So(most often this is a random variable). If its time So has expired, then the application leaves the queue and leaves the system unserved.
Mathematical description of QS
QSs are considered as some physical systems with discrete states x 0, x 1, ..., x n, operating at continuous time t. The number of states n can be finite or countable (n → ∞). The system can move from one state x i (i= 1, 2, … , n) to another x j (j= 0, 1,... ,n) at any time t. To show the rules for such transitions, use a diagram called state graph. For the types of systems listed above, state graphs form a chain in which each state (except for the extreme ones) is connected by direct and feedback with two neighboring states. This is the diagram death and reproduction .Transitions from state to state occur at random times. It is convenient to assume that these transitions occur as a result of the action of some streams(flows of input requests, refusals to service requests, flow of device restoration, etc.). If all threads protozoa, then the random flow occurring in the system a process with a discrete state and continuous time will be Markovian .
Event stream is a sequence of similar events occurring at random moments in time. It can be viewed as a sequence of random moments in time t 1 ,t 2 , ... the occurrence of events.
The simplest is a stream that has the following properties:
- Ordinariness. Events follow one at a time (the opposite of a stream, where events follow in groups).
- Stationarity. Probability of a given number of events occurring in a time interval T depends only on the length of the interval and does not depend on where this interval is located on the time axis.
- No aftereffect. For two non-overlapping time intervals τ 1 and τ 2, the number of events falling on one of them does not depend on how many events fall on the other interval.
Markovsky random events are described by ordinary differential equations. The variables in them are the probabilities of states R 0 (t), p 1 (t),…,p n (t).
For very big moments operating time of systems (theoretically at t → ∞) in the simplest systems (systems in which all flows are simplest, and the graph is a scheme of death and reproduction) is observed steady, or stationary operating mode. In this mode, the system will change its state, but the probabilities of these states ( final probabilities) r k, k= 1, 2 ,…, n, do not depend on time and can be considered as average relative time the system remains in the appropriate state.
When researching operations, one often encounters systems designed for reusable use when solving similar problems. The processes that arise in this case are called service processes, and systems - queuing systems (QS). Examples of such systems are telephone systems, repair shops, computer complexes, ticket offices, shops, hairdressers, etc.
Each SMO consists of a certain number service units (devices, devices, points, stations), which we will call service channels. Channels can be communication lines, work points, computers, sellers, etc. Based on the number of channels, the QS is divided into single-channel And multichannel.
Applications are usually received by the CMO not regularly, but randomly, forming the so-called random flow of applications (requirements). Service of requests, generally speaking, also continues for some random time. The random nature of the flow of requests and service time leads to the fact that the QS is unevenly loaded: in some periods of time a very large number of a large number of requests (they either queue up or leave the QS unserved); in other periods, the QS works with underload or is idle.
The subject of queuing theory is the construction mathematical models, linking the specified operating conditions of the QS (number of channels, their productivity, nature of the flow of requests, etc.) with performance indicators of the QS, describing its ability to cope with the flow of requests.
As QS performance indicators used: the average number of applications served per unit of time; average number of applications in queue; average waiting time for service; the possibility of denial of service without waiting; the probability that the number of applications in the queue will exceed specific value and so on.
QSs are divided into two main types (classes): QS with failures And QS with waiting (queue). In a QS with refusals, an application received at a time when all channels are busy receives a refusal, leaves the QS and does not participate in the further service process (for example, an application for phone conversation at the moment when all channels are busy, it receives a refusal and leaves the QS unserviced). In a waiting QS, a request that arrives at a time when all channels are busy does not leave, but becomes queued for service.
QS with expectation are divided into different types depending on how the queue is organized: with a limited or unlimited queue length, with a limited waiting time, etc.
For classification of SMO important It has service discipline, which determines the procedure for selecting applications from among those received and the procedure for distributing them between free channels. On this basis, service of an application can be organized according to the principle “first come - first served”, “last come - first served” (this order can be used, for example, when retrieving products from a warehouse for servicing, since the last of them are often more accessible) or priority service (when the most important requests are serviced first). The priority can be either absolute, when a more important request “displaces” a regular request from service (for example, in the event of an emergency, the planned work of repair crews is interrupted until the emergency is eliminated), or relative, when a more important request receives only the “best” place queue.
The concept of a Markov random process
The work process of the QS is random process.
Under random (probabilistic or stochastic) process refers to the process of changing the state of a system over time in accordance with probabilistic laws.
The process is called process with discrete states, if its possible states can be listed in advance, and the transition of the system from state to state occurs instantly (in a jump). The process is called continuous time process, if the moments of possible transitions of the system from state to state are not fixed in advance, but are random.
The QS operation process is a random process with discrete states and continuous time. This means that the state of the QS changes abruptly at random moments when some events occur (for example, the arrival new application, end of service, etc.).
The mathematical analysis of the operation of a QS is significantly simplified if the process of this operation is Markovian. The random process is called Markovian or random process without consequences, if for any moment in time the probabilistic characteristics of the process in the future depend only on its state at the moment and do not depend on when and how the system came to this state.
Example Markov process: system - taxi meter. The state of the system at a moment is characterized by the number of kilometers (tenths of kilometers) traveled by the car up to that moment. Let the counter show at the moment. The probability that at the moment the meter will show this or that number of kilometers (more precisely, the corresponding number of rubles) depends on , but does not depend on at what points in time the meter readings changed before the moment .
Many processes can be approximately considered Markovian. For example, the process of playing chess; system - a group of chess pieces. The state of the system is characterized by the number of enemy pieces remaining on the board at the moment. The probability that at the moment the material advantage will be on the side of one of the opponents depends primarily on the state of the system at the moment, and not on when and in what sequence the pieces disappeared from the board before the moment.
In some cases, the prehistory of the processes under consideration can simply be neglected and Markov models can be used to study them.
When analyzing random processes with discrete states, it is convenient to use a geometric scheme - the so-called state graph. Typically, system states are depicted by rectangles (circles), and possible transitions from state to state are depicted by arrows (oriented arcs) connecting the states.
Example 1. Construct a state graph of the following random process: the device consists of two nodes, each of which can fail at a random moment in time, after which you immediately begin repairing the node, which continues for a previously unknown random time.
Solution. Possible system states: - both nodes are operational; - the first unit is being repaired, the second is operational; - the second unit is being repaired, the first one is working; - both units are being repaired. The system graph is shown in Fig. 1.
An arrow directed, for example, from to, means a transition of the system at the moment of failure of the first node, from to - a transition at the moment of completion of repair of this node.
There are no arrows from to and from to in the graph. This is explained by the fact that the failures of nodes are assumed to be independent of each other and, for example, the probability of simultaneous failure of two nodes (transition from to) or the simultaneous completion of repairs of two nodes (transition from to) can be neglected.
For a mathematical description of a Markov random process with discrete states and continuous time flowing in a QS, we will get acquainted with one of the important concepts of probability theory - the concept of a flow of events.
Event Streams
Under stream of events is understood as a sequence of homogeneous events following one after another at some random moments in time (for example, a flow of calls at a telephone exchange, a flow of computer failures, a flow of customers, etc.).
The flow is characterized intensity- frequency of occurrence of events or the average number of events entering the QS per unit of time.
The stream of events is called regular, if events follow one another at certain equal intervals of time. For example, the flow of products on an assembly line in an assembly shop (at a constant speed) is regular.
The stream of events is called stationary, if its probabilistic characteristics do not depend on time. In particular, the intensity of a stationary flow is a constant value: . For example, the flow of cars on a city avenue is not stationary during the day, but this flow can be considered stationary during the day, say, during rush hours. Please note that in the latter case, the actual number of cars passing per unit of time (for example, every minute) may differ markedly from each other, but their average number will be constant and will not depend on time.
The stream of events is called flow without aftereffect, if for any two non-overlapping time periods and - the number of events falling on one of them does not depend on the number of events falling on the others. For example, the flow of passengers entering the subway has virtually no aftereffect. And, say, the flow of customers leaving the counter with purchases already has an aftereffect (if only because the time interval between individual customers cannot be less than the minimum service time for each of them).
The stream of events is called ordinary, if the probability of two or more events occurring in a small (elementary) period of time is negligible compared to the probability of one event occurring. In other words, a stream of events is ordinary if events appear in it singly and not in groups. For example, the flow of trains approaching a station is ordinary, but the flow of cars is not ordinary.
The flow of events is called the simplest (or stationary Poisson), if it is simultaneously stationary, ordinary and has no aftereffect. The name “simplest” is explained by the fact that QS with the simplest flows has the simplest mathematical description. Note that a regular flow is not the “simplest” one, since it has an aftereffect: the moments of occurrence of events in such a flow are strictly fixed.
The simplest flow appears as a limit in the theory of random processes as naturally as in the theory of probability the normal distribution appears as a limit for a sum of random variables: when superposing (superposition) a sufficiently large number of independent, stationary and ordinary flows (comparable to each other in intensity), a flow is obtained that is close to the simplest with an intensity equal to the sum of the intensities of the incoming flows, i.e. Let us consider on the time axis (Fig. 1) the simplest flow of events as an unlimited sequence of random points.
It can be shown that for the simplest flow, the number m of events (points) falling on an arbitrary portion of time is distributed over Poisson's law
for which the mathematical expectation random variable is equal to its variance: .
In particular, the probability that no event will occur during time is equal to
Let us find the distribution of the time interval between arbitrary two neighboring events of the simplest flow.
In accordance with (2), the probability that no subsequent events will appear in a time segment of length is equal to
and the probability of the opposite event, i.e. distribution function of a random variable, there is
The probability density of a random variable is the derivative of its distribution function (Fig. 3), i.e.
The distribution specified by the probability density (5) or distribution function (4) is called indicative(or exponential). Thus, the time interval between two neighboring arbitrary events has an exponential distribution, for which the mathematical expectation is equal to the standard deviation of the random variable
and vice versa according to the flow intensity.
The most important property exponential distribution (inherent only in the exponential distribution) is as follows: if a period of time distributed according to the exponential law has already lasted for some time, then this does not in any way affect the distribution law of the remaining part of the interval: it will be the same as the distribution law of the entire interval.
In other words, for a time interval between two consecutive neighboring events of a flow that has an exponential distribution, any information about how long this interval took place does not affect the distribution law of the remaining part. This property of the exponential law is, in essence, another formulation for the “absence of aftereffect” - the main property of the simplest flow.
For the simplest flow with intensity, the probability of hitting (Note that this approximate formula, obtained by replacing the function with only the first two terms of its expansion in powers, is more accurate the smaller it is).
When researching operations, one often encounters systems designed for reusable use when solving similar problems. The processes that arise in this case are called service processes, and systems - queuing systems (QS). Examples of such systems are telephone systems, repair shops, computer complexes, ticket offices, shops, hairdressers, etc.
Each QS consists of a certain number of service units (instruments, devices, points, stations), which we will call service channels. Channels can be communication lines, work points, computers, sellers, etc. Based on the number of channels, the QS is divided into single-channel And multichannel.
Applications are usually received by the CMO not regularly, but randomly, forming the so-called random flow of applications (requirements). Service of requests, generally speaking, also continues for some random time. The random nature of the flow of applications and service time leads to the fact that the QS is unevenly loaded: in some periods of time a very large number of applications accumulate (they either get queued or leave the QS unserved), in other periods the QS operates with underload or idle.
The subject of queuing theory is the construction of mathematical models that connect the specified operating conditions of the QS (the number of channels, their productivity, the nature of the flow of requests, etc.) with performance indicators of the QS, describing its ability to cope with the flow of requests.
As QS performance indicators used: the average number of applications served per unit of time; average number of applications in queue; average waiting time for service; the possibility of denial of service without waiting; the probability that the number of applications in the queue will exceed a certain value, etc.
QSs are divided into two main types (classes): QS with failures And QS with waiting (queue). In a QS with refusals, an application received at a time when all channels are busy receives a refusal, leaves the QS and does not participate in the further service process (for example, a request for a telephone conversation at a time when all channels are busy, receives a refusal and leaves the QS unserved). In a waiting QS, a request that arrives at a time when all channels are busy does not leave, but becomes queued for service.
Queues with waiting are divided into different types depending on how the queue is organized: with limited or unlimited queue length, with limited waiting time, etc.
For the classification of SMO it is important service discipline, which determines the procedure for selecting applications from among those received and the procedure for distributing them between free channels. On this basis, service of an application can be organized according to the principle “first come - first served”, “last come - first served” (this order can be used, for example, when retrieving products from a warehouse for servicing, since the last of them are often more accessible) or priority service (when the most important requests are serviced first). The priority can be either absolute, when a more important request “displaces” a regular request from service (for example, in the event of an emergency, the planned work of repair crews is interrupted until the emergency is eliminated), or relative, when a more important request receives only the “best” place queue.
The concept of a Markov random process
The work process of the QS is random process.
Under random (probabilistic or stochastic) process refers to the process of changing the state of a system over time in accordance with probabilistic laws.
The process is called process with discrete states, if its possible states S_1,S_2,\ldots,S_n can be listed in advance, and the transition of the system from state to state occurs instantly (in a jump). The process is called continuous time process, if the moments of possible transitions of the system from state to state are not fixed in advance, but are random.
The QS operation process is a random process with discrete states and continuous time. This means that the state of the QS changes abruptly at random moments when some events occur (for example, the arrival of a new request, the end of service, etc.).
The mathematical analysis of the operation of a QS is significantly simplified if the process of this operation is Markovian. The random process is called Markovian or random process without consequences, if for any moment of time t_0 the probabilistic characteristics of the process in the future depend only on its state at the given moment t_0 and do not depend on when and how the system came to this state.
An example of a Markov process: system S is a taxi meter. The state of the system at moment t is characterized by the number of kilometers (tenths of kilometers) traveled by the car up to this moment. Let the counter show S_0 at time t_0. The probability that at the moment t>t_0 the counter will show this or that number of kilometers (more precisely, the corresponding number of rubles) S_1 depends on S_0, but does not depend on at what points in time the counter readings changed before the moment t_0.
Many processes can be approximately considered Markovian. For example, the process of playing chess; system S is a group of chess pieces. The state of the system is characterized by the number of enemy pieces remaining on the board at time t_0. The probability that at the moment t>t_0 the material advantage will be on the side of one of the opponents depends primarily on the state the system is in at the moment t_0, and not on when and in what sequence the pieces disappeared from the board to moment t_0 .
In some cases, the prehistory of the processes under consideration can simply be neglected and Markov models can be used to study them.
When analyzing random processes with discrete states, it is convenient to use a geometric scheme - the so-called state graph. Typically, system states are depicted by rectangles (circles), and possible transitions from state to state are depicted by arrows (oriented arcs) connecting the states.
Example 1. Construct a state graph of the following random process: device S consists of two nodes, each of which can fail at a random moment in time, after which you immediately begin repairing the node, which continues for an unknown random time.
Solution. Possible system states: S_0 - both nodes are operational; S_1 - the first unit is being repaired, the second is operational; S_2 - the second unit is being repaired, the first one is operational; S_3 - both units are being repaired. The system graph is shown in Fig. 1.
An arrow directed, for example, from S_0 to S_1 means a transition of the system at the moment of failure of the first node, from S_1 to S_0 - a transition at the moment of completion of repair of this node.
The graph lacks arrows from S_0 to S_3 and from S_1 to S_2. This is explained by the fact that node failures are assumed to be independent of each other and, for example, the probability of simultaneous failure of two nodes (transition from S_0 to S_3) or simultaneous completion of repairs of two nodes (transition from S_3 to S_0) can be neglected.
For a mathematical description of a Markov random process with discrete states and continuous time flowing in a QS, we will get acquainted with one of the important concepts of probability theory - the concept of a flow of events.
Event Streams
Under stream of events is understood as a sequence of homogeneous events following one after another at some random moments in time (for example, a flow of calls at a telephone exchange, a flow of computer failures, a flow of customers, etc.).
The flow is characterized intensity\lambda - the frequency of occurrence of events or the average number of events entering the QS per unit of time.
The stream of events is called regular, if events follow one another at certain equal intervals of time. For example, the flow of products on an assembly line in an assembly shop (at a constant speed) is regular.
The stream of events is called stationary, if its probabilistic characteristics do not depend on time. In particular, the intensity of a stationary flow is a constant value: \lambda(t)=\lambda. For example, the flow of cars on a city avenue is not stationary during the day, but this flow can be considered stationary during the day, say, during rush hours. Please note that in the latter case, the actual number of cars passing per unit of time (for example, every minute) may differ markedly from each other, but their average number will be constant and will not depend on time.
The stream of events is called flow without aftereffect, if for any two non-overlapping time periods \tau_1 and \tau_2 - the number of events falling on one of them does not depend on the number of events falling on the others. For example, the flow of passengers entering the subway has virtually no aftereffect. And, say, the flow of customers leaving the counter with purchases already has an aftereffect (if only because the time interval between individual customers cannot be less than the minimum service time for each of them).
The stream of events is called ordinary, if the probability of two or more events occurring in a small (elementary) time interval \Delta t is negligible compared to the probability of one event occurring. In other words, a stream of events is ordinary if events appear in it singly and not in groups. For example, the flow of trains approaching a station is ordinary, but the flow of cars is not ordinary.
The flow of events is called the simplest (or stationary Poisson), if it is simultaneously stationary, ordinary and has no aftereffect. The name “simplest” is explained by the fact that QS with the simplest flows has the simplest mathematical description. Note that a regular flow is not the “simplest” one, since it has an aftereffect: the moments of occurrence of events in such a flow are strictly fixed.
The simplest flow appears as a limit in the theory of random processes as naturally as in the theory of probability the normal distribution appears as a limit for a sum of random variables: with the imposition (superposition) of a sufficiently large number n of independent, stationary and ordinary flows (comparable to each other in intensity \lambda_i~(i=1,2,\ldots,n) the result is a flow close to the simplest with an intensity \lambda equal to the sum of the intensities of the incoming flows, i.e. \textstyle(\lambda=\sum\limits_(i=1)^(n)\lambda_i). Let us consider on the time axis Ot (Fig. 1) the simplest flow of events as an unlimited sequence of random points.
It can be shown that for the simplest flow, the number m of events (points) falling on an arbitrary time segment \tau is distributed over Poisson's law
P_(m)(\tau)= \frac((\lambda\tau)^m)(m\,e^{-\lambda\tau}, !}
for which the mathematical expectation of a random variable is equal to its variance: a=\sigma^2=\lambda\tau.
In particular, the probability that no event will occur during time \tau (m=0) is equal to
P_0(\tau)=e^(-\lambda\tau).
Let us find the distribution of the time interval T between arbitrary two neighboring events of the simplest flow.
In accordance with (2), the probability that during a period of time of length t none of the subsequent events will occur is equal to
P(T\geqslant t)=e^(-\lambda t),
and the probability of the opposite event, i.e. distribution function of the random variable T, is
F(t)=P(T The probability density of a random variable is the derivative of its distribution function (Fig. 3), i.e. \varphi(t)=F"(t)=\lambda e^(-\lambda t). The distribution specified by the probability density (5) or distribution function (4) is called indicative(or exponential). Thus, the time interval between two neighboring arbitrary events has an exponential distribution, for which the mathematical expectation is equal to the standard deviation of the random variable A=\sigma=\frac(1)(\lambda) And vice versa according to the flow intensity \lambda. The most important property of the exponential distribution (inherent only in the exponential distribution) is the following: if a period of time distributed according to the exponential law has already lasted for some time \tau, then this does not in any way affect the distribution law of the remaining part of the interval (T-\tau): it will the same as the law of distribution of the entire interval T. In other words, for a time interval T between two consecutive neighboring events of a flow that has an exponential distribution, any information about how long this interval took place does not affect the distribution law of the remaining part. This property of the exponential law is, in essence, another formulation for the “absence of aftereffect” - the main property of the simplest flow. For the simplest flow with intensity \lambda, the probability of hitting elementary (small) the time interval \Delta t of at least one flow event is equal according to (4) P_(\Delta t)= P(T<\Delta t)= 1-e^{-\lambda\Delta t}\approx\lambda\Delta t.
(Note that this approximate formula, obtained by replacing the function e^(-\lambda\Delta t) only the first two terms of its expansion in powers of \Delta t, the more accurate the smaller \Delta t).
Go to next section
Kolmogorov equations. Limit probabilities of states Javascript is disabled in your browser.
To perform calculations, you must enable ActiveX controls!