Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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