0
$\begingroup$

Given a Markov process among a (possibly infinite) set of states $S$, with possibly infinite depth (that is, the transition probabilities from $s_i \to s_j$ at time $t$ are permitted to depend not only on the state at time $t-1$ but also on all previous states). Say the initial state is $\sigma_0$ and for some specific infinite sequence of target states $\{\sigma_i\} | i \in \Bbb{N}$ it has been proven that for all $i$ and all possible paths leading to $\sigma_i$, state $\sigma_i$ almost surely transitions to state $\sigma_{i+1}$ in finite time.

Does that necessarily imply that the process will a.s. traverse the entire (possibly infinite) chain of target states? (Obviously, if the chain is infinite, we cannot ask for traversing the chain in a finite number of time steps.) Or if that implication does not hold, can you show a counterexample?

An example of this sort of problem is a depth-1 random walk on a 2-d grid, with the target chain $\sigma_i = (i,0)$. Here each state $\sigma_i$ a.s. reaches $\sigma_i+1$ (but the expected time of first transition is infinite). And it can be shown that in fact the process does visit each point in the chain sequentially, a.s. Of course, one example does not prove the implication!

$\endgroup$
2
  • $\begingroup$ If "the transition probabilities from $s_i \to s_j$ at time $t$ are permitted to depend not only on the state at time $t−1$ but also on all previous states", this is not what I'd call a Markov process with the given set of states. Perhaps you can call it a Markov process on a different state space $\bigcup_n S^n$, where the new "state" incorporates the history of the process. $\endgroup$ Feb 22, 2016 at 18:39
  • $\begingroup$ That's true. I originally framed this in terms of Markov processes of finite depth, but since I had a feeling that the answer was going to be that the implication holds anyway, I wanted to make the original "givens" as weak as was practical, so as to make the implication as meaningful as was practical. $\endgroup$ Feb 22, 2016 at 19:37

1 Answer 1

0
$\begingroup$

Since you speak of "time $t-1$", presumably this is a discrete-time process: all "times" will be integers.

Let $A_k$ be the event that the finite sequence $\sigma_0, \ldots, \sigma_k$ occurs (i.e. that there exist $0 \le t_0 < t_1 < \ldots < t_k$ such that $X(t_j) = \sigma_j$, $0 \le j \le k$). If all $A_k$ occur, then the infinite sequence $\sigma$ occurs. Namely, let $s_j$ be the least time $s > s_{j-1}$ such that $X(s) = \sigma_j$, and prove by induction that $s_j$ exists. Thus if the infinite sequence does not a.s. occur, there must be some $k$ such that $P(A_k) < 1$. Take the least such $k$, and you get a contradiction of your hypothesis.

$\endgroup$

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.