Limit probabilities of a Markov chain example. Markov chains

Markov chains

Introduction

§ 1. Markov chain

§ 2. Homogeneous Markov chain. Transition probabilities. Transition matrix

§3. Markov equality

§4. Stationary distribution. Theorem on marginal probabilities

§5. Proof of the theorem on limiting probabilities in a Markov chain

§6. Applications of Markov chains

Conclusion

List of used literature

Introduction

The theme of our term paper Markov chains. Markov chains are named after the outstanding Russian mathematician, Andrei Andreevich Markov, who worked a lot on random processes and made a great contribution to the development of this field. AT recent times You can hear about the application of Markov chains in a variety of areas: modern web technologies, in the analysis of literary texts, or even in the development of football team tactics. For those who do not know what Markov chains are, there may be a feeling that this is something very complex and almost inaccessible to understanding.

No, it's just the opposite. A Markov chain is one of the simplest cases of a sequence of random events. But, despite its simplicity, it can often be useful even when describing rather complex phenomena. A Markov chain is a sequence of random events in which the probability of each event depends only on the previous one, but does not depend on earlier events.

Before delving deeper, we need to consider a few subsidiary issues that are well known, but are absolutely necessary for further presentation.

The purpose of my course work is to study in more detail the applications of Markov chains, the problem statement and Markov problems.

§one. Markov chain

Imagine that a sequence of tests is being performed.

Definition. A Markov chain is a sequence of trials, in each of which one and only one of the incompatible events of the complete group appears, and the conditional probability that an event occurs in the i-th trial , provided that the event occurred in the -th trial , does not depend on the results of previous tests.

For example, if the sequence of trials forms a Markov chain and the complete group consists of four incompatible events , and it is known that the event appeared in the sixth trial, then the conditional probability that the event occurs in the seventh trial does not depend on what events appeared in the first, second, ..., fifth trials.

Note that independent trials are a special case of a Markov chain. Indeed, if the trials are independent, then the occurrence of some specific event in any trial does not depend on the results of previously performed trials. It follows that the concept of a Markov chain is a generalization of the concept of independent trials.

Often, when presenting the theory of Markov chains, they adhere to a different terminology and talk about some physical system, which at each moment of time is in one of the states: , and changes its state only at certain points in time, that is, the system passes from one state to another (for example, from to ). For Markov chains, the probability of going to any state at the moment depends only on the state of the system at the moment , and does not change from the fact that its states become known at earlier moments. Also, in particular, after the test, the system can remain in the same state (“transition” from state to state ).

To illustrate, consider an example.

Example 1 Imagine that a particle located on a straight line moves along this straight line under the influence of random shocks occurring at moments . The particle can be located at points with integer coordinates: ; at points and there are reflecting walls. Each push moves the particle to the right with probability and to the left with probability , unless the particle is near a wall. If the particle is located near the wall, then any push moves it one unit inside the gap between the walls. Here we see that this example of a particle walk is a typical Markov chain.

Thus, events are called states of the system, and tests are called changes in its states.

We now give a definition of a Markov chain using the new terminology.

A discrete-time Markov chain is a chain whose states change at certain fixed points in time.

A continuous-time Markov chain is a chain whose states change at any random possible time.

§2. Homogeneous Markov chain. Transition probabilities. Transition matrix

Definition. A Markov chain is called homogeneous if the conditional probability (transition from state to state ) does not depend on the test number. Therefore, instead of writing simply.

Example 1 Random wander. Let there be a material particle on a straight line at a point with an integer coordinate. At certain moments of time, the particle experiences shocks. Under the action of the push, the particle is displaced by one to the right with probability and by one to the left. It is clear that the position (coordinate) of the particle after the shock depends on where the particle was after the immediately preceding shock, and does not depend on how it moved under the action of the other previous shocks.

Thus, a random walk is an example of a homogeneous Markov chain with discrete time.

The transition probability is the conditional probability that from the state (in which the system ended up as a result of some test, no matter what number) as a result of the next test, the system will go to the state.

Thus, in the notation, the first index indicates the number of the previous state, and the second one indicates the number of the subsequent state. For example, is the probability of transition from the second state to the third.

Let the number of states be finite and equal to .

The transition matrix of a system is a matrix that contains all transition probabilities this system:

Since each row of the matrix contains the probabilities of events (transition from the same state to any possible state), which form a complete group, the sum of the probabilities of these events is equal to one. In other words, the sum of the transition probabilities of each row of the transition matrix is ​​equal to one:

Let us give an example of the transition matrix of a system that can be in three states; the transition from state to state occurs according to the scheme of a homogeneous Markov chain; transition probabilities are given by the matrix:

Here we see that if the system was in the state , then after changing the state in one step, it will remain in the same state with a probability of 0.5, with a probability of 0.5 it will remain in the same state, with a probability of 0.2 it will go to the state, then after the transition, it may end up in the states ; it cannot go from state to state. The last row of the matrix shows us that from the state to go to any of possible states with the same probability of 0.1.

