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
$$\pi_x=\left(\frac{1}{2k},\frac{1}{k},...,\frac{1}{k},\frac{1}{2k}\right).$$
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.