The Azimuth Project
Blog - network theory (part 6)

Skip the Navigation Links | Home Page | All Pages | Recently Revised | Authors | Feeds | Export |

This page is a blog article in progress, written by John Baez. To see the final polished article, go to the Azimuth Blog.

Now for the fun part. Let’s see how quantum theory ideas can be used to understand random processes. I’ll try to make this post completely self-contained, except at the very end. So, even if you skipped a bunch of the previous ones, this should make sense.

You also don’t need to know quantum theory, though you’ll have more fun if you do. What we’re doing here is very similar, but also strangely different—for reasons I explained last time.

Rabbits and quantum mechanics

Suppose we have a population of rabbits in a cage and we’d like to describe its growth in a stochastic way, using probability theory. Let ψ n\psi_n be the probability of having nn rabbits. We can borrow a trick from quantum theory, and summarize all these probabilities in a formal power series like this:

Ψ=∑ n=0 ∞ψ nz n \Psi = \sum_{n = 0}^\infty \psi_n z^n

The variable zz doesn’t mean anything in particular, and we don’t care if the power series converges. See, in math ‘formal’ means “it’s only symbols on the page, just follow the rules”. It’s like when someone says a party is ‘formal’, so you need to wear a white tie: you’re not supposed to ask what the tie means.

However, there’s a good reason for this trick. We can define two operators on formal power series, called the annihilation operator:

aΨ=ddzΨ a \Psi = \frac{d}{d z} \Psi

and the creation operator:

a †Ψ=zΨ a^\dagger \Psi = z \Psi

They’re just differentiation and multiplication by zz, respectively. So, for example, suppose we start out being 100% sure we have nn rabbits for some particular number nn. Then ψ n=1\psi_n = 1, while all the other probabilities are 0, so:

Ψ=z n \Psi = z^n

If we then apply the creation operator, we obtain

a †Ψ=z n+1 a^\dagger \Psi = z^{n+1}

Voilà! One more rabbit!

The annihilation operator is more subtle. If we start out with nn rabbits:

Ψ=z n \Psi = z^n

and then apply the annihilation operator, we obtain

aΨ=nz n−1 a \Psi = n z^{n-1}

What does this mean? The z n−1z^{n-1} means we have one fewer rabbit than before. But what about the factor of nn? It means there were nn different ways we could pick a rabbit and make it disappear! This should seem a bit mysterious, for various reasons… but we’ll see how it works soon enough.

The creation and annihilation operators don’t commute:

(aa †−a †a)Ψ=ddz(zΨ)−zddzΨ=Ψ (a a^\dagger - a^\dagger a) \Psi = \frac{d}{d z} (z \Psi) - z \frac{d}{d z} \Psi = \Psi

so for short we say:

aa †−a †a=1 a a^\dagger - a^\dagger a = 1

or even shorter:

[a,a †]=1 [a, a^\dagger] = 1

where the commutator of two operators is [S,T]=ST−TS [S,T] = S T - T S .

The noncommutativity of operators is often claimed to be a special feature of quantum physics, and the creation and annihilation operators are fundamental to understanding the quantum harmonic oscillator. There, instead of rabbits, we’re studying quanta of energy, which are peculiarly abstract entities obeying rather counterintuitive laws. So, it’s cool that the same math applies to purely classical entities, like rabbits!

Here’s how it works. We want to describe how the probabilities ψ n\psi_n change with time, so we write

Ψ(t)=∑ n=0 ∞ψ n(t)z n \Psi(t) = \sum_{n = 0}^\infty \psi_n(t) z^n

Then, we write down an equation describing the rate of change of Ψ\Psi:

ddtΨ(t)=HΨ(t) \frac{d}{d t} \Psi(t) = H \Psi(t)

Here HH is an operator called the Hamiltonian, and the equation is called the master equation. The details of the Hamiltonian depend on our problem! But we can often write it down using creation and annihilation operators. Let’s do some examples, and then I’ll tell you the general rule.

Catching rabbits

Last time I told you what happens when we stand in a river and catch fish as they randomly swim past. Today we’re doing rabbits. This works almost the same way. But there’s a fundamental difference: rabbits don’t swim.

So, suppose an inexhaustible supply of rabbits are randomly roaming around a huge field, and each time a rabbit enters a certain area, we catch it and add it to our population of caged rabbits. Suppose that on average we catch one rabbit per unit time. Suppose the chance of catching a rabbit during any interval of time is independent of what happens before or afterwards. What is the Hamiltonian describing the probability distribution of caged rabbits, as a function of time?

There’s an obvious dumb guess: the creation operator! However, we saw last time that this doesn’t work, and we saw how to fix it. The right answer is

H=a †−1H = a^\dagger - 1

To see why, suppose for example that at some time tt we have nn rabbits, so:

Ψ(t)=z n\Psi(t) = z^n

Then the master equation says that at this moment,

