Introduction

Many natural and artificial phenomena are endowed with non-deterministic dynamic behavior. Stochastic processes are utilized to model such dynamic phenomena. There are a number of applications, e.g. in physics [1,2], where the stochastic model can be in only one of two states, modeled by the so-called dichotomous stochastic process (e.g., dichotomous Markov noise). In particular, the notion of a unit random process {X(t), t 0}, i.e., a random process whose state space consists of two values, {−1, 1}, arises naturally in many applications e.g. bit transmission in communications systems, or detection theory. In the latter case, some random process, {Y (t), t 0}, is provided as input to a threshold detector, where the output X(t) is the sign of Y (t), i.e. X(t) = sign(Y (t)). Thus {X(t), t 0} is a unit process and can be shown to be Markovian under some conditions on Y (t). More generally, quantization of a general random process leads to a finite-state random process, which is often Markovian, so the study of more general finite-state processes is also of interest.

The characterization of the autocorrelation function, R(t, t + τ ) = E[X(t)X(t + τ )], τ, t 0, of a unit process {X(t), t 0}, is considered an important problem [3]. Several interesting properties of such autocorrelation functions are studied in [4,5].

Wide sense stationary (or even strictly stationary) random processes naturally arise as stochastic models in a variety of applications. They also arise in time series models (AR, ARMA processes) of natural and artificial phenomena. The autocorrelation function of a wide sense stationary process does not depend on t, that is,

R(τ ) := R(t, t + τ ) = E[X(0)X(τ )].

In many interesting models, the autocorrelation function, R(τ ) is integrable and hence the power spectral density (the Fourier transform of R(τ )) exists.

With this in mind, we are motivated to study the function space of finite state Markov processes. Masry [5] has studied the functional space properties of stationary unit random processes. However, the study of the integrability of R(τ ) was not undertaken. To the best of our knowledge, the L p -norm of R(τ ) for finite state Continuous Time Markov Chains (CTMCs) has not been investigated. In this paper, we determine conditions under which the autocorrelation function is not integrable, and by extension conditions under which the L p -norm of R(τ ) approaches zero as p → ∞.

To put our work into context, there is related work in three directions: the characterization of autocorrelation functions of random processes, the characterization of point processes, and the use of autocorrelation properties in the analysis of stochastic models, in particular the analysis of queues. For the characterization of autocorrelation functions, we point the reader to work in time series analysis [6,7,8] and in telecommunications [9]. Point process characterization has been studied in [10,11,12]. Properties of autocorrelation functions have been employed to determine appropriate simulation strategies for queues [13] and is a feature of modelling arrival traffic to queues, using Markovian Arrival Processes, see [14], for example. This paper is organized as follows. In Section 2, the autocorrelation function of a unit CTMC is computed and the structure of the function space is studied. In Section 3, the autocorrelation function of a finite state space CTMC is computed and the finiteness of its L p norm is discussed. It is shown that under some conditions, the autocorrelation function is not integrable. In Section 4, various interesting inferences are made for point processes. Finally, the paper concludes in Section 5.

Auto-Correlation Function of Homogeneous Unit CTMC: Integrability

In this section we consider a homogeneous Continuous Time Markov Chain (CTMC) {X(t), t 0} with the state space J = {−1, 1} and generator matrix

Q = −α α β −β , α, β > 0.

We assume that the resulting stochastic process is wide sense stationary (and not necessarily strictly stationary). Although results on R(τ ) can be found in the literature [1], it is instructive to show the evaluation of R(τ ) with the help of spectral representation.

Since {X(t), t 0} is a unit random process,

R(τ ) = P {X(0) = X(τ )} − P {X(0) = X(τ )} = 2P {X(0) = X(τ )} − 1. (1)

It remains to compute P {X(0) = X(τ )}. Note that

P {X(τ ) = X(0)} = j∈J P (X(τ ) = j|X(0) = j)P (X(0) = j).(2)

The conditional probabilities in (2) are computed using the transient probability distribution π(τ ) of X(τ ) at time τ 0, whereas the values P (X(0) = j), j ∈ J, are the components of the initial probability distribution, π(0). For a homogeneous CTMC with finite state space,

π(τ ) = π(0)e Qτ ,(3)

where e Qτ = ∞ i=0 Q i τ i /i! is the matrix exponential (see e.g. [15]). Using the Jordan canonical form [16], e Qτ is computed below.

Since Q is a rank one matrix, the eigenvalues are λ 1 = −(α + β), λ 2 = 0. Denote the corresponding right eigenvectors by {ḡ 1 , ḡ2 } (column vectors) as the solutions of

Qḡ i = λ i ḡi , i = 1, 2.(4)

