HW6solutions - The solution to HW6. PDF

Preview

Summary

The solution to HW6....

Description

Math 4221 - Fall 2017 Homework 5: Due Monday Nov 20th On a cover sheet with your name please answer: (I) Name any sources you used in this homework assignment or write none used. This includes students in class, students not in the class, websites, textbooks, online forums, etc. Any website needs to be cited specifically enough to be found. You may work with other students, but must write up your answers individually. (II) Which problems on this assignment were you unable to complete or gave you the most difficulty, and why? (III) Which problems on this assignment were you most interested in? Why? Read Chapter 3.3 Lawler’s Introduction to Stochastic Processes and Chapter 3 of Levin, Peres, and Wilmer and answer the following questions: (1) Lawler section 3.5 Exercise 3.10 Suppose α gives the rates for an irreducible continuous-time Markov chain on a finite state space. Suppose the invariant probability measure for the continuous time chain be π. Let p(x, y) = α(x, y)/α(x), x 6= y We want to find the stationary distribution π ˜ for the discrete time chain. P We want to find π ˜ for each x π ˜ (x) = y π ˜ (y)p(y, x) given that πA = 0. P The equation πA = 0 expands into, for each x, y∈S π(y)A(y, x) = 0. Note that A(y, x) = α(y, x) if y 6= x while X A(x, x) = −α(x) = − α(x, y) y6=x

Therefore, we can rewrite πA = 0 as equivalent to, for each x ∈ S , X π(x)α(x) = π(y)α(y, x) y∈S

Moving the π(x) term of the discrete time chain to the left hand side gives: X α(y, x) π ˜ (x) = π ˜ (y) α(y) y∈S Rearranging this: Xπ π ˜ (x) ˜ (y) α(y, x) α(x) = α(y) α(x) y∈S

We see that as long as for some constant z, π ˜ (x) = z −1 α(x)π (x), that using that π satisfies its equations, means that π ˜ will satisfy the equations to be a stationary distribution, P provided x π ˜ (x) = 1. X X π ˜ (x) = z −1 α(x)π(x) x

x

1

2

P So z = x α(x)π(x). In the event that α(x) = α is a constant, then z = α and π = π ˜. Otherwise the discrete time chain and continuous time chain will have different stationary distributions. Note: It is still the case that both chains conditioned on having made the same number of transitions will have identical distributions (and so in the case of irreducible chains still have the same behavior in terms of recurrence). However, since the continuous time chain can vary by state the time needed to make those transitions, the two stationary distributions can be quite different. For example, take a two state continuous time chain with α(0, 1) = 10−10 , α(1, 0) = 1010 . The chain will almost immediately (in expectation) move back to 0 anytime it reaches 1, but will take an eon (in expectation) to move from 0 to 1. Therefore, most of the time, we should expect the state to be 0. The discrete analog of this chain instead is merely p(0, 1) = p(1, 0) = 1. By using a different kind of discrete time chain analog with p(x, x) > 0, we make the two chains have the same stationary distribution, but would loose the property about conditioning on number of transitions made. (2) Lawler section 3.5 Exercise 3.12 Considering the population model, the birth-death process with µn = nµ and λn = λn, we wish to find for what values of µ and λ extinction (reaching Xn = 0 for some n) is certain. We cannot use the formulas with sums over µn and λn in their original sense since this chain is absorbing at 0 and hence not irreducible (and not classifiable as transitive or recurrent). However, a(n) (or our α(n)) as the probability the chain ever hits 0 starting from n is still perfectly valid. Therefore, we can reuse the solution of the recurrence for a(n) in this different context, and say the chain has certain extinction if a(n) = 1 for all n:

a(n) = (a(1) − 1)

n X µ1 · · · µj j=0

λ1 · · · λj

−1

With a non-trivial (i.e. not equal to 1 solution, i.e. non-extinction) if ∞ X µ1 · · · µn n=0

Here for n ≥ 1,

µn λn

=

nµ nλ

=

µ , λ

λ1 · · · λn

0, λn = nλ + ν, µn = nµ and wish to know when the chain is positive recurrent, negative recurrent, and transitive. We know if the following sum is finite, the chain is transient (otherwise recurrent), ∞ X µ1 · · · µn n=0

λ1 · · · λn

1. It is inconclusive if equal to 1. For the first sum,

an+1 µ nµ µn+1 = , = = nλ + ν λ + ν/n λn+1 an µ = λµ < 1 (and the chain is transient), i.e. λ > µ and the series converges if limn→∞ λ+ν/n and diverges if µ > λ (and the chain is recurrent). If λ = µ, we need to decide if the following sum converges or diverges: ∞ X

n=0

n!µn (ν + µ) · · · (ν + nµ)

If ν ≤ µ, this is bigger than: ∞ X

∞

X 1 n!µn = (n + 1)!µn n=0 n + 1 n=0 Which diverges by the p-series test (and hence the chain is transient). If instead ν = cµ with c > 1, the sum is (where (m)n = m · (m − 1)n−1 and (m)0 = 1): ∞ X

∞

