# Determining computational complexity of stochastic processes

I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let's use T to denote the average number of steps made by the Markov chain before convergence.

I want to know how T scales with N. Specifically I'd like to know whether T=O(poly(N)) or T=O(exp(N)), anything more specific would be a bonus but is not required. To determine this I have run the program for many values of N and got the corresponding values of T. But how do I determine the complexity from this data? How do I distinguish whether between a high order polynomial and a slow exponential? To what degree is it actually possible to do this?

Note: I have also posted this question in an alternative form at Polynomial and exponential regression

-
What is a spin lattice? – Ricky Demer Jan 29 '12 at 11:18
Basically it is just N bits that have certain correlations based on the geometry of a 2d lattice. I suppose the only important point is that the dimension of the state space explored by the Markov chain grows with N, and I need to know how T grows in response to that. I've edited my post to make that clearer (and remove some errors) – Matthew Matic Jan 29 '12 at 11:37
I have also posted this question in an alternative form... You definitely should not have. This question is already far from satisfactory but, compared to it, the other one is a real mess. Re the question here: what do you call the average number of steps made by the Markov chain before convergence? – Did Jan 30 '12 at 9:44
I have a convergence test, and stop the chain when it is satisfied. I count the number of steps required for this in each run of the program, and average over many. Also, I would regard the other form of the question as the better one, since it states the actual abstract problem, avoiding the concepts that have needed to be clarified here. If you could give me any pointers on why these questions are badly formed, I would be grateful to hear it. – Matthew Matic Jan 30 '12 at 9:53
There is no (stochastic-processes) nor (markov-chains) in this question. – Did Feb 6 '12 at 7:26

The mathematical distinction between the two regimes is clear:

• Polynomial growth means that $\log T(N)\leqslant c\cdot\log N$ for every $N$, for some finite $c$.
• Exponential growth means that $\log T(N)\geqslant c\cdot N$ for every $N$, for some positive $c$.

Hence, theoretically speaking, the task is to prove that $\limsup A(N)$ is finite or that $\liminf B(N)$ is positive, where $$A(N)=\frac{\log T(N)}{\log N},\qquad B(N)=\frac{\log T(N)}N.$$ In real life however, the distinction is less clear since the data one has to rely on is a finite collection of points $(N_k,T(N_k))$ with $1\leqslant k\leqslant K$, for some finite $K$, hence it is impossible, strictly speaking, to decide from these $K$ points if the growth is polynomial or exponential (or intermediate).

What one usually does in such cases is to plot the points $(N_k,A(T(N_k)))$ and $(N_k,B(T(N_k)))$. If the $A$ plot seems to reach (upwards) a plateau of finite height for the large values of $N_k$, then polynomial growth is possible. If the $B$ plot seems to reach (downwards) a plateau of positive height for the large values of $N_k$, then exponential growth is possible.

-
Thanks for your answer. I suppose that one can also say that for polynomial growth log log T = O(log log N), and for exponential growth log log T = O(log N). As such, we could define A' = loglog(T)/loglog(N) and B' = loglog(T)/log(N), which would have the same properties as A and B, above. Or does this extra level of logarithms cause more ambiguity? – Matthew Matic Jan 31 '12 at 10:06
Hmmm... Surely you realize that $T=N^{\log N}$ yields a finite $A'$ and that $T=\mathrm e^{T^8}$ yields a finite $B'$. However, one might wish to avoid calling polynomial growth, resp. exponential growth, these regimes. – Did Jan 31 '12 at 11:39
Sorry, in my previous comment one should read that: $T=\mathrm e^{N^8}$ yields a finite $B'$. – Did Jan 31 '12 at 18:58