Let the left eigenvectors (row vectors) { f1 , f2 } be the solutions of

fi Q = λ i fi , i = 1, 2. (5)

Compose columnwise the matrix G of right eigenvectors, and let F contain the left eigenvectors as rows. Then since Q is diagonalizable,

Q = G −(α + β) 0 0 0 F,

where also we have GF = I. Hence it follows that e Qτ = e −(α+β)τ ḡ1 f1 + ḡ2 f2 .

Since ḡ1 is unique up to multiplicative constant, it follows from (4) that ḡ1 = 1

−β α .

At the same time, since λ 2 = 0, (4) is the condition for Q to be a generator matrix, that is, ḡ2 = 1, where 1 is the (column) vector of ones. The left eigenvectors are obtained after some algebra from F G = I as follows:

f1 = α α+β − α α+β , f2 = β α+β α α+β .

It is interesting to note that since λ 2 = 0, it follows from (5) that the second left eigenvector, f2 , is indeed the steady-state probability vector π = π(∞) of the process {X(t), t 0}, that is, the stochastic vector solving πQ = 0, i.e.

π = f2 = β α + β α α + β .(7)

Thus, it follows from ( 6) that

e Qτ = Π − Q e −(α+β)τ α + β ,(8)

where

Π = 1π(9)

is the matrix that contains the steady-state vector π in its rows. Interestingly, ergodicity is observed from (8) in the limit,

Π = lim τ →∞ e Qτ .

Noting from (9) that π(0)Π = π, from (3) and ( 8) we have

π(τ ) = π − π(0)Q e −(α+β)τ α + β .(10)

Equation ( 10) demonstrates the exponential speed of convergence of π(τ ) to equilibrium π, given in (7), as τ → ∞. Finally, using (10) in (2), we obtain

P {X(τ ) = X(0)} = π(0)π T − e −(α+β)τ α + β π(0)q,

where q is the negative (column) vector of diagonal elements of Q. Recalling (1), denoting c = 2π(0)π T − 1 and d = 2 α+β π(0)q, an explicit expression for R(τ ) is in turn

R(τ ) = c − de −(α+β)τ .(11)

It remains to note that since q is negative componentwise, d is also negative, and thus R(τ ) c, while R(0) = 1. It is rather straighforward to check that in fact

c = 2π(0)π T − 1 = EX(0)EX,(12)

where EX = π[−1 1] T is the steady-state mean value of the process. Thus, the ergodicity result follows from (11):

lim τ →∞ R(τ ) = EX(0)EX. (13)

We now turn to some interesting special cases.

Equilibrium case: assume π(0) = π. In this case π(τ ) = π, and the coefficients in (11) are

c = 2ππ T − 1 = α − β α + β 2 , d = − 4αβ (α + β) 2 ,

which allows us to write

R(τ ) = α − β α + β 2 + 4αβ (α + β) 2 e −(α+β)τ .(14)

It can be seen from ( 14) that R(0) = 1 and then the autocorrelation is monotonically non-increasing until finally R(∞) = c. As expected from (12), in this case c = (EX(0)) 2 . Further, in the symmetric case α = β, from ( 14) we have

R(τ ) = e −2ατ .(15)

Uniform initial probability: Let now π(0) = [1/2 1/2]. In such a case, in (11), the constant c = 0 and d = 1, thus R(τ ) = e −(α+β)τ , which again gives (15) if α = β.

We conclude the section with a lemma that presents one possible characterization of the function space of autocorrelation functions of a unit CTMC.

Lemma 1. Consider a unit CTMC {X(t), t 0} with transition matrix Q and initial probability vector π(0) = [1/2 1/2]. If α = β, then the autocorrelation function, R(τ ), is not in L p [R(τ )] for any p 1 (the L p norm of the autocorrelation function is infinite). However, as p tends to ∞, the L p -norm of the autocorrelation function, R(τ ), approaches a finite constant. Further the L ∞norm is equal to one.

Proof. If α = β and π(0) = [1/2 1/2], then it follows from (12) that |c| ∈ (0, 1). Since R(τ ) c and R(τ

) → c, τ → ∞, then ∞ 0 |R(τ )| p dτ is infinite, that is, R(τ ) is not in L p (R) for any p 1. However, since |c| < 1, it follows that |c| p → 0 if p → ∞.

Hence the L p -norm of the autocorrelation function, R(τ ), approaches a finite constant. ♦

In the following discussion, we generalize the above results to CTMCs with arbitrary state space. It is shown that the existence of an equilibrium probability distribution ensures that the expression for the autocorrelation function has a constant part that, under suitable conditions, is not zero.

Auto-Correlation Function of Homogeneous Finite State Space CTMC

