# Optimal stopping for Markov Chain

If the problem of optimal stopping for finite state discrete time Markov Chains is solved on the infinite horizon explicitly?

Edited: This means if for a given MC $X(n)$ with a state space $x_1,...,x_n$, transition matrix $P$; and a vector $g_1 = g(x_1),...,g_n = g(X_n)$ there is an explicit solution to the problem $$v_i = \sup\limits_{\tau<\infty}\mathsf{E}[g(X(\tau))|X_0 = x_i].$$

-
I don't understand what you are asking. Can you state your question more precisely? –  Nate Eldredge May 13 '11 at 12:26
I've edited it. –  Ilya May 13 '11 at 15:57
This is still not a question –  TheBridge May 13 '11 at 20:46
For an irreducible Markov chain, $v_i$ is $\max g(\ )$ for every $i$. –  Did May 14 '11 at 22:13
Hence $v_i$ does not depend on $i$. And an optimal stopping time $\tau$ is the first hitting time of the set argmax $g(\ )$. –  Did May 15 '11 at 10:21

Yes, it is solved in a finite number of steps by so called the State Elimination algorithm (for Markov chains), see the papers of Isaac M. Sonin.

-
That's yours? Ok, thanks ) –  Ilya Jun 7 '11 at 16:45