Based on the transition matrix of the system, you can build the so-called system state graph, it is also called the labeled state graph. This is useful for visualizing the circuit. Let's consider the order of graph construction using an example.

Example 2 Based on the given transition matrix, construct a state graph.

Because matrix of the fourth order, then, accordingly, the system has 4 possible states.

The graph does not indicate the probabilities of the system transition from one state to the same one. When considering specific systems, it is convenient to first construct a state graph, then determine the probability of system transitions from one state to the same one (based on the requirement that the sum of the matrix row elements be equal to one), and then compile the system transition matrix.

§3. Markov equality

Definition. Denote by the probability that as a result of steps (tests) the system will pass from state to state . For example, is the probability of transition in 10 steps from the second state to the fifth.

We emphasize that, as , we obtain the transition probabilities

Let's set ourselves the task: knowing the transition probabilities, find the probabilities of the system transition from state to state in steps.

For this purpose, let us introduce into consideration an intermediate (between and ) state . In other words, we will assume that the system will pass from the initial state in steps to the intermediate state with probability , after which, in the remaining steps, it will pass from the intermediate state to the final state with probability .

According to the total probability formula, we get

. (1)

This formula is called Markov's equality.

Explanation. Let us introduce the notation:

is the event of interest to us (in steps the system will pass from the initial state to the final state), therefore, ; - hypotheses (in steps the system will move from the initial state to the intermediate state), therefore,

According to the total probability formula,

()

Or in our notation

which coincides with the Markov formula (1).

Knowing all the transition probabilities, i.e. knowing the transition matrix from state to state in one step, you can find the transition probabilities from state to state in two steps, therefore, the transition matrix itself; using a known matrix, you can find the transition matrix from state to state in three steps, and so on.

Indeed, putting in the Markov equality

,

mark chain random probability

,

(2)

Thus, by formula (2) one can find all the probabilities, hence, the matrix itself. Since the direct use of formula (2) turns out to be tedious, and the matrix calculus leads to the goal faster, I will write the relation following from (2) in matrix form:

Putting in (1), we similarly obtain

In general

Theorem 1. For any s, t

(3)

Proof. Calculate the probability according to the total probability formula (), setting

From equalities

Hence from equalities (4) and

we obtain the assertion of the theorem.

Let us define the matrix In matrix notation (3), it has the form

Since where is the transition probability matrix. From (5) it follows

(6)

The results obtained in the theory of matrices allow using formula (6) to calculate and study their behavior at

Example 1 The transition matrix is ​​given Find transition matrix

Decision. Let's use the formula

Multiplying the matrices, we finally get:

.

§4. Stationary distribution. Theorem on marginal probabilities

The probability distribution at an arbitrary point in time can be found using the total probability formula

(7)

It may turn out that it does not depend on time. Let's call stationary distribution vector , satisfying the conditions

where are the transition probabilities.

If in a Markov chain then for any

This assertion follows by induction from (7) and (8).

Let us state the theorem on limiting probabilities for one important class of Markov chains.

Theorem 1. If for some >0 all elements of the matrix are positive, then for any , for

, (9)

where stationary distribution with and some constant satisfying the inequality 0< h <1.

Since , then, according to the condition of the theorem, one can get from any state to any state in time with a positive probability. The conditions of the theorem exclude chains that are in some sense periodic.

If the condition of Theorem 1 is satisfied, then the probability that the system is in some state , in the limit, does not depend on the initial distribution. Indeed, from (9) and (7) it follows that for any initial distribution ,

Let us consider several examples of Markov chains, where the conditions of Theorem 1 are not satisfied. It is easy to check that such examples are examples. In the example, the transition probabilities have limits, but these limits depend on the initial state. In particular, when

In other examples, the limits of probabilities at obviously do not exist.

Let's find the stationary distribution in example 1. We need to find the vector satisfying conditions (8):

,

;

Hence, Thus, the stationary distribution exists, but not all coordinate vectors are positive.

For the polynomial scheme, random variables were introduced equal to the number of outcomes of this type. Let us introduce similar quantities for Markov chains. Let be the number of hits of the system in the state during the time . Then the frequency of the system hitting the state . Using formulas (9), we can prove that for approaches . To do this, we need to obtain asymptotic formulas for and and use the Chebyshev inequality. We present the derivation of the formula for . Let's represent in the form

(10)

where , if , and otherwise. As

,

then, using the property of mathematical expectation and formula (9), we obtain

.

The second term on the right-hand side of this equality, by virtue of Theorem 1, is a partial sum of a convergent series. Putting , we get

Insofar as

From formula (11), in particular, it follows that

at

You can also get the formula for which is used to calculate the variance.

§5. Proof of the theorem on limiting probabilities in a Markov chain

Let us first prove two lemmas. Let's put

Lemma 1. There are limits for any

Proof. Using equation (3) with we get

