Censored Markov Chains - a Powerful Tool in Probability Theory and its Applications.

Add to your list(s) Download to your calendar using vCal

• Isaac M. Sonin (University of North Carolina, Charlotte, USA)
• Thursday 23 March 2017, 12:00-13:00
• University House, 110.

If you have a question about this talk, please contact Sergey Sergeev.

An important, though not well-known tool for the study of Markov chains (MCs) is the notion of a Censored (Embedded) MC. It is based on a simple and insightful idea of Kolmogorov and Doeblin: a MC observed only on a subset of its state space is again a MC with a reduced state space and a new transition matrix. The sequential application of this idea leads to an amazing variety of important algorithms in Probability Theory and its Applications. The brief list of such Applications and algorithms is as follows.

A. State Reduction approach to recursively calculate many important characteristic of MCs, e.g. GTH /S algorithm to calculate the limiting distribution of an ergodic MC.

B. The solution of the Optimal stopping of MCs. In deterministic terms this is equivalent to the solution of the Bellman equation v = max(g; c+Pv), where c(x) is a one step reward function, g(x) is a terminal reward function, v is the value function and P is an averaging operator.

C. An algorithm to calculate the well-known Gittins Index and so called Generalized Gittins Index. Their relationship with Katehakis-Veinot and Whittle indices. Evolution of random graphs and Gittins theorem in a general form.

D. There is a remarkable theorem in the theory of finite MCs – the MC Tree theorem (MCTT), initially discovered by G. Kirchhoff, which expresses the limiting distribution for an ergodic MC in terms of directed spanning trees and a transition matrix. This theorem serves as a bridge between MCs and Graph Theory. The applications of MCTT were limited by the fact that the number of trees directed to a point grows exponentially. In my paper (Adv. in Mathematics, 1999) it was noted and proved that there is a polynomial algorithm to calculate a crucial characteristic in this theorem. Recently in B. Benek Gursoy, S. Kirkland, O. Mason and S. Sergeev 2015, (The Markov Chain Tree Theorem in commutative semirings and the State Reduction Algorithm in commutative semields, Linear Algebra and its Applications), this algorithm and corresponding theorem were generalized to the case of so called idempotent (tropical) calculus.

E. One of the main approaches to studying Markov models with large and “very large” state spaces is based on the idea of selecting “clusters” – groups of states with many strong connections inside the cluster and weak connections between clusters. There is a more narrow model – called the “Islands” and “Ports” model, which allows us to obtain exact results in such a way that the main volume of calculations is performed in parallel.

In my talk I will briefly touch on a couple of other questions: Continue, Quit, Restart model and Insertion, a new operation for MCs; Some Remarks about Independence; Decomposition-Separation (DS) Theorem, describing the behaviour of a family of nonhomogeneous MCs defined by the sequence of stochastic matrices (Pn) when there are no assumptions about this sequence; Tanks model of clearing in financial networks.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• Optimisation and Numerical Analysis Seminars
• School of Mathematics events
• University House, 110

Note that ex-directory lists are not shown.