Solved – Markov Chain: Simple Symmetric Random walk on {0,1,…,k}

markov-processself-studystochastic-processes

Consider a simple symmetric random walk on {0,1,…,k} with reflecting boundaries. if the walk is at state 0, it moves to 1 on the next step. If the walk is at k, it moves to k-1 on the next step. Otherwise the walk moves left or right, with probability 1/2.

a. Find the stationary distribution.

b. For k = 1,000, if the walk starts at 0, how many steps will it take on average for the walk to return to 0?

I'm struggling to figure out how to start this. I know how to solve these types of problems for chains that have a known number of states but having unknown number of states makes it so much more difficult. Now I know the Markov Chain is irreducible with period 2 (so it's no ergodic).

Can someone help me get started? Thank you in advance.

EDIT:

My textbook has the following which I don't follow:

Let $x= (x_1, x_2, …, x_n)$ with $x_1 = 1$

$$x_j = \sum_{i=1}^{n} x_i P_{ij} = x_{j-1} P_{j-1,j}$$

I understanding using $x_1 = 1$ but the equality for $x_j$ doesn't click for me..

Best Answer

(A) Find the Stationary Distribution

First, let's make some observations about this DTMC. Firstly, if we draw this out, we can immediately see that it has period 2, and therefore will have no limiting distribution. Due to this, we can't assume that there exists a stationary distribution. Noting this, we also can't do any fancy numerical tricks such as $P^{10000}$ to find the stationary distribution, so we will need to find these the old fashioned way.

Nothing the method whuber states, let's start with small $k$ and look for patterns. Starting with $k = 1$, the stationary distribution is trivial $$\pi = \left[ \frac{1}{2} \quad \frac{1}{2}\right]$$

Moving on to $k = 2$, we can solve $\pi P = \pi$ by reducing the following matrix, also considering the additional qualification that $\sum_{i=1}^n \pi_i = 1$, $$P = \begin{bmatrix} -1 & .5 & 0 & 0\\ 1 & -1 & 1 & 0\\ 1 & 1 & 1 & 1 \end{bmatrix} \implies \pi = \left[\frac{1}{4} \quad \frac{1}{2} \quad \frac{1}{4}\right]$$ Moving on to $k = 3$, solving a similar matrix leads to $$\pi = \left[\frac{1}{6} \quad \frac{1}{3} \quad \frac{1}{3} \quad \frac{1}{6}\right]$$ and $k = 4$ gives $$\pi = \left[\frac{1}{8} \quad \frac{1}{4} \quad \frac{1}{4} \quad \frac{1}{4} \quad \frac{1}{8} \right]$$

At this point, a pattern is clearly formed. The stationary distribution can be summarized by $$\pi = \begin{cases} \frac{1}{2k}, & \text{for }k = 0, n\\ \frac{1}{k}, & \text{for }0 < k < n \end{cases}$$

This can be tested with the time reversible equations where we must show $$\pi_i p_{i,j} = \pi_j p_{j,i} \quad \forall \quad i,j$$

The intermediate probabilities are trivial, so we will show specifically that $\pi_0 p_{0,1} = \pi_1 p_{1,0}$ as it is clearly equal to solving $\pi_{n-1} p_{n-1,n} = \pi_n p_{n,n-1}$.

\begin{align*} \pi_0 p_{0,1} &= \frac{1}{2k} * 1\\ &= \frac{1}{2} * \frac{1}{k}\\ &= \frac{1}{k} * \frac{1}{2}\\ &= \pi_1 p_{1,0} \end{align*}

and as this solution satisfies our time reversibly equations, it is indeed the stationary distribution.

(B) Expected Walks to return to $P_0$

If you haven't read it yet, understand that the expected time between visits is a geometric problem, and it reduces simply to $$E[\text{Return to }P_0] = \dfrac{1}{\pi_0} = \dfrac{1}{\frac{1}{2000}} = 2000$$

Let me know if that made sense or if you have any questions.

Related Solutions

Solved – Probability of visiting all other states before return

This looks like homework so I'm trying to give a hint, not a solution.

For part (b), you definitely want to use the structure of the graph. Without loss of generality suppose you start at $12$ and your first step is to $1$. Can you say what the probability is that you hit $11$ before you hit $12$?

Solved – Stochastic Process: On a chessboard a single random knight performs a simple random walk

Yes, you can simulate it using a big transition matrix and roll it, while observing the cumulative probability of jumping back to the corner, an absorbing state. This is a Markov traverse on a graph with 64 nodes and a lot of sides, each representing allowed move of a knight on a board.

The average is suprisingly high: 168. This many steps in average is the length of the cycle in this graph when you start in the corner.

Here's the solution in Python:

import numpy as np

def jump(i,j):
   "true if jump is allowed"
   ret = (abs(i) == 2 and abs(j) == 1) or (abs(i) == 1 and abs(j) == 2)
   return ret

# init state after 1st jump
s1 = np.zeros(64) # state after 1st jump

for i in range(8):
    for j in range(8):
        if jump(i,j):
            s1[i*8 + j] = 1
s1 = s1 / np.sum(s1)
# print(np.reshape(s1,(8,8)))           

p = np.zeros((64,64)) # transition matrix, where state num k = 8 * i + j

# init tx matrix
for ki in range(8):
    for kj in range(8):
        k = ki*8 + kj
        for i in range(8):
            for j in range(8):
                if jump(ki-i,kj-j):
                    p[k, i*8 + j] = 1
        p[k, :] = p[k, :] / np.sum(p[k, :])
        # print(ki,kj,np.reshape(p[k,:],(8,8)))
p[0,:] = np.zeros(64)
p[0,0] = 1
# print(0,0,np.reshape(p[0,:],(8,8)))

steps = 10000
cumps = np.zeros(steps) # cumulative probability of each cycle length

s = s1
for step in range(2,steps):
    s = np.matmul(s, p)
    cumps[step] = s[0]
#    print(step, ps[step])
ps = np.diff(cumps) # probability of a step
print("check add up to 1: ",cumps[steps-1])
print("mean steps: ",np.dot(range(1,steps),ps))

import matplotlib.pyplot as plt

# plt.plot(range(1,1001), ps[0:1000])
plt.plot(range(1,1001), cumps[1:1001])
plt.xlabel("cycle length")
plt.ylabel("probability")
plt.title("CDF")
plt.show()