Thus, the sequences are both monotone and bounded. This implies the assertion of Lemma 1.

Lemma 2. If the conditions of Theorem 2 are satisfied, then there are constants , such that

For any

where , means summation over all , for which is positive, and summation over the rest . From here

. (12)

Since under the conditions of Theorem 1 the transition probabilities for all , then for any

And due to the finiteness of the number of states

Let us now estimate the difference . Using equation (3) with , , we obtain

Hence, using (8)-(10), we find

=.

Combining this relation with inequality (14) , we obtain the assertion of the lemma.

Go to the proof of the theorem. Since the sequences , are monotone, then

0<. (15)

From here and from Lemma 1 we find

Therefore, when you get and

The positivity follows from inequality (15). Passing to the limit at and in equation (3), we obtain that satisfies equation (12). The theorem has been proven.

§6. Applications of Markov chains

Markov chains serve as a good introduction to the theory of random processes, i.e. the theory of simple sequences of a family of random variables, usually depending on a parameter, which in most applications plays the role of time. It is intended primarily to fully describe both the long-term and local behavior of the process. Here are some of the most studied issues in this regard.

Brownian motion and its generalizations - diffusion processes and processes with independent increments . The theory of stochastic processes contributed to the deepening of the connection between the theory of probability, the theory of operators and the theory of differential equations, which, among other things, was of great importance for physics and other applications. Applications include processes of interest to actuarial (insurance) mathematics, queuing theory, genetics, traffic control, electrical circuit theory, and accounting and accumulation theory.

martingales . These processes preserve enough of the properties of Markov chains for them to hold important ergodic theorems. Martingales differ from Markov chains in that when the current state is known, only the expectation of the future, but not necessarily the probability distribution itself, does not depend on the past. In addition to being an important research tool, martingale theory has enriched the theory of random processes arising in statistics, the theory of nuclear fission, genetics, and information theory with new limit theorems.

Stationary processes . The oldest known ergodic theorem, as noted above, can be interpreted as a result describing the limiting behavior of a stationary random process. Such a process has the property that all probabilistic laws that it satisfies remain invariant under time shifts. The ergodic theorem, first formulated by physicists as a hypothesis, can be represented as a statement that, under certain conditions, the average over the ensemble coincides with the average over time. This means that the same information can be obtained from long-term observation of the system and from the simultaneous (and instantaneous) observation of many independent copies of the same system. The law of large numbers is nothing but a special case of Birkhoff's ergodic theorem. Interpolation and prediction of the behavior of stationary Gaussian processes, understood in a broad sense, serve as an important generalization of the classical theory of least squares. The theory of stationary processes is a necessary research tool in many areas, for example, in communication theory, which deals with the study and creation of systems that transmit messages in the presence of noise or random interference.

Markov processes (processes without aftereffect) play a huge role in modeling queuing systems (QS), as well as in modeling and choosing a strategy for managing socio-economic processes occurring in society.

Also, the Markov chain can be used to generate texts. Several texts are fed into the input, then a Markov chain is built with the probabilities of following one word after another, and the resulting text is created based on this chain. The toy is very entertaining!

Conclusion

Thus, in our term paper we were talking about the scheme of Markov chains. They learned in what areas and how it is applied, independent tests proved the theorem on the limiting probabilities in the Markov chain, gave examples for a typical and homogeneous Markov chain, as well as for finding the transition matrix.

We have seen that the Markov chain scheme is a direct generalization of the independent test scheme.

List of used literature

1. Chistyakov V.P. Probability course. 6th ed., rev. - St. Petersburg: Publishing house "Lan", 2003. - 272 p. − (Textbook for universities. Special literature).

2. Gnedenko B.V. Probability course.

3. Gmurman V.E. Theory of Probability and Mathematical Statistics.

4. Wentzel E.S. Probability theory and its engineering applications.

5. Kolmogorov A.N., Zhurbenko I.G., Prokhorov A.V. Introduction to the theory of probability. − Moscow-Izhevsk: Institute for Computer Research, 2003, 188 pages.

6. Kats M. Probability and related issues in physics.

Homogeneous is called a Markov chain for which the conditional probability of transition from the state into a state does not depend on the test number. For homogeneous circuits instead of
use the notation
.

Random walks are an example of a homogeneous Markov chain. Let there be a material particle on the straight line Ox at the point with integer coordinate x=n. At certain points in time
the particle abruptly changes its position (for example, it can move to the right with probability p and to the left with probability 1 –p). Obviously, the coordinate of the particle after the jump depends on where the particle was after the immediately preceding jump, and does not depend on how it moved at the previous moments of time.

In what follows, we confine ourselves to considering finite homogeneous Markov chains.

Transition probabilities. transition matrix.

transition probability
is called the conditional probability that from the state as a result of the next test, the system will go into the state . So the index refers to the previous - to the next state.

transition matrix system is called a matrix that contains all the transition probabilities of this system:

, where represent the transition probabilities in one step.

