October 9, 2011

Network Theory (Part 12)

John Baez

But to do this, I need to say more about the analogy between stochastic mechanics and quantum mechanics. And whenever I try, I get pulled toward explaining some technical issues involving analysis: whether sums converge, whether derivatives exist, and so on. I've been trying to avoid such stuff—not because I dislike it, but because I'm afraid you might. But the more I put off discussing these issues, the more they fester and make me unhappy. In fact, that's why it's taken so long for me to write this post!

So, this time I will gently explore some of these technical issues. But don't be scared: I'll mainly talk about some simple big ideas. Next time I'll discuss Noether's theorem. I hope that by getting the technicalities out of my system, I'll feel okay about hand-waving whenever I want.

And if you're an expert on analysis, maybe you can help me with a question.

Stochastic mechanics versus quantum mechanics

First, we need to recall the analogy we began sketching in Part 5, and push it a bit further. The idea is that stochastic mechanics differs from quantum mechanics in two big ways:

• First, instead of complex amplitudes, stochastic mechanics uses nonnegative real probabilities. The complex numbers form a ring; the nonnegative real numbers form a mere rig, which is a 'ring without negatives'. Rigs are much neglected in the typical math curriculum, but unjustly so: they're almost as good as rings in many ways, and there are lots of important examples, like the natural numbers $\mathbb{N}$ and the nonnegative real numbers, $[0,\infty)$. For probability theory, we should learn to love rigs.

But there are, alas, situations where we need to subtract probabilities, even when the answer comes out negative: namely when we're taking the time derivative of a probability. So sometimes we need $\mathbb{R}$ instead of just $[0,\infty)$.

• Second, while in quantum mechanics a state is described using a 'wavefunction', meaning a complex-valued function obeying

$$ \int |\psi|^2 = 1 $$

in stochastic mechanics it's described using a 'probability distribution', meaning a nonnegative real function obeying

$$ \int \psi = 1 $$

So, let's try our best to present the theories in close analogy, while respecting these two differences.

States

We'll start with a set $X$ whose points are states that a system can be in. Last time I assumed $X$ was a finite set, but this post is so mathematical I might as well let my hair down and assume it's a measure space. A measure space lets you do integrals, but a finite set is a special case, and then these integrals are just sums. So, I'll write things like

$$ \int f $$

and mean the integral of the function $f$ over the measure space $X$, but if $X$ is a finite set this just means

$$ \sum_{x \in X} f(x) $$

Now, I've already defined the word 'state', but both quantum and stochastic mechanics need a more general concept of state. Let's call these 'quantum states' and 'stochastic states':

• In quantum mechanics, the system has an amplitude $\psi(x)$ of being in any state $x \in X$. These amplitudes are complex numbers with

$$\int | \psi |^2 = 1$$

We call $\psi: X \to \mathbb{C}$ obeying this equation a quantum state.

• In stochastic mechanics, the system has a probability $\psi(x)$ of being in any state $x \in X$. These probabilities are nonnegative real numbers with

$$\int \psi = 1$$

We call $\psi: X \to [0,\infty)$ obeying this equation a stochastic state.

In quantum mechanics we often use this abbreviation:

$$ \langle \phi, \psi \rangle = \int \overline{\phi} \psi $$

so that a quantum state has

$$ \langle \psi, \psi \rangle = 1 $$

Similarly, we could introduce this notation in stochastic mechanics:

$$ \langle \psi \rangle = \int \psi $$

so that a stochastic state has

$$ \langle \psi \rangle = 1 $$

But this notation is a bit risky, since angle brackets of this sort often stand for expectation values of observables. So, I've been writing $\int \psi$, and I'll keep on doing this.

In quantum mechanics, $\langle \phi, \psi \rangle$ is well-defined whenever both $\phi$ and $\psi$ live in the vector space

$$L^2(X) = \{ \psi: X \to \mathbb{C} \; : \; \int |\psi|^2 < \infty \} $$

In stochastic mechanics, $\langle \psi \rangle$ is well-defined whenever $\psi$ lives in the vector space

$$L^1(X) = \{ \psi: X \to \mathbb{R} \; : \; \int |\psi| < \infty \} $$

You'll notice I wrote $\mathbb{R}$ rather than $[0,\infty)$ here. That's because in some calculations we'll need functions that take negative values, even though our stochastic states are nonnegative.

Observables

A state is a way our system can be. An observable is something we can measure about our system. They fit together: we can measure an observable when our system is in some state. If we repeat this we may get different answers, but there's a nice formula for average or 'expected' answer.

