[helene_t]

Consider a chain of Schrodinger-cats, evolving in discrete time. In each time step, a cat's probability of being alive influences the neighbor cat's probability of being alive after the time step. So over many time steps, the whole chain becomes inter-correlated. Somewhat counter-intuitively, cats are allowed to revive as well as to die.

Now the question: does it matter if the cats are observed (i.e. the probabilities collapse) at each time step, or if they are only observed at the end of time, after say 100 time steps?

The reason I ask this question is that I'm experimenting with the following algorithm for estimation in Hidden Markov Models:

We have a single measurement for each cat which is correlated to its true state. Further, we know that each cat's true state is related to its neighbors' states. We can exploit this correlation in the estimation procedure:

Our posterior knowledge about a cats state after the i'th iteration is obtained by a Bayesian update of its prior state as inferred from the neighbor cats' prior states, plus the measurement from the cat in question. Now the posterior distribution of that state is used for the update procedure for the neighbor cats in the next iteration, etc.

The problem is that it's not always computationally feasible to retain the whole distribution of states during the iteration, so one must opt for either:
MCMC: sample a state from the posterior distribution and use this "deterministic" state in the next step
EM: use some summary statistic, say the "expected" state

I have the idea that MCMC is more robust while EM is faster. In particular, I'm interesting in intermediate solutions where the sampling is vague:
MCMC: 70% chance of deadness=1, 30% of alive, i.e. deadness=0
EM: deadness=0.7
Vague sampling: say 55% chance of deadness=0.85 and 45% chance of deadness=0.5, or some such.

It suddenly struck me that this algorithm has a taste of quantum dynamics: I have the choice of letting the probability distribution describing our knowledge about each cat's state collapse during the iteration.

Is this analogy valid? If so, is there any physics literature that I should read in order to understand the estimation problem better, or to explain it better?

[Fluffy]

I hope Gerben knows something about this, I have no idea.

I think Heissenberg's law or theory, or I don't know how to say in english), is based on the fact that you give energy to a particle in order to 'watch' it, and that energy will move it.

Here that principle doesn't happen, as the cats won live or die ebcause you look at them.

[Al_U_Card]

How about if you make the cats aware of the state of each cat immediately adjacent to it and it must assume the same state as both cats if they are the same state, but can independantly choose a state should the adjacent cats be in different states. This superposition of the wave will negate the observational effect as we all know that birds of a feather (there may be more than one way to skin a cat, but they should be dead first.....)

[Al_U_Card]

btw Helene, did Shubi put you up to posting this?

[hrothgar]

Comment 1: Quantum mechanics is ugly, counter-intuitive stuff. Unless you have a very real need to incorporate these types of phenomena into a model, I recommend keeping very far away from this stuff.

Comment 2: You need to be a lot more precise in formulating the characteristics of your model. From the sounds of things, you have a chain of objects

X1, X2, X3, X4, X5,.... Xn-1, Xn

existing in a discrete time model. Each of these objects can be in one of two different states (State 1 or State 2). Objects are able to randomly flip from State 1 to State 2 and vice versa. The probability that X3 is in State 1 at time "T" is a function of X3's state at Time T-1, as well as the state of X2 and X4. (Its unclear how a change in state propagates across the system. Thing's look very different if X3's state in Time T is a function of X2's state at Time T or X2's state at time T-1. Lag's are a bitch)

My own advice would be to start by solving your model without introducing any kind of quantum uncertainty to the system. If you run into any kind of problem with computational limits, constrain the size of the initial vector. (Alternatively, you might prefer to assume that you have a vector of infinite size to avoid problems with the corners) Once you are comfortable with the simple stuff, you can add complexity like uncertainty. Once you are comfortable with the complex stuff, you can increase the size of vector.

Ultimately, the most important question is going to be whether or not you have any kind of path dependency. (Assume that you were to run the system for an infinite number of rounds with no measurements what-so-ever. Does the system always converge on the same state regardless of the starting conditions?) I suspect that if you have no path dependency, measurement won't really matter much.

BTW: There is an old computer game called "Life" that you might want to look at. In some ways, the game is similar to what you are describing. The game is deterministic rather than probabilistic, but it feels the same. More importantly, LOTS of folks did a bunch of interesting work with this game. You might find some interesting results.

There is a decent description of the game on wikipedia that will almost immediately lead you to a discussion of whats known as a cellular automaton.

[Al_U_Card]

Man! does that bring back memories of being an undergrad at Waterloo in the 70's and going by a darkened room in the computing centre....inside were 3 or 4 mathies clustered around a crt looking at a pattern of zeroes on a grid.....when they exclaimed that it was the game of life....we figured it was time that they got one instead....lol

[cherdano]

hrothgar, on Jun 18 2007, 12:54 PM, said:

Comment 1: Quantum mechanics is ugly, counter-intuitive stuff. Unless you have a very real need to incorporate these types of phenomena into a model, I recommend keeping very far away from this stuff.

I admit I thought quantum mechanics is beautiful, counter-intuitive stuff. It's definitely more elegant than any other physical theory I know or have some idea off.

[helene_t]

Tx for comments, Richard.

You say it's unclear how the state propagates through the system. Here there may be some general MCMC results that apply, but I find it hard to read those articles and besides I'm not sure if anyone has ever used the MCMC approach to this kind of models. You have two Markov chains at work at the same time, in different dimensions: My model for the correlations between the true states is a Markov chain in geometric space (cat space), while the chain of succesive estimates generated by my algortihm is a Markov chain in iteration space (time space).

Anyway, starting with a deterministic approach for simplicity is not an option since the problem I'm interested in is stocastic. If we call the state of node A at iteration step i X[A,i], the determinstic version would be something like
X[B,i+1] = X[A,i] if B is closer to A than to C
X[B,i+1] = X[C,i] otherwise
and that is not so interesting. I have used celular automata ("life"-like models) for problems where the form of the prior distribution is such that even the deterministic version can give some insight, such as when modelling ecosystems. For my current project, though, stocastics is everything.

