16.1 Elements of markov sequences  (Page 10/13)

The convergence process is clear, and the agreement with the error is close to the predicted. We have not determined the factor a , and we have approximated the long run matrix P ₀ with P ¹⁶ . This exhibits a practical criterion for sufficient convergence. If the rows of P ⁿ agree within acceptable precision, then n is sufficiently large. For example, if we consider agreement to four decimal places sufficient, then

shows that $n=10$ is quite sufficient.

Simulation of finite homogeneous markov sequences

In the section, "The Quantile Function" , the quantile function is used with a random number generator to obtain a simple random sample from a given population distribution. In thissection, we adapt that procedure to the problem of simulating a trajectory for a homogeneous Markov sequences with finite state space.

Elements and terminology

1. States and state numbers . We suppose there are m states, usually carrying a numerical value. For purposes of analysis and simulation, we number the states 1 through m . Computation is carried out with state numbers; if desired, these can be translated intothe actual state values after computation is completed.
2. Stages, transitions, period numbers, trajectories and time . We use the term stage and period interchangeably. It is customary to number the periods or stages beginning withzero for the initial stage. The period number is the number of transitions to reach that stage from the initial one. Zero transitions are required to reach the original stage (periodzero), one transition to reach the next (period one), two transitions to reach period two, etc. We call the sequence of states encountered as the system evolves a trajectory or a chain . The terms “sample path” or “realization of the process” are also used in the literature. Now if the periods are of equal time length, the number of transitions is ameasure of the elapsed time since the chain originated. We find it convenient to refer to time in this fashion. At time k the chain has reached the period numbered k . The trajectory is $k+1$ stages long, so time or period number is one less than the number of stages.
3. The transition matrix and the transition distributions . For each state, there is a conditional transition probability distribution for the next state. These arearranged in a transition matrix . The i th row consists of the transition distribution for selecting the next-period state when the current state number is i . The transition matrix P thus has nonnegative elements, with each row summing to one. Such a matrix is known as a stochastic matrix .

The fundamental simulation strategy

1. A fundamental strategy for sampling from a given population distribution is developed in the unit on the Quantile Function. If Q is the quantile function for the population distribution and U is a random variable distributed uniformly on the interval $[0,1]$ , then $X=Q\left(U\right)$ has the desired distribution. To obtain a sample from the uniform distribution usea random number generator. This sample is “transformed” by the quantile function into a sample from the desired distribution.
2. For a homogeneous chain, if we are in state k , we have a distribution for selecting the next state. If we use the quantile function for that distribution anda number produced by a random number generator, we make a selection of the next state based on that distribution. A succession of these choices, with the selectionof the next state made in each case from the distribution for the current state, constitutes a valid simulation of a trajectory.