## Transcribed Text

Problems:
1). A random walk is defined on the integers {0, 1, 2, 3, . . .} with the following transition
probabilities:
p00 =
1
2
, p01 =
1
2
pn,n+1 = pn,n−1 =
1
2
n = 1, 2, . . .
Determine whether the walk is transient or persistent. [Hint: relate the walk to the
standard symmetric walk on the integers. The standard symmetric walk is persistent, thus
f1,0 = 1. By conditioning on the first step of the walk starting at 0, use this to compute
f0,0 for the walk on the half-line given above].
2). Examine the random walk on the two-dimensional lattice of points {(m, n)} with m, n
all positive and negative integers, where at each step there is a random jump to one of
the four neighbors with probability 1/4 each. Determine if the walk is transient, positive
persistent or null persistent. [Hint: use Stirling’s formula for the asymptotics of n!:
n! ∼ n
n
e
−n
√
2πn
3). Suppose that X and Y are independent irreducible aperiodic Markov chains with the
same state space S and the same transition matrix P. Let Z = (X, Y ) be the chain with
state space S × S and transition matrix
P
Z1 = (j, l)|Z0 = (i, k)
= P(X1 = j | X0 = i) P(Y1 = l | Y0 = k)
Show that Z is also irreducible and aperiodic. [Hint: use the following theorem: “an
infinite set of integers which is closed under addition contains all but a finite number of
positive multiples of its greatest common divisor”]
4). Consider a Markov chain on the set S = {0, 1, 2, . . .} with transition probabilities
pi,i+1 = ai
, pi,0 = 1 − ai
for i ≥ 0, where {ai
|i ≥ 0} is a sequence of constants which satisfy 0 < ai < 1 for all i.
Let b0 = 1, bi = a0a1 · · · ai−1 for i ≥ 1. Show that the chain is
(a) persistent if and only if bi → 0 as i → ∞
(b) non-null persistent if and only if P
i
bi < ∞,
and write down the stationary distribution if the latter condition holds.
5). Let {Xn} and {Yn} be independent random walks on the integers, with X0 = x
and Y0 = y. At each step Xn moves to the right with probability p and to the left with
probability 1−p. For Yn the probabilities are q and 1−q, respectively. Find the probability
that Xn = Yn for some n ≥ 0.

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.