Michael Grabchak

Title: Insertion – A New Operation for Markov Chains and their Applications

Abstract: It is well known that a Markov chain (MC), observed only when it is outside of a subset D, is again a MC, called the Censored MC, with a new transition matrix. This matrix can be obtained in |D| iterations, each requiring O(n^2) operations, when the states from D are “eliminated” one at a time. We show how to modify these iterations to allow for a state, previously eliminated, to be “reinserted” into the  state space in one iteration. This modification sheds a new light on the relationship between an initial and censored MC, and introduces a new operation – “insertion” into the theory of MCs. We briefly describe the applications of these operations in different probability models, and even outside of Probability Theory.

Title: Dynamical systems and stochastic processes Part 2