Taken from Random Walks on Finite Quantum Groups by Franz & Gohm

In this section we will show how one can recover a classical Markov chain from a quantum Markov chain. We will apply a folklore theorem that says one gets a classical Markov process, if a quantum Markov process can be restricted to a commutative algebra.

We might like to do more. This result recovers a Markov chain — if the quantum process is in fact a random walk on a finite quantum group can we recover the group, the transition probabilities (yes), the driving probability measure?? 


If we restrict a random walk on a finite quantum group to a commutative subalgebra we can recover a random walk on a finite group.

For random walks on quantum groups we have the following result.

Theorem 6.1

Let A be a finite quantum group \{j_n\}_{n\geq 0} a random walk on a finite dimensional A-comodule algebra B, and B_0 a unital abelian sub-*-algebra of B. The algebra B_0 is isomorphic to the algebra of functions on a finite set, say B_0\cong F(X) where X={1,\dots,d}.

If the transition operator T_\phi of \{j_n\}_{n\geq 0} leaves B_0 invariant, then there exists a classical Markov chain \{\xi_n\}_{n\geq 0} with values in X, whose probabilities can be computed as time-ordered moments of \{j_n\}_{n\geq 0}, i.e.

P(\xi_0=i_0,\dots,\xi_\ell=i_\ell)=\Psi\left(j_0\left(\mathbf{1}_{\{i_0\}}\right)\cdots j_\ell\left(\mathbf{1}_{\{i_\ell\}}\right)\right)

for all \ell\geq 0 and i_0,\dots,i_\ell\in X.

Proof : We use the indicator functions \mathbf{1}_{\{1\}},\dots,\mathbf{1}_{\{d\}},

\mathbf{1}_{\{i\}}(j)=\delta_{ij}1\leq i,\,j\leq d,

as a basis for B_0\subset B. They are positive, therefore

\lambda_1=\Psi\left(j_0\left(\mathbf{1}_{\{1\}}\right)\right), …, \lambda_d=\Psi\left(j_0\left(\mathbf{1}_{\{d\}}\right)\right)

are non-negative. Since furthermore


these numbers define a probability measure on X.

Define now \{(p(i,j))\}_{1\leq i,j\leq d} by

\displaystyle T_\phi\left(\mathbf{1}_{\{j\}}\right)=\sum_{i=1}^dp(i,j)\mathbf{1}_{\{i\}}.

Since T_\phi=(I_{F(X)}\otimes \phi)\circ\Delta is positive (\checkmark), we have p(i,j)\geq 0 for 1\leq i,\,j\leq d. Furthermore, T_\phi(\mathbf{1})=\mathbf{1} implies

\displaystyle \mathbf{1}=T_\phi(\mathbf{1})=T_\phi\left(\sum_{j=1}^d\mathbf{1}_{\{j\}}\right)=\sum_{j=1}^d\sum_{i=1}^dp(i,j)\mathbf{1}_{\{i\}}=\sum_{i=1}^d\mathbf{1}_{\{i\}}\underbrace{\sum_{j=1}^dp(i,j)}_{\overset{!}{=}1}.

Hence [p(i,j)]_{1\leq i,\,j\leq d} is a stochastic operator.

Therefore there exists a unique Markov chain \{\xi_n\}_{n\geq 0} with initial distribution \{\lambda_{i}\}_{1\leq i,\,j\leq d} and transition matrix \{p(i,j)\}_{1\leq i,\,j\leq d}.

We show by induction that the equation in the theorem statement holds.

For \ell=0 this is clear by the definition of \lambda_1,\dots,\lambda_d. Suppose now that \ell\geq 1 and i_0,\dots,i_\ell\in X. Then we have

\Psi\left(j_0(\mathbf{1}_{\{i_0\}})\cdots j_\ell(\mathbf{1}_{\{i_\ell\}})\right)

=\Psi\left(j_0(\mathbf{1}_{\{i_0\}})\cdots j_{\ell-1}(\mathbf{1}_{\{i_{\ell-1}\}})\left(j_{\ell-1}({\mathbf{1}_{\{i_\ell\}}}_{(1)})\otimes{\mathbf{1}_{\{i_\ell\}}}_{(2)}\right)\right)