Let us note some features of the transition matrix.

Markov equality

Denote by
the probability that as a result of n steps (tests) the system will pass from the state into a state . For example,
- the probability of transition in 10 steps from the third state to the sixth. Note that for n= 1 this probability reduces simply to the transition probability
.

The question arises how, knowing the transition probabilities
, find the state transition probabilities into a state for n steps. For this purpose, an intermediate (between and ) state r. In other words, it is believed that from the initial state after m steps, the system will pass to an intermediate state r with probability
, after which, in the remaining n–m steps, it will pass from the intermediate state to the final state with probability
. Using the total probability formula, one can show that the formula is valid

This formula is called Markov equality .

Knowing all transition probabilities
, i.e. knowing the transition matrix from state to state in one step, you can find the probabilities
transition from state to state in two steps, and hence the transition matrix itself , then according to the known matrix - to find etc.

Indeed, assuming in the Markov equality n= 2,m= 1 we get

or
. In matrix form, this can be written as
.

Assuming n=3,m=2, we get
. In the general case, the relation
.

Example. Let the transition matrix is equal to

It is required to find the transition matrix
.

Multiplying a matrix on itself, we get
.

For practical applications, the issue of calculating the probability of a system being in a particular state at a particular moment in time is extremely important. The solution of this question requires knowledge of the initial conditions, i.e. the probabilities of the system being in certain states at the initial moment of time. The initial probability distribution of a Markov chain is the probability distribution of the states at the beginning of the process.

Here through
the probability of finding the system in the state at the initial time. In a particular case, if the initial state of the system is exactly known (for example,
), then the initial probability
, and all others are equal to zero.

If for a homogeneous Markov chain the initial probability distribution and the transition matrix are given, then the probabilities of the system states at the nth step
are calculated by the recursive formula

.

Let's take a simple example to illustrate. Consider the process of functioning of some system (for example, a device). Let the device for one day can be in one of two states - serviceable ( ) and faulty ( ). As a result of mass observations of the operation of the device, the following transition matrix was compiled
,

where - the probability that the device will remain in good condition;

- the probability of the device transition from a serviceable to a faulty state;

- the probability of the device transition from a faulty to a serviceable state;

- the probability that the device will remain in the "faulty" state.

Let the vector of initial probabilities of device states be given by the relation

, i.e.
(at the initial moment the device was faulty). It is required to determine the probabilities of the state of the device after three days.

Decision: Using the transition matrix, we determine the probabilities of states after the first step (after the first day):

The probabilities of the states after the second step (the second day) are

Finally, the probabilities of states after the third step (third day) are

Thus, the probability that the device will be in good condition is 0.819, and that it is in a faulty state, respectively, 0.181.

Markov chain- such a chain of events in which the probability of each event depends only on the previous state.

This article is abstract in nature, based on the sources cited at the end, which are cited in places.

Introduction to the theory of Markov chains

A Markov chain is such a sequence of random events in which the probability of each event depends only on the state in which the process is currently located and does not depend on earlier states. The finite discrete circuit is defined by:

∑ j=1…n p ij = 1

An example of a matrix of transition probabilities with a set of states S = (S 1 , ..., S 5 ), a vector of initial probabilities p (0) = (1, 0, 0, 0, 0):

With Using the vector of initial probabilities and the transition matrix, you can calculate the stochastic vector p (n) - a vector composed of the probabilities p (n) (i) that the process will be in state i at time n. You can get p(n) using the formula:

p(n) = p(0)×Pn

The vectors p (n) with the growth of n in some cases stabilize - they converge to some probability vector ρ, which can be called the stationary distribution of the chain. Stationarity manifests itself in the fact that taking p (0) = ρ, we get p (n) = ρ for any n.

The simplest criterion that guarantees convergence to a stationary distribution is as follows: if all elements of the transition probability matrix P are positive, then as n tends to infinity, the vector p (n) tends to the vector ρ, which is the only solution to the system of the form

It can also be shown that if, for some positive value of n, all elements of the matrix P n are positive, then the vector p (n) will stabilize anyway.

The proof of these assertions is given in detail.

A Markov chain is depicted as a transition graph, the vertices of which correspond to the states of the chain, and the arcs correspond to the transitions between them. The weight of the arc (i, j) connecting the vertices si and sj will be equal to the probability pi(j) of the transition from the first state to the second. The graph corresponding to the matrix shown above:

To classification of states of Markov chains

When considering Markov chains, we may be interested in the behavior of the system in a short period of time. In this case, the absolute probabilities are calculated using the formulas from the previous section. However, it is more important to study the behavior of the system over a large time interval, when the number of transitions tends to infinity. Next, definitions of the states of Markov chains are introduced, which are necessary to study the behavior of the system in the long term.

Markov chains are classified depending on the possibility of transition from one state to another.

