Math assignment 8 hrs

HOMEWORK B-3: DUE ON MAY 8 NOON

Abstract. ONLY FOR STUDENTS WITH UW STUDENT ID ENDING

WITH 0, 2, 4, 6, and 8.

Problem 1. (Random walk bridge.) Consider an urn with N many +1s and N many −1s. Randomly sample, without replacement, each of these 2N numbers one by one. This gives us a random sequence w = (w1,w2, . . . ,w2N ) of exactly N many +1s and N many −1s. For example if N = 2, such samples can result in sequences like u or v in Problem 1.

Consider a stochastic process by declaring S0 = 0 and then successively adding coordinates of w, i.e.,

Sk = w1 + w2 + . . . + wk, k = 1, 2, . . . ,N.

(a) Show that S2N = 0. This process is called a random walk bridge. (b) Find the probability mass function and expectation of each Sk. (c) Show that the bridge has the following time-reversal symmetry:

(S2N,S2N−1, . . . ,S1,S0)

is again distributed as a random walk bridge. Hint: Time-reverse the random sequence w.

Problem 2. Suppose the weather on any day depends on the weather conditions of the previous two days. More precisely, suppose the weather can only be sunny (S) or cloudy (C). If it was sunny today and yesterday, it will be sunny tomorrow with probability 0.8. If it is sunny today and cloudy yesterday, it will be sunny tomorrow with probability 0.6. If it is cloudy today but sunny yesterday, it will be sunny tomorrow with probability 0.4, and if it cloudy for the last two days, it will be sunny tomorrow with probability 0.1.

Such a model can be turned to a Markov chain whose current state is the weather both today and yesterday. Consider Ω = {(S,C), (S,S), (C,S), (C,C)}, where (S,C) means sunny yesterday but cloudy today.

(a) Find the transition probability matrix of this Markov chain? (b) What is the stationary distribution of this Markov chain?

Problem 3. Consider two independent random walkers A and B on the 5-cycle with vertices Ω = {1, 2, 3, 4, 5}. They walk independently clockwise or anticlockwise with probability 1

2 . Consider the graph distance between A and B, i.e., the length

of the shortest path joining the two. For example, if A is at 1 and B is at 5, the graph distance is 1 and not 4. In particular the graph distance can only take values {0, 1, 2}. (a) Let Xt denote the graph distance between the two walkers at time t. Show

that Xt is a Markov chain by describing its transition probabilities.

Date: April 27, 2020.

1

2

(b) Suppose, at time zero, walker A start at 2 while walker B starts at 5. Find the expected number of steps after which they are at the same vertex.

Problem 4. Consider the random walk on the n-cycle. Suppose the random walk starts at 1. We are interested in the expectation of the cover time τn which is the first time when the random walk has visited every vertex of the cycle.

(a) Let τn−1 be the first time when all but exactly one of the vertices of the n-cycle has been visited. That is Xτn−1 visits the last but one new vertex to be visited. Use Gambler’s Ruin to show that

E (τn − τn−1) = n− 1.

Hint: Look at the set of all already visited vertices at τn−1. Suppose Xτn−1 = 5 and vertex 6 is the last vertex to be yet visited. Then the random walk can either go to 6 from 5, or go all the way in the reverse direction and get to 6 from 7.

(b) Repeat the argument above to show that if τk is the stopping time which is the first time k vertices in the cycle have been visited, then

E(τk − τk−1) = k − 1.

(c) Show that the expected cover time is given by the formula

E(τn) = n(n− 1)

2 .

Problem 5. Consider the Pólya urn model with a black balls and b red balls initially in an urn where a and b are arbitrary positive integers. At each turn you pick a ball at random and return it to the urn along with a ball with the same color. Let Xn denote the number of balls in the urn after the nth turn is completed (X0 = 1).

(a) Show that, for all n = 1, 2, 3, . . .,

E

( Xn n + 2

| Xn−1 )

= Xn−1 n + 1

.

(b) Use the above (or otherwise) to compute E(Xn) for every n. (c) Use the above (or otherwise) to show

P(nth pick is black) = a

a + b , for all n ≥ 1.

(d) Use the same method to show,

P(nth pick is black | first two picks are black) = a + 2

a + b + 2 , for all n ≥ 3.

Problem 6. Imagine the queue in front of an ice cream shop. Suppose there are currently k people standing in the queue. In the next time period, the first person in the queue gets his/her ice cream and leaves with probability 1/2. Independently, another person joins the queue with probability 1/2. If the queue is currently empty, there is 1/2 probability that someone will join the queue in the next time period. Suppose the shop can only accommodate at most a queue of N people after which no more new customers are allowed to join the queue until someone leaves.

3

(a) Let Xn be the number of people standing in the queue at time n. This is a Birth-and-Death chain. Find its state space and transition probabilities. Is it irreducible? Aperiodic?

(b) What is the probability that starting with k person queue, the shop will reach full house with N person queue before the queue gets empty.

(c) Find the stationary distribution for this chain. (d) Suppose N = ∞, i.e., there is no upper bound on the length of the queue. Con-

sider a lazy random walk {Sk, k = 0, 1, 2, 3, . . .} on the integers with transition probabilities

p(j,j + 1) = 1

4 , p(j,j − 1) =

1

4 , p(j,j) =

1

2 .

Show that the absolute value process {|Sk| , k = 0, 1, 2, 3, . . .} is the same Birth- and-Death chain as X by find its transition probabilities.

(e) Find the expected time it will take from an empty queue (0 people) to become full (N people) for the first time.