MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G(n,p)$ be the usual random graph on $n$ vertices with each edge existing independently with probability $p$ (no self loops , or double edges not are allowed). I would like to simulate the distribution of a random graph given the event $T\geq a$ where $T$ is the number of triangles in the random graph. The natural approach is Metropolis Hastings. I've already found some semi-efficient algorithms that approximate the number of triangles in a given random graph, however I am still at a loss of what Markov chain to pick for a good rate of convergence. I would immensely appreciate a push in the right direction. In particular, some references would be fantastic. Thanks!

share|cite|improve this question
what value of $a$ are you interested in? Also, if you are interested in computing expectations of the form $E[\phi(G) | T(G) \geq a]$, importance sampling might just work as well. – Alekk Apr 26 '12 at 23:33
My question would be: which values of $p$ are you interested in? Are you talking about the regime where you expect to have lots of triangles or few? – Anthony Quas Apr 26 '12 at 23:41
@Alekk: I am interested in all values of $a$ but in particular for $a>E(T)$ which is on the order of $n^3p^3/6$. I'm not so much interested in calculating expectations as just seeing what the graphs look like. – Alex R. Apr 27 '12 at 2:11
@Anthony Quas: I would be interested in all (fixed) values of $p$. What I am sure of is the number of triangles is expected to be much less than $a$, which translates to $P(T\geq a)$ being very small by itself. – Alex R. Apr 27 '12 at 2:13
@Alex R: just being curious but how are you planning to "see what the graphs look like"? For small graphs that might be easy to plot some of them, but for large graphs I think that you are going to compute some expectations (number of copie of K_4, is it connected, etc...), aren't you? – Alekk Apr 27 '12 at 8:48

Your Answer


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

Browse other questions tagged or ask your own question.