Activities This Week

The mixing time is a fundamental quantity measuring the rate of convergence of a Markov chain towards its stationary distribution. We will discuss the problem of estimating the mixing time from one single long trajectory of observations. The reversible setting was addressed using spectral methods by Hsu et al. (2015), who left the general case as an open problem. In the reversible setting, the analysis is greatly facilitated by the fact that the Markov operator is self-adjoint, and Weyl’s inequality allows for dimension-free perturbation analysis of the empirical eigenvalues. In the absence of reversibility, the existing perturbation analysis has a worst-case exponential dependence on the number of states. Furthermore, even if an eigenvalue perturbation analysis with better dependence on the number of states were available, in the non-reversible case the connection between the spectral gap and the mixing time is not nearly as straightforward as in the reversible case. We design a procedure, using spectral methods, that allows us to overcome the loss of self-adjointness and to recover a sample size with a polynomial dependence in some natural complexity parameters of the chain. Additionally, we will present an alternative estimation procedure that moves away from spectral methods entirely and is instead based on a generalized version of Dobrushin’s contraction. Joint work with Aryeh Kontorovich.

Estimating the Mixing Time of Ergodic Markov Chains Geoffrey Wolfer, Aryeh Kontorovich - COLT2019 http://proceedings.mlr.press/v99/wolfer19a.html
https://arxiv.org/abs/1902.01224

Mixing Time Estimation in Ergodic Markov Chains from a Single Trajectory with Contraction Methods Geoffrey Wolfer - ALT2020 https://arxiv.org/abs/1912.06845

The theory of non-commutative (nc) rational functions which are regular at 0 is well known and studied, in terms of their minimal realizations: any such function admits a unique minimal realization centred at 0 and the domain of the function coincides with the invertibility set of the (resolvent of the) realization. In addition, a nc power series around the origin will be the power series expansion of a nc rational function if and only if a given Hankel matrix built from the coefficients of the given power series has a finite rank (Fliess-Kronecker).

In this talk, we present generalizations of these ideas to the case where the centre is non-scalar. In particular, we prove the existence and uniqueness of a minimal Fornasini-Marchesini realization for every nc rational function, centred at an arbitrary matrix point in its domain of regularity, and show that using this realization, one can evaluate the function on all of its domain (of matrices of all sizes).

Unlike the case of a scalar centre, the coefficients of the realization can not be chosen arbitrarily. We present necessary and sufficient conditions (called the linearized lost-abbey conditions) on the coefficients of a minimal realization centred at a matrix point, such that there exists a nc rational function which admits the realization.

This is a joint work with Victor Vinnikov.

The commutative DG rings in the title are more commonly known as “nonpositive strongly commutative unital differential graded cochain K-algebras”, where K is a commutative base ring. In the literature the standard assumption is that K is a field of characteristic zero - but one of our themes in this talk is that this assumption is superfluous (K = Z works just as well).

There are two kinds of derived categories ralated to commutative DG rings. First, given a DG ring A, we can consider D(A), the derived category of DG A-modules, which is a K-linear triangulated category. This story is well understood by now, and I will only mention it briefly.

In this talk we shall consider another kind of derived category. Let DGRng denote the category whose objects are the commutative DG rings (the base K is implicit), and whose morphisms are the DG ring homomorphisms. The derived category of commutative DG rings is the category D(DGRng) gotten by inverting all the quasi-isomorphisms in DGRng. (In homotopy theory the convention is to call it the “homotopy category”, but this is an unfortunate historical accident.)

I will define semi-free DG rings, and prove their existence and lifting properties. Then I will introduce the quasi-homotopy relation on DGRng, giving rise to the quotient category K(DGRng), the “genuine” homotopy category. One of the main results is that the canonical functor from K(DGRng) to D(DGRng) is a faithful right Ore localization.

I will conclude with a theorem on the existence of the left derived tensor product inside D(DGRng), and with the pseudofunctor from D(DGRng) to the TrCat, sending a DG ring A to the triangulated category D(A).

Next semester I will talk about the geometrization of these ideas: “The Derived Category of Sheaves of Commutative DG Rings”.