=\Psi\left(j_0(\mathbf{1}_{i_0})\cdots j_{\ell-1}(\mathbf{1}_{\{i_{\ell-1}\}}{\mathbf{1}_{\{i_\ell\}}}_{(1)})\right)\phi\left({\mathbf{1}_{\{i_\ell\}}}_{(2)}\right)

=\Psi\left(j_0(\mathbf{1}_{\{i_0\}})\cdots j_{\ell-1}\left(\mathbf{1}_{\{i_{\ell-1}\}}T_\phi(\mathbf{1}_{\{i_\ell\}})\right)\right)

=\Psi\left(j_0(\mathbf{1}_{\{i_0\}})\cdots j_{\ell-1}(\mathbf{1}_{\{i_{\ell-1}\}})\right)p(i_{\ell-1},i_{\ell})

=\lambda_{i_0}p(i_0,i_1)\cdots p(i_{\ell-1},i_\ell)

=P(\xi_0=i_0,\dots,\xi_\ell=i_\ell) \bullet


If the condition that T_\phi leaves A_0 invariant is dropped, then one can still compute the “probabilities” but in general they are no longer positive or even real, and so it is impossible to construct a classical stochastic process \{\xi_n\}_{n\geq 0} from them.


The comodule algebra B=\mathbb{C}^4 that we considered here is abelian, so we can take B_0=B. For any pair of states \psi on B and \phi on A (the Kac-Paljutkin quantun group), we get a random walk on B and a corresponding Markov chain on X={1,2,3,4}. We identify F(X) with B by v_i\equiv\mathbf{1}_{\{i\}} for i\in X.

The initial distribution is given by \lambda_i=\psi(v_i) and the transition matrix is given by (3.1) on page 10.


Let us now consider random walks on the Kac-Paljutkin quantum group A itself. For the defining relations, the calculation of the dual of A and a parameterisation of all states see here. Let us consider here transition states of the form


with the \mu_i positive real numbers summing to 1.

The transition operators T_\phi=(I_A\otimes\phi)\circ\Delta of these states leave the abelian subalgebra A_0=\text{Lin}\{e_1,e_2,e_3,e_4\}\cong \mathbb{C}^4 invariant. The transition matrix of the associated classical Markov chain on X=\{1,2,3,4\} that arises by identifying e_i\equiv\mathbf{1}_{\{i\}} for i\in X has the form


This actually the transition matrix of a random walk on the the group \mathbb{Z}_2\times\mathbb{Z}_2.

A pertinent point here is that in this case we actually have a random walk on a finite group rather than just an ordinary Markov chain. If we had an ordinary Markov chain there is no distinction between \mathbb{Z}_2\times\mathbb{Z}_2 and \mathbb{Z}_4. In fact a quick calculation shows that this is the stochastic operator of the random walk driven by the probability \nu\in M_p(\mathbb{Z}_2\times\mathbb{Z}_2) 

\nu((0,0))=\mu_1\nu((1,0))=\mu_2\nu((0,1))=\mu_3 and \nu((1,1))=\mu_4.

Could it be the the stochastic operator of a random walk on \mathbb{Z}_4 — well not always because these have to be circulant matrices. The only time when this stochastic operator is circulant is when \mu_2=\mu_4

The subalgebra \text{Lin}\{a_{11},a_{12},a_{21},a_{22}\}\cong M_2(\mathbb{C}) is also invariant under these states, T_\phi acts on it by

T_\phi(M)=\mu_1 M\mu_2 V_2^*M V_2+\mu_3 V_3^*MV_3+\mu_4 V^*_4 MV_4





Let u=(\cos \vartheta,e^{i\delta}\sin\vartheta) be a unit vector in \mathbb{C}^2 and denote by P_u, the orthogonal projection onto \text{Lin}\{u\}. The maximum abelian subalgebra A_u=\text{Lin}\{P_u,\mathbf{1}-P_u\}\subset M_2(\mathbb{C})\subset A is in general not invariant under T_\phi.

For example, for u=(1/\sqrt{2},1/\sqrt{2}) we get the algebra


It can be identified with F(\{1,2\}) via

\left(\begin{array}{cc}a&b\\b&a\end{array}\right)\equiv (a+b)\mathbf{1}_{\{1\}}+(a-b)\mathbf{1}_{\{2\}}.

