A Markov chain $X$ with finite state space $\{1,2,\cdots,N\}$ is defined on a probability space $(\Omega, P, \mathcal{F})$ equiped with filtration $\{\mathcal{F}_t\}$. And we assume that we can reach all the states. We consider a process $\{R_t\}$ which is $\mathcal{F}_t$ supermartingale, therefore for any two stopping times $ T \geq S$, $E[R_T|\mathcal{F_t}] \leq E[R_S|\mathcal{F_t}]$ (due to optional stopping theorem). Now, let $g$ be a real valued bounded function of $\mathbb{R}$.

Intuitively, I seems obvious to me that:

$$\sup_{t \leq \tau \leq \infty} E[R_{\tau} g(X_{\tau})| \mathcal{F}_t] = \max_{k\in {1,\dots,N}}E[R_{\tau_k}g(X_{\tau_k})|\mathcal{F}]$$ where

$\tau_k= \inf\{s \geq t, X_s= k\}$.

I am having trouble showing it though, the 'math' behind my intuition is this : take the supremum over the partition $\cup_k \tau(\{\omega: X_{\tau} =k \})$ and then the supremum will become

$\max(\sup_{\tau( \{\omega: X_{\tau} =1 \})}E[R_\tau g(1)|\mathcal{F}_t], \cdots, \sup_{\tau( \{\omega: X_{\tau} =N \})} E[R_\tau g(N)|\mathcal{F}_t]) = \max_{k\in {1,..,N}}E[R_{\tau_k}g(X_{\tau_k})|\mathcal{F}]$

as $\sup_{\tau( \{\omega: X_{\tau} =k \})} E[R_\tau g(k)|\mathcal{F}_t]= E[R_{\tau_k}g(X_{\tau_k})|\mathcal{F}]$.

I am not sure about my first step though i.e the supremum over the union.

I appreciate any suggestion. Thanks.

  • $\begingroup$ There are very simple counterexamples to your claim. e.g. if $g\equiv-1$, $R_t=-t$, then the optimizer is $\tau=\infty$. Even if you assume $g, R \geq 0$ it does not hold, for instance taking $R_t=1$ for $t=0,1$ and $R_t=0$ for $t \geq 2$. Then the optimizer $\tau$ will be $0$ or $1$ but it will not be in general the hitting time of a singleton. $\endgroup$
    – pgassiat
    Sep 4, 2014 at 8:18

1 Answer 1


Consider the sequence of stopping times $\tau_{1,k} = \inf\{s \geq t, X_s = k\}$, $\tau_{2,k} = \inf\{s \geq \tau_{1,k}, X_s = k\}$, $\tau_{3,k} = \inf\{s \geq \tau_{2,k}, X_s = k\}$, etc. Then $\cup_{i \geq t, k} \{\tau_{i,k}\}$ is all the natural numbers bigger than $t$, and also $E[R_{\tau_{i,k}} g(X_{\tau_{i,k}}) | \mathcal{F}_t]$ is decreasing in $i$ for each $k$. I think these give you your result, i.e. $$ \sup_{t \leq \tau < \infty} E[R_\tau g(X_\tau) | \mathcal{F}_t] = \sup_{i \geq t, k} E[R_{\tau_{i,k}} g(X_{\tau_{i,k}}) | \mathcal{F}_t] = \max_k E[R_{\tau_{1,k}} g(X_{\tau_{1,k}}) | \mathcal{F}_t]. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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