Connections between probability estimation and graph theory

摘要

Several authors [1], [2], [3], [4], [5], [6], [7] have characterized limits of graph sequences in terms of extremal distributions on exchangeable random graphs. Parallely, information theorists and statisticians have used patterns of i.i.d. sequences as a framework to develop probability estimation techniques over large alphabets.In this brief note, we observe that measures over patterns of infinite i.i.d. sequences correspond to extremal distributions on exchangeable random graphs.