# Markov chain with exponentially decreasing transition probabilities

I'm currently trying to figure out the steady-state vector of a particular infinite-state Markov chain. The chain has (countably) infinitely many states $$S_0, S_1, \dots, S_i, \dots$$, such that for all $$i$$: \begin{align} \mathbb{P}(S_i \to S_i) &= 0 \\ \mathbb{P}(S_i \to S_{i+1}) &= \frac{1}{2^i} \\ \mathbb{P}(S_i \to S_{i-1}) &= 1-\frac{1}{2^i}. \end{align} So far, all I can tell that if $$\mathbf{p}$$ is the steady-state vector for this chain, then $$\lim_{i\to\infty} \mathbf{p}_i = 0.$$ I know that for a finite-state Markov chain, the rows of $$P^\infty$$ are equal to the steady-state vector — I'm assuming that this holds for a Markov chain with infinitely many states as well? For Markov chains with a small number of states (i.e. two or three), I can usually find $$P^n$$ by hand with diagonalization, but in this case I feel like there should be an easier way.

How should I approach problems like this, and how would I find $$\mathbf{p}$$ in this case?

• Suppose the steady state vector is $p^{\infty}=[p_i]_{i\in\Bbb Z_{\ge0}}$. Then in the next time level, the probability vector should stay the same. $s_i,i\ge1$ in next time level can be reached from $s_{i-1}$ in the previous time level with probability $p_{i-1}/2^{i-1}$ and $s_{i+1}$ in the previous time level with probability $(1-1/2^{i+1})p_{i+1}$ and thus$$p_i=p_{i-1}/2^{i-1}+(1-1/2^{i+1})p_{i+1},i\ge1$$where $p_0=p_1/2$. – Shubham Johri May 14 at 15:33
• In steady state, we have $p_0=\frac12p_1$ or $P_1=2p_0$. Also, $p_1=p_0+\frac34p_2$, so $p_2=\frac43p_0$ and so on. Hopefully, one can find a general formula for $p_n$ in terms of $p_0$, and then use the fact that the probabilities must sum to $1$ to solve for $p_0$ – saulspatz May 14 at 15:35
• @Robert It looks like there's no closed form solution for the probabilities of the steady state. Are you interested in some kind of approximate solution? – Ben Grossmann May 14 at 15:49

## 2 Answers

If I'm not mistaken, the steady-state vector satisfies $$p_n=\frac{2^n}{\prod_{k=1}^n(2^k-1)}p_0\tag1$$ The sum of the probabilities must equal $$1$$, and the series converges very rapidly. Summing the first few terms gives $$p_0\approx 0.20971122089755811$$

You can check this answer by substitution of $$(1)$$ into the formula in Ben's answer.

I arrived at this solution, by computing the first few terms in exact arithmetic. I recognized the numerators, or course, and I plugged the denominators into OEIS.

EDIT

I just realized I pasted in the wrong number for $$p_0$$. I've corrected it.

• That is a much neater solution than I would have expected! – Ben Grossmann May 14 at 16:27

First of all, the approach you describe for finite state-space Markov chains is inefficient; the steady state can be more easily computed as the left-eigenvector of $$P$$ associated with the eigenvalue $$1$$. That is, $$\mathbf p$$ is the solution to the equation $$(P - I)^T\mathbf p = 0$$ normalized so that its entries are non-negative with sum $$1$$.

The analogous process for your infinite Markov chain is to solve the infinite system of equations $$\mathbf p_0 = \frac 12 \mathbf p_1\\ \mathbf p_i = \frac 1{2^{i-1}} \mathbf p_{i-1} + \left(1 - \frac 1{2^{i+1}} \right) \mathbf p_{i+1}, \quad i \geq 1.$$ Note that the second equation can be reindexed and rearranged to yield a recurrence relation. After applying the substitution $$j = i+1$$ and solving for $$\mathbf p_j$$, we get $$\mathbf p_j = \frac{2^j}{2^{j} - 1}\cdot \mathbf p_{j-1} - \frac{2^{j}}{2^j - 1} \cdot \frac{1}{2^{j-2}} \mathbf p_{j-2} \\ = \frac{2^j}{2^{j} - 1}\cdot \mathbf p_{j-1} - \frac{4}{2^j - 1} \mathbf p_{j-2}, \quad j \geq 2.$$ From the first equation, we have $$\mathbf p_1 = 2 \mathbf p_0$$. Plugging this into the recurrence relation allows us to express $$\mathbf p_k$$ in terms of $$\mathbf p_0$$ for all $$k$$. For instance, we can find $$\mathbf p_2$$ with $$\mathbf p_2 = \frac{2^2}{2^2 - 1} \mathbf p_1 - \frac 4{2^2 - 1}\mathbf p_0 = \frac 43 (2 \mathbf p_0) - \frac 43 \mathbf p_0 = \frac 43 \mathbf p_0\\$$ and similarly $$\mathbf p_3 = \frac{2^3}{2^3 - 1} \mathbf p_2 - \frac 4{2^3 - 1}\mathbf p_1.$$