Sankhya: The Indian Journal of Statistics

2006, Volume 68, Pt. 2, 183--197

A Poisson Approximation for Coloured Graphs Under Exchangeability

Annalisa Cerquetti and Sandra Fortini, Universit\`a Bocconi, Milano, Italy

SUMMARY. We introduce random graphs with exchangeable hidden colours and prove an asymptotic result on the number of times a fixed graph appears as a subgraph of such a random graph. In particular, we give necessary and sufficient conditions for the number of subgraphs isomorphic to a given graph to converge, under a negligibility assumption on the frequencies of colours. Moreover, we prove that the limiting law, when it exists, is a mixture of Poisson distributions. Our proofs rely on Stein-Chen method for Poisson approximations of sums of weakly dependent random variables. Finally, we discuss an application of the asymptotic result in Bayesian modeling.

AMS (2000) subject classification. Primary 60F05; secondary 05C80, 62F99.

Key words and phrases. Exchangeability, Poisson approximation, random graphs, subgraph enumeration.

Full paper (PDF)