Specialising to the transition state \phi=\eta_2 and starting from the Haar measure \psi=\eta, we see that the time-ordered joint moment is negative and thus can not be obtained from a classical Markov chain.


For states in \text{Lin}\{\eta_1,\eta_2,\eta_3,\eta_4,\alpha_{11}+\alpha_{22}\}, the centre Z(A)=\text{Lin}\{e_1,e_2,e_3,e_4,a_{11},a_{22}\} of A is invariant under T_\phi. A state on A parameterised by (B.1) belongs to this set if and only if x=y=z=0 (\checkmark). With respect to the basis \{e_1,e_2,e_3,e_4,a_{11}+a_{22}\} of Z(A) we get

{T_\phi}_{|Z(A)}=\left(\begin{array}{ccccc}\mu_1&\mu_2&\mu_3&\mu_4&\mu_5\\\mu_2&\mu_1&\mu_4&\mu_3&\mu_5\\\mu_3&\mu_4&\mu_1&\mu_2&\mu_5\\\mu_4&\mu_3&\mu2&\mu_1&\mu_5\\[1ex] \mu_5/4&\mu_5/4&\mu_5/4&\mu_5/4&1-\mu_5\end{array}\right).

This is not the stochastic operator of a random walk on a finite group — it is not doubly stochastic. Furthermore this puts paid to the conjecture made above (however I am under the impression that there is an isomorphism between abelian finite quantum groups and finite groups — more on this later).

For Lévy processes or random walks on quantum groups there exists another way to prove the existence of a classical version that does not use the Markov property. We will illustrate this with an example.


We consider restrictions to the centre Z(A) of A. If a\in Z(A), then a\otimes 1_A\in Z(A\otimes A) and therefore

[a\otimes 1_A,\Delta (b)]=0 for all a,\,b\in Z(A).

This implies that the range of the restriction \{{j_n}_{|Z(A)}\}_{n\geq 0} of any random walk on A to Z(A) is commutative, i.e.


=[(j_0\star k_1\star\cdots \star k_\ell)(a),(j_0\star k_1\cdots \star k_n(b))]

=[(j_0\star k_1\star\cdots\star k_\ell)(a),(j_0\star k_1\star\cdots\star k_\ell)(b_{(1)})(k_{\ell+1}\star\cdots\star k_n)(b_{(2)})]

=\nabla(j_\ell\otimes(k_{\ell+1}\star\cdots\star k_n))([a\otimes 1_A,\Delta (b)])=0

for all 0\leq\ell\leq n and a,\,b\in Z(A) (I must admit I’m not sure of the calculus of these calculations). Therefore the restriction \{{j_n}_{|Z(A)}\}_{n\geq 0} corresponds to a classical process.

Let us now takes states for which T_\phi does not leave the centre of the Kac-Paljutkin quantum group invariant; for example

\phi_c=\frac{1+c}{2}\alpha_{11}+\frac{1-c}{2}\alpha_{22} for z\in [-1,1].

In this particular case we have the invariant commutative subalgebra A_0=\text{Lin}\{e_1,e_2,e_3,e_4,a_{11},a_{22}\} which contains the centre Z(A). If we identify A_0 with F(1,\dots,6) via e_i\equiv\mathbf{1}_{\{i\}}a_{11}\equiv\mathbf{1}_{\{5\}} and a_{22}\equiv \mathbf{1}_{\{6\}}, then the transition matrix is given at the bottom of page 21.

The classical process corresponding to the centre Z(A) arises from this Markov chain by “gluing” the two states 5 and 6 into one. More precisely, if \{\xi_n\}_{n\geq 0} is a Markov chain that has the same time-ordered moments as \{j_n\}_{n\geq 0} restricted to A_0, and if g:\{1,\dots,6\}\rightarrow\{1,\dots,5\} is the mapping defined by g(i)=i for i=1,\dots,5 and g(6)=5, then \{\zeta_n\}_{n\geq 0} with \zeta_n=g\circ \xi_n, for n\geq 0, has the same joint moments as \{j_n\}_{n\geq 0} restricted to the centre Z(A) of A. Note that \{\zeta_n\}_{n\geq 0} is not a Markov process.