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

To motivate the definition of quantum Markov chains let us start with a reformulation of the classical Markov chain. Let M,\,G be finite sets. Any map b:M\times G\rightarrow M may be called an action of G on M. Let F(M) and F(G) be the *-algebra of complex functions on M and G. For all g\in G, we have unital *-homomorphisms (\checkmark) \alpha_g:F(M)\rightarrow F(M) given by (\alpha_g f)(x):=f(b(x,g)). They can be put together into a single unital *-homomorphism

\displaystyle\beta:F(M)\rightarrow F(M)\otimes F(G), \displaystyle f\mapsto \sum_{g\in G}\alpha_g f\otimes\mathbf{1}_{\{g\}},

where \mathbf{1}_{\{g\}} is the indicator function. We get a natural non-commutative generalisation just by allowing the algebras to become non-commutative (by replacing the C*-algebras F(M) and F(G) by more general (!), not necessarily commutative C*-algebras).

Let B and A be unital C*-algebras and \beta:B\rightarrow B\otimes A a unital *-homomorphism. Here B\otimes A is the spatial tensor product. Then we can build up the following iterative scheme for n\geq 0:

j_0:B\rightarrow B, b\mapsto b

j_1:B\rightarrow B\otimes A, b\mapsto\beta(b)=b_{(0)}\otimes a_{(0)}.

(Sweedler’s notation b_{(0)}\otimes b_{(1)} stands for \sum_i b_{0i}\otimes b_{1i} and is very convenient for writing formulas).

\displaystyle j_n:B\rightarrow B\otimes\bigotimes_{1}^nA, j_n=(j_{n-1}\otimes I_A)\circ\beta,

\displaystyle b\mapsto j_{n-1}(b_{(0)})\otimes b_{(1)}\in \left(B\otimes\bigotimes_1^{n-1}A\right)\otimes A.

Clearly all the j_n are unital *-homomorphisms (\checkmark). If we want to have an algebra \hat{B} which includes all their ranges we can form the infinite tensor product \hat{A}:=\bigotimes_{1}^\infty A (the closure of the union of all of \bigotimes_1^{n} A with the natural inclusions x\mapsto x\otimes 1) and then \hat{B}=B\otimes\hat{A}.

Denote by \sigma the right shift on \hat{A}, i.e. \sigma(a_1\otimes a_2\otimes\cdots)=1_B\otimes a_1\otimes a_2\otimes\cdots Using this we can also write

j_n:B\rightarrow \hat{B}, b\mapsto \hat{\beta}^n(b\otimes 1_A),

where \hat{\beta} is a unital *-homomorphism given by

\hat{\beta}:\hat{B}\rightarrow\hat{B}, b\otimes a\mapsto\beta\circ(I_B\otimes\sigma)(b\otimes a)=\beta(b)\otimes a.

i.e. by applying the shift, we first obtain b\otimes 1_A\otimes a\in\hat{B} and then interpret ‘\beta\circ‘ as the operation which replaces b\otimes 1_A by \beta(b). We may interpret \hat{\beta} as a kind of time evolution producing j_1,j_2,\dots

To do probability theory, consider states \psi,\,\phi on B,\,A and form product states

\displaystyle\psi\otimes\bigotimes_1^n\phi

for B\otimes \bigotimes_1^n A (in particular for n=\infty the infinite product state on \hat{B}, which we call \Psi). Now we can think of the j_n as non-commutative random variables with distributions \Psi\circ j_n and \{j_n\}_{n\geq 0} is a non-commutative stochastic process. We call \psi the initial state and \phi the transition state.

In order to analyse this process, we define for n\geq 1 the linear maps:

\displaystyle Q_{[0,n-1]}:B\otimes\bigotimes_1^nA\rightarrow B\otimes\bigotimes_1^{n-1}A,

b\otimes a_1\otimes\cdots\otimes a_{n-1}\otimes a_n\mapsto b\otimes a_1\otimes\cdots \otimes a_{n-1}\phi(a_n).

In particular, Q:=Q_{[0,0]}=I_B\otimes \phi:B\otimes A\rightarrow B, b\otimes a\mapsto b\phi(a).

Such maps are often called slice maps. From a probabilistic point of view, it is common to refer to idempotent  norm-one (completely) positive maps onto a C*-subalgebra as (non-commutative) conditional expectations. Clearly the slice map Q_{[0,n-1]} is a conditional expectation (with its range embedded by x\mapsto x\otimes 1) and it has the additional property of preserving the state, i.e. \Psi\circ Q_{[0,n-1]}=\Psi.

Proposition 2.1: The Markov Property

Q_{[0,n-1]}\circ j_n=j_{n-1}\circ T_\phi

where T_\phi:B\rightarrow B, 

b\mapsto Q\circ\beta(b)=(I_B\otimes\phi)\circ\beta(b)=b_{(0)}\phi(b_{(1)}).

Proof

Q_{[0,n-1]}j_n(b)=Q_{[0,n-1]}(j_{n-1}(b_{(0)})\otimes b_{(1)})

=j_{n-1}(b_{(0)})\phi(b_{(1)})=j_{n-1}T_\phi(b) \bullet

We interpret this as a Markov property of the process \{j_n\}_{n\geq0}. Note that if there are state-preserving conditional expectations P_{n-1} onto j_{n-1}(B) and P_{[0,n-1]} onto the algebraic span of j_0(B),\dots,j_{n-1}(B), then because P_{n-1} is dominated by P_{[0,n-1]} and P_{[0,n-1]} is dominated by Q_{[0,n-1]}, we get

P_{[0,n-1]}\circ j_n=j_{n-1}\circ T_\phi

(Markov Property)

The reader should check that for commutative algebras, this is the usual Markov property of classical probability.

Suppose that X=\{1,\dots,d\} is a finite set and consider the C*-algebra F(X) of complex-valued functions on X. This algebra has basis \{\mathbf{1}_{\{i\}}:i\in X\}. We now construct the \{j_n\}_{n\geq 0}, the stochastic operator T_\phi and a conditional expectation E_{[0,n-1]}.

Now let A=B=F(X). We need a unital *-homomorphism \beta. Let us try

\beta:F(X)\rightarrow F(X), \displaystyle\mathbf{1}_{\{i\}}\mapsto \mathbf{1}_{\{i\}}\otimes \mathbf{1}_{X}.

It is not difficult to show that this is a unital *-homomorphism.

In this framework the \{j_n\} are quite simple:

\displaystyle j_n(\mathbf{1}_{\{i\}})=\mathbf{1}_{\{i\}}\otimes\bigotimes_{\ell=1}^{n-1}\mathbf{1}_X.

Now let \phi be a probability measure on X. We have

T_\phi(\mathbf{1}_{\{i\}})=(I_{F(X)}\otimes \phi)\circ\beta(\mathbf{1}_{\{i\}})=\mathbf{1}_{\{i\}}.

i.e. T_\phi=I_{F(X)}. Now we need to construct a conditional expectation E_{[0,n-1]}. The following seems reasonable:

\displaystyle E_{[0,n-1]}\left(\mathbf{1}_{\{i\}}\otimes\bigotimes_{\ell=1}^{n}\mathbf{1}_X\right)=\mathbf{1}_{\{i\}}\otimes\bigotimes_{\ell=1}^{n-1}\mathbf{1}_X.

I’m hoping to show that for commutative algebras the Markov property above it the correct one. Here I’ve started with a commutative algebra, and showed that the Markov property holds. However I don’t think I have the correct \beta. Even if I do find the correct \beta, I also need to show that classical Markov chains satisfy this quantum Markov property. In the next paragraph there is a hint how we might do this. Let \{\xi_n\}_{n\geq0} be a classical Markov chain with stochastic operator P=p(i,j). In the classical situation the stochastic operator can tell us a lot about the random variables \{\xi_n\}_{n\geq0} — hopefully in the quantum case also! 

So in hoping to find the correct \beta for classical Markov chains,  define

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

We should be able to get something out of this by looking at Q=I\otimes\phi=Q_{[0,0]}=E_{[0,0]} — which is connected to \phi via T_\phi=(I\otimes\phi)\circ \beta. This suggests to me that we can look at the Markov property for n=1 (recalling j_1=\beta and j_0=I_{F(X)}):

E_{[0,0]}\circ \beta=(I_{F(X)}\otimes\phi)\circ \beta=T_\phi.

With the prescription T_\phi(\mathbf{1}_{\{j\}})=\sum_i p(i,j)\mathbf{1}_{\{i\}} we should be able to write down a \beta that satisfies the Markov property for some \phi. Following this procedure I have derived

