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.