This paper studies the problem of ergodicity of transition probability matrices in Markovian models, such as hidden Markov models (HMMs), and how it makes very difficult the task of learning to represent long-term context for sequential data. This phenomenon hurts the forward propagation of long-term context information, as well as learning a hidden state representation to represent long-term context, which depends on propagating credit information backwards in time. Using results from Markov chain theory, we show that this problem of diffusion of context and credit is reduced when the transition probabilities approach 0 or 1, i.e., the transition probability matrices are sparse and the model essentially deterministic. The results found in this paper apply to learning approaches based on continuous optimization, such as gradient descent and the Baum-Welch algorithm.

We study the asymptotic behaviour of points under matrix cocyles generated by rectangular matrices. In particular we prove a random Perron-Frobenius and a Multiplicative Ergodic Theorem. We also provide an example where such products of random rectangular matrices arise in the theory of random walks in random environments and where the Multiplicative Ergodic Theorem can be used to investigate recurrence problems. Key words: random dynamical system, products of random matrices, random walks in...

Inspired by the work of Daubechies and Lagarias on a set of matrices with convergent infinite products, we study the geometric approach to the classical problem of (weakly) ergodic non-homogeneous Markov chains. The existing key inequalities (related to the Hajnal inequality) in the literature are unified in this geometric picture. A more general inequality is established. Important quantities introduced by various authors are easily interpreted. A quantitative connection is established between ...

In this paper we prove exponential asymptotic stability for discrete time filters for signals arising as solutions of d-dimensional stochastic difference equations. The observation process is the signal corrupted by an additive white noise of su#ciently small variance. The model for the signal admits non-ergodic processes. We show that almost surely, the total variation distance between the optimal filter and an incorrectly initialized filter converges to 0 exponentially fast as time ...

Three algorithms for the model reduction of large-scale, continuous-time, timeinvariant, linear, dynamical systems with a sparse or structured transition matrix and a small number of inputs and outputs are described. They rely on low rank approximations to the controllability and observability Gramians, which can eciently be computed by ADI based iterative low rank methods. The rst two model reduction methods are closely related to the well-known square root method and Schur method, which are...

this paper we?ll formulate the results in terms of random walks, and mostly restrict our attention to the undirected case. 2 L. Lov?asz

The resistance between arbitrary two nodes in a resistor network is obtained in terms of the eigenvalues and eigenfunctions of the Laplacian matrix associated with the network. Explicit formulas for two-point resistances are deduced for regular lattices in one, two, and three dimensions under various boundary conditions including that of a Moebius strip and a Klein bottle. The emphasis is on lattices of finite sizes. We also deduce summation and product identities which can be used to analyze large-size expansions of two-and-higher dimensional lattices.