Discrete state-space

The easiest nontrivial example is a time-discrete Markov chain on a discrete state space. For example, take the chain with state space S — 1, 2,3,4 and one-step transition probabilities as illustrated in Fig. 1. 

Discrete-time Markov chains are discrete-time stochastic processes with a discrete state space. Let the state of the random variable at time t be represented by y, then the stochastic process can be represented by (yi, y2, y, ...). 

For Markovian networks (with a discrete state space), there is a convenient definition of stabUity a stable network is one that is a positive recurrent Markov chain. This definition may be extended to more general networks, but doing this formally would require a mathematical digression. For a detailed discussion of stability, see Meyn and Tweedie (1993). 

The state space S can be a finite, countably infinite, or uncountable set. This article addresses dynamic programs with finite or countably infinite, also called discrete, state spaces S. 

M. A. Novotny, A tutorial on advanced dynamic Monte Carlo methods for systems with discrete state spaces, Annual Reviews of Computational Physics, vol. 9, pp. 153-210, 2001. 

The size of the chemical system is small. In this case we cannot apply continuous state models even as an approximation. (For the case of a finite particle number, a precise continuous model cannot be defined, since in the strict sense the notion of concentration can be used only for infinite systems.) Discrete state space, but deterministic, models are also out of question, since fluctuations cannot be neglected even in the zeroth approximation , because they are not superimposed upon the phenomenon, but they represent the phenomenon itself. 

Discrete state space stochastic models of chemical reactions can be identified with the Markovian jump process. In this case the temporal evolution can be described by the master equation ... 

The state-space (or site space according to the terminology soon to be introduced) can be chosen either continuous (A <= U ) or discrete (A c= Z ). To emphasise the existence of elementary particles of a population (as, for example, sometimes in reaction kinetics and in population dynamics), a discrete state-space formalism can be used. Continuum mechanics is an illustration for preferring a continuous state-space, since the mass points can arbitrarily occupy space. 

An (A, (p) dynamic system is deterministic if knowing the state of the system at one time means that the system is uniquely specified for all r 6 T. In many cases, the state of a system can be assigned to a set of values with a certain probability distribution, therefore the future behaviour of the system can be determined stochastically. Discrete time, discrete state-space (first order) Markov processes (i.e. Markov chains) are defined by the formula... 

The terminology is nonstandard, and in physical literature the Kramers-Mpyal expansion is given as a (nonsystematic) procedure to approximate discrete state-space processes by continuous processes. The point that we want to emphasise here is the clear fact that, even in the case of a continuous state-space, the process itself can be noncontinuous, when the Lindeberg condition is not fulfilled. The functions for the higher coefficients do not necessarily have to vanish. 

These kinds of equations have to be specified to obtain continuous time discrete state space models of chemical reactions. 

Equation (5.27) is an ordinary difierential equation in function space. Giving an appropriate interpretation of the state-space it can describe spatiotemporal phenomena . Thinking of chemical applications we might set the state-space as the unification of the real three-dimensional space and the w-dimensional component space. However, the formulation of stochastic models of chemical reactions accompanied by difiusion is not easy, and practically all of the applications treat both the component space and the real space by discrete methods. Although it is quite natural to apply the notion of discrete state-space for chemical reactions, at least from the mesoscopic point of view, it might be better if diflTusion were described in terms of continuous models. In Chapter 6 we return to this question. 

A great amount of stochastic physics investigates the approximation of jump processes by diffusion processes, i.e. of the master equation by a Fokker-Planck equation, since the latter is easier to solve. The rationale behind this procedure is the fact that the usual deterministic (CCD) and stochastic (CDS) models differ from each other in two aspects. The CDS model offers a stochastic description with a discrete state space. In most applications, where the number of particles is large and may approach Avogadro s number, the discreteness should be of minor importance. Since the CCD model adopts a continuous state-space, it is quite natural to adopt CCS model as an approximation for fluctuations. 

One of the most extensively discussed topics of the theory of stochastic physics is whether the evolution equations of the discrete state-space stochastic processes, i.e. the master equations of the jump processes, can be approximated asymptotically by Fokker-Planck equations when the volume of the system increases. We certainly do not want to deal with the details of this problem, since the literature is comprehensive. Many opinions about this question have been expressed in a discussion (published in Nicolis et ai, 1984). However, some comments have to be made. 

According to the basic assumption of this model, not only is the component space discrete, but the real space is also subdivided into mesoscopic cells. The meaning of the term mesoscopic here is that the size of cells is larger than the size of the constituent molecules, but much smaller than the characteristic scale of the total system. While from a heuristic point of view the discrete state-space description of chemical reactions seems to be natural, the discretisation of the space can be qualified as a more or less forced technical procedure. 

We consider the discrete state space Q s Q ,np,..., Qvn-2 of tho rotational isomeric configurations of a chain of N bonds having v states accessible to each bond. The stochastic process of v xv " transitions between those configurations is the object of study. In the following, the terms states and system will be used interchangeably for configurations and chain , respectively. 

The spectral analysis is performed on the free vibrations associated with the discretized state-space equations (7), which for convenience are written in the generic form... 

A linear, discrete, state-space model of a process is usually described by the following equations. 

We have invoked so far Markov processes in discrete state space as the natural model of fluctuations, since the latter are the consequence of the discrete nature of the microscopic processes underlying the macroscopic evolution laws. 

The algorithm was developed in connection with issues involving a large state space and with the existence of several local minima of some loss function. The algorithm does not require further assumptions on the loss function as continuity, differentiability and convexity and can also be used in the case of a discrete state space. The state space is obviously discrete and consequently the identification of the minimum of any loss function is extremely difficult as even a small change in the current combination of interrupted links can have a dramatic impact on the value of the loss function. 

Those with eontinuous parameter and discrete state spaces (i.e., continuous-time Markov ehains, or simply Markov proeesses)... 

By this theorem we see that the discretized state space form and the discretized linear DAE share the same (dynamic) eigenvalues. 

The analysis so far was related to linear systems with constant system matrices. It suggests that the dynamics of discretized systems is entirely determined by the discretized state space form (see middle part of Tab. 5.3). Having the linear test equation in mind, one might think of stiff DAEs as those systems having a stiff state space form. 

This can be viewed as a characterization of the solution of the discretized state space form in terms of the original variables. 

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. 

The states of a Markov chain with a discrete state space can be classified using either the first return probabilities /] or the n-step transition probabilities... 

In order to obtain a discrete state-space equation for computation, the fimctions in Eq. 4 is linearized for each time step t e [Mf, (k + l)Af) as follows ... 

Reverting to a discrete state space, the ensemble average of M is written as... 

---