A note on perfect simulation for Exponential Random Graph Models

¹ Statistics Department, Universidade Federal de São Carlos, São Carlos, Brazil.
² Unité de Mathématiques Pures et Appliquées, Laboratoire de l’Informatique du Parallélisme, Ecole Normale Supérieure de Lyon, Université de Lyon, Lyon, France.
³ Statistics Department, Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, Brazil.

^* Corresponding author: acerqueira@ufscar.br

Received: 27 April 2018
Accepted: 6 November 2019

Abstract

In this paper, we propose a perfect simulation algorithm for the Exponential Random Graph Model, based on the Coupling from the past method of Propp and Wilson (1996). We use a Glauber dynamics to construct the Markov Chain and we prove the monotonicity of the ERGM for a subset of the parametric space. We also obtain an upper bound on the running time of the algorithm that depends on the mixing time of the Markov chain.