\displaystyle\beta(\mathbf{1}_{\{j\}})=\left\{\begin{array}{cc}\sum_{i=1}^dp(i,j)\mathbf{1}_{\{i\}}\otimes\frac{\mathbf{1}_{\{j\}}}{\phi(\mathbf{1}_{\{j\}})}&\text{ if }\phi(\mathbf{1}_{\{j\}})>0\\[2ex] 0&\text{ if }\phi(\mathbf{1}_{\{j\}})=0\end{array}\right.

… this isn’t linear. Does \phi determine p(i,j) and vice versa? If \phi is allowed to be chosen independently of p(i,j) then things don’t seem to work. We must establish a link between p(i,j) and \phi. To try and get linearity we have for A\subset X

\displaystyle\beta(\mathbf{1}_{A})=\sum_{i=1}^d\mathbf{1}_{\{i\}}\otimes \left(\sum_{\ell\in A}p(\ell,i)\mathbf{1}_{\{ \ell\}}\right).

As unlikely as it seems, this \beta is additive and I’m going to extend to linearity by allowing homogeneity. In fact this is easier written as

\beta(\mathbf{1}_{\{j\}})=\sum_{i=1}^d\mathbf{1}_{\{i\}}\otimes p(i,j)\mathbf{1}_{\{j\}}.

However this implies that \mathbf{\phi}=\mathbf{1} which doesn’t seem correct… Well thankfully I’m doing random walks on groups as that is perfectly straightforward — can’t seem to find a \beta to do the job at all. If I had thought for a moment then this shouldn’t have been a problem — it’s when we have a group action can we write down the classical version in this way. Suppose again that X=\{1,\dots,d\} and we have an action of  a finite group G on F(X):

\alpha_g: F(X)\times G\rightarrow F(X).

It is better that this is induced by a group action b:X\times G\rightarrow G via \alpha_g(f)(x)=f(b(x,g)). As before this can be encoded as a coaction

\beta:F(X)\rightarrow F(X)\otimes F(G), \mathbf{1}_{\{x\}}\mapsto\sum_{g\in G}\alpha_g(\mathbf{1}_{\{x\}})\otimes\mathbf{1}_{\{g\}}.

My ‘interpretation’ of this is as follows. If the action is going to be by g, then \alpha_{g}\left(\mathbf{1}_{\{x\}}\right) is like the set of points which will be sent to x in that case. So it should be very difficult to do what I wanted to do above without a group action somewhere. Can we still do it? Perhaps we can construct a Markov chain which can’t be realised in this framework? Consider a two state Markov chain with transition probabilities \lambda and \gamma. I can show that after quite a lot of calculations that this can only be done if \lambda=1/2=\gamma. This suggests that we can only do Markov chains which are induced by group actions — this does not cover all Markov chains however. Therefore I must disagree with the author and call this (classical) construction a non-invariant random walk on a finite group (NIRWG).

We must show therefore that the above Markov Property is the same as that of the classical chain when we have a NIRWG. Let X be a set and b:X\times G\rightarrow X be a group action. Let \nu\in M_p(G) be a probability measure on G and define a stochastic operator by:

\displaystyle p(x,y)=\sum_{g\in G}\nu(g:b(x,g)=y), for all x,\,y\in X.

Now the unital *-homomorphisms \alpha_g are given by

\alpha_g\left(\mathbf{1}_{\{x\}}\right)(y)=\mathbf{1}_{\{x\}}(b(y,g)).

We also have a transition operator

T_\phi\left(\mathbf{1}_{\{x\}}\right)=\sum_{y\in X}p(y,x)\mathbf{1}_{\{y\}}.

Now let us check out what \phi is given by. It’s not easy (possibly not unique) but we have

p(x,y)=\sum_{b(x,g)=y}\phi(\mathbf{1}_{\{y\}}).

This seems to suggest that an action of G on X and a state on F(G) can define a classical non-invariant random walk but that the other direction there may not necessarily be unique. Hmmm — can this be inverted? At this point we have to ask questions about the comparative sizes of X and G — or moreover |\text{supp}(\nu)|=\Sigma. From now on I will assume that |\Sigma|=X.

We examine the Markov property for n=2.

Thus in the general case, we say that \{j_n\}_{n\geq0} is a quantum Markov chain on B. The map T_\phi is called the transition operator of the Markov chain. In the classical case, it can be identified with the transition matrix by choosing indicator functions of single points as a basis, i.e. T_\phi(\mathbf{1}_{\{j\}})=\sum_{i=1}^dp_{ij}\mathbf{1}_{\{i\}}. It is an instructive exercise to start with a given transition matrix P and to realise the classical Markov Chain with the construction above. As indicated I don’t think this is always possible.

Let \xi be the random walk on \mathbb{Z}_p with stochastic operator induced by the driving probability\nu(1)=\nu(2)=1/2. The action, b we will be concerned with shall be left-multiplication (well \mathbb{Z}_p is an additive abelian group so we can right-addition —I am considering the action to be ‘on’ x):

b:\mathbb{Z}_p\times \mathbb{Z}_p\rightarrow \mathbb{Z}_p, b(x,y)=x+y.

This yields the unital *-homomorphisms of F(G) given by:

 \alpha_y(f)(x):=f(b(x,y))=f(x+y).

They can be put together (encoded?)  into a single unital *-homomorphism

\beta:F(G)\rightarrow F(G)\otimes F(G), f\mapsto \sum_{z=0}^{p-1}\alpha_z(f)\otimes\mathbf{1}_{\{z\}}.

Now \beta is linear and the indicator functions are a basis for F(G), hence we examine \beta(\mathbf{1}_{\{x\}}):

\beta(\mathbf{1}_{\{x\}})=\sum_{z=0}^{p-1}\alpha_z(\mathbf{1}_{\{x\}})\otimes\mathbf{1}_{\{z\}}.

=\sum_{z=0}^{p-1}\mathbf{1}_{\{x+z\}}\otimes\mathbf{1}_{\{z\}}.

My reading of this is that if the ‘action’ was z (\mathbf{1}_{\{z\}}), then the random walk will be (considering it started ‘at’ \mathbf{1}_{\{x\}}) ‘at’ \mathbf{1}_{\{x+z\}}.

Now we can examine the stochastic process \{j_n\}_{n\in\mathbb{N}}. We have that j_0(\mathbf{1}_{\{x\}})=\mathbf{1}_{\{x\}}, j_1(\mathbf{1}_{\{x\}})=\beta(\mathbf{1}_{\{x\}}). Now we calculate:

j_2(\mathbf{1}_{\{x\}})=(j_1\otimes I_{F(G)})\circ\beta(\mathbf{1}_{\{x\}}) ,

=(j_1\otimes I_{F(G)})\left(\sum_{z=0}^{p-1}\left(\mathbf{1}_{\{x+z\}}\otimes\mathbf{1}_{\{z\}}\right)\right),

=\sum_{z,w=0}^{p-1}\left(\mathbf{1}_{\{x+z+w\}}\otimes\mathbf{1}_{\{w\}}\otimes\mathbf{1}_{\{z\}}\right).

My interpretation here is that the random walk in in a superposition of states — it’s true state can only be determined when we know which combination of z and w acted. Inductively, we have that

j_n(\mathbf{1}_{\{x\}})=\sum_{z_1,\dots,z_n=0}^{p-1}\left(\mathbf{1}_{\left\{x+\sum_{k=0}^nz_k\right\}}\otimes\bigotimes_{k=1}^n\mathbf{1}_{\{z_k\}}\right).

Again the construction is clear, the \{j_n\} are indeed random variables on the function space, and further we can see that the random walk is the random variable given by x+\sum_{k=1}^nz_k. 

Whoops: Most of the next paragraph doesn’t make sense. I would define the states on F(G) linearly by:

 \phi(\mathbf{1}_{\{x\}})=\nu(x)

Eh, actually this fixes the next paragraph!   

For the probability theory, we might look at the probability measures M_p(\mathbf{Z}_p). For these to be states they need to be norm 1, positive elements in the dual of F(G). When F(G) is normed by the supremum norm, the elements of M_p(G) are in the dual space with the l^1 norm — thus we have that the probability measures are indeed norm 1. Also, as we know that the positive elements of F(G) are those that are real-valued with f(x)\geq0, we clearly have \mu(f)\in\mathbf{R}^+ for \mu\in M_p(G) so the probability measures are indeed our states.

I‘d like to take \psi being equivalent to \delta^0 — for a walk starting deterministically at 0, and \phi=\nu — but this doesn’t make a whole pile of sense at the moment, so we’ll just stick with \psi. So the distribution of j_n is given by \Psi\circ j_n, where \Psi=\psi\otimes\bigotimes_1^{\infty}\nu.

Now for the slice maps. This is where I am confused. My interpretation so far is that j_n\in F(G)\otimes\bigotimes_1^n F(G), where the first F(G) describes the current state, and the kth element of the tensor product of the n F(G)s accounts for the action at step k. The definition of the slice maps is very much at odds with this (probably false) interpretation. It’s pretty clear that the slice maps act on the j_n(F(G)). Considering Q_{[0,n-1]}(j_n(\mathbf{1}_{\{x\}}):

\sum_{z_1,\dots,z_n=0}^{p-1}\left(\mathbf{1}_{\left\{x+\sum_{k=0}^nz_k\right\}}\otimes\bigotimes_{k=1}^{n-2}\mathbf{1}_{\{z_k\}}\otimes\mathbf{1}_{\{z_{n-1}\}}\nu(z_n)\right).

Hmmm — it seems as if the actions are the wrong way around. Maybe we can do them the other way around?

Well anyway, let us consider the Q map — what does that look like. It acts on j_1(F(G)) anyway:

Q(j_1(\mathbf{1}_{\{x\}}))=\sum_{z=0}^{p-1}\mathbf{1}_{\{x+z\}}\nu(z).

This does seem to encode the walk that begins at x. Perhaps I am doing things slightly wrong — but looking at the “right-shift” formulation, the same problems emerge…

Now looking to the Markov property. Again we’ll just look at f=\mathbf{1}_{\{x\}}. On the left-hand side we have:

\sum_{z_1,\dots,z_n=0}^{p-1}\left(\mathbf{1}_{\left\{x+\sum_{k=0}^nz_k\right\}}\otimes\bigotimes_{k=1}^{n-2}\mathbf{1}_{\{z_k\}}\otimes\mathbf{1}_{\{z_{n-1}\}}\nu(z_n)\right).

Now for the right-hand side. Firstly

T_\phi(\mathbf{1}_{\{x\}})=Q(j_1(\mathbf{1}_{\{x\}}))=\sum_{z=0}^{p-1}\mathbf{1}_{\{x+z\}}\nu(z).

Now we must hit this with j_{n-1} — I’m happy enough that they are equal actually. Now we need to endorse the interpretation — that this is the usual Markov property of classical probability. We can take this to be as simple as:

\mathbb{P}[\xi_{k+1}=y:\xi_k=x]=p(x,y)…

Analogous to a classic formula, we can also derive the following semigroup property for transition operators from the Markov property. It is one of the main reasons why Markov chains are easier than more general processes.

Corollary 2.2: Semigroup Property

Qj_n=T_\phi^n.

It might be useful to prove this is the commutative case for a random walk on a group G of order |G|=N. Both Qj_n and T_\phi act on F(G) and as both are linear it suffices to prove the result for \mathbf{1}_{\{g\}}. As per usual, this is given by

\sum_{g_1,\dots,g_N\in G}\left(\mathbf{1}_{\left\{\left(\prod_{k=n}^0 g_k\right)g\right\}}\otimes\bigotimes_{k=1}^n\mathbf{1}_{\{g_k\}}\right).

Now, as far as I am concerned, the action of Q on this is unclear: Q=I_{F(G)}\otimes \phi acts on F(G) \otimes F(G)…

On the other hand, it’s pretty easy to show that T_\phi^n(\mathbf{1}_{\{g\}}) is given by:

\left(\sum_{g_1,\dots,g_n\in G}\mathbf{1}_{\left\{\left(\prod_{k=n}^1g_k\right)g\right\}}\right)\left(\prod_{k=n}^1\nu(g_k)\right)

 I can’t reconcile this exactly, but if Q can act like this then no problem.

Finally we note that if (\psi\otimes\phi)\circ\beta=\psi, then \Psi\circ\hat{\beta}=\Psi.

Suppose that (\psi\otimes\phi)\circ\beta=\psi. Let b\in B; then there exist elementary tensors b_i\otimes a_i such that

\beta(b)=\sum_{i=1}^nb_i\otimes a_i.

Now apply the product state \psi\otimes\phi:

(\psi\otimes\phi)\circ\beta(b)=\sum_{i=1}^n\psi(b_i)\phi(a_i)\overset{!}{=}\psi(b).

Now let b\otimes a embedded into \hat{B}. Now

\hat{\beta}(b)=\sum_{i=1}^nb_i\otimes a_i\otimes a

\Rightarrow \Psi\circ\hat{\beta}=\underbrace{\left(\sum_{i=1}^n\psi(b_i)\phi(a_i)\right)}_{=\psi(b)}\phi(a)

=\psi(b)\phi(a)=\Psi(b\otimes a),

and the claim is proved \bullet

This implies that the Markov chain is stationary, i.e. correlations between random variables only depend on time differences (???) In particular, the state \psi is then preserved by T_\phi, i.e. \psi\circ T_\phi=\psi.

Suppose that we have a stationary Markov chain and let b\in B. Now

T_\phi=\sum_{i=1}^nb_i\phi(a_i)

\Rightarrow \psi\circ T_\phi(b)=\sum_{i=1}^n\psi(b_i)\phi(a_i)=\psi(b) \bullet 

The construction above is called coupling to a shift.