4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ May 14, 2021 at 15:33
  • $\begingroup$ 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$ $\endgroup$
    – saulspatz
    May 14, 2021 at 15:35
  • $\begingroup$ @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? $\endgroup$ May 14, 2021 at 15:49

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That is a much neater solution than I would have expected! $\endgroup$ May 14, 2021 at 16:27
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .