Network Theory (Part 6)

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

You’ll need to know a bit of math: calculus, a tiny bit probability theory, and linear operators on vector spaces. You 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 \psi_n be the probability of having n rabbits. We can borrow a trick from quantum theory, and summarize all these probabilities in a formal power series like this:

\Psi = \sum_{n = 0}^\infty \psi_n z^n

The variable z 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 if someone says a party is ‘formal’, so 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 \Psi = \frac{d}{d z} \Psi

and the creation operator:

a^\dagger \Psi = z \Psi

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

\Psi = z^n

If we then apply the creation operator, we obtain

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

Voilà! One more rabbit!

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

\Psi = z^n

and then apply the annihilation operator, we obtain

a \Psi = n z^{n-1}

What does this mean? The z^{n-1} means we have one fewer rabbit than before. But what about the factor of n? It means there were n 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:

(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:

a a^\dagger - a^\dagger a = 1

or even shorter:

[a, a^\dagger] = 1

where the commutator of two operators is

[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!

In particular, the equation [a, a^\dagger] = 1 just says that there’s one more way to put a rabbit in a cage of rabbits, and then take one out, than to take one out and then put one in.

But how do we actually use this setup? We want to describe how the probabilities \psi_n change with time, so we write

\Psi(t) = \sum_{n = 0}^\infty \psi_n(t) z^n

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

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

Here H 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. Let me remind you of how that works. But today let’s use rabbits.

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 happened before. 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^\dagger - 1

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

\Psi(t) = z^n

Then the master equation says that at this moment,

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

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

\frac{d}{d t} \psi_{n+1}(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, \psi_{n+1}(t) is the probability of having one more rabbit, and this is going up at rate 1. Meanwhile, \psi_n(t) is the probability of having n rabbits, and this is going down at the same rate.

Puzzle 1. Show that with this Hamiltonian and any initial conditions, 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 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

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

N = a^\dagger a

The reason is that if we start with n rabbits, and apply this operator, it amounts to multiplication by 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 t we have n rabbits, so

\Psi(t) = z^n

Then the master equation says that at this time

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

So, our probabilities are changing like this:

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

while the rest have zero derivative. And this is good! We’re starting with n 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 n. 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 and any initial conditions, 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^\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^\dagger a^\dagger a - N

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

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 n rabbits, the rate of rabbit duplication is n. 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 n rabbits goes down.

Puzzle 3. Show that with this Hamiltonian and any initial conditions, 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^\dagger a a, but in fact:

H = a^\dagger a a - N(N-1)

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

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) ordered pairs of rabbits, the rate at which duels take place is 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 n 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^\dagger a^3 - N(N-1)(N-2)

You can check that:

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) is the number of ordered triples of rabbits. You can see how this number shows up from the math, too:

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 k rabbits as input and having j rabbits as output:

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

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

This works because

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 n rabbits, we get

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

See? As the probability of having n+j-k rabbits goes up, the probability of having n rabbits goes down, at an equal rate. This sort of balance is necessary for H 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 k-tuples taken from a collection of n rabbits. This is called the kth falling power of n, and written as follows:

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^{\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^{\dagger}}^2 a^2 - N(N-1)

However,

{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^n form a ‘basis’ for the formal power series, we see that:

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

so in fact:

H = 0

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

\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^{\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^{\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 a more realistic example from population biology.

37 Responses to Network Theory (Part 6)

  1. David Corfield says:

    For puzzle 1, you have shown for the basis element z^n, that \frac{d}{d t} \psi_{n+1}(t) = 1 and \frac{d}{d t} \psi_{n}(t) = -1. So the rate of increase of the expected number is (n + 1) - n = 1. So for a general distribution, the rate of increase of the expected number of rabbits is \sum_n \psi_{n}(t) = 1.

    Is there a slick way of doing it via \frac{d}{d t} (N \Psi(t)) evaluated at z = 1?

    • John Baez says:

      Great! Thanks, David! I have a slick way to do these, but I like your way because, unlike mine, it doesn’t convey the impression that you need to be a crazed quantum physicist to solve these problems.

      Here’s my way. We start with some general useful observations that have nothing to do with this particular puzzle. They’ll come in handy for all these puzzles.

      As you note, the expected value of the number of rabbits in any probability distribution \psi is

      \sum_{n=0}^\infty n \psi_n

      On the other hand:

      \begin{array}{ccl} N \Psi &=& z \frac{d}{d z} \sum_{n=0}^\infty \psi_n z^n \\   \\ &=& \sum_{n=0}^\infty n \psi_n z^n \end{array}

      So, if we evaluate N\Psi at z = 1 we get the expected number of rabbits:

      N\Psi |_{z = 1} = \sum_{n=0}^\infty n \psi_n z^n

      Now suppose our probability distribution \psi and thus \Psi depend on time. Then to see how the expected number of rabbits changes with time, we can compute

      \frac{d}{d t}(N \Psi(t)) |_{z = 1}

      Let’s try. The old “do whatever you can do” strategy is always good in this sort of situation:

      \begin{array}{ccl} \frac{d}{d t}(N \Psi(t)) |_{z = 1} &=& N (\frac{d}{d t} \Psi(t)) |_{z = 1} \\   \\ &=& N H \Psi(t) |_{z=1} \end{array}

      where in the first step we pass the derivative through the linear operator (anyone who doubts we can, belongs in math grad school), and in the second we use the master equation

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

      What can we do next? Well, we can use the definition of H (which depends on which puzzle we’re doing) and the definition of N (which doesn’t):

      N = a^\dagger a

      To solve Puzzle 1, we should show the rate at which the expected number of rabbits grows is a constant. In fact you’ve already shown this constant equals 1, so we know what we’re aiming for.

      In this puzzle we have

      H = a^\dagger - 1

      so the rate at which the expected number of rabbits grows is

      a^\dagger a ( a^\dagger - 1) \Psi(t) |_{z=1}

      and we’re trying to show this equals 1.

      But remember that a^\dagger is multiplication by z, while

      a = \frac{d}{d z}

      This should do the job somehow… no?

      All this may seem like overkill—and indeed it is for this puzzle. But it’s a powerful strategy, and after we codify it a bit, it will become less work.

  2. David Corfield says:

    That last equation is where I reached. I guess there was never going to be a simplification before setting z = 1. The other two puzzles work out fine.

    • John Baez says:

      Great. But that kind of remark tends kill off anyone else’s desire to solve the puzzles: there’s this guy out there who’s already done ‘em…

      I want to actually see the solutions. I haven’t actually done them. Should I offer a bounty?

    • David Corfield says:

      My chances of having lengthy stretches of Latex working without preview are slim, but here goes.

      Puzzle 2:

      \begin{array}{ccl} \frac{d}{d t}(N \Psi(t)) &=& N (\frac{d}{d t} \Psi(t)) \\ \\ &=& N H \Psi(t) \\ \\ &=& N(a - N) \Psi \\ \\ &=& \sum n(n - 1) \psi_n z^{n - 1} - n^2 \psi_n z^n . \end{array}

      so

      \begin{array}{ccl} \frac{d}{d t}(N \Psi(t)) |_{z = 1} &=& - \sum n \psi_n \\ \\ &=& (N \Psi(t)) |_{z = 1} \end{array}

      So, (N \Psi(t)) |_{z = 1} = A e^{t}.

      • John Baez says:

        Great! I don’t mind fixing up the LaTeX around here. You got exponential growth instead of exponential decay, by dropping a minus sign, but that’s no big deal.

        Let me try it my way. It’s really the same as your way, just with slightly different notation. Like many physicists I’ve spent decades playing with many different formalisms for operators in quantum field theory, so I can’t resist trying different formalisms for this probabilistic version.

        In my general formalism I like to use \int \psi to mean the total integral of a function over some measure space, so that ‘states’, that is probability distributions, are the functions obeying

        \int \psi = 1

        and

        \psi \ge 0.

        In the examples today the integral is really a sum, and it might be confusing to use integral notation since we’re using derivatives for a completely different purpose. So let me define sum notation as follows:

        \sum \Psi = \sum_{n = 0}^\infty \psi_n

        This may annoy you, since after all we really have

        \Psi|_{z = 1} =  \sum_{n = 0}^\infty \psi_n

        but please humor me.

        So, there’s a nice rule, easily verified:

        \sum a^\dagger \Psi = \sum \Psi

        I mentioned it before: it’s part of the creation operator being a stochastic operator. This implies another nice rule:

        \sum a \Psi = \sum N \Psi

        Indeed:

        \sum N \Psi = \sum a^\dagger a \Psi = \sum a \Psi

        The expected value of any observable O in the state \Psi is

        \sum O \Psi

        So, if we’re trying to work out the time derivative of the expected value of O, we can start by doing

        \frac{d}{dt} \sum O \Psi =  \sum O \frac{d}{dt} \Psi =  \sum O H \Psi

        and then write O and H using annihilation and creation operators and use our rules.

        For example, in Puzzle 2 we have

        H = a - N

        and the observable we’re interested in is the number of rabbits

        O = N

        so we want to understand

        \sum O H \Psi = \sum N(a-N) \Psi

        So far I’ve just gotten to the third line of our answer! But I’m having fun playing with the machinery.

        Now every kid who’s studied quantum field theory knows

        N a = a (N - 1)

        It’s easy to prove, and it says that annihilating a particle and then counting them is the same as counting them, subtracting one and then annihilating one.

        So:

        \sum N(a-N) \Psi = \sum (a N - N - a) \Psi

        but here our rules come in handy!

        \sum (a N - N - a)\Psi =  \sum (N - N - N) \Psi = - \sum N \Psi

        so we we see

        \frac{d}{dt} \sum N \Psi = - \sum N \psi

        as was to be shown.

        Perhaps this fascination with formalism seems odd, but I keep enjoying how everything compares with quantum mechanics! For example, in quantum mechanics the expected value of an observable is

        \langle \Psi, O \Psi \rangle

        and its time derivative is

        i \langle \Psi, (H O - O H) \Psi \rangle

        hence the vast appeal of Lie algebras. Now the expected value is

        \sum O \Psi

        and its time derivative is just

        \sum O H \Psi

        We don’t get two terms because \Psi shows up just once in the formula — we’re using L^1 instead of L^2. So everything is similar… but eerily simple!

        • David Corfield says:

          Now you’ve dropped the minus sign too!

        • John Baez says:

          Yup. I caught that while you were writing your comment. And I added a bunch of new stuff. Moderator’s privilege, sorry.

          Anyway, someone else should try Puzzle 3, to try out the spiffy new modifications of quantum theory!

        • David Corfield says:

          Why does

          \sum N(a-N) \Psi = \sum (a N - N - a) \Psi? Shouldn’t it be

          \sum (a N - N^2 - a) \Psi?

        • John Baez says:

          Let me try again:

          Na = aN - a

          so

          \sum N(a-N) \Psi = \sum (a N - a - N^2) \Psi

          but

          \sum a \Psi = \sum N \Psi

          and for the same reason

          \sum a N \Psi = N^2 \Psi

          so two terms cancel and we’re left with

          - \sum N \Psi

          as desired.

          I knew what answer I wanted, so I wasn’t gonna let a few mistakes stop me from getting it!

          Thanks, David. But I think all the mathematicians and physicists out there should be ashamed to be lurking in the background while a philosopher is doing all the hard work here.

        • DavidTweed says:

          I’m a little confused about the second line above. Unless I’m missing something

          \begin{array}{ccl} \sum N(a-N)\Psi &=& \sum (N a-N^2) \Psi \\  \\ &=&\sum (a N - a -N^2)\Psi. \end{array}

          If \sum a N \Psi=\sum N^2\Psi, then what rewriting makes this -\sum N \Psi rather than -\sum a \Psi?

        • DavidTweed says:

          Sorry. I didn’t see the equivalence of \sum a \Psi=\sum N \Psi immediately below the line you mentioned.

        • David Corfield says:

          What’s quickest for 3? Something like

          \begin{array}{ccl} N(a^\dagger a^\dagger a - N) &=& N a^\dagger N - N^2 \\  \\ &=& a^\dagger (N+1) N - N^2. \end{array}

          Then

          \begin{array}{ccl} \sum N H \Psi &=& \sum (a^\dagger (N+1) N - N^2) \Psi \\  \\ &=& \sum ((N+1)N -N^2) \Psi \\  \\ &=& \sum N \Psi. \end{array}

  3. 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,

    In english it’s called a truel, but I would prefer it as in German, triel. I know of two western films with truels: The Good, the Bad and the Ugly of which I have forgotten the triel scene, and another good western whose title I’ve forgotten, but remember the paradigmatic triel scene (one character was a poker player)… Sigh, my swiss cheese brain.

    I guess the quantum and octonion philosopher has more to say of why its not the duel what makes the world move, but the truel…

    BTW I got interested in that stuff because I once worked for the inventor of a 3-player chess variant. (Mess and design of that page is not my fault….). Now I know why I always found duel-chess boring – and methinks it actually makes stupid…

  4. jack fuller says:

    Seems to me we are either in the process of total revolution or meddling in things of the devil — or both! “All seriousness aside”, as once said, Newton and Maxwell/Faraday asserted that there was a continuum of “forces” in the universe, albeit under the aegis of the “field” concept in the latter case. Einstein made the most of this in his remarkable “warping” of space-time dimensional parameters we use to converse about nature. Now, under the province of field operators and commutators we discover maybe all of the universe is ‘quantized’, where integers come to the fore. However, importantly and certainly fortuitously, in physics and perhaps everywhere there exists an inherent “correspondence” in the “classical limit” to the original continuum. All very well, except that the ‘limit’ is apparently only for experimental verification, whereas the quantum picture is what’s “really happening”, except that according to Bohr and Feynman, we don’t ‘understand’ what’s happening!

    The mathematical tricks involving differentiation and other operations as enlighteningly shown above are the mechanism behind all this quantization, but except for the various eponyms involved, what, really, are we doing when carrying out this revolution (or diabolical collusion)?

    My original venerable antique Leonard Schiff-era QFT background probably accounts for my ignorance here, but I feel there has to be a fairly clear path to just a few fundamental and universally relevant premises that, at least insofar as simply logic is concerned (perhaps abandoning any hope for “common sense”), we substantively know what IS the revolutions. (Which for good measure, according to another post might be involved with the coding of the very life process besides.)

    • John Baez says:

      Jack wrote:

      Seems to me we are either in the process of total revolution or meddling in things of the devil — or both!

      Since I don’t really believe in the devil, I guess it must be a revolution!

      Seriously: in my former life as a mathematical physicist mainly concerned with ‘foundational’ issues like quantum gravity, I spent a lot of time wondering what quantum theory was trying to tell us. And I wrote a lot about this, too. It’s hard to write about these things without descending into flakiness, unless one uses lots of math as a kind of cold-water cure. So, most of my thoughts are camouflaged under thick layers of math.

      If you go here, you’ll see me arguing that to reach a deeper understanding of quantum theory and spacetime, we must exploit the fact that these two columns are mathematically a lot more similar than we tend to give them credit for being:

      SPACE       STATE
       
      SPACETME     PROCESS

      We tend to describe states of matter quantum-mechanically as vectors in a Hilbert space, while also thinking of these states as ‘living in space’ at a given time. We tend to describe quantum-mechanical processes using operators between Hilbert spaces, while also thinking of these processes as ‘living in spacetime’. But from work on quantum gravity, one of the few things that seems really is that space itself must have a quantum state, and spacetime itself must be a quantum process.

      As Wheeler put it: in general relativity, spacetime stops being the mere stage on which events play out, and becomes one of the actors. But we also know the actors are quantum-mechanical. So we need a theory of quantum spacetime.

      This sounds scary, but luckily there are lots of mathematical clues to point the way. The paper I just linked to lists some. This one lists a lot more:

      • John Baez and Aaron Lauda, A prehistory of n-categorical physics, to appear in Deep Beauty: Mathematical Innovation and the Search for an Underlying Intelligibility of the Quantum World, ed. Hans Halvorson, Cambridge U. Press.

      When we’re done figuring this out, I’m sure the world will make a lot more sense… though it won’t be ‘common sense’.

      But now I’m trying to think about slightly more practical issues. So in this series of posts, I’m taking some of the math developed for the purposes of understanding quantum theory (so-called groupoidification), and reusing a tiny piece of it to think about stochastic processes.

  5. DavidTweed says:

    I’m trying to relate what I know about using probability generating functions to the physics formalism. Now John has presented “creation” as an operator. Another way of looking at it is using, for two pgf’s \Psi(z) for X and \Lambda(z) and Y, then the pgf of X+Y is \Psi(z) \Lambda(z). So we get the same answer by taking X (via \Psi) as the current distribution and Y as the distribution with “definitely exactly one rabbit” (ie \Lambda(z)=z).

    The corresponding rule for X-Y is \Psi(z) \Lambda(1/z), so (assuming we’re fine with a probability distribution including a value of -1 when we initially had no rabbits) the same calculation gives \Psi(z)/z for this. So there’s a difference between annihilating a rabbit and “subtracting a rabbit”. I can see intuitively the difference, because it’s due to the selection of which rabbit dies, but is there a more clear rule for demarcating which cases count as “annihilation” and which count as “subtraction”?

    • John Baez says:

      Hi, David!

      So there’s a difference between annihilating a rabbit and “subtracting a rabbit”. I can see intuitively the difference, because it’s due to the selection of which rabbit dies, but is there a more clear rule for demarcating which cases count as “annihilation” and which count as “subtraction”?

      It sounds like you understand what’s going on, but would like to see it formalized a bit better. Perhaps you’ll feel better if I provide some reassurance that this is a known issue. The question is whether you want to say there are n different ways to annihilate one of n things, or just one way. The problem at hand determines which answer is right.

      In combinatorics they distinguish between two types of generating functions: so-called ordinary generating functions:

      \mathrm{OG}(a_n,z) = \sum_{n = 0}^\infty a_n z^n

      and so-called exponential generating functions:

      \mathrm{EG}(a_n, z) = \sum_{n = 0}^\infty a_n \frac{z^n}{n!}

      (Writing a_n on the left here instead of just a should be enough to drive Giampiero Campara insane; even I can’t stand it, because n is just a dummy variable on the right-hand side: these generating functions are not really functions of n. But the combinatorists have a good reason for this abuse of notation: there is no standard name for the sequence n^2, say, except n^2.)

      In these notes I’ve been using ordinary generating functions. If you differentiate one of these, a factor of n shows up:

      \frac{d}{d z} \sum_{n = 0}^\infty a_n z^n = \sum_{n = 0}^\infty n a_{n+1} z^n

      That suits my applications. If you don’t want that factor of n to show up here, you can use exponential generating functions:

      \frac{d}{d z} \sum_{n = 0}^\infty a_n \frac{z^n}{n!} = \sum_{n = 0}^\infty a_{n+1} \frac{z^n}{n!}

      But you pay a price: multiplying an exponential generating function by z introduces a factor of n, while this doesn’t happen for ordinary generating functions. Again, ordinary generating functions do the right thing for my applications.

      If you don’t want this factor of n either way, and you don’t want to introduce any ugly ad hoc rules, I think you’re forced to allow negative numbers of things as well as positive numbers of things. Then instead of a formal power series we can use a Laurent series

      \sum_{n = -\infty}^\infty a_n z^n

      As you note, multiplying or dividing this Laurent series by z shifts it without introducing any factor of n either way:

      z \sum_{n = -\infty}^\infty a_n z^n = \sum_{n = -\infty}^\infty a_{n-1} z^n

      z^{-1} \sum_{n = -\infty}^\infty a_n z^n = \sum_{n = -\infty}^\infty a_{n+1} z^n

      I’ve generally avoided this trick because I’m somewhat confused about the mathematical status of ‘sets with a negative number of elements’, a mysterious topic that has spawned many interesting papers. In physics, when you have one antiparticle, that may perhaps count as having -1 particles, and that’s one reason why negative sets would be nice. But in biology, I see no application of antirabbits. Chemistry is an interesting borderline case: antihydrogen exists, but you won’t find it in your typical child’s chemistry set. Good thing, too.

      For vastly more about these issues, see Wilf’s Generatingfunctionology and my page on the mysteries of counting.

      And by the way: in case anyone is confused by the fact that differentating (‘annihilating one rabbit’) changes a_n to a_{n+1} here, instead of a_{n-1}:

      \frac{d}{d z} \sum_{n = 0}^\infty a_n z^n = \sum_{n = 0}^\infty n a_{n+1} z^n

      don’t worry: it only took me 10 years to feel perfectly comfortable with this. It’s basically the same effect as when you’re riding a train: the scenery looks like it’s moving backwards, but it’s because you’re moving forwards.

      • DavidTweed says:

        It’s more that I can see what’s happening mathematically, but I’m trying to figure out why, and in what “application” situations, it’s annihilation or subtraction. I’ve been pondering this and I think that it’s this: the sum becomes product of pgf’s is actually only valid for independent variables. And it’s a coincidence that increasing the number of rabbits in a distribution by one is a sum of two independent distributions as well as a transformation of one pgf. So there’s no a priori reason to believe that removing a rabbit is expressible as a difference of two independent distributions, and it doesn’t look like it is expressible that way at all. So given a situation to analyse I guess it’s a case of figuring out if all the operations you’re modelling are combining two independent distributions or transforming one distribution.

      • Peter Morgan says:

        The Laurent series example has raising and lowering operators that commute, which ties in, though I’m not sure how loosely, with my paper showing that the quantized complex Klein-Gordon field is empirically equivalent to a Klein-Gordon random field, EPL 87 (2009) 31002.

        Dollars in a bank account seem to match the Laurent series model, where there’s exactly one way both to add or to remove one dollar, there aren’t $n$ ways to remove a dollar, and one can be in debt? Must read Wilf’s page and yours on generating functions.

        Incidentally, your RSS feed seems not to be working (at least not from Mozilla or Thunderbird).

  6. John Baez says:

    I put clearly explained (?) answers to all 3 puzzles at the bottom of this page on my website:

    Network Theory (Part 6).

    This page uses jsmath to put LaTeX on a webpage. I think jsmath takes a while to grab the necessary math fonts if you don’t have them. So, while I can link directly to the correct location on the page, the page then expands and I’m left at another location—at least using Firefox 3.6.16 without the math fonts installed. I’d be curious what happens to you!

    • David Corfield says:

      It might help the reader if you took David T’s point and put in an extra line.

    • John Baez says:

      I rewrote the explanation so that future David T’s wouldn’t be confused, but it seems my new explanation was confusing in other ways – more below on that.

      • David Corfield says:

        I mean as you have it, you’ve already used Rule 2 when you write

        \sum N(a-N) \Psi = \sum (a N - N - N^2) \Psi

        Why not write

        \sum N(a-N) \Psi = \sum (a N - a - N^2) \Psi, then invoke Rule 2 twice?

        • John Baez says:

          I wasn’t using Rule 2, I was using the commutation relations N a = a N - a and then making a typo, which gave N a = a N - N.

          I think the typos are mostly gone now, thanks to you. The more important problem here is that there are so many ways to use the rules to do these calculations that it’s hard to find the ‘best’ way.

  7. David Corfield says:

    Then you have

    \sum (a N - N - a) \Psi = \sum (N^2 - N - N^2) \Psi = -\sum N \Psi .

    The second a in the first term should be N^2.

    And is it obvious that \sum a N \Psi = \sum N^2 \Psi? It’s true, but it’s not by Rule 2, unless you strengthen that to \sum a O \Psi = \sum N O \Psi for all O.

  8. John Baez says:

    David C. wrote:

    The second a in the first term should be N^2.

    Thanks – fixed!

    And is it obvious that \sum a N \Psi = \sum N^2 \Psi? It’s true, but it’s not by Rule 2…

    Rule 2 (for those not keeping score) says

    \sum a \Psi = \sum N \Psi

    but surely it was clear that this rule applies to all formal power series \Psi, even those that happen to be called N \Psi.

    Well, okay: it obviously wasn’t clear. I’ll make it clearer.

    This is how all papers and books should be written: with an audience of actual people reading it as it’s written, saying what they like, what they don’t like, and what they find confusing. Otherwise it’s too easy for author to dream up perfectly convincing reasons that the audience should like or understand something. But if they don’t, they don’t!

  9. David Corfield says:

    Where you have

    …the commutation relation [a^{\dagger}, N] = -a^{\dagger} implies that N a^{\dagger} = a^{\dagger} N + 1

    you need brackets around N + 1. And again in the next line.

    • John Baez says:

      Thanks. I decided to switch to an argument that seems a bit simpler:

      In Puzzle 1, the Hamiltonian for catching rabbits is

      H = a^\dagger - 1

      so the rate of change of the expected number of rabbits caught is

      \begin{array}{ccl} \frac{d}{dt} \sum N \Psi(t) &=& \sum N H \Psi(t) \\  &=& \sum N(a^\dagger - 1) \Psi(t) \end{array}

      There are many ways to use our rules to evaluate this. For example, Rule 1 implies that

      \sum N(a^\dagger - 1) \Psi(t) = \sum a(a^\dagger - 1)\Psi(t) $

      but the commutation relations say

      a a^\dagger = a^\dagger a + 1 = N+1

      so

      \sum a(a^\dagger - 1)\Psi(t) = \sum (N + 1 - a) \Psi(t)

      and using Rule 1 again we see this equals

      \sum \Psi(t) = 1

      Thus we have

      \frac{d}{dt} \sum N \Psi(t) = 1

      It follows that the expected number of rabbits grows linearly:

      \sum N \Psi(t) = t + c

  10. Arjun Jain says:

    Why are we considering all the a^{\dagger}s to appear on the left side of all the as in H ({a^{\dagger}}^j a^k - N^{\underline{k}})?

    Surely, there can be situations when the order is not- all inputs, then all outputs. Suppose that 2 rabbits meet and fight and one gets killed. The overconfident victor then challenges any one of the remaining rabbits to a duel and one of them then gets killed. The new victor seeing that he might get killed if he further challenges, stops. If this constitutes the transition, shouldn’t H be a^{\dagger} a a^{\dagger} a^2 - N(N-1)^2 ?

    Also, if operating with a on z^n includes n, the number of ways a rabbit can be chosen from n rabbits, then shouldn’t operating with a^{\dagger} also include the number of ways an output rabbit can be chosen from the k inputs?

    • John Baez says:

      Arjun wrote:

      Why are we considering all the a^{\dagger}s to appear on the left side of all the as in H = ({a^{\dagger}}^j a^k - N^{\underline{k}})?

      Because each transition in a stochastic Petri net describes a processes where a bunch of things get used simultaneously to create some other bunch of things.

      Surely, there can be situations when the order is not- all inputs, then all outputs. Suppose that 2 rabbits meet and fight and one gets killed. The overconfident victor then challenges any one of the remaining rabbits to a duel and one of them then gets killed. The new victor seeing that he might get killed if he further challenges, stops.

      That’s true. I would think of this using a Petri net with a set S consisting of several states. For example: ordinary rabbits, and ‘overconfident victor rabbits’, and ‘wisely cautious victor rabbits’. I’d also introduce several transitions in T, for example:

      ordinary rabbit + ordinary rabbit \to overconfident victor rabbit

      overconfident victor rabbit + ordinary rabbit \to wisely cautious rabbit

      You can try to work out the Hamiltonian for such a process.

      Or, you can check to see if the Hamiltonian you propose is an infinitesimal stochastic operator. If it is, it describes some random process. If not, there’s something wrong with it.

      • Arjun Jain says:

        Also, if operating with a on z^n includes n, the number of ways a rabbit can be chosen from n rabbits, then shouldn’t operating with a^{\dagger} also include the number of ways an output rabbit can be chosen from the k inputs (at least in some cases)?

        • John Baez says:

          We shouldn’t redefine a^\dagger, it’s too beautiful to change. If we have a situation where a transition occurs at a rate proportional to f(k) because we need to make some choice among the k inputs, we can multiply the Hamiltonian by f(k) to account for that. I don’t think duels between rabbits occur twice as fast because there are 2 choices of which rabbit might survive.

  11. Arjun Jain says:

    In the section on Dueling Rabbits, you say “(If you prefer unordered pairs of rabbits, just divide the Hamiltonian by 2. We should talk about this more, but not now.)”. Have you talked about this in some later post?

    • John Baez says:

      I never got around to it. But it’s easy to create a number of variants of the rate equation and master equation, depending on whether one is interested in:

      • ordered k-tuples of not-necessarily-distinct inputs
      • unordered k-tuples of not-necessarily-distinct inputs
      • ordered k-tuples of distinct inputs
      • unordered k-tuples of distinct inputs

      In my notes I’m always considering ordered k-tuples of distinct inputs. These are counted by the falling powers n^{\underline{k}}. This case turns out to be most easily described using annihilation and creation operators. However, to count unordered k-tuples of distinct inputs, you just divide by k!. So, you can just divide each term in the Hamiltonian by a suitable factor.

You can use HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,818 other followers