• In quantum mechanics, an observable is a self-adjoint operator $A$ on $L^2(X)$. The expected value of $A$ in the state $\psi$ is

$$ \langle \psi, A \psi \rangle $$

Here I'm assuming that we can apply $A$ to $\psi$ and get a new vector $A \psi \in L^2(X)$. This is automatically true when $X$ is a finite set, but in general we need to be more careful.

• In stochastic mechanics, an observable is a real-valued function $A$ on $X$. The expected value of $A$ in the state $\psi$ is

$$ \int A \psi $$

Here we're using the fact that we can multiply $A$ and $\psi$ and get a new vector $A \psi \in L^1(X)$, at least if $A$ is bounded. Again, this is automatic if $X$ is a finite set, but not otherwise.

Symmetries

Besides states and observables, we need 'symmetries', which are transformations that map states to states. We use these to describe how our system changes when we wait a while, for example.

• In quantum mechanics, an isometry is a linear map $U: L^2(X) \to L^2(X)$ such that

$$ \langle U \phi, U \psi \rangle = \langle \phi, \psi \rangle$$

for all $\psi, \phi \in L^2(X)$. If $U$ is an isometry and $\psi$ is a quantum state, then $U \psi$ is again a quantum state.

• In stochastic mechanics, a stochastic operator is a linear map $U: L^1(X) \to L^1(X)$ such that

$$ \int U \psi = \int \psi $$

and

$$ \psi \ge 0 \; \; \Rightarrow \; \; U \psi \ge 0 $$

for all $\psi \in L^1(X)$. If $U$ is stochastic and $\psi$ is a stochastic state, then $U \psi$ is again a stochastic state.

In quantum mechanics we are mainly interested in invertible isometries, which are called unitary operators. There are lots of these, and their inverses are always isometries. There are, however, very few stochastic operators whose inverses are stochastic:

Puzzle 1. Suppose $X$ is a finite set. Show that any isometry $ U: L^2(X) \to L^2(X)$ is invertible, and its inverse is again an isometry.

Puzzle 2. Suppose $X$ is a finite set. Which stochastic operators $ U: L^1(X) \to L^1(X)$ have stochastic inverses?

This is why we usually think of time evolution as being reversible quantum mechanics, but not in stochastic mechanics! In quantum mechanics we often describe time evolution using a '1-parameter group', while in stochastic mechanics we describe it using a 1-parameter semigroup... meaning that we can run time forwards, but not backwards.

But let's see how this works in detail!

Time evolution in quantum mechanics

In quantum mechanics there's a beautiful relation between observables and symmetries, which goes like this. Suppose that for each time $t$ we want a unitary operator $U(t) : L^2(X) \to L^2(X)$ that describes time evolution. Then it makes a lot of sense to demand that these operators form a 1-parameter group:

Definition. A collection of linear operators U(t) ($t \in \mathbb{R}$) on some vector space forms a 1-parameter group if

$$ U(0) = 1 $$

and

$$ U(s+t) = U(s) U(t) $$

for all $s,t \in \mathbb{R}$.

Note that these conditions force all the operators $U(t)$ to be invertible.

Now suppose our vector space is a Hilbert space, like $L^2(X)$. Then we call a 1-parameter group a 1-parameter unitary group if the operators involved are all unitary.

It turns out that 1-parameter unitary groups are either continuous in a certain way, or so pathological that you can't even prove they exist without the axiom of choice! So, we always focus on the continuous case:

Definition. A 1-parameter unitary group is strongly continuous if $U(t) \psi$ depends continuously on $t$ for all $\psi$, in this sense:

$$ t_i \to t \;\; \Rightarrow \; \;\|U(t_i) \psi - U(t) \psi \| \to 0 $$

Then we get a classic result proved by Marshall Stone back in the early 1930s. You may not know him, but he was so influential at the University of Chicago during this period that it's often called the "Stone Age". And here's one reason why:

Stone's Theorem. There is a one-to-one correspondence between strongly continuous 1-parameter unitary groups on a Hilbert space and self-adjoint operators on that Hilbert space, given as follows. Given a strongly continuous 1-parameter unitary group $U(t)$ we can always write

$$ U(t) = \exp(-i t H)$$

for a unique self-adjoint operator $H$. Conversely, any self-adjoint operator determines a strongly continuous 1-parameter group this way. For all vectors $\psi$ for which $H \psi$ is well-defined, we have

