Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
That's yours? Ok, thanks ) – Ilya Jun 7 '11 at 16:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.