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

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..

• Treat $k$ as known. The mathematics of the situation doesn't care who actually "knows" its value or not--that's for psychology to deal with. – whuber Feb 20 '18 at 22:23
• But that's easier said than done. With known k (say k=3) I can create a very obvious system of equations which i can use to solve and acquire my stationary distribution. In this case, though, I don't know how to proceed. – Nicklovn Feb 20 '18 at 22:28
• Then you might have to work it through explicitly for a sequence of small $k$ (start at $k=0$) and look for patterns. In the process you will likely see how to generalize your work. – whuber Feb 20 '18 at 22:30
• Are you familiar at all with the time reversible equations? If so, you can check the stationary distribution up to some $k$ to come up with a guess and then verify your guess with the time reversible equations. That is, if this is time reversible which you would also need to verify. – Ryan Honea Feb 20 '18 at 23:52
• @Nicklovn Is this an exercise from a textbook? If so, which exercise from which book? (Also, consider adding the self-study tag.) – Jim Feb 23 '18 at 19:22

## (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.