$$ \left.\frac{d}{d t} U(t) \psi \right|_{t = 0} = -i H \psi $$

Moreover, for any of these vectors, if we set

$$ \psi(t) = \exp(-i t H) \psi $$

we have

$$ \frac{d}{d t} \psi(t) = - i H \psi(t) $$

When $U(t) = \exp(-i t H)$ describes the evolution of a system in time, $H$ is is called the Hamiltonian, and it has the physical meaning of 'energy'. The equation I just wrote down is then called Schrödinger's equation.

So, simply put, in quantum mechanics we have a correspondence between observables and nice one-parameter groups of symmetries. Not surprisingly, our favorite observable, energy, corresponds to our favorite symmetry: time evolution!

However, if you were paying attention, you noticed that I carefully avoided explaining how we define $\exp(- i t H)$. I didn't even say what a self-adjoint operator is. This is where the technicalities come in: they arise when $H$ is unbounded, and not defined on all vectors in our Hilbert space.

Luckily, these technicalities evaporate for finite-dimensional Hilbert spaces, such as $L^2(X)$ for a finite set $X$. Then we get:

Stone's Theorem (Baby Version). Suppose we are given a finite-dimensional Hilbert space. In this case, a linear operator $H$ on this space is self-adjoint iff it's defined on the whole space and

$$ \langle \phi , H \psi \rangle = \langle H \phi, \psi \rangle $$

for all vectors $\phi, \psi$. Given a strongly continuous 1-parameter unitary group $U(t)$ we can always write

$$ U(t) = \exp(- i t H) $$

for a unique self-adjoint operator $H$, where

$$ \exp(-i t H) \psi = \sum_{n = 0}^\infty \frac{(-i t H)^n}{n!} \psi $$

with the sum converging for all $\psi$. Conversely, any self-adjoint operator on our space determines a strongly continuous 1-parameter group this way. For all vectors $\psi$ in our space we then have

$$ \left.\frac{d}{d t} U(t) \psi \right|_{t = 0} = -i H \psi $$

and if we set

$$ \psi(t) = \exp(-i t H) \psi $$

we have

$$ \frac{d}{d t} \psi(t) = - i H \psi(t) $$

Time evolution in stochastic mechanics

We've seen that in quantum mechanics, time evolution is usually described by a 1-parameter group of operators that comes from an observable: the Hamiltonian. Stochastic mechanics is different!

First, since stochastic operators aren't usually invertible, we typically describe time evolution by a mere 'semigroup':

Definition. A collection of linear operators $U(t)$ ($t \in [0,\infty)$) on some vector space forms a 1-parameter semigroup if

$$ U(0) = 1 $$

and

$$ U(s+t) = U(s) U(t) $$

for all $s, t \ge 0$.

Now suppose this vector space is $L^1(X)$ for some measure space $X$. We want to focus on the case where the operators $U(t)$ are stochastic and depend continuously on $t$ in the same sense we discussed earlier.

Definition. A 1-parameter strongly continuous semigroup of stochastic operators $U(t) : L^1(X) \to L^1(X)$ is called a Markov semigroup.

What's the analogue of Stone's theorem for Markov semigroups? I don't know a fully satisfactory answer! If you know, please tell me.

Later I'll say what I do know—I'm not completely clueless—but for now let's look at the 'baby' case where $X$ is a finite set. Then the story is neat and complete:

Theorem. Suppose we are given a finite set $X$. In this case, a linear operator $H$ on $L^1(X)$ is infinitesimal stochastic iff it's defined on the whole space,

$$ \int H \psi = 0 $$

for all $\psi \in L^1(X)$, and the matrix of $H$ in terms of the obvious basis obeys

$$ H_{i j} \ge 0 $$

for all $j \ne i$. Given a Markov semigroup $U(t)$ on $L^1(X)$, we can always write

$$ U(t) = \exp(t H) $$

for a unique infinitesimal stochastic operator $H$, where

$$ \exp(t H) \psi = \sum_{n = 0}^\infty \frac{(t H)^n}{n!} \psi $$

with the sum converging for all $\psi$. Conversely, any infinitesimal stochastic operator on our space determines a Markov semigroup this way. For all $\psi \in L^1(X)$ we then have

$$ \left.\frac{d}{d t} U(t) \psi \right|_{t = 0} = H \psi $$

and if we set

$$ \psi(t) = \exp(t H) \psi $$

we have the master equation:

$$ \frac{d}{d t} \psi(t) = H \psi(t) $$

In short, time evolution in stochastic mechanics is a lot like time evolution in quantum mechanics, except it's typically not invertible, and the Hamiltonian is typically not an observable.

Why not? Because we defined an observable to be a function $A: X \to \mathbb{R}$. We can think of this as giving an operator on $L^1(X)$, namely the operator of multiplication by $A$. That's a nice trick, which we used to good effect last time. However, at least when $X$ is a finite set, this operator will be diagonal in the obvious basis consisting of functions that equal 1 one point of $X$ and zero elsewhere. So, it can only be infinitesimal stochastic if it's zero!

Puzzle 3. If $X$ is a finite set, show that any operator on $L^1(X)$ that's both diagonal and infinitesimal stochastic must be zero.

The Hille–Yosida theorem

I've now told you everything you really need to know... but not everything I want to say. What happens when $X$ is not a finite set? What are Markov semigroups like then? I can't abide letting this question go unresolved! Unfortunately I only know a partial answer.

We can get a certain distance using the Hille–Yosida theorem, which is much more general.

Definition. A Banach space is a vector space with a norm such that any Cauchy sequence converges.

Examples include Hilbert spaces like $L^2(X)$ for any measure space, but also other spaces like $L^1(X)$ for any measure space!

Definition. If $V$ is a Banach space, a 1-parameter semigroup of operators $U(t) : V \to V$ is called a contraction semigroup if it's strongly continuous and

$$ \| U(t) \psi \| \le \| \psi \| $$

for all $t \ge 0 $ and all $\psi \in V$.

Examples include strongly continuous 1-parameter unitary groups, but also Markov semigroups!

Puzzle 4. Show any Markov semigroup is a contraction semigroup.

The Hille--Yosida theorem generalizes Stone's theorem to contraction semigroups. In my misspent youth, I spent a lot of time carrying around Yosida's book Functional Analysis. Furthermore, Einar Hille was the advisor of my thesis advisor, Irving Segal. Segal generalized the Hille--Yosida theorem to nonlinear operators, and I used this generalization a lot back when I studied nonlinear partial differential equations. So, I feel compelled to tell you this theorem:

Hille–Yosida Theorem. Given a contraction semigroup $U(t)$ we can always write

$$ U(t) = \exp(t H)$$

for some densely defined operator $H$ such that $H - \lambda I $ has an inverse and

$$ \displaystyle{ \| (H - \lambda I)^{-1} \psi \| \le \frac{1}{\lambda} \| \psi \| } $$

for all $\lambda \gt 0 $ and $\psi \in V$. Conversely, any such operator determines a strongly continuous 1-parameter group. For all vectors $\psi$ for which $H \psi$ is well-defined, we have

$$ \left.\frac{d}{d t} U(t) \psi \right|_{t = 0} = H \psi $$

Moreover, for any of these vectors, if we set

$$ \psi(t) = U(t) \psi $$

we have

$$ \frac{d}{d t} \psi(t) = H \psi(t) $$

If you like, you can take the stuff at the end of this theorem to be what we mean by saying $U(t) = \exp(t H)$. When $ U(t) = \exp(t H)$, we say that $ H$ generates the semigroup $ U(t)$.

But now suppose $V = L^1(X)$. Besides the conditions in the Hille–Yosida theorem, what extra conditions on $H$ are necessary and sufficient for $H$ to generate a Markov semigroup? In other words, what's a definition of 'infinitesimal stochastic operator' that's suitable not only when $X$ is a finite set, but an arbitrary measure space?

I asked this question on Mathoverflow a few months ago, and so far the answers have not been completely satisfactory.

Some people mentioned the Hille--Yosida theorem, which is surely a step in the right direction, but not the full answer.

Others discussed the special case when $\exp(t H)$ extends to a bounded self-adjoint operator on $L^2(X)$. When $X$ is a finite set, this special case happens precisely when the matrix $H_{i j}$ is symmetric: the probability of hopping from $j$ to $i$ equals the probability of hopping from $i$ to $j$. This is a fascinating special case, not least because when $H$ is both infinitesimal stochastic and self-adjoint, we can use it as a Hamiltonian for both stochastic mechanics and quantum mechanics! Someday I want to discuss this. However, it's just a special case.

After grabbing people by the collar and insisting that I wanted to know the answer to the question I actually asked—not some vaguely similar question— the best answer seems to be Martin Gisser's reference to this book:

• Zhi-Ming Ma and Michael Röckner, Introduction to the Theory of (Non-Symmetric) Dirichlet Forms, Springer, Berlin, 1992.

This book provides a very nice self-contained proof of the Hille–Yosida theorem. On the other hand, it does not answer my question in general, but only when the skew-symmetric part of $ H$ is dominated (in a certain sense) by the symmetric part.

So, I'm stuck on this front, but that needn't bring the whole project to a halt. We'll just sidestep this question.

For a good well-rounded introduction to Markov semigroups and what they're good for, try:

• Ryszard Rudnicki, Katarzyna Pichór and Marta Tyran-Kamínska, Markov semigroups and their applications.

You can also read comments on Azimuth, and make your own comments or ask questions there!

Here are the answers to the puzzles. The answer to Puzzle 2 is an expanded version of one given by Graham Jones.

Puzzle 1. Suppose $X$ is a finite set. Show that any isometry $ U: L^2(X) \to L^2(X)$ is invertible, and its inverse is again an isometry.

Answer. Remember that $U$ being an isometry means that it preserves the inner product:

and thus it preserves the $L^2$ norm

since we can write $\phi' = U^{-1} \phi,$ $\psi' = U^{-1} \psi$ and then the above equation says

Puzzle 2. Suppose $X$ is a finite set. Which stochastic operators $ U: L^1(X) \to L^1(X)$ have stochastic inverses?

Answer. Suppose the set $ X$ has $ n$ points. Then the set of stochastic states

is a simplex. It's an equilateral triangle when $ n = 3$, a regular tetrahedron when $ n = 4$, and so on.

In general, $S$ has $ n$ corners, which are the functions $ \psi$ that equal 1 at one point of $ S$ and zero elsewhere. Mathematically speaking, $S$ is a convex set, and its corners are its extreme points: the points that can't be written as convex combinations of other points of $ S$ in a nontrivial way.

Any stochastic operator $ U$ must map $ S$ into itself, so if $ U$ has an inverse that's also a stochastic operator, it must give a bijection $ U : S \to S$. Any linear transformation acting as a bijection between convex sets must map extreme points to extreme points (this is easy to check), so $ U$ must map corners to corners in a bijective way. This implies that it comes from a permutation of the points in $ X$.

In other words, any stochastic matrix with an inverse that's also stochastic is a permutation matrix: a square matrix with every entry 0 except for a single 1 in each row and each column.

It is worth adding that there are lots of stochastic operators whose inverses are not, in general, stochastic. We can see this in at least two ways.

First, for any measure space $X$, every stochastic operator $U : L^1(X) \to L^1(X)$ that's 'close to the identity' in this sense:

(where the norm is the operator norm) will be invertible, simply because every operator obeying this inequality is invertible! After all, if this inequality holds, we have a convergent geometric series:

Second, suppose $X$ is a finite set and $H$ is infinitesimal stochastic operator on $ L^1(X)$. Then $H$ is bounded, so the stochastic operator $\exp(t H)$ where $t \gt 0$ will always have an inverse, namely $\exp(-t H)$. But for $t$ sufficiently small, this inverse $\exp(-tH)$ will only be stochastic if $-H$ is infinitesimal stochastic, and that's only true if $H = 0$.

In something more like plain English: when you've got a finite set of states, you can formally run any Markov process backwards in time, but a lot of those 'backwards-in-time' operators will involve negative probabilities for the system to hop from one state to another!

Puzzle 3. If $X$ is a finite set, show that any operator on $L^1(X)$ that's both diagonal and infinitesimal stochastic must be zero.

Answer. We are thinking of operators on $L^1(X)$ as matrices with respect to the obvious basis of functions that equal 1 at one point and 0 elsewhere. If $H_{i j}$ is an infinitesimal stochastic matrix, the sum of the entries in each column is zero. If it's diagonal, there's at most one nonzero entry in each column. So, we must have $H = 0$.

Puzzle 4. Show any Markov semigroup $ U(t): L^1(X) \to L^1(X)$ is a contraction semigroup.

Answer. We need to show $$ \|U(t) \psi\| \le \| \psi \| $$

for all $t \ge 0$ and $\psi \in L^1(X)$. Here the norm is the $L^1$ norm, so more explicitly we need to show

We can split $ \psi$ into its positive and negative parts:

where

Since $ U(t)$ is stochastic we have

and

so

© 2011 John Baez
baez@math.removethis.ucr.andthis.edu
home