Stochastic Calculus, Fall 2002 (http://www.math.nyu.edu/faculty/goodman/teaching/StochCalc/)

Assignment 3.

Given September 20, due September 26. Last revised, September 23.

Objective: Conditioning and Markov chains, II.

1. Suppose an n×n matrix, A, has n linearly independent right eigenvectors (column vectors) with corresponding eigenvalues λ_{j}: Ar_{j} = λ_{j}r_{j}. Suppose the the corresponding left (row vector) eigenvectors are L_{j}: l_{j}A = λ_{j}l_{j}. Suppose that the r_{j} and l_{k} have been normalized to be biorthogonal: l_{j}r_{k} = δ_{jk}, where δ_{jk} = 1 if j = k and δ_{jk} = 0 if j ≠ k (this is the “Kronecker delta”; the δ_{jk} are the entries in the identity matrix.).

a. Show that A = ∑_{j=1}^{n} λ_{j}r_{j}l_{j}. Note that each term in the sum is an n × n matrix. In the other order, l_{j}r_{j} is a 1 × 1 matrix.

b. Find a similar expression for A^{t}, the product of A with itself t times, not the transpose of A.

2. We have a three state Markov chain wih transition matrix

P = ( \frac{1}{2} \frac{1}{2} 0_{\frac{1}{3} \frac{1}{3} \frac{1}{3}}^{\frac{1}{2} \frac{1}{4} \frac{1}{4}} ) .

For example, some of the transition probabilities are P (1 → 1) = \frac{1}{2}, P (3 → 1) = \frac{1}{3}, and P (1 → 2) = \frac{1}{4}. Let τ = min(t | X_{t} = 3). Even though this τ is not bounded (it could be arbitrarily large), we will see that P (τ > t) ≤ Ca^{t} for some a < 1 so that the probability of large τ is very small. This is enough to prevent the stopping time paradox (take my word for it). Suppose that at time t = 1, all states are equally likely.

a. Consider the quantities u_{t}(j) = P (X_{t} = j and τ > t). Find a matrix evolution equation for a two component vector made from the u_{t}(j) and a submatrix of P.

b. Solve this equation using the method of problem 1 to find a formula for m_{t} = P (τ = t). For this you will have to find the eigenvalues and the left and right eigenvectors of the 2 × 2 matrix A.

c. Use the answer of part b to find E[τ]. It might be helpful to use the formula

∑_{t=1}^{∞} tP (τ = t) = ∑_{t=1}^{∞} P (τ ≥ t) .

Verify the formula if you want to use it.

d. Consider the quantities f_{t}(j) = P (τ ≥ t | X_{1} = j). Find a matrix recurrence for them.

e. Use the method of question 1 to solve this and find the f_{t}.

3. Let P be the transition matrix for an n state Markov chain. Let v(k) be a function of the state k ∈ S. For this problem, suppose that paths in the Markov chain start at time t = 0 rather than t = 1, so that X = (X_{0}, X_{1}, …). For any complex number, z, with |z| < 1, consider the sum

E [∑_{t=0}^{∞} z^{t}v(X_{t}) | F_{0}] .  (1)

Of course, this is a function of X_{0} = k, which we call f(k). Find a linear matrix equation for the quantities f that involves P, z, and v. Hint: the sum

E [∑_{t=1}^{∞} z^{t}v(X_{t}) | F_{1}] .

may be related to (1) if we take out the common factor, z.

4. A particular random walk has states X_{t} that are integers, possibly negative. In general the transition probabilities are P (k → k − 1) = P (k → k) = P (k → k + 1) = \frac{1}{3} with all other transion probabilities being zero. Don’t worry that the state space might be infinite or that stopping times might be infinite.

a. Show that F_{t} = X_{t} and G_{t} = X_{t}^{2} − \frac{2}{3}t are martingales.

b. Define the stopping time τ_{a} = min(t | |X_{t}| = a). Use the result of part a and the Doob stopping time theorem to show that E(τ_{a} | X_{0} = 0) = \frac{3}{2}a^{2}.

c. Let f(k) be defined by f(X_{0}) = E[τ_{a} | F_{0}]. Find a system of linear equations satisfied by the numbers f(k) for −a < k < a. Express these equations in the form Af = 1, where A is a (2a − 1) × (2a − 1) matrix and 1 is a vector of all ones. To find the solution, calculate Aw where w(k) = 1, w(k) = k, and w(k) = k^{2}, then express the answer as a linear combination of these vectors.

d. Show that the martingale method of part b also applies to E[τ_{a} | X_{0} = k] for any |k| < a. Check that this is consistent with the answer to part c.