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?? 

Conjecture

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

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

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

Remark

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.

Example

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.

Example

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

\phi=\mu_1\eta_1+\mu_2\eta_2+\mu_3\eta_3+\mu_4\eta_4,

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

\left(\begin{array}{cccc}\mu_1&\mu_2&\mu_3&\mu_4\\\mu_2&\mu_1&\mu_4&\mu_3\\\mu_3&\mu_4&\mu_1&\mu_2\\\mu_4&\mu_3&\mu_2&\mu_1\end{array}\right).

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

for

M=aa_{11}+ba_{12}+ca_{21}+da_{22}\equiv\left(\begin{array}{cc}a&b\\c&d\end{array}\right)a,\,b,\,c,\,d\in\mathbb{C},

with

V_2=\left(\begin{array}{cc}0&i\\1&0\end{array}\right)V-3=\left(\begin{array}{cc}0&-i\\1&0\end{array}\right)V_4=\left(\begin{array}{cc}1&0\&-1\end{array}\right).

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

A_u=\text{Lin}\left\{\begin{array}{cc}a&b\\b&a\end{array}:a,\,b\in\mathbb{C}\right\}.

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.

Example

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.

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_\ell(a),j_n(b)]

=[(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.

Advertisements