Stochastic Processes I

Lecture 5 : Stochastic Processes I 1 Stochastic process A stochastic process is a collection of random variables indexed by time. An alternate view is that it is a probability distribution over a space of paths; this path often describes the evolution of some random value, or system, over time. In a deterministic process, there is a fixed trajectory (path) that the process follows, but in a stochastic process, we do not know apriori which path we will be given. One should not regard this as having no information of the path since the information on the path is given by the probability distribution. For example, if the probability distribution is given as one path having probability one, then this is equivalent to having a deterministic process. Also, it is often interpreted that the process evolves over time. However, from the formal mathematical point of view, a better picture to have in mind is that we have some underlying (unknown) path, and are observing only the initial segment of this path. For example, the function f : R≥0 → R given by f (t) = t is a deterministic process, but a ‘random function’ f : R≥0 → R given by f (t) = t with probability 1/2 and f (t) = −t with probability 1/2 is a stochastic process. This is a rather degernerate example and we will later see more examples of stochastic processes. We are still dealing with a single basic experiment that involves outcomes goverened by a probability law. However, the newly introduced time variable allows us to ask many new interesting questions. We emphasize on the following topics: (a) We tend to focus on the dependencies in the sequence of values generated by the process. For example, how do future prices of a stock depend on past values? (b) We are interested in long-term averages involving the entire sequence of generated values. For example, what is the fraction of time that a machine is idle? 1 Lecture 5 (c) We are interested in boundary events. For example, what is the probability that within a given hour all circuits of some telephone system become simultaneously busy? A stochastic process has discrete-time if the time variable takes positive integer values, and continuous-time if the time variable takes postivie real values. We start by studying discrete time stochastic processes. These processes can be expressed explicitly, and thus are more ‘tangible’, or ‘easy to visualize’. Later we address continuous time processes. 2 Simple random walk Let Y1 , Y2 , · · · be i.i.d. random variables such that Yi = ±1 with equal probability. Let X0 = 0 and Xk = Y1 + · · · + Yk , for all k ≥ 1. This gives a probability distribution over the sequences {X0 , X1 , · · · , }, and thus defines a discrete time stochastic process. This process is known as the one-dimensional simple random walk, which we conveniently refer to as random walk from now on. By the central limit theorem, we know that for large enough n, the distribution of √1n Xn converges to the normal distribution with mean 0 and variance 1. This already tells us some information about the random walk. We state some further properties of the random walk. Proposition 2.1. (i) E[Xk ] = 0 for all k. (ii) (Independent increment) For all 0 = k0 ≤ k1 ≤ · · · ≤ kr , the random variables Xki+1 − Xki for 0 ≤ i ≤ r − 1 are mutually independent. (iii) (Stationary) For all h ≥ 1 and k ≥ 0, the distribution of Xk+h − Xk is the same as the distribution of Xh . Proof. The proofs are straightforward and are left as an exercise. Note that these properties hold as long as the increments Yi are identical and independent and have mean 0. Example 2.2. (i) Suppose that a gambler plays the following game. At each turn the dealer throws an un-biased coin, and if the outcome is head the gambler wins $1, while if it is head she loses $1. If each coin toss is independent, then the balance of the gambler has the distribution of the simple random walk. (ii) Random walk can also be used as a (rather inaccurate) model of stock price. 2 Lecture 5 For two positive integers A and B, what is the probability that the random walk reaches A before it reaches −B? Let τ be the first time at which the random walk reaches either A or −B. Then Xτ = A or −B. Define f (k) = P(Xτ = A | X0 = k), and note that our goal is to compute f (0). The recursive formula f (k) = 1 1 2 f (k + 1) + 2 f (k − 1) follows from considering the outcome of the first cointoss. We also have the boundary conditions f (A) = 1, f (−B) = 0. If we let f (−B + 1) = α, then it follows that f (−B + r) = αr for all r ≤ A + B. 1 Therefore, α = A+B , and it follows that f (0) = 3 B . A+B Markov Chain One important property of the simple random walk is that the effect of the past on the future is summarized only by the current state, rather than the whole history. In other words, the distribution of Xk+1 depended only on the value of Xk , not on the whole set of values of X0 , X1 , · · · , Xk . A stochastic process with such property is called a Markov chain. More formally, let X0 , X1 , · · · be a discrete-time stochastic process where each Xi takes value in some discrete set S (note that this is not the case in the simple random walk). The set S is called the state space. We say that the stochastic process has the Markov property if P(Xn+1 = i | Xn , Xn−1 , · · · , X0 ) = P(Xn+1 = i | Xn ) for all n ≥ 0 and i ∈ S. We will discuss the case when S is a finite set. In this case, we let S = [m] for some positive integer m. A stochastic process with the Markov property is called a Markov chain. Note that a finite Markov chain can be described in terms of the transition probabilities pij = P(Xn+1 = j | Xn = i) i, j ∈ S. One can easily see that X pij = 1 ∀i ∈ S. j∈S 3 Lecture 5 All the elements of a Markov chain model can be encoded in a transition probability matrix   p11 p21 · · · pm1  p12 p22 · · · pm2    A= . . .. ... ...   ..  . p1m p2m · · · pmm Note that the sum of each column is equal to one. Example 3.1. (i) A machine can be either working or broken on a given day. If it is working, it will break down in the next day with probability 0.01, and will continue working with probability 0.99. If it breaks down on a given day, it will be repaired and be working in the next day with probability 0.8, and will continue to be broken down with probability 0.2. We can model this machine by a Markov chain with two states: working, and broken down. The transition probability matrix is given by   0.99 0.8 . 0.01 0.2 (ii) A simple random walk is an example of a Markov chain. However, there is no transition probability matrix associated with the simple random walk since the sample space is of infinite cardinatlity. Let rij (n) = P(Xn = j | X0 = i) be the n-th step transition probabilities. These probabilities satisfy the recurrence relation rij (n) = m X rik (n − 1)pkj f or n > 1, k=1 where rij (1) = pij . Hence the n-step transition probability matrix can easily be shown to be An . A stationary distribution of a Markov chain is a probability distribution over the state space S (where P(X0 = j) = πj ) such that πj = m X πk · pkj (∀j ∈ S). k=1 Example 3.2. Let S = Zn and X0 = 0. Consider the Markov chain X0 , X1 , X2 , · · · such that Xn+1 = Xn + 1 with proability 21 and Xn+1 = Xn − 1 with probability 12 . Then the stationary distribution of this Markov chain is πi = n1 for all i. 4 Lecture 5 Note that the vector (π1 , π2 , · · · , πm ) is an eigenvector of A with eigenvalue 1. Hence the following theorem can be deduced from the PerronFrobenius theorem. Theorem 3.3. If pij > 0 for all i, j ∈ S, then there exists a unique stationary distribuion of the system. Moreover, lim rij (n) = πj , n→∞ ∀i, j ∈ S. A corresponding theorem is not true if we consider infinite state spaces. 4 Martingale Definition 4.1. A discrete-time stochastic process {X0 , X1 , · · · } is a martingale if Xt = E[Xt+1 |Ft ], for all t ≥ 0, where Ft = {X0 , · · · , Xt } (hence we are conditioning on the initial segment of the process). This says that our expectated gain in the process is zero at all times. We can also view this definition as a Mathematical formalization of a game of chance being fair. Proposition 4.2. For all t ≥ s, we have Xs = E[Xt |Fs ]. Proof. This easily follows from induction. Example 4.3. (i) Random walk is a martingale. (ii) The balance of a roulette player is not a martingale (we always have Xk > E[Xk+1 |Fk ]). (iii) Let Y1 , Y2 , · · · be i.i.d. random variables such that Yi =Q2 with probability 31 and Yi = 12 with probability 32 . Let X0 = 0, Xk = ki=1 Yi . Then {X0 , X1 , · · · } forms a martingale. 5 Optional stopping theorem Definition 5.1. (Stopping time) Given a stochastic process {X0 , X1 , · · · }, a non-negative integer-valued random variable τ is called a stopping time if for every integer k ≥ 0, the event τ ≤ k depends only on the events X0 , X1 , · · · , Xk . 5 Lecture 5 Example 5.2. (i) In the coin toss game, consider a gambler who bets $1 all the time. Let τ be the first time at which the balance of the gambler becomes $100. Then τ is a stopping time. (ii) Consider the same gambler as in (i). Let τ be the time of the first peak (local maximum) of the balance of the gambler. Then τ is not a stopping time. Theorem 5.3. (Doob’s optional stopping time theorem, weak form) Suppose that X0 , X1 , X2 , · · · is a martingale sequence and τ is a stopping time such that τ ≤ T for some constant T . Then E[Xτ ] = E[X0 ]. Proof. Note that Xτ = X0 + T −1 X (Xi+1 − Xi ) · 1{τ ≥i+1} . i=0 (we used the fact τ ≤ T ). Since T is a constant, by linear of expectation we have E[Xτ ] = E[X0 ] + T −1 X h i E (Xi+1 − Xi ) · 1{τ ≥i+1} . i=0 The main observation is that τ ≥ i + 1 is determined by X0 , X1 , · · · , Xi . Hence h i h  i E (Xi+1 − Xi ) · 1{τ ≥i+1} = E E (Xi+1 − Xi ) · 1{τ ≥i+1} | Fi h i = E (E[Xi+1 | Fi ] − Xi ) · 1{τ ≥i+1} h i = E 0 · 1{τ ≥i+1} = 0. Hence E[Xτ ] = E[X0 ]. The condition can be further weakened (see [4]). The lesson to learn is that ‘a mortal being has no winning strategy (when the game is fair)’. On the other hand, if one has some advantage over an opponent in some game, then no matter how small that advantage is, he/she will win in the long run. Exercise 5.4. In the coin toss game, consider the following strategy. The gambler stops playing the first time at which the balance becomes $100. Note that by definition, we have E[Xτ ] = 100. Does this contradict the optional stopping theorem? 6 Lecture 5 Optional stopping time theorem can be used to deduce interesting facts. Exercise 5.5. For two positive integers a and b , consider the following strategy for the coin toss game. A player stops at the first time the balance equals either to a or to −b . Let this time be τ . What is the probability distribution of Xτ ? (i.e., what are the probabilities that Xτ = a and Xτ = b ?) References [1] S. Ross, A first course in probability [2] D. Bertsekas, J. Tsitsiklis, Introduction to probability ´ [3] L. Bachelier, Théorie de la spéculation, Annales Scientifiques de l’Ecole Normale Supérieure, 3, 21-86. [4] R. Durrett, Probability: Theory and Examples, 3rd edition. [5] S.R.Srinivasa Varadhan, Lecture Note (http://www.math.nyu.edu/faculty/varadhan/spring06/spring06.1.pdf) 7