ddtΨ(t)=(a †−1)Ψ(t)=z n+1−z n \frac{d}{d t} \Psi(t) = (a^\dagger - 1) \Psi(t) = z^{n+1} - z^n

Since Ψ=∑ n=0 ∞ψ n(t)z n\Psi = \sum_{n = 0}^\infty \psi_n(t) z^n, this implies that the coefficients of our formal power series are changing like this:

ddtψ n+1(t)=1\frac{d}{d t} \psi_{n+1}(t) = 1
ddtψ n(t)=−1\frac{d}{d t} \psi_{n}(t) = -1

while all the rest have zero derivative at this moment. And that’s exactly right! See, ψ n+1(t)\psi_{n+1}(t) is the probability of having one more rabbit, and this is going up at rate 1. Meanwhile, ψ n(t)\psi_n(t) is the probability of having nn rabbits, and this is going down at the same rate.

Puzzle 1. Show that with this Hamiltonian, the master equation predicts that the expected number of rabbits grows linearly.

Dying rabbits

Don’t worry: no rabbits are actually injured in the research that Jacob Biamonte is doing here at the Centre for Quantum Technologies. He’s keeping them well cared for in a big room on the 6th floor. This is just a thought experiment.

Suppose a mean nasty guy had a population of rabbits in a cage and didn’t feed them at all. Suppose that each rabbit has a unit probability of dying per unit time. And as always, suppose the probability of this happening in any interval of time is independent of what happens before or after that time.

What is the Hamiltonian? Again there’s a dumb guess: the annihilation operator! And again this guess is wrong, but it’s not far off. As before, the right answer includes a ‘correction term’:

H=a−N H = a - N

This time the correction term is famous in its own right. It’s called the number operator:

N=a †aN = a^\dagger a

The reason is that if we start with nn rabbits, and apply this operator, it amounts to multiplication by nn:

Nz n=zddzz n=nz n N z^n = z \frac{d}{d z} z^n = n z^n

Let’s see why this guess is right. Again, suppose that at some particular time tt we have nn rabbits, so

Ψ(t)=z n\Psi(t) = z^n

Then the master equation says that at this time

ddtΨ(t)=(a−N)Ψ(t)=nz n−1−nz n \frac{d}{d t} \Psi(t) = (a - N) \Psi(t) = n z^{n-1} - n z^n

So, our probabilities are changing like this:

ddtψ n−1(t)=n\frac{d}{d t} \psi_{n-1}(t) = n
ddtψ n(t)=−n\frac{d}{d t} \psi_n(t) = -n

while the rest have zero derivative. And this is good! We’re starting with nn rabbits, and each has a unit probability per unit time of dying. So, the chance of having one less should be going up at rate nn. And the chance of having the same number we started with should be going down at the same rate.

Puzzle 2. Show that with this Hamiltonian, the master equation predicts that the expected number of rabbits decays exponentially.

Breeding rabbits

Suppose we have a strange breed of rabbits that reproduce asexually. Suppose that each rabbit has a unit probability per unit time of having a baby rabbit, thus effectively duplicating itself.

As you can see from the cryptic picture above, this ‘duplication’ process takes one rabbit as input and has two rabbits as output. So, if you’ve been paying attention, you should be ready with a dumb guess for the Hamiltonian: a †a †aa^\dagger a^\dagger a. This operator annihilates one rabbit and then creates two!

But you should also suspect that this dumb guess will need a ‘correction term’. And you’re right! As always, the correction terms makes the probability of things staying the same go down at exactly the rate that the probability of things changing goes up.

You should guess the correction term… but I’ll just tell you:

H=a †a †a−N H = a^\dagger a^\dagger a - N

We can check this in the usual way, by seeing what it does when we have nn rabbits:

Hz n=z 2ddzz n−nz n=nz n+1−nz n H z^n = z^2 \frac{d}{d z} z^n - n z^n = n z^{n+1} - n z^n

That’s good: since there are nn rabbits, the rate of rabbit duplication is nn. This is the rate at which the probability of having one more rabbit goes up… and also the rate at which the probability of having nn rabbits goes down.

Puzzle 3. Show that with this Hamiltonian, the master equation predicts that the expected number of rabbits grows exponentially.

Dueling rabbits

Let’s do some stranger examples, just so you can see the general pattern.

Here each pair of rabbits has a unit probability per unit time of fighting a duel with only one survivor. You might guess the Hamiltonian a †aaa^\dagger a a , but in fact:

H=a †aa−N(N−1) H = a^\dagger a a - N(N-1)

Let’s see why this is right! Let’s see what it does when we have nn rabbits:

Hz n=zd 2dz 2z n−n(n−1)z n=n(n−1)z n−1−n(n−1)z n H z^n = z \frac{d^2}{d z^2} z^n - n(n-1)z^n = n(n-1) z^{n-1} - n(n-1)z^n

That’s good: since there are n(n−1)n(n-1) ordered pairs of rabbits, the rate at which duels take place is n(n−1)n(n-1). This is the rate at which the probability of having one less rabbit goes up… and also the rate at which the probability of having nn rabbits goes down.

