Markov chain

A Markov chain ( Markov chain german, also Markov process, according to Andrei Markov, other spellings: Markov chain Markov chain, Markof chain) is a special stochastic process. A Markov chain is defined about the fact that by knowing a limited history as good forecasts of the future development are possible, such as the knowledge of the entire history of the process.

A distinction Markov chains of different orders. In the case of a first-order Markov chain this means that the future of the system depends only on the present ( the current state ) and not of the past from. The mathematical formulation in the case of a finite set of states requires only the concept of the discrete distribution and the conditional probability, while the concepts of filtration and the conditional expectations are needed in the continuous-time case.

Goal in the application of Markov chains to provide probabilities for the occurrence of future events.

• 2.1 Definition
• 2.4 Modelling 2.4.1 Arrival First ( AF)
• 2.4.2 Departure First ( DF)

Examples

Markov chains are very well suited to model random changes of state of a system, if one has reason to believe that the state changes only over a limited period of time have influence on each other or even without memory. One example is the utilization of operating systems with memoryless arrival and service times.

Continuous Markov chain

The prime example of a continuous Markov process with the real numbers as the state space is the Wiener process.

Discrete, finite Markov chain

A popular example of a discrete-time Markov chain with finite state space is the random walk ( engl. random walk ) on a discrete circuit, modeled by the residue class ring. This leads to a finite state space. This one starts in the equivalence class of 0, and moves in each step from the current state with probability after or after ( so vividly: a step to the left or to the right).

In another example, you throw a coin repeatedly and recorded at each throw, how many times so far ' head ' has been released. The sequence of numbers thus formed also forms a ( discrete-time ) Markov chain, this time with state space with each of the transition probability for the transition from to and for staying.

Discreet, infinite Markov chain: Lamplighter

With a random random walk on a lamp at any time on or off at each location. The current state at time n of the Markov process is described by two variables: the current location of the lamp and Lamplighters configuration ( for example, by a picture of after ). Then (Pn, η ) is a Markov process and even (Pn ) alone is a Markov process; on its own is ( η ) but not a Markov process.

Discrete -time and finite set of states

Definition

In the case of a finite set of states and the discrete time is a Markov chain of order on a stochastic process with values ​​in the property and

The equation means that the probability distribution for the state at the time depends only on the previous states, but not yet more distant. Of particular interest are first-order Markov chains, ie chains with

This can be interpreted that the future behavior of the system depends only on the current state and not on the previous states. This property is called memoryless or Markov property. Usually one means by the term Markov chain only a first-order Markov chain; This is also handled in the rest of the article so.

A probability vector is a ( written as a row vector ) vector in with the property that for all and. Such vectors correspond exactly means the probability distributions on the state space. For simplicity, we say to even distribution. ( It should be noted that - as with the introduced below the transition matrix - the associated distribution depends on the numbering of the state space, and therefore, only modulo Basisumordnung is unique.)

We now consider the following is a discrete-time Markov chain on a finite state space. The probability vector by

Is given, ie initial distribution. The transition probabilities are given by

[If some conditional probabilities are not defined, is written instead of just the same in the matrix. ]

Are the transition probabilities irrespective of the time, thus for all, then we speak of a homogeneous Markov chain with transition matrix.

A homogeneous Markov chain, the probability of transition to the state in the steps from the state can be calculated using the - th power of the transformation matrix:

It follows easily that the distribution of already uniquely determined by and is

That is, the distribution is given by the probability vector.

A distribution is stationary ( with respect to the Markov chain ), if applicable

This can be interpreted as follows: one from Dice according to a state, and now turns to the one described by the homogeneous Markov chain random transition to this state, the result is true in general, a different result, but the probability distribution remains the same; described by the coincidence is invariant under the transformation of the Markov chain. In other words: Would you rather start with initial distribution, so one would be a stationary process. (Sometimes also somewhat inaccurate, spoken by a steady state. )

It may well be more than one stationary distribution; the degenerate extreme case that the transition is given by the unit matrix (the Markov chain that is always equal to the initial value), all the even distribution are stationary. But there is a large class of interesting Markowprozessen for which there exists a stationary distribution:

An irreducible, aperiodic homogeneous Markov chain has exactly one stationary distribution, see the set of Perron - Frobenius; this can be described in two ways: First, if the transformation matrix, so, the sequence of the template against the matrix which is inscribed in the distribution in each row. This relationship can also be formulated differently: For the distributions of you, the distributions of the Markov chain thus converge to the stationary distribution.

Secondly, is referred to the average waiting time required for the process to pass from the point to the point, it follows that for all.

