This paper is devoted to computational problems related to Markov chains (MC) on a finite state space. We present formulas and bounds for characteristics of MCs using directed forest expansions given by the Matrix Tree Theorem. These results are applied to analysis of direct methods for solving systems of linear equations, aggregation algorithms for nearly completely decomposable MCs and the Markov chain Monte Carlo procedures.

The Bruhat order is defined in terms of an interchange operation on the set of permutation matrices of order $n$ which corresponds to the transposition of a pair of elements in a permutation. We introduce an extension of this partial order, which we call the stochastic Bruhat order, for the larger class ${\Omega }_n$ of doubly stochastic matrices (convex hull of $n\times n$ permutation matrices). An alternative description of this partial order is given. We define a class of special faces of ${\Omega }_n$ induced by permutation matrices,...

The present paper focuses on the dynamics of doubly stochastic quadratic operators (d.s.q.o) on a finite-dimensional simplex. We prove that if a d.s.q.o. has no periodic points then the trajectory of any initial point inside the simplex is convergent. We show that if d.s.q.o. is not a permutation then it has no periodic points on the interior of the two dimensional (2D) simplex. We also show that this property fails in higher dimensions. In addition, the paper also discusses the dynamics classifications...