We now prove that for any finite state space CTMC, the autocorrelation function is not integrable and in fact the L p -norm of the autocorrelation function, R(τ ), is infinite for any p 1. Let the state space of the CTMC {X(t), t 0} be J = {C 1 , . . . , C N }. Keeping the notation from Section 2, denote by C the diagonal matrix with vector [C 1 , . . . , C N ] as the main diagonal. Then, similarly to (2),

R(τ ) = N i=1 N j=1 C i C j P {X(0) = i, X(τ ) = j} = π(0)Ce Qτ C1.(16)

But, we have that

e Qτ = N k=1 e λ k τ E k ,

where E k is the residue matrix such that E k = fk ḡk with fk being the right eigenvector of Q and ḡk being the left eigenvector of Q corresponding to the eigenvalue λ k , defined similarly to (4) and ( 5), respectively. Let

|λ 1 | |λ 2 | • • • |λ N | = 0 (

the latter equality holds since Q is the generator matrix). Then, by definition of the eigenvectors, it follows that ḡN = π while fN = 1, where π is the steady-state probability vector corresponding to Q. Thus, it follows from ( 16) that

R(τ ) = π(0)C N −1 k=1 e λ k τ E k C1 + π(0)C1πC1,(17)

where, recall, E N = fN ḡN = 1π. Finally, noting that π(0)C1 = EX(0) and πC1 = EX, where X is the steady-state r.v. distributed as π, we rewrite (17) as

R(τ ) = f (τ ) + EX(0)EX,(18)

which is consistent with (12). Note that c = EX(0)EX is zero if and only if either EX(0) or EX is zero (or both). Note also that if π(0) = π, then c = (EX) 2 . Finally, we see from (18) that lim τ →∞ R(τ ) = EX(0)EX, which corresponds to (13). This result agrees with the fact that asymptotically the initial random variable X(0) and the equilibrium random variable X(∞) are independent. In fact, one may note that f (τ ) is indeed the autocovariance function of {X(t), t 0}. Now, f (τ ) is a sum of decaying exponentials. It can be easily verified that f (τ ) is integrable. More generally, f (τ ) corresponds to a function which is in L p (R) for p 1. But, when c is non-zero, then R(τ ) is not in L p (R) for any p 1. If c = 0, then |R(τ )| p dτ is infinite for every p 1. Further, if |c| < 1, then (R(τ )) p dτ approaches zero as p → ∞.

Discussion

From (15), we see that R(τ ) can be normalized to correspond with a Laplace density. In turn, the fact that this is a Laplace density has the interpretation that it corresponds to the density of the difference between two independent random variables with identical exponential distributions. Thus, from the point of view of the autocorrelation function, a unit CTMC corresponds to a Laplace density.

Now we discuss the speed of convergence in (18). It follows from ( 18) that the speed is governed by the second smallest eigenvalue λ N −1 , which is consistent with more general results on Markov chains, e.g. [17,18].

It is well known that the interarrival times of a Poisson process are exponentially distributed random variables. Also, the sojourn times in every state of a finite state CTMC are exponentially distributed random variables. This observation has been explored in [19], for example, to establish that when successive visits to a state of a CTMC are stitched together, a Poisson process naturally results. Hence, an arbitrary finite state CTMC can be viewed as a superposition of point processes. From a practical viewpoint, the superposition of point processes naturally arises in applications, such as packet streams in packet multiplexers. Such packet streams have been modelled in [20], for example. Several versatile point processes have also been studied in [21,22], amongst others. Such Markovian point processes are actively utilized in queueing theoretic applications.

One potential application of these results is characterizing how phase transitions at high levels of a Quasi-Birth-Death (QBD) process are correlated, in particular how the the autocorrelation of these phase transitions decay. Consider a QBD process {[Z(t), X(t)], t 0}, which is a two-dimensional Markov process, skip-free (ladder type) on the first component govered by generator matrix

        

A 0,0 A 0,1 0 0 . . . A 1,0 A (1) A (0) 0 . . . 0 A (2) A (1) A (0) . . . 0 0 A (2) A (1) . . . Let the state space of the second component X(t) be the finite set J. Then, at the high levels, the (projected) transitions of the component X(t) are governed by matrix A = A (0) + A (1) + A (2) which itself is a generator matrix. Hence, considering a Markov process {X(t), t 0} governed by the matrix A, we may observe the exponential speed of decay of the autocorrelation R(τ ), which is defined by the second smallest eigenvalue of A.

Conclusion

We have computed the autocorrelation function of a unit CTMC and the conditions for integrability (more generally finiteness of the L p -norm) were established. More generally, the function space structure of arbitrary finite state space CTMC was explored. Interesting inferences related to point processes (in a superposition point process) were made based on their relationship to finite state space Markov chains.