You say that I might like to assume infinite cat space to avoid boundaries, while at the same time use a small set of cats to start with to get some computational results fast. Realistic cat space is 317,000 (it's genomic research) but for experimental purposes I could use circular cat space. I used to do that when I played with celular automata. Haven't tried it here. Since my department is very much focused on practical applications in genomic research, such unrealistic models are not kosher, unfortunately. In principle, the boudaries are not a problem since it is biologically plausible to assume the "outside" to remain non-informative through the whole iteration, but the programming would be simpler if I could avoid them.

Al:
It's a funny idea to modify the problem to one of cats observing each other, rather than all the cats being observed by an external observer. Actually, your idea may be closer to the problem I'm interesting in. Have to think about it.

For the quantum analogi, cats observing each other is not relevant, though, as far as I understand it. The quantum wave function of cat is an objective thing that either collapses or does not collapse. It's not like it could collapse from the neighbor cats' points of view and stay undertermined from distant cats' points of view at the same time.

[hotShot]

If the cat's just "see" each other, it adds nothing to the problem.

If you want to to view your problem from the cat's point of view, the proper theory from physics to handle that is the relativity theory.

If you think the cat's interact, the complexity of your problem explodes.
This is of cause similar to the quantum mechanics needed to describe Atoms with more than one electron. You need to describe the interaction between each pair of cats.
Your problem might be even more complex, because the electrons are assumed to be equivalent and exchangeable and don't know if thats true for your cats.

[helene_t]

hotShot, on Jun 19 2007, 12:10 PM, said:

[....]If you want to to view your problem from the cat's point of view, the proper theory from physics to handle that is the relativity theory.

If you think the cat's interact, the complexity of your problem explodes.[.....]

Oh no, my cats don't move at all, certainly not at near-light speed.

In my algortihm, the genomic markers ("cats") interact only in the sense that their true states are correlated. This indeed causes some complexity which is what makes the problem interesting.

The interaction between the cats in my quantum dynamics analogi corresponds to the way the correlation between the true states casuses information about the true states to propagate through the cat chain as the algorithm proceeds.

In a way this is not a good analogy since in quantum dynamics, the true state of each cat is probabilistic. In my algortihm, there is a single, constant true state for each genomic marker, and the probability distribution of that marker reflects our limited knowledge about it.

[Gerben42]

In fact I've been having a similar problem in my work recently.

Schrödinger's cat was only to visualise the problem. To someone like me your problem looks more simple looking at a set of particles, either with spin up or spin down. Consider a row of particles where each particle that changes its spin will have a nonzero chance of interacting with its neighbours (trigger effect).

What you are looking for is something called statistical dynamics. The same is done to develop theories like plasma dynamics. You start with single particles, then statistics thereof, and from that you deduce macroscopic behaviour.

My approach would be to use the statistical parameters as in MCMC and then describe your interaction mechanism in terms of these variables.

[hotShot]

Well stochastic and Morkov chains are not my piece of cake, but I spend some time with numerical simulations and iteration/optimization algorithms.

Would it be right to say you are using sort of genetic algorithms to optimize a genetic problem?

[Al_U_Card]

The most curious aspect of quantized information is the observational effect. This is the basis and the foundation of consciousness. We know what we observe and we change what we interact with.......sometimes just by observing it because our conscious observation contained intent. The intention is what perturbs the quantum states as they react to the inherent energy field of the observer. This is pretty heady stuff for a stochastic simulation but then, so is life.....

[helene_t]

hotShot, on Jun 19 2007, 12:50 PM, said:

Would it be right to say you are using sort of genetic algorithms to optimize a genetic problem?

Not quite, I think. In genetic algorithms, several solutions compete and the more succesful ones are allowed to survive and reproduce.

Here, you could say that the cats that are most succesful in being dead (rsp alive) are allowed to stay dead (rsp alive) and to reproduce their deadness by influencing their neighbor's state. But this is somewhat far-fetched.

Actually, I recently saw an article about a hybrid of MCMC and genetic algortithms, in which multiple MCMC-chains compete for survival and reproduction.

[helene_t]

Gerben42, on Jun 19 2007, 12:50 PM, said:

[....]Schrödinger's cat was only to visualise the problem. To someone like me your problem looks more simple looking at a set of particles, either with spin up or spin down. Consider a row of particles where each particle that changes its spin will have a nonzero chance of interacting with its neighbours (trigger effect).[......]

Out of curiosity: is the trigger effect a classical effect or a quantum effect?

Quote

My approach would be to use the statistical parameters as in MCMC and then describe your interaction mechanism in terms of these variables.

You're probably right. I thought that this quantum analogy was cool because the undecided state of the cat is something that is easier to visualize than all this dissying, subjective probabilities. But I see that such a not-so-accurate analogy creates confusion.

[hotShot]

So you have a stable number of entities that have a given set of "attribute states" that could change at each step following a given set of rules and you are interested in the result distribution?

And are you "optimizing" the set of rules to match some reality or is it purely a theoretical model.

[helene_t]

hotShot, on Jun 19 2007, 03:45 PM, said:

So you have a stable number of entities that have a given set of "attribute states" that could change at each step following a given set of rules and you are interested in the result distribution?

And are "optimizing" your set of rules to match some reality or is it purely a theoretical model.

No, it's not a dynamic model. The only thing that changes during iteration is my estimate, which (hopefully) comes closer and closer to the reality.

Each marker has some hidden state which could be caryotype, chromatin state, which two of the four grandparents that passed a copy on to a specific grandchild, or some such. The important thing is that two neighbor loci are likely to have the same state.

[Al_U_Card]

The most interesting part (and scariest for some) is the quantum realisation that reality is subjective and that objective reality is transitory! Consciousness is the creator of reality and therefore is part of the source of creation. Even a cat (when named for Schrödinger) can show you that..... Me? Ow!

[DrTodd13]

Al_U_Card, on Jun 19 2007, 10:55 AM, said:

The most interesting part (and scariest for some) is the quantum realisation that reality is subjective and that objective reality is transitory! Consciousness is the creator of reality and therefore is part of the source of creation. Even a cat (when named for Schrödinger) can show you that..... Me? Ow!

That is only one interpretation of quantum mechanics. There are other interpretations in which consciousness plays no role at all.

[Al_U_Card]

Well, those certainly are of interest......to people for whom consciousness is unimportant or irrelevant...

In that respect, perhaps quite a few in fact .....