The groups of states of a Markov chain (a subset of vertices of the transition graph) to which dead-end vertices of the order diagram of the transition graph correspond are called ergodic classes of the chain. If we consider the graph shown above, we see that it has 1 ergodic class M1 = (S5) reachable from the strongly connected component corresponding to the subset of vertices M2 = (S1, S2, S3, S4). States that are in ergodic classes are called essential, and the rest are called inessential (although such names do not agree well with common sense). The absorbing state si is a special case of the ergodic class. Then, once in such a state, the process will stop. For Si, pii = 1 will be true, i.e. in the transition graph, only one edge will come out of it - a loop.

Absorbing Markov chains are used as temporary models of programs and computational processes. When modeling a program, the states of the chains are identified with the blocks of the program, and the matrix of transition probabilities determines the order of transitions between the blocks, depending on the structure of the program and the distribution of the initial data, the values ​​of which affect the development of the computational process. As a result of the representation of the program by the absorbing chain, it is possible to calculate the number of calls to program blocks and the program execution time, estimated by means, variances, and, if necessary, distributions. Using these statistics in the future, you can optimize the program code - apply low-level methods to speed up critical parts of the program. This technique is called code profiling.

For example, in Dijkstra's algorithm, there are the following circuit states:

vertex (v), extracting a new vertex from the priority queue, transition to state b only;

begin (b), the beginning of the cycle of enumeration of outgoing arcs for the weakening procedure;

analysis (a), analysis of the next arc, possible transition to a, d, or e;

decrease (d), decrease in the estimate for some graph vertex, transition to a;

end (e), end of the loop, move to the next vertex.

It remains to set the transition probabilities between vertices, and we can study the duration of transitions between vertices, the probabilities of getting into different states, and other average characteristics of the process.

Similarly, the computational process, which is reduced to requests for system resources in the order determined by the program, can be represented by an absorbing Markov chain, the states of which correspond to the use of system resources - processor, memory and peripheral devices, transition probabilities reflect the order of access to various resources. Due to this, the computational process is presented in a form convenient for the analysis of its characteristics.

A Markov chain is said to be irreducible if any state Sj can be reached from any other state Si in a finite number of transitions. In this case, all states of the chain are said to be communicating, and the transition graph is a strongly connected component. The process generated by an ergodic chain, starting in a certain state, never ends, but successively passes from one state to another, falling into different states with different frequencies, depending on the transition probabilities. Therefore, the main characteristic of an ergodic chain is

the probabilities of the process being in the states Sj, j = 1,…, n, the fraction of time that the process spends in each of the states. Irreducible chains are used as systems reliability models. Indeed, if a resource that the process uses very often fails, the health of the entire system will be in jeopardy. In such a case, duplication of such a critical resource can help avoid failures. At the same time, the states of the system, which differ in the composition of the serviceable and failed equipment, are interpreted as the states of the circuit, the transitions between which are associated with failures and restoration of devices and changes in the connections between them, carried out to maintain the system's operability. Estimates of the characteristics of an irreducible circuit give an idea of ​​the reliability of the behavior of the system as a whole. Also, such chains can be models of the interaction of devices with tasks coming for processing.

Examples of using

Failure Service System

The server consists of several units, such as modems or network cards, which receive requests from users for service. If all blocks are busy, then the request is lost. If one of the blocks receives a request, then it becomes busy until the end of its processing. As states, we take the number of idle blocks. Time will be discrete. Denote by α the probability of receiving a request. We also assume that the service time is also random and consists of independent continuations, i.e. a request with probability β is served in one step, and with probability (1 - β) is served after this step as a new request. This gives the probability (1 - β) β for a two-step service, (1 - β)2 β for a three-step service, and so on. Consider an example with 4 devices operating in parallel. Let's make a matrix of transition probabilities for the chosen states:

M It can be seen that it has a unique ergodic class, and hence the p × P = p system has a unique solution in the class of probability vectors. We write down the equations of the system that allows us to find this solution:

Now we know the set of probabilities πi that i blocks will be occupied in the system in the stationary mode. Then the fraction of time p 4 = С γ 4 /4 in the system is occupied by all blocks, the system does not respond to requests. The results obtained apply to any number of blocks. Now you can use them: you can compare the cost of additional devices and the reduction in the time the system is completely busy.

You can read more about this example in .

Decision processes with a finite and infinite number of stages

Consider a process in which there are several matrices of transition probabilities. For each moment of time, the choice of one or another matrix depends on the decision we made. The above can be understood with the following example. As a result of the analysis of the soil, the gardener evaluates its condition with one of three numbers: (1) - good, (2) - satisfactory, or (3) - poor. At the same time, the gardener noticed that the productivity of the soil in the current year depends only on its condition in the previous year. Therefore, the probabilities of soil transition from one state to another without external influences can be represented by the following Markov chain with matrix P1:

L Naturally, soil productivity deteriorates over time. For example, if last year the state of the soil was satisfactory, then this year it can only remain the same or become bad, but it will never become good. However, the gardener can influence the state of the soil and change the transition probabilities in the P1 matrix to those corresponding to them from the P2 matrix:

T Now you can assign to each transition from one state to another some function of income, which is defined as profit or loss over a one-year period. The gardener can choose to use or not to use fertilizer, it will depend on his final income or loss. Let us introduce the matrices R1 and R2, which determine the income functions depending on the costs of fertilizers and soil quality:

H Finally, the gardener is faced with the task of what strategy to choose to maximize the average expected income. Two types of problems can be considered: with a finite and infinite number of stages. In this case, someday the activity of the gardener will definitely end. In addition, visualizers solve the decision problem for a finite number of stages. Let the gardener intend to stop his occupation in N years. Our task now is to determine the optimal strategy for the gardener's behavior, that is, the strategy that maximizes his income. The finiteness of the number of stages in our problem is manifested in the fact that the gardener does not care what will happen to his agricultural land for N + 1 years (all years up to N inclusive are important to him). Now it is clear that in this case the problem of finding a strategy turns into a problem of dynamic programming. If we denote by fn(i) the maximum average expected income that can be obtained in stages from n to N inclusive, starting from the state with number i, then it is easy to derive the recursive

W where k is the number of the strategy used. This equation is based on the fact that the total income rijk + fn+1(j) is obtained as a result of the transition from state i at stage n to state j at stage n+1 with probability pijk.

Now the optimal solution can be found by sequentially computing fn(i) in the downward direction (n = N…1). At the same time, the introduction of the vector of initial probabilities into the condition of the problem will not complicate its solution.

This example is also discussed in .

Modeling word combinations in text

Consider a text consisting of the words w. Imagine a process in which the states are words, so that when it is in the state (Si) the system goes to the state (sj) according to the matrix of transition probabilities. First of all, it is necessary to “train” the system: submit a sufficiently large text to the input to estimate the transition probabilities. And then you can build the trajectories of the Markov chain. An increase in the semantic load of a text constructed using the Markov chain algorithm is possible only with an increase in order, where the state is not one word, but sets with greater power - pairs (u, v), triples (u, v, w), etc. And that in the chains of the first, that of the fifth order, there will be little more sense. Meaning will begin to appear when the dimension of the order increases to at least the average number of words in a typical phrase of the source text. But it is impossible to move in this way, because the growth of the semantic load of the text in Markov chains of high orders is much slower than the decrease in the uniqueness of the text. And a text built on Markov chains, for example, of the thirtieth order, will still not be so meaningful as to be of interest to a person, but already quite similar to the original text, moreover, the number of states in such a chain will be amazing.

This technology is now very widely used (unfortunately) on the Internet to create content for web pages. People who want to increase traffic to their site and improve its ranking in search engines tend to put as many search keywords on their pages as possible. But search engines use algorithms that can distinguish real text from a rambling jumble of keywords. Then, in order to deceive the search engines, they use texts created by the generator based on the Markov chain. There are, of course, positive examples of using Markov chains to work with text, they are used to determine authorship and analyze the authenticity of texts.

Markov chains and lotteries

In some cases, a probabilistic model is used in predicting numbers in various lotteries. Apparently, there is no point in using Markov chains to model the sequence of different circulations. What happened to the balls in the draw will not affect the results of the next draw, because after the draw the balls are collected, and in the next draw they are placed in the lottery drum in a fixed order. The connection with the previous edition is lost. Another thing is the sequence of balls falling within the same draw. In this case, the fall of the next ball is determined by the state of the lottery drum at the time of the fall of the previous ball. Thus, the sequence of balls falling in one draw is a Markov chain, and such a model can be used. When analyzing numerical lotteries, there is a great difficulty here. The state of the lottery drum after the next ball has fallen determines further events, but the problem is that this state is unknown to us. All we know is that some ball fell out. But when this ball falls out, the other balls can be arranged in different ways, so that there is a group of a very large number of states corresponding to the same observed event. Therefore, we can only construct a matrix of transition probabilities between such groups of states. These probabilities are an average of the transition probabilities between different individual states, which of course reduces the effectiveness of applying the Markov chain model to number lotteries.

Similar to this case, such a neural network model can be used for weather forecasting, currency quotes, and in connection with other systems where there is historical data, and new information can be used in the future. A good application in this case, when only the manifestations of the system are known, but not the internal (hidden) states, can be applied hidden Markov models, which are discussed in detail in Wikibooks (hidden Markov models).

All possible states of the system in a homogeneous Markov chain, and is the stochastic matrix defining this chain, composed of transition probabilities (See page 381).

Denote by the probability that the system is in a state at a time if it is known that at the time the system was in a state (,). Obviously, . Using the theorems on addition and multiplication of probabilities, we can easily find:

or in matrix notation

Hence, giving successively the values ​​of , we obtain the important formula

If there are limits

or in matrix notation

then the quantities are called limiting or final transition probabilities.

To find out in which cases there are limiting transition probabilities, and to derive the corresponding formulas, we introduce the following terminology.