X 1 n!µn ≈ n (n + c)c (n + c)n µ n=0 n=0 Which by p-series test converges if c > 1 (and hence the chain is recurrent). For the second sum, nλ + ν λn λ + ν/n an+1 . = = = µ + µ/n µn+1 an (n + 1)µ And limn→∞ λ+ν/n µ+µ/n = λ/µ. If λ/µ < 1 the sum converges and the chain is positive recurrent. It remains to decide if λ = ν whether the chain is positive recurrent or null recurrent based on ν for ν > µ. Letting again ν = cµ with c > 1, c(1 + c) · · · (n + c − 1) (n + c − 1)n λ0 · · · λn−1 (ν)(ν + µ) · · · (ν + (n − 1)µ) = = = µn n! n! µ1 · · · µn n! These terms are clearly not going to 0 since the numerator is larger than the denominator, and so the sum diverges and the chain is null recurrent.

4

(4) Lawler section 3.5 Exercise 3.14 1 and µn = 1. We need to show the chain Consider the birth-death process with λn = n+1 is positive recurrent and find its stationary distribution. To do so we need to compute the series (which will be the normalizing constant for our stationary distribution): ∞ ∞ X X 1 λ0 · · · λn−1 = e = q −1 = µ · · · µ (n)! 1 n n=0 n=0

Where the stationary distribution is given by: λ0 · · · λn−1 −1 e π(n) = q = µ1 · · · µn n! (5) Simulating Fibonacci sequences (Lawler Ch 7 exercise 7.7) Let Sn be the set of sequences k0 k1 . . . kn with ki ∈ {0, 1} and no two adjacent 1’s (i.e. for all i, if ki = 1, then ki−1 = ki+1 = 0). Let pn (j) denote the fraction of sequences with kj = 1. Design a Markov chain on Sn with uniform distribution using the Metropolis algorithm. Explain how to estimate pn (j) using the Markov chain. For 5 bonus points on the homework, write a program to run Monte Carlo simulations and use 100 trials to estimate what p200 (0) and p2 00(100) are. To use the Metropolis algorithm, we first have to have any Markov chain on Sn . A simple one is, choose i ∈ {0, 1, . . . , n} uniformly at random, pick ˜ki ∈ {0, 1} uniformly at random, if replacing ki with ˜ki gives an element of Sn , replace the digit ki with ˜ki (note they may be the same), otherwise stay at the old sequence. The probability of moving between two 1 . As this is already symmetric, sequences in Sn that differ at one coordinate is then 2n the chain is reversible with respect to the uniform stationary distribution, and a trivial application of the Metropolis algorithm suffices. To estimate pn (j), the proportion of sequences of length n with a 1 in the jth spot, we can use Markov chain Monte Carlo as follows. To get one sample from Sn we run the chain for a fixed long time (say n3 or for as many steps as your computer can do in 1 second), and take the current state as an approximate draw from the uniform distribution on Sn . We record whether the jth digit is a 0 or 1. Repeat this, and the proportion of times you get a 1 is an approximation for pn (j). There are two sources of error here: (1) the chain will never quite sample uniformly from Sn but the longer you run it, the less the error will be (2) random draws from Sn are only approximating the proportion pn (j), you can use probability to estimate how big the error is based on your number of samples, again the more the merrier. (6) Instead, design a Markov chain on Sn with π(k0 k1 . . . kn ) = λk0 +...+kn . Okay, we can now non-trivially adapt our Markov chain from the previous question to get this stationary distribution. Consider two sequences K and K ′ differ at a single coordinate with K having a 0 and K ′ a 1. The π(K) = λ1 π(K ′ ). For the original chain above 1 = Ψ(K ′ , K). The Metropolis algorithm tells us our new Markov chain Ψ(K, K ′ ) = 2n should have transition probabilities: P (K, K ′ ) = Ψ(K, K ′ )[1 ∧

1 π(K ′ ) ]= [1 ∧ λ] π(K) 2n

P (K ′ , K ) = Ψ(K ′ , K )[1 ∧

1 1 π(K) ]= [1 ∧ ] ′ π(K ) 2n λ

5

Simplifying the minimum (the ∧) depends on whether λ > 1 or λ < 1 (the case λ = 1 1 1 . we already have from the previous question). If λ > 1, P (K, K ′ ) = 2n , P (K ′ , K) = λ2n λ and P (K ′ , K) = 1 ′ Otherwise, P (K, K ) = 2n 2n . The probability of P (K, K) is a little hard to write down explicitly as you have to know how many digits can be swapped to give a valid element of Sn . (7) Levin, Peres, and Wilmer Exercise 3.1 This exercise shows how to use the Metropolis algorithm even if the base chain is not symmetric (or even reversible!). Given the original transition matrix Ψ, we construct:  h i (y,x) Ψ(x, y) π(y)Ψ ∧ 1 π(x)Ψ (x,y) h i P (x, y) = P π(z)Ψ (z,x) 1 − ∧ 1 Ψ(x, z) z6=x π(x)Ψ (x,z)

y 6= x x=y

Note that when Ψ(x, y) = 0 that, we take the minimum of 1 and “undefined” to be 1. Let x, y be given. Without loss of generality, assume π(y)Ψ(y, x) ≤ π(x)Ψ(x, y) (otherwise, (y,x) relabel so its true). Then P (x, y) = Ψ(x, y) π(y)Ψ π(x)Ψ (x,y) and P (y, x) = Ψ(y, x). Then P is reversible for π for x and y. π (x)P (x, y) = π (x)Ψ(x, y)

π(y)Ψ(y, x) = π (y)Ψ(y, x) = π (y)P (y, x) π(x)Ψ(x, y)...