(If you prefer unordered pairs of rabbits, just divide the Hamiltonian by 2. We should talk about this more, but not now.)

Brawling rabbits

Now each triple of rabbits has a unit probability per unit time of getting into a fight with only one survivor! I don’t know the technical term for a three-way fight, but perhaps it counts as a small ‘brawl’ or ‘melee’. In fact the Wikipedia article for ‘melee’ shows three rabbits in suits of armor, fighting it out:

Now the Hamiltonian is:

H=a †a 3−N(N−1)(N−2) H = a^\dagger a^3 - N(N-1)(N-2)

You can check that:

Hz n=n(n−1)(n−2)z n−2−n(n−1)(n−2)z n H z^n = n(n-1)(n-2) z^{n-2} - n(n-1)(n-2) z^n

and this is good, because n(n−1)(n−2)n(n-1)(n-2) is the number of ordered triples of rabbits. You can see how this number shows up from the math, too:

a 3z n=d 3dz 3z n=n(n−1)(n−2)z n−3 a^3 z^n = \frac{d^3}{d z^3} z^n = n(n-1)(n-2) z^{n-3}

The general rule

Suppose we have a process taking kk rabbits as input and having jj rabbits as output:

I hope you can guess the Hamiltonian I’ll use for this:

H=a † ja k−N(N−1)⋯(N−k+1) H = {a^{\dagger}}^j a^k - N(N-1) \cdots (N-k+1)

This works because

a kz n=d kdz kz n=n(n−1)⋯(n−k+1)z n−k a^k z^n = \frac{d^k}{d z^k} z^n = n(n-1) \cdots (n-k+1) z^{n-k}

so that if we apply our Hamiltonian to nn rabbits, we get

Hz n=n(n−1)⋯(n−k+1)(z n+j−k−z n) H z^n = n(n-1) \cdots (n-k+1) (z^{n+j-k} - z^n)

See? As the probability of having n+j−kn+j-k rabbits goes up, the probability of having nn rabbits goes down, at an equal rate. This sort of balance is necessary for HH to be a sensible Hamiltonian in this sort of stochastic theory (an ‘infinitesimal stochastic operator’, to be precise). And the rate is exactly the number of ordered kk-tuples taken from a collection of nn rabbits. This is called the kkth falling power of nn, and written as follows:

n k̲=n(n−1)⋯(n−k+1) n^{\underline{k}} = n(n-1) \cdots (n-k+1)

Since we can apply functions to operators as well as numbers, we can write our Hamiltonian as:

H=a † ja k−N k̲ H = {a^{\dagger}}^j a^k - N^{\underline{k}}

Kissing rabbits

Let’s do one more example just to test our understanding. This time each pair of rabbits has a unit probability per unit time of bumping into one another, exchanging a friendly kiss and walking off. This shouldn’t affect the rabbit population at all! But let’s follow the rules and see what they say.

According to our rules, the Hamiltonian should be:

H=a † 2a 2−N(N−1) H = {a^{\dagger}}^2 a^2 - N(N-1)

However,

a † 2a 2z n=z 2d 2dz 2z n=n(n−1)z n=N(N−1)z n {a^{\dagger}}^2 a^2 z^n = z^2 \frac{d^2}{dz^2} z^n = n(n-1) z^n = N(N-1) z^n

and since z nz^n form a ‘basis’ for the formal power series, we see that:

a † 2a 2=N(N−1) {a^{\dagger}}^2 a^2 = N(N-1)

so in fact:

H=0 H = 0

That’s good: if the Hamiltonian is zero, the master equation will say

ddtΨ(t)=0 \frac{d}{d t} \Psi(t) = 0

so the population, or more precisely the probability of having any given number of rabbits, will be constant.

There’s another nice little lesson here. Copying the calculation we just did, it’s easy to see that:

a † ka k=N k̲ {a^{\dagger}}^k a^k = N^{\underline{k}}

This is a cute formula for falling powers of the number operator in terms of annihilation and creation operators. It means that for the general transition we saw before:

we can write the Hamiltonian in two equivalent ways:

H=a † ja k−N k̲=a † ja k−a † ka k H = {a^{\dagger}}^j a^k - N^{\underline{k}} = {a^{\dagger}}^j a^k - {a^{\dagger}}^k a^k

Okay, that’s it for now! We can, and will, generalize all this stuff to stochastic Petri nets where there are things of many different kinds—not just rabbits. And we’ll see that the master equation we get matches the answer to the puzzle in Part 4. That’s pretty easy. But first, we’ll have a guest post by Jacob Biamonte, who will explain an example from population biology.

category: blog

Revised on May 24, 2014 17:49:22 by David Tanzer (72.229.60.112)
Edit | Back in time (4 revisions) | See changes | History | Views: Print | TeX | Source | Linked from: Blog articles in progress