Roughly as follows:

Markov chain, Andre? Markov (A.A.Markov, 1856- 1922) is mathematically named as a discrete-time stochastic process with Markov properties. In this process, given the current knowledge or information, the past (that is, the historical state before the current period) is irrelevant to predict the future (that is, the future state after the current period).

Brief introduction of principle

Markov chain is a sequence of random variables X_ 1, X_2, X_3 ... The range of these variables, that is, the set of all their possible values, is called "state space", and the value of X_n is the state at n moment. If the conditional probability distribution of X_{n+ 1} for past states is only a function of X_n, The above identities can be regarded as Markov properties.

Theoretical development of editing this paragraph

Markov first did this process in 1906. Kolmogorov extended this to countable infinite state space in 1936. Markov chain is related to Brownian motion and ergodic hypothesis, two important topics in physics at the beginning of the 20th century. However, it seems that Markov seeks not only mathematical motives, but also an extension of the law of large numbers of vertical events in name. Physical Markov chain is usually used to model queuing theory and statistics, and can also be used as a signal model of entropy coding technology, such as arithmetic coding (the famous LZMA data compression algorithm uses Markov chain and interval coding similar to arithmetic coding). Markov chain also has many applications in biology, especially population process, which can help to simulate the modeling of biological population process. Hidden Markov model is also used to predict coding regions or genes in bioinformatics. The recent application of Markov chain is in geostatistics. Among them, Markov chain is used for random simulation of two-dimensional to three-dimensional discrete variables based on observation data. This application is similar to Kriging statistics, which is called Markov chain statistics. This Markov chain geostatistics method is still in the process of development.

Edit this Markov process

Markov processes can generate rough but seemingly real text for a given sample text: they are used in many entertainment "imitation generator" software. Markov chains are also used to compose music. They are indispensable conditions for the following deduction: (1) scale has Markov property. Random fields form a Markov chain from top to bottom, that is, the distribution of Xi depends only on Xi, and has nothing to do with other coarser scales. (2) Conditional independence of pixels in random fields. If the parent node of the Xi pixel is known, then the Xi pixels are independent of each other. This property makes it unnecessary for us to consider the relationship between adjacent pixels in the plane grid, but to study the relationship between adjacent pixels (that is, parent-child nodes) between scales. (3) Given Xn, the pixels in y are independent of each other. (4) separability. If any node xs is given, the variables corresponding to the subtree with its child nodes as the root are independent of each other. From the root with only one node to the leaf node with the same size as the image, a complete quadtree model is established, and the causal relationship of Markov chains between layers enables us to quickly calculate the maximum posterior probability or posterior marginal probability of X through non-iterative derivation.

Edit this paragraph model

The complete quadtree model also has some problems. (1) Because the probability value is too small, it is difficult to guarantee the accuracy of the computer. If there are more levels, this problem will be more prominent. Although a small value close to 0 can be converted into a large negative value by taking logarithm, if there are too many levels and the probability value is too small, this method will be difficult to work. And the techniques used for these transformations add a lot of calculations. (2) When the image is large, resulting in more layers, the layer-by-layer calculation is very complicated, and underflow will definitely occur. The intermediate variables in the storage will also occupy a lot of space, and the overhead in time and space will be more. (3) The layered model has block effect, that is, the boundary of the region may jump, because in this model, adjacent pixels in the same layer of the random field may not have the same parent node, and there is no interaction between adjacent pixels in the same layer, so the boundary may be discontinuous.

Edit this MRF model

In order to solve these problems, we propose a new hierarchical MRF model-semi-tree model. Its structure is similar to figure 1 5, and it is still a quadtree, but the number of layers is greatly reduced compared with that of a complete quadtree, which is equivalent to cutting a complete quadtree into two parts and removing only the half part. The bottom layer of the model is still consistent with the image size. However, there are multiple nodes at the top level. The properties of the complete quadtree model are completely applicable to the semi-tree model, and the difference is only at the top level. The complete tree model constitutes a complete causal dependence from top to bottom, while the causal relationship between the layers of the semi-tree model is truncated, and the parents and ancestors of the nodes in this layer are deleted, so each node in this layer does not have conditional independence, that is, it does not meet the above property 2. Therefore, the layer is changed to consider the relationship between adjacent nodes in the layer. Compared with the complete tree model, the semi-tree model has many layers, so that the information between layers can be transmitted faster, and the probability value will not be too small to overflow because of too many layers of calculation. However, layer 0 brings new problems, and the interaction between nodes must be considered in order to get the correct deduction results. It is precisely because the influence between adjacent nodes is considered at Layer 0. The blocky phenomenon of this model is better than that of the complete tree model. For the selection of the number of levels, we think it should not be too much, which can not achieve the purpose of simplifying the model and its advantages can not be reflected, but it can not be too little. Because the probability calculation of level 0 still needs non-iterative algorithm, a small number of levels means that the number of nodes of level 0 is still large, and the calculation is time-consuming, so the series is half or slightly less than the complete series in the experiment.

