19
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Cross-posted from cstheory.stackexchange.com/q/22698/23060 $\endgroup$
    – Daniel Moskovich
    Commented May 28, 2014 at 8:34
  • $\begingroup$ 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). $\endgroup$
    – Bati
    Commented May 28, 2014 at 10:39
  • 6
    $\begingroup$ @Bati: Except for the fact that space-time chains have no stationary distributions $\endgroup$
    – R W
    Commented May 28, 2014 at 11:50
  • $\begingroup$ @R W: You are right. $\endgroup$
    – Bati
    Commented May 28, 2014 at 15:08

5 Answers 5

Reset to default
9
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The link doesn't work. $\endgroup$
    – Math1000
    Commented May 9, 2018 at 8:08
7
$\begingroup$

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/

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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 $\endgroup$
    – Delio Mugnolo
    Commented May 29, 2014 at 21:33
  • $\begingroup$ @SteveHuntsman The link to the blog post no longer works, fortunately it was saved here: web.archive.org/web/20150617061708/http://blog.eqnets.com/2009/… $\endgroup$
    – Math1000
    Commented Aug 31, 2016 at 5:07
3
$\begingroup$

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 https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf

Improve this answer
$\endgroup$
2
$\begingroup$

There is also the (old) book of Seneta: Non-negative Matrices and Markov Chains. First edition: 1973. See chapters 3-4.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Second ed 1981. $\endgroup$
    – Janos Englander
    Commented Aug 5, 2020 at 0:06
1
$\begingroup$

You may be interested in https://www.sciencedirect.com/science/article/pii/S016771520800271X

For a more abstract set up: There is the Birkhoff Hopf Theorem which is used to prove the strict contraction of the Hilbert metric for the product of positive matrices. (https://www.jstor.org/stable/pdf/1992971.pdf?casa_token=2mX8IdHWexkAAAAA:9z0FIWE5FbADdzqF0cE1NdRzSGcmFPNMjmgO-M_iV_zvmdQWhj_t-qKVrBzZZn4TL_FDN7PFOx8gJrwyzcW7CibNJiUOF1ubuJDlcQORt9MFtL9CjA)

This implies a mixing property (exponentially in time) if your (multiplication of) transitive matrices have strictly positive coefficients (or if the operator is of positive Kernel).

I think this is what is used in the book of Seneta "Non-negative Matrices and Markov Chains" (chapter 3: "Inhomogeneous Products of Non-negative Matrices")

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .