In my pursuit of an Ergodic Theorem for Random Walks on (probably finite) Quantum Groups, I have been looking at analogues of Irreducible and Periodic. I have, more or less, got a handle on irreducibility, but I am better at periodicity than aperiodicity.

The question of how to generalise these notions from the (finite) classical to noncommutative world has already been considered in a paper (whose title is the title of this post) of Fagnola and Pellicer. I can use their definition of periodic, and show that the definition of irreducible that I use is equivalent. This post is based largely on that paper.

Introduction

Consider a random walk on a finite group G driven by \nu\in M_p(G). The state of the random walk after k steps is given by \nu^{\star k}, defined inductively (on the algebra of functions level) by the associative

\nu\star \nu=(\nu\otimes\nu)\circ \Delta.

The convolution is also implemented by right multiplication by the stochastic operator:

\nu\star \nu=\nu P,

where P\in L(F(G)) has entries, with respect to a basis (\delta_{g_i})_{i\geq 1} P_{ij}=\nu(g_jg_{i^{-1}}). Furthermore, therefore

\nu^{\star k}=\varepsilon P^k,

and so the stochastic operator P describes the random walk just as well as the driving probabilty \nu.

The random walk driven by \nu is said to be irreducible if for all g_\ell\in G, there exists k\in\mathbb{N} such that (if g_1=e) [P^k]_{1\ell}>0.

The period of the random walk is defined by:

\displaystyle \gcd\left(d\in\mathbb{N}:[P^d]_{11}>0\right).

The random walk is said to be aperiodic if the period of the random walk is one.

These statements have counterparts on the set level.

If P is not irreducible, there exists a proper subset of G, say S\subsetneq G, such that the set of functions supported on S are P-invariant.  It turns out that S is a proper subgroup of G.

Moreover, when P is irreducible, the period is the greatest common divisor of all the natural numbers d such that there exists a partition S_0, S_1, \dots, S_{d-1} of G such that the subalgebras A_k of functions supported in S_k satisfy:

P(A_k)=A_{k-1} and P(A_{0})=A_{d-1} (slight typo in the paper here).

In fact, in this case it is necessarily the case that \nu is concentrated on a coset of a proper normal subgroup N\rhd G, say gN. Then S_k=g^kN.

Suppose that f is supported on g^kN. We want to show that for Pf\in A_{k-1}. Recall that 

\nu^{\star k-1}P(f)=\nu^{\star k}(f).

This shows how the stochastic operator reduces the index P(A_k)=A_{k-1}.

A central component of Fagnola and Pellicer’s paper are results about how the decomposition of a stochastic operator:

P(f)=\sum_{\ell}L_\ell^*fL_{\ell},

specifically the maps L_\ell can speak to the irreducibility and periodicity of the random walk given by P. I am not convinced that I need these results (even though I show how they are applicable).

Stochastic Operators and Operator Algebras

Let F(X) be a \mathrm{C}^*-algebra (so that X is in general a  virtual object). A \mathrm{C}^*-subalgebra F(Y) is hereditary if whenever f\in F(X)^+ and h\in F(Y)^+, and f\leq h, then f\in F(Y)^+.

It can be shown that if F(Y) is a hereditary subalgebra of F(X) that there exists a projection \mathbf{1}_Y\in F(X) such that:

F(Y)=\mathbf{1}_YF(X)\mathbf{1}_Y.

All hereditary subalgebras are of this form.

A stochastic operator P is irreducible if there exists no proper hereditary P-invariant \mathrm{C}^*-subalgebra of F(X).

Classically, the proper hereditary subalgebras are algebras of the form F(S) with S\subsetneq G. In the case of random walks on groups, we need only look at subgroups rather than all subsets.

Fagnola points out that the appropriate generalisation in the noncommutative case is not merely a subalgebra but a hereditary subalgebra. Fagnola gives some references I must see how this result interacts with my results on irreducible random walks on (finite) quantum groups. Looking ahead there is a choice between equivalent definitions:

  • no proper P-invariant hereditary subalgebras, and
  • no non-trivial P–subharmonic projections,

and as they are equivalent, and Fagnola and Pellicer go on to prove an ergodic theorem and so this is perfect… although I also read that Fagnola and Pellicer say that this is not new, and they are primarily interested in the result for completely bounded maps… another paper title Spectral Properties of Positive Maps on \mathrm{C}^*-algebras is referenced by Fagnola and Pellicer

Irreducible Positive Maps

Fagnola and Pellicer prove that:

Theorem 3.2

A stochastic operator P\in L(F(G)) is irreducible if and only if for all projections p,

P(p)\geq p\Rightarrow p=0\text{ or }\mathbf{1}_G \bullet

They also show that the spectrum of P, \sigma(P)\subset \mathbb{D}, the unit disk.

Proposition 3.4

A stochastic operator P\in L(F(G)) with a non-trivial fixed point is not irreducible \bullet

Constant functions are certainly eigenvectors of eigenvalue one. If there is a non-constant fixed points we have a second eigenvalue equal to one. If P is irreducible, this is not the case.

Proposition 3.4

An irreducible stochastic operator has a unique faithful invariant state \bullet

In the (finite) quantum group case, this is the Haar state \displaystyle \pi:=\int_G.

At this point Fagnola and Pellicer ask that P be a Schwarz Map. In the random walk case, the stochastic operator is in fact completely positive and so Schwarz (proof in a paper in preparation).

Periodic Stochastic Operators

Let P be an irreducible stochastic operator. A partition of unity (F+P say resolution of the identity) p_0,p_1,\dots,p_{d-1} is called P-cyclic if the hereditary subalgebra p_kF(X)p_k is mapped to the hereditary p_{k-1}F(x)p_{k-1} by P. If there exists such a partition such that d\geq 2, then the random walk given by P is periodic.

Classically, we have a partition of \displaystyle G=\bigcup_{k=0}^{d-1}S_k, and the random walk bounces around the S_k in a cyclic way, and the support of \nu^{\star k} will be concentrated on such subsets. For the case of a random walk on a group, S_0=N\rhd G, and S_k=g^kN.

For random walks on (finite) quantum groups:

Proposition 4.1

Let P be an irreducible stochastic operator for a random walk on a finite quantum group. A partition of unity p_0,\dots,p_{d-1} is cyclic for P if and only if:

P(p_k)=p_{k-1}.

Furthermore:

Theorem 4.3

Let P be an irreducible stochastic operator for a random walk on a finite quantum group. The following are equivalent:

  • \exists a P-cyclic partition of unity
  • \sigma(P)\cap \mathbb{T} contains all the d-th roots of unity.

This provides a non-commutative generalisation of the standard ergodic theorem. Think in terms of eigenvalues. If there exists a P-cyclic partition of unity with d\geq 2), then e^{2\pi i/d}\in\sigma(P) and so we do not have convergence.

Therefore, for convergence, one must be irreducible AND have only a trivial P-cyclic partition of unity. Assume this in the prequel. Theorem 3.7 says that \sigma(P)\cap\mathbb{T} is a finite subgroup. Therefore there cannot be an irrational \alpha such that e^{i\alpha}\in\sigma(P).

Could there be a rational q such that e^{iq}\in\sigma(P)? The spectrum is a group and so if q=m/n, all the n-th roots of unity are in the spectrum and so, by assumption n=1…

Therefore if there is no non-trivial P-cyclic partition of unity, then \sigma(P)\cap \mathbb{T}=\{1\} and the convergence of P^k follows.

Conclusion

Idea: take a random walk on a (finite) quantum group. Assume that the driving probability is not concentrated on a quasi-subgroup. Assume that the stochastic operator T_\nu\in L(F(G)) has a cyclic partition of unity with d>1. Construct some kind of an object such that the projections in the partitions of unity are the identities on the cosets, and that the support of \nu lies on one of them… the cyclic group to appear.

Summary

We have a zoo of results. From quantum to classicial, from spectral to algebraic, from sets to groups.

The fundamental result in this analysis is spectral. At this point we define a stochastic operator to be a completely positive and unital operator on a \mathrm{C}^*-algebra F(X). Examples include the stochastic operator of a random walk on a compact quantum group and the stochastic operator of a classical Markov chain. We do not always need completely bounded for these results.

As we are primarily interested in

irreducible + aperiodic = ergodic,

