代写Homework 2代做留学生SQL语言

Homework 2

Q.1 Let ξ1, ξ2, . . . be a sequence of i.i.d. coin tosses with bias P(ξ1 = H) = p. Find the probability that we will see the pattern HH before seeing TT. Conditioned on ξ1ξ2 =HT, find the probability that we will see HT again before seeing either HH or TT.

Q.2 Consider a 3-state Markov chain with transition matrix Π(1, 1) = 1 − Π(1, 2) = p, Π(2, 1) = 1 − Π(2, 3) = q, and Π(3, 3) = 1. Let G(x, y) := E[ P ∞ n=0 1{Xn=y} |X0 = x] = P ∞ n=0 Πn (x, y) denote the expected number of visits to state y, given that the Markov chain starts at x. Find G(1, 2) and G(2, 1).

Q.3 Consider a random walk on {0, 1, . . . , L}, with transition matrix Π(i, i ± 1) = 1 2 for each i ∈ {1, . . . , L − 1}, and Π(0, 0) = Π(L, L) = 1. For each i ∈ {0, . . . , L}, find the return proability fii := P(Xn = i for some n ∈ N|X0 = i).

Q.4 Let X := (Xn)n∈N0 be a simple symmetric random walk on Z. For x ∈ Z, let Px(·), respectively Ex[·], denote probability and expectation for X with initial condition X0 = x. Let Ty := Ty(X) := min{n ≥ 0 : Xn = y} be the first time X visits the point y ∈ Z. Let L ∈ N, and define T := min{T0, TL}, the first hitting time of either 0 or L. Show that for 0 ≤ x ≤ L, Px(T < ∞) = 1, and furthermore, Ex[T] < ∞. (Hint: Use the fact that Ex[T] = P k=1 Px(T ≥ k) and Lecture 9 Proposition 1.)

Q.5 Let X be a simple symmetric random walk on Z with X0 = 0. Let a ∈ N.

(a) By conditioning on the Markov chain’s first visit to a and using the symmetry of the random walk, show that

P0( max Xi ≥ a) = P0(Xn = a) + 2P0(Xn ≥ a + 1) = P0(Xn ∈/ [−a, a − 1]).

0≤i≤n

(Hint: partition into three disjoint events: {Xn < a}, {Xn = a}, and {Xn > a}.)

(b) Deduce from the above identity that for any a ∈ N,

Pa(T0 > n) = P0( max Xi ≤ a − 1) = P0(Xn ∈ [−a, a − 1]).

0≤i≤n

(c) Deduce from (b) that Ea[T0] = ∞ for all a ∈ N.

(d) Deduce from (b) that for all n ∈ N,

P0(X1, . . . , X2n = 0) = P0(X2n = 0).

Q.6 A general random walk X on Z is a Markov chain on Z with transition matrix Π(x, y) = Π(0, y − x) = µ(y − x) for all x, y ∈ Z, where µ is a probability measure on Z. In particular, the increments X1 − X0, X2 − X1, X3 − X2, . . . are i.i.d with distribution µ. Find a stationary measure for X. Can X be positive recurrent?

Q.7 Let X be a random walk on {0, 1, . . . , L} with transition matrix Π, such that Π(0, 1) = Π(L, L − 1) = 1, Π(i, i + 1) = 1 − Π(i, i − 1) = p for all 1 ≤ i ≤ L − 1. Find the stationary distribution of this random walk. If X0 = 0, find the expected number of visits to L before returning to 0, as well as the expected time of returning. (Hint: use the cycle trick construction of the stationary distribution.)

Q.8 At each time n ∈ N, we light up ξn many candles, where (ξn)n∈N are i.i.d. Poisson random variables with mean 1. The lifetimes of the candles are assumed to be i.i.d. integer-valued with a common probability mass function f := (fk)k∈N. Assume that the mean lifetime λ := P ∞ k=1 kf(k) < ∞. Let Xn denote the number of candles burning at time n. Is X a Markov chain? Is it irreducible? Is it aperiodic? Find the stationary distribution if it exists. (Hint: To identify the stationary distribution, let n be large and consider the joint distribution of the number of burning candles with different lifetimes.)

Q.9 A birth-death chain is a Markov chain with state space N0 and transition probabilities Π(0, 1) = p0, Π(0, 0) = r0 = 1−p0, and for each k ∈ N, we have Π(k, k+ 1) = pk, Π(k, k−1) = qk, Π(k, k) = rk, with pk + qk + rk = 1. Find a necessary and sufficient condition for this Markov chain to be irreducible. Show that when X is irreducible, it is in fact reversible and identify the reversible measure. Find a necessary and sufficient condition for this Markov chain to be positive recurrent.

Q.10 Consider a knight jumping randomly on a 5 by 5 square. At each step, it picks one of the admissible moves with equal probability. Find the stationary distribution for this Markov chain by identifying the Markov chain as a random walk on a graph.

Q.11 In Q.10, suppose that the knight starts at the center.

(i) Find the probability that the knight will reach one of the corners before returning to the center.

(ii) Find the expected time it takes for the knight to reach one of the corners.