Mathematics homework help
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.