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$ – Shubham Johri May 14 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 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$ – Ben Grossmann May 14 at 15:49
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$ – Ben Grossmann May 14 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$

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.