# Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce Markov chains this way but then quickly restrict themselves to the time-homogeneous case where you have one transition matrix.

Obviously, in general such Markov chains might not converge to a unique stationary distribution, but I would be surprised if there isn't a large (sub)class of these chains where convergence is guaranteed. I'm particularly interested in theorems on the mixing time and convergence theorems that state when there exists a stationary distribution.

-
Cross-posted from cstheory.stackexchange.com/q/22698/23060 – Daniel Moskovich May 28 '14 at 8:34
Note that you can homogenise the chain. If $X=(X_t:t \geq 0)$ is an inhomogeneous Markov chain on $E$ then $(X_t,t)$ is a homogeneous Markov chain on $E \times \mathbb Z^+$ (see Revuz and Yor Chapter III Excercise 1.10). – Bati May 28 '14 at 10:39
@Bati: Except for the fact that space-time chains have no stationary distributions – R W May 28 '14 at 11:50
@R W: You are right. – Bati May 28 '14 at 15:08

Stroock's Markov processes book is, as far as I know, the most readily accessible treatment of inhomogeneous Markov processes: he does all the basics in the context of simulated annealing, which is neat. Kleinrock's volume 1 is also of interest, though "buggy" IIRC.

In my experience the key object is the propagator $U(t) := \mathcal{TO}^* \int_0^t Q(s) \ ds$, where $Q$ is the time-dependent generator and $\mathcal{TO}^*$ is the formal adjoint or reverse time-ordering operator (see here and here for forward time-ordering). With this in hand, the transition kernel can be expressed as $P(s,t) = U^{-1}(s)U(t)$. Thus, e.g., an initial distribution $p(0)$ is propagated as $p(t) = p(0)U(t)$, which gives you the essential stuff to get a handle on (e.g.) mixing times.

One way to guarantee convergence is to have $U(t)$ varying within the group fixing a distribution, cf. Has the Lie group preserving a probability distribution been used in Bayesian statistics?

As another push towards your goal, the Dynkin martingale formula becomes (under suitable conditions, e.g., $t \mapsto f_t$ is $C^1$ and $f_t(X_t)$ is bounded) $$\mathbb{E}(f_t(X_t)-f_0(X_0)) = \mathbb{E}\int_0^t(\partial_s+Q(s))f_s \circ X_s \ ds$$ Here Rogers and Williams IV.20-21 is of interest, since the extension to inhomogeneous processes is trivial.

Finally, I will note that the cutest time-inhomogenous Markov process is the Poisson process, cf. http://blog.eqnets.com/2009/07/28/why-poissonian-traffic-models-matter-more-now-than-ever-part-4/

-
I would like to add that in the field of differential equations on Banach spaces (which contain time continuous Markov chains as special cases) transition matrices that can vary over time become time-dependent operators. There is a well-developed (if not very elementary) theory for this kind of problems, which starts by replacing $C_0$-semigroups by objects called "evolution families". And yes, much is known the long time behavior of this kind of problems: see e.g. www.math.kit.edu/iana3/~schnaubelt/media/survey1.pdf – Delio Mugnolo May 29 '14 at 21:33

You don't find much about time-inhomogeneous Markov chains because it's extremely difficult to prove anything about them without strong additional assumptions, and it's not clear what additional assumptions make sense. The only literature I'm aware of is some quite recent papers by Jessica Zúñiga and Laurent Saloff-Coste; see this page for links. (If there is any prior literature on the problems you're interested in, I'm sure those papers have references.)

-

Interestingly enough, one can prove Azume-Hoeffding and Talagrand-type concentration inequalities for inhomogeneous Markov chains using contraction-type conditions:

Concentration of measure inequalities for Markov chains and \Phi-mixing processes http://projecteuclid.org/euclid.aop/1019160125

Concentration inequalities for dependent random variables via the martingale method http://projecteuclid.org/euclid.aop/1229696598

Obtaining Measure Concentration from Markov Contraction http://dl.dropboxusercontent.com/u/3198145/mark-conc2.pdf

-