-1
$\begingroup$

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

  • 0
    I don't understand what you are asking. Can you state your question more precisely?2011-05-13
  • 0
    I've edited it.2011-05-13
  • 2
    This is still not a question2011-05-13
  • 0
    For an irreducible Markov chain, $v_i$ is $\max g(\ )$ for every $i$.2011-05-14
  • 0
    Hence $v_i$ does not depend on $i$. And an optimal stopping time $\tau$ is the first hitting time of the set argmax $g(\ )$.2011-05-15
  • 0
    For the irreducible it's trivial. The question was about an arbitrary MC.2011-05-15
  • 0
    Still trivial: replace the global maximum by the maximum on the connected component of the starting point $x_i$. (I read your last comment by chance, please use this @ thing.)2011-05-27
  • 0
    @Didier Piau, thanks. I am curious again for the vote down.2011-06-08
  • 0
    @Gortaur: You are welcome. Am I supposed to be related to the downvote?2011-06-08
  • 0
    @Didier Piau, I don't know. You just usually have a guess why it was downvoted (anyway comment "This is still not a question" is slightly incorrect)2011-06-08
  • 0
    @Gortaur: Am I supposed to be concerned by your guess? (Anyway, since you mention TheBridge's comment, I happen to disagree with the content of your parenthesis.)2011-06-08
  • 0
    @TheBridge: Just to let you know that you are mentioned in a little drama we seem to be having here (see last comments above).2011-06-08
  • 0
    @Didier Piau, thanks for redirecting ) I was thinking that everyone see new messages in his inbox regardless of @ thing - just because he already wrote a comment on this question. Now it seems more clear.2011-06-08

1 Answers 1

2

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.

  • 0
    That's yours? Ok, thanks )2011-06-07