Determining computational complexity of stochastic processes

Question

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

Answer 1

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.