Applications of some formulas for finite Markov chains (Q617702)

The authors describe how some elementary computations with finite state Markov chain transition matrices lead to interesting and promising applications. The computations and sample applications are based on two observations. The first one is that the product of the transition matrix interlaced with projections on states of interest gives probabilities along corresponding subsets of paths. The scond observation is a discrete version of the Feynman-Kac formula. Finally four applications are presented. In one of these applications the two observations are combined to yield an effective computational method for evaluating the expected value (over paths) of a function of the sum of path attributes; each path starts at a specific point within a subset of states, and ends when the path exits the given subset for the first time. At the same time they describe some sample problems for which their methods may be of use. The authors propose, in another application, a variant of the occasionally used approach to calculate solutions to a large class of Dirichlet-Poisson boundary value problems via diffusion. The proposed method finds the exact solution for each discretization of the continuous boundary value problem. It is emphasized that the existing stochastic methods of which they are aware rely on Monte Carlo simulations and thus require a large number of trials to achieve good accuracy.