The one-step transition probability matrix

DeHnition. The one-step transition probability function pjk for a Markov chain is a function that gives the probability of going from state j to state k in one step (one time interval) for each j and k. It will be denoted by  

Note that the concept of conditional probability is imbedded in the definition of pjk. Considering Eq.(2-1 la), we may write also  

for a time-homogeneous chain, the probability of a transition in a unit time or in a single step from one given state to another, depends only on the two states and not on the time. 

In general, the one-step transition probability function is given by  

The one-step transition probabilities can be arranged in a matrix form as follows  

---

The basic elements of Markov-chain theory are the state space, the one-step transition probability matrix or the policy-making matrix and the initial state vector termed also the initial probability function In order to develop in the following a portion of the theory of Markov chains, some definitions are made and basic probability concepts are mentioned. 

Example 2.20 is a random walk with retaining barriers (partially reflecting). It has been assumed that the occupation probability by the system of the boundary state, or moving to the other boundary state is 0.5. Thus, the one-step transition probability matrix reads ... 

Example 2.22 is a modified version of the random walk. If the system (bird) occupies one of the seven interior states S2 to S7, it has equal probability of moving to the right, moving to the left, or occupying its present state. This probability is 1/8. If the system occupies the boundaries Si and S9, it can not remain there, but has equal probability of moving to any of the other seven states. The one-step transition probability matrix, taking into account the above considerations, is given by ... 

Deflnitions. The basic elements of Markov chains associated with Eq.(2-24) are the system, the state space, the initial state vector and the one-step transition probability matrix. Considering refs.[26-30], each of the elements will be defined in the following with special emphasize to chemical reactions occurring in a batch perfectly-mixed reactor or in a single continuous plug-flow reactor. In the latter case, which may simulated by perfectly-mixed reactors in series, all species reside in the reactor the same time. 

Z+1 designates the number of states, i.e. Z perfectly mixed reactors in the flow system as well as the tracer collector designated by As shown later, the probabilities Si(0) may be replaced by the initial concentration of the fluid elements in each state, i.e. Cj(0) and S(0) will contain all initial concentrations of the fluid elements. The one-step transition probability matrix is given by Eqs.(2-16) and (2-20) whereas pjk represent the probability that a fluid element at Cj will change into Ck in one step, pjj represent the probability that a fluid element will remain unchanged in concentration within one step. 

Let P be the one-step transition probability matrix, and P" the n-step transition probability matrix. Given that initially all nodes are contending for time slots, i.e., Xo = 0 with probability 1, the unconditional probability distribution of X is represented by the first row of P". That is,... 

Presently Monte Carlo calculations are based on the technique proposed by Metropolis [22] in 1953 which involves selecting the successive configurations in such a way that they build up a Markov chain [23], The one-step transition probabilities pij are defined as the probability that beginning from the i configuration with qj(N), the configuration j with qj,N> is reached in one step. These probabilities are the elements of the one-step probability matrix associated to the Markov chain and they must fulfill the following conditions ... 

The models discrete in space and continuous in time as well as those continuous in space and time, led many times to non-linear differential equations for which an analytical solution is extremely difficult or impossible. In order to solve the equations, simplifications, e.g. linearization of expressions and assumptions must be carried out. However, if this is not sufficient, one must apply numerical solutions. This led the author to a major conclusion that there are many advantages of using Markov chains which are discrete in time and space. The major reason is that physical models can be presented in a unified description via state vector and a one-step transition probability matrix. Additional reasons are detailed in Chapter 1. It will be shown later that this presentation coincides also with the fact that it yields the finite difference equations of the process under consideration on the basis of which the differential equations have been derived. 

Throughout this chapter it has been decided to apply Markov chains which are discrete in time and space. By this approach, reactions can be presented in a unified description via state vector and a one-step transition probability matrix. Consequently, a process is demonstrated solely by the probability of a system to occupy or not to occupy a state. In addition, complicated cases for which analytical solutions are impossible are avoided. 

The above probabilities may be grouped in the matrix given by Eq. 3-17). It should be noted that Eq.(2-18) is not satisfied along each row because the one-step transition probabilities pjk depend on time n. This is known as the non-homogeneous case defined in Eqs.(2-19) and (2-20), due to non-linear rate equations, i.e. Eqs.(3-12). 

By applying Eqs.(3-6) and (3-10), the following one step transition probability matrix is obtained ... 

The following one step transition probability matrix is obtained ... 

It should be emphasized that the matrix representation becomes possible due to the Euler integration of the differential equations, yielding appropriate difference equations. Thus, flow systems incorporating heat and mass transfer processes as well as chennical reactions can easily be treated by Markov chains where the matrix P becomes "automatic" to construct, once gaining enough experience. In addition, flow systems are presented in unified description via state vector and a one-step transition probability matrix. 

The one-step transition probabilities can be obtained from the empirical transition frequencies. All possible transitions from one state to another are summarised in the transition probability matrix P ... 

In Section 5.1 we introduce the stochastic processes. In Section 5.2 we will introduce Markov chains and define some terms associated with them. In Section 5.3 we find the n-step transition probability matrix in terms of one-step transition probability matrix for time invariant Markov chains with a finite state space. Then we investigate when a Markov ehain has a long-run distribution and discover the relationship between the long-run distribution of the Markov chain and the steady state equation. In Section 5.4 we classify the states of a Markov chain with a discrete state space, and find that all states in an irreducible Markov chain are of the same type. In Section 5.5 we investigate sampling from a Markov chain. In Section 5.6 we look at time-reversible Markov chains and discover the detailed balance conditions, which are needed to find a Markov chain with a given steady state distribution. In Section 5.7 we look at Markov chains with a continuous state space to determine the features analogous to those for discrete space Markov chains. 

Suppose the state space consists of all integers —oo < k < oo. When the state space is countably infinite instead of being finite, we cannot represent the one-step transition probabilities in a finite matrix, nor can we represent the occupation probability distribution as a finite vector. However, the equations for the elements of these matrices and vectors corresponding to Equations 5.2, 5.4, 5.7 are still the same except that now the summation goes from k = —oo to oo. Similarly, we can t write the steady state equation in matrix terms, but the equation for the elements of the steady state equation would be similar. 

The one-step transition probabilities for a time-invariant Markov chain with a finite state space can be put in a matrix P, where the pij is the probability of a transition from state i to stated in one-step. This is the conditional probability... 

Maximum number of nodes which can exist in a two-hop set Number of nodes in the two-hop neighbourhood of node x which have successfully acquired a time slot One-step transition probability matrix of a Markov chain n-step transition probability matrix of a Markov chain y) Conditional probability that discrete random variable X takes the value x given that discrete random variable Y takes the value y... 

A useful quantity based on the above concepts, needed for evaluating the probabilities in the one-step transition matrix, is the following one... 

This is called the Chapman-Kolmogorov equation. It follows that the matrix of n-step transition probabilities is the matrix of one-step transition probabilities to the power... 

Let the matrix of one-step transition probabilities for a Markov chain be... 

A visitor, designated as system, wishes to visit the tribes. His transition between the states assumes that the probabilities of remaining in a state or moving to the other states is the same and that the following one-step transition matrix holds ... 

---