This is a Markov chain problem, but my struggle seems to be of basic Linear algebra nature.

  • Consider a simple random walk on $\{0,1,...,k\}$ with reflecting boundaries at $0$ and $k$, that is, random walk on the path from $0$ to $k$.
  • A random walker earns $k$ dollars every time the walk reaches $0$ or $k$ but loses $1$ dollar at each interval vertex $\left(~\mbox{from}\ 1\ \mbox{to}\ k - 1~\right)$.
  • In $10,000$ steps of the walk, how much, on average, will be gained ?.

I define a function

$$r(x)=\left\{ \begin{array}{rcr} k & \text{if} & x&=&0,k \\ -1 & \text{if} & x&=&1,...,k-1 \\ \end{array} \right.$$

We want to find the long term expected reward

$$\mathbb{E}[r(x)]=\lim_{n\rightarrow \infty}\frac{r(x_1)+r(x_2)+...+r(x_n)}{n}=\sum_xr(x)\pi_x.$$

So I need to find the statinary distribution $\pi_x.$ The transition matrix is given by

$$P=\begin{pmatrix}0 & 1 & 0 & \dots & 0 &0 \\ 1/2 & 0 & 1/2 & \dots & 0 &0 \\ 0 & 1/2 & 0 & \dots & 0&0 \\ \vdots & \vdots & \vdots & \ddots & 1/2&0 \\ 0 & 0 & 0 & 1/2 &0&1/2 \\ 0&0&0&0&1&0\end{pmatrix}.$$

Here I run into trouble when solving $\pi_x P=\pi_x$. The answer should be


How do I do this?


The routine linear algebra way:

First, reduce that system to $(P-I)\pi_x=0$, and write $\pi_x=(p_0,p_1,\dots,p_k)^T$. $$\begin{bmatrix}-1&1&0&\cdots&0&0\\ \frac12&-1&\frac12&\cdots&0&0\\ 0&\frac12&-1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-1&\frac12\\ 0&0&0&\cdots&1&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&1&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&\frac12&-1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-1&\frac12\\ 0&0&0&\cdots&1&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&1&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&0&-\frac12&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-1&\frac12\\ 0&0&0&\cdots&1&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&1&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&0&-\frac12&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-\frac12&\frac12\\ 0&0&0&\cdots&1&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&1&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&0&-\frac12&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-\frac12&\frac12\\ 0&0&0&\cdots&0&0\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ Now that we're done with the row-reduction, we have $n$ equations, all of which amount to $p_i=p_{i+1}$. The solution has all of them equal? What's up? Simple answer: that's the wrong transition matrix. The transition matrix in a Markov chain must have the sum of each column equal to $1$, while the sum of each row can vary. The state following a pure state is represented by the corresponding column.

So then, the correct transition matrix has those $1$ entries in the first and last columns, rather than the first and last rows. Running the fixed version: $$\begin{bmatrix}-1&\frac12&0&\cdots&0&0\\ 1&-1&\frac12&\cdots&0&0\\ 0&\frac12&-1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-1&1\\ 0&0&0&\cdots&\frac12&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&\frac12&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&\frac12&-1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-1&1\\ 0&0&0&\cdots&\frac12&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&\frac12&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&0&-\frac12&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-1&1\\ 0&0&0&\cdots&\frac12&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&\frac12&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&0&-\frac12&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-\frac12&1\\ 0&0&0&\cdots&\frac12&-1\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ $$\begin{bmatrix}-1&\frac12&0&\cdots&0&0\\ 0&-\frac12&\frac12&\cdots&0&0\\ 0&0&-\frac12&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&-\frac12&1\\ 0&0&0&\cdots&0&0\end{bmatrix} \begin{bmatrix}p_0\\p_1\\p_2\\ \vdots\\p_{n-1}\\p_n\end{bmatrix}=\begin{bmatrix}0\\0\\0\\ \vdots\\0\\0\end{bmatrix}$$ Almost the same, but the first and last equations are different, giving $2a_0=a_1$ and $2a_k=a_{k-1}$. The (normalized) solution $(\frac1{2k},\frac1k,\frac1k,\dots,\frac1k,\frac1{2k})$ is what it should be.

Note that this isn't the only solution that doesn't decay. The possible transitions form a bipartite graph, and that means there's also something corresponding to the eigenvalue $-1$. In that case, we get an eigenvector $(1,-2,2,\dots,2\cdot (-1)^{k-1},(-1)^k)$ - no point in normalizing that one. Long-term behavior will alternate based on how much weight we put into even and odd terms.


The vector you suggested clearly satisfies the defining equation: it is a straightforward calculation to check that. If you are worried about unicity, it is clear that $P-I$ has co-rank 1. There are theoretical results to guarantee this, but also, in this particular case, it is straightforward that once you pick the first coordinate, it determines all other coordinates (just see the system of equations, you can always express the next variable from the last two). So the co-rank is at most 1. Of course, it is at least 1 (sum of columns equals to 0).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.