and the usual thing is to establish irreducibility and then look at aperiodicity assuming irreducibility. In a paper in preparation, I sometimes study periodicity not assuming irreducibilty. Perhaps assuming irreducibilty might help my look at periodicity. Let us not look at reducible + aperiodic (although I am fairly sure) we can restrict such stochastic operators to ergodic ones.

Spectral Picture

This is basically finite dimensional linear algebra. Let P\in L(F(X)) be a stochastic operator.

  • We have that \sigma(P)\subset \mathbb{D}. In particular, 1\in \sigma(P).
  • If 1 is a simple eigenvalue, then P is said to be irreducible. A non-trivial fixed point h\in F(X) should give rise to non-faithful invariant states to which \mu P^k can converge to.
  • Assuming irreducibility, if \sigma(P)\cap \mathbb{T}=\{1\}, then (P^k) converges (aperiodic).  Otherwise P^k does not converge (periodic).
  • In the case of irreducible + aperiodic, P^k converges to P_\infty:

P_\infty(F(X))=\mathbb{C}\mathbf{1}_X.

Algebra of Functions Picture

This is the topic of the paper of Fagnola and Pellicer.

  • P(F(X)_1^+)\subset F(X)_1^+.
  • A stochastic operator is irreducible if for all projections p\in F(X), P(p)\geq p\Rightarrow p=0 or \mathbf{1}_X. A reducible stochastic operator has a projection q\in F(X) such that P(q)=q (recall \|P\|=1). This should correspond to a non-faithful invariant state \nu_qP=\nu_q.
  • Assuming irreducibility, a stochastic operator is aperiodic if and only if the only partition of unity (p_i\,:\,i=0,\dots,d-1) such that

P(p_i)=p_{i-1},

          is the trivial p_0=\mathbf{1}_X. Otherwise P^k does not converge.

  • In the case of irreducible + aperiodic, for all \mu\in M_p(X), \mu P^k\rightarrow \pi, where \pi\in M_p(X) is the unique faithful P-invariant state, and P is called ergodic.

Random Walks on (Finite) Quantum Groups Picture

This is the topic of my paper in preparation. For any random walk driven by \nu\in M_p(G), the stochastic operator:

T_\nu:=(\nu\otimes I_{F(G)})\circ \Delta,

and the support projection of \nu is the the smallest projection p_\nu\in F(G) such that \nu(p_\nu)=1.

  • M_p(G)T_\nu\subset M_p(G)
  • T_\nu is irreducible if and only if the \nu is NOT supported on a proper-quasi-subgroup (if the support projection is a group-like projection not equal to \mathbf{1}_G).
  • Assuming irreducibility…. this is where we are stuck but we can use the language of Fagnola and Pellicer.
  • In the case of irreducible + aperiodic, for all \mu\in M_p(G), \nu^{\star k}\rightarrow \pi, where \pi\in M_p(G) is the Haar state, and the random walk driven by \nu is ergodic.

Classical Markov Chain (Random Variable) Picture

For a stochastic operator [P]_{yz}=\mathbb{P}[\xi_{k+1}=z\,|\,\xi_k=y]

  • M_p(G)P\subset M_p(G)
  • P is irreducible if and only if for all y,z\in X, there exists k\in\mathbb{N} such that

\mathbb{P}[\xi_k=z\,|\,\xi_0=y]>0

  • Assuming irreducibility, a markov chain is aperiodic if for all y\in X, the state y\in X‘s period:

\text{gcd}\left\{n>0\,|\,\mathbb{P}[\xi_n=y\,|\,\xi_0=n]>0\right\}=1.

  • In the case of irreducible + aperiodic, the distribution converges to a unique stationary, strict \pi\in M_p(X) in the sense that as k\rightarrow \infty:

\mathbb{P}[\xi_k=y]\rightarrow \pi(y)

Random Walks on (Finite Classical) Groups Picture

For any random walk driven by \nu\in M_p(G)

  • (\nu\star \nu)\subset M_p(G)
  • \nu is irreducible if and only if the \nu is NOT supported on a proper-subgroup
  • Assuming irreducibility, the random walk is aperiodic if \nu is not supported on the coset of any proper normal subgroup.
  • In the case of irreducible + aperiodic, \nu^{\star k}\rightarrow \pi, where \pi\in M_p(G) is the uniform distribution, and the random walk driven by \nu is ergodic.