We will call a stochastic matrix and the corresponding homogeneous Markov chain correct if the matrix does not have characteristic numbers that are different from unity and equal in absolute value to unity, and regular if unity is additionally a simple root of the characteristic equation of the matrix .

A regular matrix is ​​characterized by the fact that in its normal form (69) (p. 373) the matrices are primitive. For a regular matrix, additionally .

In addition, a homogeneous Markov chain is called indecomposable, decomposable, acyclic, cyclic, if for this chain the stochastic matrix is, respectively, indecomposable, decomposable, primitive, imprimitive.

Since a primitive stochastic matrix is ​​a special kind of a regular matrix, an acyclic Markov chain is a special kind of a regular chain.

We will show that limiting transition probabilities exist only for regular homogeneous Markov chains.

Indeed, let be the minimal polynomial of a regular matrix . Then

According to Theorem 10, we can assume that

Based on formula (24) Ch. V (page 113)

(96)

where is the reduced adjoint matrix and

If is a regular matrix, then

and therefore on the right side of formula (96) all the terms, except for the first one, tend to zero as . Therefore, for a regular matrix, there is a matrix composed of limiting transition probabilities, and

The opposite is obvious. If there is a gap

then the matrix cannot have a characteristic number for which , but , since then the limit would not exist [The same limit must exist due to the existence of the limit (97").]

We have proved that for a correct (and only correct) homogeneous Markov chain there exists a matrix . This matrix is ​​determined by formula (97).

Let us show how the matrix can be expressed in terms of the characteristic polynomial

and the associated matrix .

From identity

by virtue of (95), (95") and (98) it follows:

Therefore, formula (97) can be replaced by the formula

(97)

For a regular Markov chain, since it is a special type of a regular chain, the matrix exists and is determined by any of formulas (97), (97"). In this case, formula (97") also has the form

2. Consider a regular chain of general type (irregular). We write the corresponding matrix in normal form

(100)

where are primitive stochastic matrices, and indecomposable matrices have maximum characteristic numbers . Assuming

,

write in the form

(101)

But , since all the characteristic numbers of the matrix are less than unity in absolute value. So

(102)

Since are primitive stochastic matrices, then the matrices according to formulas (99) and (35) (p. 362) are positive

and in each column of any of these matrices, all elements are equal to each other:

.

Note that the normal form (100) of the stochastic matrix corresponds to the division of the system states into groups:

Each group in (104) corresponds to its own group of series in (101). According to the terminology of L. N. Kolmogorov, the states of the system included in are called essential, and the states included in the remaining groups are called inessential.

It follows from the form (101) of the matrix that, for any finite number of steps (from moment to moment ), only the transition of the system is possible a) from an essential state to an essential state of the same group, b) from an insignificant state to an essential state, and c) from an insignificant state to the non-essential state of the same or an earlier group.

From the form (102) of the matrix, it follows that in the process when the transition is possible only from any state to an essential state, i.e., the probability of transition to any insignificant state tends to zero with the number of steps. Therefore, essential states are sometimes also called limit states.

3. From formula (97) it follows:

.

This shows that each column of the matrix is ​​an eigenvector of the stochastic matrix for the characteristic number .

For a regular matrix, the number 1 is a simple root of the characteristic equation, and this number corresponds to only one (up to a scalar factor) matrix eigenvector . Therefore, in any -th column of the matrix, all elements are equal to the same non-negative number:

Thus, in a regular chain, the limiting transition probabilities do depend on the initial state.

Conversely, if in some regular homogeneous Markov chain the individual transition probabilities do not depend on the initial state, i.e., formulas (104) hold, then in scheme (102) for the matrix it is obligatory . But then the chain is also regular.

For an acyclic chain, which is a special case of a regular chain, is a primitive matrix. Therefore, for some (see Theorem 8 on p. 377). But then and .

Conversely, from it follows that for some , and this, according to Theorem 8, means that the matrix is ​​primitive and, therefore, the given homogeneous Markov chain is acyclic.

We formulate the results obtained in the form of the following theorem:

Theorem 11. 1. In order for all limiting transition probabilities to exist in a homogeneous Markov chain, it is necessary and sufficient that the chain be regular. In this case, the matrix , composed of the limiting transition probabilities, is determined by formula (95) or (98).

2. In order for the limiting transition probabilities to be independent of the initial state in a regular homogeneous Markov chain, it is necessary and sufficient that the chain be regular. In this case, the matrix is ​​determined by formula (99).

3. In order for all limiting transition probabilities to be different from zero in a regular homogeneous Markov chain, it is necessary and sufficient that the chain be acyclic.

4. Let us introduce columns of absolute probabilities

(105)

where is the probability of the system being in the state (,) at the moment. Using the theorems of addition and multiplication of probabilities, we find:

(,),

or in matrix notation

where is the transposed matrix for the matrix .

All absolute probabilities (105) are determined from formula (106) if the initial probabilities and the matrix of transition probabilities are known