Edit this MPM algorithm

MPM algorithm image segmentation based on trident tree model is the configuration of known observation image Y and estimated image X, which can be expressed as an optimization problem by Bayesian estimator. X = argmin [e c (x, x) ′| y = y], where the cost function c gives the cost when the real configuration is x and the actual segmentation result is x ′. When y is known, the expectation of this cost is minimized and the optimal segmentation is obtained. Different estimators are obtained by taking different cost functions. If c (x, x')= 65438, δ(x, x') (when x = x', δ(x, x')= 1, otherwise δ(x, x')= 0) gets a MAP estimator, which means that as long as x and x' are different in one pixel. Wang Xili, et al.: A hierarchical Markov image model and its derivation algorithm, but there are some misclassification in practical application. If the MPM algorithm of semi-tree model is named HT-MPM, it is divided into two steps: upward algorithm and downward algorithm. The upward algorithm calculates P(yd(s)|xs) and P (xs, xρ (s) layer by layer according to equations (2) and (3). For the lowest layer P(yd(s)|xs)=P(ys|xs), the downward algorithm calculates P(xs|y) layer by layer according to the formula (1), and the sampling x0 (1), ..., x0 (n) starts from the top layer.

Please edit this paragraph for details.

Markov chain, named after A.A.Markov (1856- 1922), is a discrete-time stochastic process with Markov property in mathematics. In this process, given the current knowledge or information, the past (that is, the historical state before the current period) is irrelevant to predict the future (that is, the future state after the current period). Markov processes with discrete time and state are called Markov chains, abbreviated as xn = x (n), n = 1, 2,3,4 ... Markov chains are a sequence of random variables. The range of these variables, that is, the set of all their possible values, is called "state space", and the value of Xn is the state at time n. If the conditional probability distribution Xn+ 1 of the past state is only a function of Xn, then x here is a state in the process. The above identities can be regarded as Markov properties. Markov first did this process in 1906. Kolmogorov extended this to countable infinite state space in 1936. Markov chain is related to Brownian motion and ergodic hypothesis, two important topics in physics at the beginning of the 20th century. However, it seems that Markov seeks not only mathematical motives, but also an extension of the law of large numbers of vertical events in name. Markov chain is a stochastic process that satisfies the following two assumptions: the probability distribution of system state at 1 and T+ 1 is only related to the state at time t, but not to the state before time t; 2. The state transition from time t to time t+ 1 has nothing to do with the value of t ... A Markov chain model can be expressed as =(S, p, q), in which the meanings of each element are as follows: 1)S is a non-empty state set composed of all possible states of the system, sometimes called the state space of the system, which can be a finite and countable set or a countable set. This paper assumes that S is a countable set (that is, finite or countable). Use lowercase letters I, J (or s i, Sj) to indicate the status. 2) is the state transition probability matrix of the system, where Pij represents the probability that the system is in state I at time t and in state I at the next time t+ 1, and n is the number of all possible states of the system. For any i∈s, there is. 3) is the initial probability distribution of the system, and qi is the probability that the system is in state I at the initial moment, satisfying.

Edit the basic properties of this paragraph