Example: As an example of how the second relationship can be used, we consider the (symmetric ) random walk on the set; here the transition matrix is given by

We first consider how long is the average waiting time for a change from one point to another, very different. Because the matrix is invariant under permutation of the elements of the state space, this wait time is always the same. Let us therefore consider the waiting time from point 0 to point 1 with probability is 1, with probability we meet in the first train instead of '1 ' '2'. In this case, we have now from '2 ' to '0'; However, the waiting time for this is the means the same as for the path from '1 ' to '0'. Thus we obtain the relation This equation has the unique solution. Now we consider the average waiting time to 'to '0 ' to go from '0. The process is in step 1 in any case hike on the '1 'or '2'; in both cases, the expected remaining waiting time, calculated as above, 2 steps, and so we get it. By symmetry, then also applies. So here is the uniform distribution is stationary.

Recurrent and transient

A state is called recurrent, if the Markov chain, returning at takeoff with probability 1, that is almost certainly at some point in this state.

Call for the formal definition

The first return time of the chain in the state with the Convention, that is, if the chain never returns to the state. Then is called recurrent, if valid, otherwise called the state transient.

Recurrence and transience can also be characterized as follows: Denote the probability of getting to steps the first time from the state back to the state, so

Is the probability of a return to start after any number of steps. If so, the state is transient. If so, the state is recurrent.

A Markov chain is called recurrent (transient ) if every state is recurrent ( transient) is.

Modeling

It has often been present in a modeling applications in which the changes of state of the Markov chain is determined by a sequence of occurring at random times events (think of the above example of control systems with random arrival and service times ). Here it must be decided in the modeling, such as the simultaneous occurrence of events (arrival vs. Execution ) is treated. Usually one chooses to artificially introduce a sequence of concurrent events. Usually, we distinguish between the possibilities Arrival and departure First First.

Arrival First ( AF)

In this discipline the operation is started at the beginning of a time step. Then make a new receivables, and only at the end of a time step occurs the operating end.

The advantage of this discipline is that demand arrivals always arrive before a possible user - end and thus the PASTA property ( Poisson Arrivals See Time Averages ) holds. With the help of this property can be used for arrivals, which are modeled as a Bernoulli process, among other things very easy for operating systems expect important properties such as the loss probability.

One disadvantage is a requirement that arrives in time slot at the earliest uses in ready. This may lead to a higher number of required waiting places in the modeled system.

Departure First ( DF)

In the case of First Departure come at the beginning of a time step of demands in the system. This is followed by the start of service times and at the end of a time step, the end of service times.

In this approach, the PASTA property is no longer valid, which generally leads to more complicated calculations than in the case of First Arrival. A request may arrive at the same time step and be ready served.

Continuous -time and discrete state space

Analogously, the Markov chain formed for continuous time and discrete state space. This means that changes abruptly at certain times of the state.

Be a stochastic process with continuous time and discrete state space. Then, in a homogeneous Markov process

Here also form transition matrices: for all, and ( this is as usual for the unit matrix).

It is the Chapman - Kolmogorov equation and is correspondingly half group under certain conditions has an infinitesimal generator, namely the Q- matrix.

Markov chains can also be defined on general measurable state spaces. Is not countable state space so you need this, the stochastic core as a generalization of transition matrix. Here, a Markov chain by the initial distribution on the state space and the stochastic kernel is determined (also transition kernels or Markowkern ) already clear.

In the field of general Markov chains, there are still many open problems. Well researched are only Harris chains.

Applications

Markov chains are used in different areas.

• In economics in queuing theory. Here below is a homogeneous Markov chain. There, the waiting period to a number of customers are considered. The probabilities for a customer arrival or departure are time-invariant (regardless of the period).
• Bioinformatics: Markov chains are used in bioinformatics to investigate sequence segments on certain properties. This includes, for example, the presence of CpG islands, as these transition probabilities between CG and GC are increased.
• In health economics, for probabilistic modeling in the context of a cost- benefit analysis of health technologies such as medicines.
• In the actuarial discrete Markov chains are used for inclusion of biometric risks ( likelihood of disability, mortality, ...).
• The financial mathematics used on the Wiener process based Markov processes to model stock price and interest rate trends.
• In the music to compose algorithmic art, for example with Iannis Xenakis.
• In quality management, to determine the reliability of a system and its subcomponents
• In automated online marketing to generate texts that are difficult to distinguish from automatic spam filtering authored by people texts.
• Certain board games like Monopoly and Snakes and Ladders can be understood as a Markov chain.