Let us introduce into consideration the limiting absolute probabilities

Passing in both parts of equality (106) to the limit at , we obtain:

Note that the existence of a matrix of limiting transition probabilities implies the existence of limiting absolute probabilities for any initial probabilities and vice versa.

From formula (107) and from the form (102) of the matrix, it follows that the limiting absolute probabilities corresponding to insignificant states are equal to zero.

Multiplying both sides of the matrix equality

to the right, we, by virtue of (107), obtain:

i.e., the column of marginal absolute probabilities is the eigenvector of the matrix for the characteristic number .

If the given Markov chain is regular, then it is a simple root of the characteristic equation of the matrix . In this case, the column of limiting absolute probabilities is uniquely determined from (108) (since and ).

Let a regular Markov chain be given. Then from (104) and from (107) it follows:

(109)

In this case, the limiting absolute probabilities do not depend on the initial probabilities .

Conversely, may not depend on in the presence of formula (107) if and only if all rows of the matrix are the same, i.e.

,

and therefore (by Theorem 11) is a regular matrix.

If is a primitive matrix, then , and hence due to (109)

Conversely, if all and do not depend on the initial probabilities, then in each column of the matrix all elements are the same and according to (109) , and this, according to Theorem 11, means that is a primitive matrix, i.e., this chain is acyclic.

It follows from the above that Theorem 11 can be formulated as follows:

Theorem 11. 1. In order for all limiting absolute probabilities to exist in a homogeneous Markov chain for any initial probabilities, it is necessary and sufficient that the chain be regular.

2. In order for a homogeneous Markov chain to have limiting absolute probabilities for any initial probabilities and not depend on these initial probabilities, it is necessary and sufficient that the chain be regular.

3. In order for a homogeneous Markov chain to have positive limiting absolute probabilities for any initial probabilities and these limiting probabilities not to depend on the initial ones, it is necessary and sufficient that the chain be acyclic.

5. Consider now a homogeneous Markov chain of general type with a matrix of transition probabilities .

Let us take the normal form (69) of the matrix and denote by the imprimitivity indices of the matrices in (69). Let be the least common multiple of integers . Then the matrix does not have characteristic numbers equal in absolute value to one, but different from one, i.e., is a regular matrix; at the same time - the smallest indicator, at which - the correct matrix. We call a number the period of a given homogeneous Markov chain and. Conversely, if and defined by formulas (110) and (110").

The average limiting absolute probabilities corresponding to non-essential states are always equal to zero.

If there is a number in the normal form of the matrix (and only in this case), the average limiting absolute probabilities do not depend on the initial probabilities and are uniquely determined from equation (111).

Definition. A Markov chain is called homogeneous if the conditional probability (transition from state to state) does not depend on the test number. Therefore, instead of writing simply.

Example 1 Random wander. Let there be a material particle on a straight line at a point with an integer coordinate. At certain moments of time, the particle experiences shocks. Under the action of a push, the particle is displaced by one to the right with probability and by one to the left. It is clear that the position (coordinate) of the particle after the shock depends on where the particle was after the immediately preceding shock, and does not depend on how it moved under the action of the other previous shocks.

So a random walk? an example of a homogeneous Markov chain with discrete time.

The transition probability is the conditional probability that from the state (in which the system ended up as a result of some test, no matter what number) as a result of the next test, the system will go into the state.

Thus, in the notation, the first index indicates the number of the previous one, and the second? subsequent state number. For example, - the probability of transition from the second state to the third.

Let the number of states be finite and equal.

The transition matrix of a system is a matrix that contains all the transition probabilities of this system:

Since each row of the matrix contains the probabilities of events (transition from the same state to any possible state) that form a complete group, the sum of the probabilities of these events is equal to one. In other words, the sum of the transition probabilities of each row of the transition matrix is ​​equal to one:

Let us give an example of the transition matrix of a system that can be in three states; the transition from state to state occurs according to the scheme of a homogeneous Markov chain; transition probabilities are given by the matrix:

Here we see that if the system was in a state, then after changing the state in one step, it will remain in the same state with a probability of 0.5, with a probability of 0.5 it will remain in the same state, with a probability of 0.2 it will go into a state, then after the transition, it may end up in states; it cannot go from state to state. The last row of the matrix shows us that from the state to go to any of the possible states with the same probability of 0.1.

Based on the transition matrix of the system, you can build the so-called system state graph, it is also called the labeled state graph. This is useful for visualizing the circuit. Let's consider the order of graph construction using an example.

Example 2 Based on the given transition matrix, construct a state graph.

Because matrix of the fourth order, then, accordingly, the system has 4 possible states.

The graph does not indicate the probabilities of the system transition from one state to the same one. When considering specific systems, it is convenient to first construct a state graph, then determine the probability of system transitions from one state to the same one (based on the requirement that the sum of the matrix row elements be equal to one), and then compile the system transition matrix.