Mathematics homework help. 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´olya 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. Consider 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 Birthand-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.