Here's a simple but potential research problem that I am learning about.

Let's say I am studying a physical system that is governed by N objects. At each time, each object is either "active" and given the number "1" or inactive and given the number "0".

So, the system has $2^N$ possible states.

Now, if I am able to compute and find the state-transition-matrix of this system, it should be a $2^N \times 2^N$ matrix.

(Computability of the matrix is a different question.)

But what I am confused about is this: if I am understanding this problem correctly, the state-transition-matrix is a generalization of the transition matrix of, say, an Ergodic Markov Chain - a matrix that most students learn from basic probability theory (the entries are nonnegative and represent probabilities). Applying the transition matrix to a probability vector "updates" the probability vector that describes the Markov Chain.

But, is the same thing true of the more general state-transition-matrix of the physical system -- a system that is not necessarily a Markov Chain?

I.e., if I can compute this state-transition-matrix, would applying this matrix to some vector then "update" the vector that describes the current state of the system?

If the answer to the above is "yes", then I see one technical issue:

the matrix multiplication wouldn't make sense, as I would be applying a $2^N \times 2^N$ matrix to an N-tuple vector, with each component taking on the values 1 or 0. The vector wouldn't be of length $2^N$.

Where am I going wrong here?

Thanks in advance,

  • 1
    $\begingroup$ the Markov chain transition matrix operates on the vector containing all possible states of the system, so it operates on a rank $2^N$ vector, not on a rank $N$ vector; perhaps your system is such that the dynamics of the $N$ objects is independent; say each is flipped with some probability independent of its neighbors; then your transition matrix is $2N\times 2N$, but more generally it is $2^N\times 2^N$. $\endgroup$ – Carlo Beenakker Apr 11 '16 at 12:17

I am not sure whether you want to describe a deterministic or a stochastic system. In either case your definition of what a "state" is not the usual concept.

The states of a dynamical systems are those variables (or rather a set of variables) such that if you know their values at some time $t$ then you have complete knowledge of the system (in the context of the model, of course). So in your examples there are $N$ states $x_i$, where $x_i$ describes the activity of node $i$. These states can attain the values $0$ or $1$. Your sentence "the system has $2^N$ different states", I would prefer to express as "the state space of the system is finite, it has $2^N$ elements". Elements of the state space are sometimes called states, especially when speaking of "the state of the system at time $t$", but this is really a slight abuse (that you hardly notice any more once you get used to it).

The state transitions of your system, presumably, are then governed by some set of equations of the form $$ x_i(t+1) = f_i(t,x_1(t),\ldots,x_N(t)),\quad i=1,\ldots,N.$$

This would be some sort of discrete dynamical system. This particular class of systems has received quite a bit of attention recently under the name of Boolean networks, precisely because the variables can only take the values $0$ or $1$.

You can of course describe the dynamics of the system as you propose, by writing down a $2^N \times 2^N$ matrix, but this matrix would be pretty boring with one nonzero entry in every column (assuming you want to multiply the matrix from the left). If you do this then also your state space is a funny one, because it is the set of standard unit vectors of length $2^N$, because this vector would have to encode the current activity profile of your nodes, which is encoded by enumerating.

Your analogy with the Markov chain was in fact a good one, just that you did not follow it through. What you describe covers what is known as a "finite-state Markov chain". The system has $N$ states and the state at time $t$ is described by the probability vector which gives the probabilities of being in a particular state. So the state space is the standard simplex, i.e. an uncountable space. The transition matrix describes the evolution on that state space. Still, the system only has finitely many states, i.e. variables whose value I need to know to know what is going on.

To answer your final question: in the study of discrete-time systems $$ x(t+1) = A x(t)$$ it is not uncommon to call $A$ the transition matrix. In this context the entries of $A$ can be any element of any field that you wish. As long as everything is well-defined.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.