The property of Markov chain model Markov chain is represented by a conditional distribution P(Xn+ 1 | Xn), which is called "transition probability" in stochastic process. This is sometimes called "one-step transition probability". The transition probabilities of two, three and more steps can be derived from the one-step transition probability and Markov property: Similarly, these formulas can be multiplied by the transition probability and k? 1 integration to extend to any future time n+k. The marginal distribution P(Xn) is the state distribution at time n. The initial distribution is P(X0). The change of this process can be described by the following time step: this is a version of Frobenius-Perron equation. At this time, one or more state distributions π may be satisfied: where y is just a name of an integral variable. Such a distribution π is called "stationary distribution" or "steady distribution". Stationary distribution is a characteristic equation corresponding to a conditional distribution function whose characteristic root is 1. Whether stationary distribution exists, if it exists, is determined by the specific nature of the process. Irreducible means that each state can come from any other state. When at least one state returns continuously after a fixed period of time, this process is called "periodic".

Edit the discrete state of the paragraph.

Markov chain model in discrete state space If the state space is finite, then the transition probability distribution can be expressed as a matrix with (i, j) elements, which is called "transition matrix": Pij = P(Xn+ 1 = i | Xn = j) For a discrete state space, the integral of k-step transition probability is sum, which can be obtained by raising the transition matrix to the k power. That is to say, if it is a one-step transfer matrix, it is the transfer matrix after k-step transfer. The stationary distribution is a vector satisfying the following formula: In this case, the stationary distribution π * is the characteristic vector corresponding to the transition matrix whose characteristic root is 1. If the transfer matrix is irreducible and aperiodic, it converges to a stationary distribution π * with different columns and is independent of the initial distribution π. Peron-Frobenius theorem points out this point. Positive transition matrix (that is, every element of the matrix is positive) is irreducible and aperiodic. A matrix is called a random matrix if and only if it is a matrix of transition probability in Markov chain. Note: In the above formula, the element (I, j) is the transition probability from J to I, and sometimes an equivalent formula given by the element (I, j) is equal to the transition probability from I to J. In this case, the transition matrix is just the transposition of the transfer matrix given here. In addition, the stationary distribution of the system is given by the left eigenvector of the transfer matrix, not the right eigenvector. The transition probability has nothing to do with the past special case, which is the so-called Bernoulli scheme. Bernoulli scheme with only two possible states is called Bernoulli process.

Edit this paragraph for practical application.

Application of Markov chain model

Scientific application

Markov chain is usually used to model queuing theory and statistics, and can also be used as a signal model of entropy coding technology, such as algorithm coding. Markov chain also has many applications in biology, especially population process, which can help to simulate the modeling of biological population process. Hidden Markov model is also used to predict coding regions or genes in bioinformatics. The recent application of Markov chain is in geostatistics. Among them, Markov chain is used for random simulation of two-dimensional to three-dimensional discrete variables based on observation data. This application is similar to Kriging statistics, which is called Markov chain statistics. This Markov chain geostatistics method is still in the process of development.

Application in human resources

Markov chain model mainly analyzes the possibility of a person transferring from one position to another at a certain stage, that is, the probability of transfer. A basic assumption of this model is that the pattern and probability of internal personnel changes in the past are generally consistent with the future trend. This method is actually to analyze the flow trend and probability of human resources within the enterprise, such as promotion, job transfer, deployment or resignation, so as to provide a basis for the deployment of internal human resources. Its basic idea is to infer the future personnel supply by discovering the law of organizational personnel changes in the past. Markov chain model usually collects data in several periods and then calculates the average value. Using these data to represent the frequency of personnel changes in each position, we can infer the personnel changes. The specific method is: multiply the number of people in each position at the beginning of the plan by the probability of personnel change in each position, and then add them vertically to get the net supply of future labor within the organization. Its basic expression is: ni (t): the number of class I personnel in t time; Pji: the transfer rate of personnel from class J to class I; Vi(t): the number of people supplemented by Class I in time (T- 1, t). There are five kinds of personnel changes in enterprises: transfer-in, transfer-in, transfer-in, promotion and demotion. Table 3 assumes the changes of various personnel in a retail company from 1999 to 2000. There were 12 store managers at the beginning of the year. In that year, on average, 90% of the store managers were still in the store, 65,438+00% of the store managers left, 65,438+065,438% of the 36 assistant managers were promoted to managers, 83% stayed in their original posts and 6% left. If the turnover frequency is relatively stable, then in 2000,1person (12×90%) stayed in the position of manager, in addition, four assistant managers (36×83%) were promoted to the position of manager, and finally the total number of managers was 15 (6544 According to this matrix, the supply situation of other personnel can be obtained, and the forecast results of subsequent periods can also be calculated.

The reference comes from the encyclopedia!