Chapter 5 Random Processes 5.1 INTRODUCTION In this chapter, we introduce the concept of a random (or stochastic) process. The theory of random processes was first developed in connection with the study of fluctuations and noise in physi- cal systems. A random process is the mathematical model of an empirical process whose development is governed by probability laws, Random processes provides useful models for the studies of such diverse fields as statistical physics, communication and control, time series analysis. population growth, and management sciences, 52 RANDOM PROCESSES 1. Defintion: A random process is a family of rv.’s {X(, 1 € T} defined on a given probability space, indexed by the parameter f, where 1 varies over an index set T. Recall that a random variable is a function defined on the sample space S (Sec. 2.2). Thus, a random process {X(t), 1 T} is really a function of two arguments {X(t, (), te T, C€ S}. For a fixed (=H) Xu. = XC) is a ry. denoted by X(t) as ¢ varies over the sample space S. On the other hand, for a fixed sample point ¢;€ S, X(t, ¢,) = X,() is a single function of time t, called a sample Junction or a realization of the process. The totality of all sample functions is called an ensemble. Of course if both ¢ and ¢ are fixed, X(4,.¢,) is simply a real number. In the following we use the notation X(t) to represent X(t, 0) B. Description of a Random Process: In a random process {X(0), t T}, the index set T is called the parameter sei of the random process. The values assumed by X(t) are called states, and the set of all possible values forms the state space E of the random process. If the index set T of a random process is discrete, then the process is called a discrete-parameter (or discrete-time) process. A discrete-parameter process is also called a random sequence and is denoted by {X,. n= 1, 2,...}. If T is continuous, then we have a continuous- parameter {or continuous-time) process. If the state space E of a random process is discrete, then the process is called a discrete-state process, often referred to as a chain, In this case, the state space £ is often assumed to be {0, 1, 2, ...}. Ifthe state space & is continuous, then we have a continuous-state process, A complex random process X(t) is defined by X() = X40) 45X10 where X,(t) and X,(t) are (real) random processes and j= \/—T. Throughout this book, all random processes are real random processes unless specified otherwise. 53 CHARACTERIZATION OF RANDOM PROCESSES A. Probabilistic Descriptions: Consider a random process X() For a fixed time ty, X(t,) =X, is av. and its cdf Fyoxys 4) is defined as Faby) = PUX(4) <4} (5.1) 161162 RANDOM PROCESSES (CHAP 5 F(x,3 t)) is known as the first-order distribution of X(1). Similarly, given t, and t,, X(t,) = X, and X(t) — Xz represent two rvs. Their joint distribution is known as the second-order distribution of 1X(e) und is given by Plus X25 thy fa) = PEE) S xq, XU) S$ a} (5.2) In general, we define the nth-order distribution of X(i) by EU sy Xu ba oes) = PERE) Sp, MUG) SY (53) IEX(0 is a discrete-time process, then X(t) is specified by a collection of pms Pals ey Xyh ay eee fe) = PERU) = Xe (54) If X(0)is a continuous-time process, then X(t) is specified by a collection of pds: Fuso by = Pa se as 5) Ox + Oy, ‘The complete characterization of X(t) requires knowledge of all the distributions as n+ co. Fortu- nately, often much less is sufficient. B, Mean, Correlation, and Covariance Functions: AAs in the case of rvs, random processes are often described by using statistical averages: The mean of X(i) 1s defined by x(t) = ELX(O) (56) where X(é) is treated as a random variable for a fixed value of 1. In general, y(t) is a function of time, and itis often called the ensemble average of X(t). A measure of dependence among the r.v.'s of X(t) is provided by its autocorrelation function, defined by Ralls 3) = ELXOX(5)) 67) Note that Rult, 9) = Res. 1) 68) and Ratt, ) = FLX] (5.9) ‘The autocovariance functton of X(t) is defined by Kxlt, 8) = CovLX(0), X(s)] = EYLX(9 — wx(OJEX(9) - axl} = Rall, 5) — uta) (5.10) Iv is clear that if the mean of X(:) is zero, then K,(¢, s) = Rxlt, 5). Note that the variance of X(t) is given by oy) = VarlX(0] = {LX(0 ~ axl?) = Kalt, (aD If X(0) is @ complex random process, then its autocorrelation function Ry(t, s) and autocovariance function K,(t, s) are defined, respectively, by Rxlt, 9) = ELX(OX*(5)] (5.12) and Ky(t, ) = E{LX() — wxlICX(9) — Hyls)}*) (43) where * denotes the complex conjugate 54 CLASSIFICATION OF RANDOM PROCESSES If a random process X(t) possesses some special probabilistic structure, we can specify less to characterize X(t) completely. Some simple random processes are characterized completely by only the first- and second-order distributions.CHAP. 5) RANDOM PROCESSES 163 A. Stationary Processes: A random process {X(0), t € T) is said to be stationary or strict-sense stationary if, for all n and for every set of time instants (t, € T,4= 1, 2,..., ms Fly co Mi th th ett) (5.14) for any +. Hence, the distribution of a stationary process will be unaffected by a shift in the time origin, and X(«) and X(¢+t) will have the same distributions for any +. Thus, for the first-order distribution, Fd iy coe Xai Cay ey be) Fx(xs t) = Fylxs t +9) = F(x) (5.15) and Sal5 8) = ful) (5.16) Then x(t) = ELX(0) = 5.17) Varlx(0] = 0? (5.18) where and 0? are contants. Similarly, for the second-order distribution, Fix x3 ty) = Pty ai) 5.19) and Silty X25 ty a) = Salt, X23 a — t) (5.20) Nonstationary processes are characterized by distributions depending on the points ty, t35.++5t4- B. Wide-Sense Stationary Processes: If stationary condition (5.14) of a random process X(t) does not hold for all m but holds for n < k, then we say that the process X(t) is stationary to order k, If X(t) is stationary to order 2, then X(t) is said to be wide-sense stationary (WSS) or weak stationary. If X(t) is a WSS random process, then we have 1. ELX()] = » (constant) (5.21) 2. Relt, s) = ELX(OX(S)] = Ry — ¢|) (5.22) Note that a strict-sense stationary process is also a WSS process, but, in general, the converse is not true. C. Independent Processes: Ina random process X(0), if X(t) for i= 1, 2,..., n are independent r.v.'s, so that for n = 2,3,...5 soos t= [] Fb FrQty oy (5.23) then we call X(t) an independent random process. Thus, a first-order distribution is sufficient to charac- terize an independent random process X(t). D. Processes with Stationary Independent Increments: A random process (X(t), ¢ 2 0) is said to have independent increments if whenever 0 < ty 0, 5 <¢, then the process X(t) is said to have stationary independent increments. Let (X(d), ¢ 2 0} be a random process with stationary independent increments and assume that X(0) = 0. Then (Probs. 5.21 and 5.22) ECX(O] = ast (5.24) where 4 = ECX(I)] and VatlX()] = 047 (5.25) where 0? = Var X(I)} From Eq. (5.24), we see that processes with stationary independent increments are nonstationary. Examples of processes with stationary independent increments ate Poisson processes and Wiener processes, which are discussed in later sections. E. Markov Processes: A random process (X(i), t€ T} issaid to be a Markov process if cat = PERU 1) Spo | Xltq) = %q} (5.26) PUX tn 1) S nv 2) MCC) = Xap Xa) = Say os XG) whenever ty (5.30) Similarly, the time autocorrelation function Ry() of x() is defined as Bale) = (x(x + 9) = im +f xloate + 0) dt 631) A random process is said to be ergodic if it has the property that the time averages of sample functions of the process are equal to the corresponding statistical or ensemble averages. The subject of ergodicity is extremely complicated. However, in most physical applications, it is assumed that stationary processes are ergodic. 5S DISCRETE-PARAMETER MARKOV CHAINS In this section we treat a discrete-parameter Markov chain (X,, n 20} with a discrete state space E = {0, 1, 2, ...}, where this set may be finite or infinite. If X,~ i, then the Markov chain is said to be in state i at time n (or the nth step). A discrete-parameter Markov chain {X,, n 2 0} is characterized by (Eq. (5.27)] PU per JI Xo = toy Xe fay oes Xe == PX pes =H1Ne ) (5.32) where P{x,+, = j|X_= i} are known as one-step transition probabilities. If Pix.) =j1X,= i} is independent of n, then the Markov chain is said to possess stationary transition probabilities ‘and the process is referred to as a homogeneous Markov chain. Otherwise the process is known as a nonhomo- geneous Markov chain. Note that the concepts of a Markov chain's having stationary transition probabilities and being a stationary random process should not be confused. The Markov process, in ‘general, is not stationary. We shall consider only homogeneous Markov chains in this section. ‘A. Transition Probability Matrix: Let {X,, 2.0} be a homogeneous Markov chain with a discrete infinite state space E = {0, 1, |. Then Py= PIX. =jIX,= i} 420,720 (533) regardless of the value of n. A transition probability matrix of {X,,n 2 0} is defined by Poo Por Por Petna|P2 Pe Pe Pro Pax Paz ** where the elements satisfy py20 Spat 12012. (534 ino166 RANDOM PROCESSES [CHAP 5 In the case where the state space E is finite and equal to {1,2,...,m}, P ism x m dimensional; that is, Pur Paz °° Pim P=toj=|Pe Pm mi Pmt Pa, where p20 Spy i=12, (535) A square matrix whose elements satisfy Eq. (5.34) or (5.35) is called a Markov matrix or stochastic matrix. B. Higher-Order Transition Probabilities —Chapman-Kolmogorov Equation: Tractability of Markov chain models is based on the fact that the probability distribution of {X,, 2 0} can be computed by matrix manipulations. Let P = [p,j} be the transition probability matrix of a Markov chain (X,, 2 0). Matrix powers of P are defined by P= PP with the (i, {jth element given by pi Zeaps Note that when the state space F is infinite, the series above converges, since by Eq. (5.34), Ypary 0} are defined by P(X, = J|Xo =i) ‘Then we can show that (Prob. 5.70) Py = PK, = JX =) 637) ‘We compute p,;" by taking matrix powers. ‘The matrix identity Prem PP nm20 when written in terms of elements py = Spa's) (5.38)CHAP. 5] RANDOM PROCESSES 167 is known as the Chapman-Kolmogorov equation. It expresses the fact that a transition from i to j in n+ m steps can be achieved by moving from i 10 an intermediate k in n steps (with probability pa), and then proceeding to j from k in m steps (with probability p,,'™). Furthermore, the events “go from i to k in n steps” and “go from k to j in m steps” are independent. Hence the probability of the transition from é to j in n + m steps via i, k,) is py”r,,"". Finally, the probability of the transition from 110 jis obtained by summing over the intermediate state k. C. The Probability Distribution of (X,, 2 0}: Let p(n) = P(X, =f) and Pon) = pot) palm) palm) =“) where Lain = Then p(0) = P(X = i) are the initial-staze probabilities, PO) = [rof0) ps(0) p2(0) ---] is called the initial-state probability vector, and p(n) is called the state probability vector after n tran- sitions or the probability distribution of X,. Now it can be shown that (Prob. 5.29) Pin) = ploy" (539) which indicates that the probability distribution of a homogeneous Markov chain is completely determined by the one-step transition probability matrix P and the initial-state probability vector 10). D. Classification of States: 1. Accessible States: State j is said to be accessible from state i if for some n > 0, p,j" > 0, and we write i». Two states i and j accessible to cach other are said to communicare, and we write i++). Ifall states commu- nicate with each other, then we say that the Markov chain is irreducible. 2, Recurrent States: Let 7, be the time (or the number of steps) of the first visit to state j after time zero, unless state j is never visited, in which case we set T; = 00. Then 7; is a discrete rv. taking values in {1, 2,..., 20). Let Sif = PT, = m|Xq =) = Py = js Xy i= bom = 11K =I) (540) and f° = 0 since 7; 2 1. Then GJ = PUT = 1X9 =) = PX, = j1Xo =) = Dy (41) and Gi" = & aS m= 2,3, (5.42) ‘The probability of visiting j in finite time, starting from i is given by (5.43) Ga= XSi" = PAT; < 1X Now state jis said to be recurrent if Sy = PUT < 1X0 =) (5.44)168, RANDOM PROCESSES [CHAP 5 ‘That is, starting from j, the probability of eventual return to j is one. A recurrent state j is said to be positive recurrent if ET, |Xo =< 0 (5.43) and state is said to be null recurrent if AT |X9 =f) = 0 (5.46) Note that ET [Xo =) = Ym” (5.47) 3. Transient States: State j is said to be transient (or nonrecurrent) if Sy = P< eIXo = Nel (5.48) ive probability of never returning to state j. 4. Periodic and Apeviodic States: We define the period of state j to be aj) = ged{n > 1: py” > 0} where ged stands for greatest common divisor. If d(,} > 1, then state j is called periodic with period d(;). If d(j) = 1, then state j is called aperiodic. Note that whenever p,, > 0, jis aperiodic. 5S. Absorbing State In this case there is p State jis said to be an absorbing state if pj, = 1; that is, once state jis reached, it is never left. E. Absorption Probabil Consider a Markov chain X(n) = (X,, n> 0} with finite state space E = {1, 2,..., N} and tran- sition probability matrix P. Let A = {1,..., m} be the set of absorbing states and B= {m +1, ...,. N} be a set of nonabsorbing states. Then the transition probability matrix P can be expressed as 1 oO 0 oO 0 o 1 ° ° ° p=| 0 1 ° ° -[h al (5.494) RQ Pata Patiim Patieaet “2 Poeun or where 1 is an m x m identity matrix, 0 is an m x (N — m) zero matrix, and Preis Pot i. Prot imet Pmt iw R= Q= : (5.496) Prt Pram Primes Prax ‘Note that the elements of R are the one-step transition probabilities from nonabsorbing to absorbing states, and the elements of Q are the one-step transition probabilities among the nonabsorbing states,CHAP. 5] RANDOM PROCESSES 169 Leu mj] where gj = P(X4 = HE ADXe = KE B)) It is seen that U is an (NV ~ m) x m matrix and its elements are the absorption probabilities for the various absorbing states. Then it can be shown that (Prob. 5.40) U=I-Q'R=OR (5.50) The matrix @ = (1 —Q)~! is known as the fundamental matrix of the Markov chain X(n). Let T denote the total time units (or steps) to absorption from state k. Let T=. Tera 1° Ted Then it can be shown that (Prob. 5.74) ET) = ¥ oy kemtlyN (5.51) where dy; is the (x, th element of the fundamental matrix ©, F. Stationary Distributions: Let P be the transition probability matrix of a homogeneous Markov chain {X,, n > 0}. I there exists a probability vector p such that oP (5.52) then p is called a stationary distribution for the Markov chain. Equation (5.52) indicates that a sta- tionary distribution p is a (left) eigenvector of P with eigenvalue 1. Note that any nonzero multiple of p is also an eigenvector of P. But the stationary distribution p is fixed by being a probability vector; that is, its components sum to unity. G. Limiting Distributions: ‘A Markov chain is called regular if there is a finite positive integer m such that after m time-steps, every state has a nonzero chance of being occupied, no matter what the initial state. Let A >O denote that every element a, of A satisfies the condition a, > 0. Then, for a regular Markov chain with transition probability matrix P, there exists an m > 0 such that P® > O. For a regular homoge- neous Markov chain we have the following theorem: THEOREM 5.5.1 Let {X,, 20} be a regular homogeneous finite-state Markov chain with transition matrix P. Then lim Pt = P (5.53) where P is a matrix whose rows are identical and equal to the stationary distribution p for the Markov chain defined by Eq. (5.52) 5.6 POISSON PROCESSES A. Definitions: Let 1 represent a time variable. Suppose an experiment begins at ¢ = 0. Events of a particular kind occur randomly, the first at T,, the second at T;, and so on. The r.v. 7; denotes the time at which the ith event occurs, and the values 1, of 7;(i = 1, 2, ..) are called points of occurrence (Fig, 5-1)170 RANDOM PROCESSES (CHAP 5 be, 1, tet ——7,— 1 L 1 ran 1 1 = ° 4 6G Ne 4 ' Fig. $1 Let Zy=T-Thr (554) and Ty =0. Then Z, denotes the time between the (n— t)st and the nth events (Fig. 5-1). The sequence of ordered 1-¥’s (Z,, m2 1} is sometimes called an interarrival process. If all rvs Z, are independent and identically distributed, then {Z,, n> 1) is called a renewal process or a recurrent process. From Eq. (5.54), we sce that TaZ4+ Zt Z, lenotes the time from the beginning until the occurrence of the nth event. Thus, {7,, 2 = 0} es called an arrival process. B. Counting Processes: A random process (X(t), t 2 0} is said to be a counting process if X(t) represents the total number of “events” that have occurred in the interval (0, #). From its definition, we see that for a counting process, X(t) must satisfy the following con 1 2 3. 4. X() 2 Oand X(0) = 0. X(t) is integer valued. X(5) s XWifs . c Fig. 5:2 A sample function of « counting process. Poisson Processes: One of the most important types of counting processes is the Poisson process (or Poisson counting process), which is defined as followsCHAP. 5} RANDOM PROCESSES m DEFINITION 5.6.1, A counting process X(t) is said to be a Poisson process with rate (or intensity) A(>0) if 1. XQ) =0. 2, X(t) has independent increments. 3. The number of events in any interval of length t is Poisson distributed with mean Af; that is, for all s,¢> 0, cay PLX(t +5) — X(s) =n) =e ™ n=0,1,2,... (5.55) It follows from condition 3 of Def. 5.6.1 that a Poisson process has stationary increments and that ELX(t)] = dt (5.56) ‘Then by Eq. (2.43) (Sec. 2.7), we have VarfX(t)] = ae (557) Thus, the expected number of events in the unit interval (0, 1), or any other interval of unit length, is just d (hence the name of the rate or intensity). An alternative definition of a Poisson process is given as follows: DEFINITION 5.6.2 A counting process X(t) is said to be a Poisson process with rate (or intensity) A(> 0) if 1, X(0) =0. 2 X(t) has independent and stationary increments. 3. PEX( + 40) — XQ) = 1] = 2 Ar + ofA) 4. PLX(t-+ At) — X(0) 2 2] = of) where o(At) is a function of At which goes to zero faster than does At; that is, (Au) li mo St =0 (5.58) Note: Since addition or multiplication by a scalar does not change the property of approaching zero, even when divided by At, o(A1) satisfies useful identities such as o(At) + (41) = oft) and oft) = O(a) for alt constant a It can be shown that Def. 5.6.1 and Def. 5.6.2 are equivalent (Prob. 5.49). Note that from condi- tions 3 and 4 of Det. 5.6.2, we have (Prob. 5.50) PLX(t + At) — X(t) = 0] = 1-2 dr + oft) (559) Equation (5.59) states that the probability that no event occurs in any short interval approaches unity as the duration of the interval approaches zero. It can be shown that in the Poisson process, the intervals between successive events are independent and identically distributed exponential rx. (Prob. 5.53). Thus, we also identify the Poisson process as a renewal process with exponentially distributed intervals. The autocorrelation function Ry(t, s) and the autocovatiance function K,(t, 8) of a Poisson process X(t) with rate 2 are given by (Prob. 5.52) Raft, 5) = A mint, 5) + Hts (5.60) Kat, s) = A minie, 5) (561)172 RANDOM PROCESSES, [CHAP 5 5.7 WIENER PROCESSES Another example of random processes with independent stationary increments is a Wiener process. DEFINITION 5.7.1 A random process {X(t),t 2 0} is called a Wiener process if L._X(t) has stationary independent increments, 2, The increment X(t) — X(s) (¢ > 3) is normally distributed. 3. ELX(] =O. 4 X()=0. The Wiener process is also known as the Brownian motion process, since it originates as a model for Brownian motion, the motion of particles suspended in a fluid. From Def, 5.7.1, we can verify that a Wiener process is a normal process (Prob. 5.61) and ELX()] = 0 (5.62) VarlX(0)] = ot (5.63) where 0 is a parameter of the Wiener process which must be determined from observations. When a = 1, X(i)is called a standard Wiener (or standard Brownian motion) process. The autocorrelation function Ry(t, s) and the autocovariance function Ky(t,s) of a Wiener process X(t) are given by (see Prob. 5.23) Rut, 9) = Kylt, 3) =o min(t,s) 5,20 (5.64) DEFINITION 5.7.2 A random process {X(t ¢ 2 0} is called a Wiener process with drift coefficient w if L._X(t) has stationary independent increments. 2. X()is normally distributed with mean xt 3. X()=0. From condition 2, the pdf of a standard Wiener process with drift coefficient y is given by (5.65) Solved Problems RANDOM PROCESSES SL. Let X,, Xz, ... be independent Bernoulli rv.’s (Sec. 2.7A) with P(X, = 1) = p and P(X, = 0) = = 1~p for all n. The collection of rv.'s {X,, m > 1} is a random process, and it is called a Bernoulli process. (a) Describe the Bernoulli process. (8) Construct a typical sample sequence of the Bernoulli process. (a) The Bernoulli process {X,, m2 1) is a discrete-parameter, discrete-state process, The state space is E = {0, l}.and the index set is T = (1, 2,...}