Large Deviation Principle for Friendship Biases in Galton-Watson Trees
Abstract.
The friendship bias of a vertex is defined as the difference between the average degree of its neighbours and its own degree; for isolated vertices, this bias is considered to be zero. According to the sign of the friendship bias, vertices can naturally be classified as "negative", "neutral", or "positive". The friendship paradox says that the average friendship bias is non-negative for all finite undirected graphs, whether simple graphs or multigraphs. However, the combined number of neutral and positive vertices can be significantly smaller than the number of negative vertices. For instance, in a complete graph on a large number of vertices with a single edge removed, only the two endpoints of the removed edge are positive, while all other vertices are negative. The fractions of different vertex types can also vary across graphs and reflect aspects of the geometry of a graph. The typical behaviour of these fractions has been studied for sparse random graphs that are locally tree-like, as well as for finite and infinite Galton-Watson trees. In this talk, we analyse the atypical behaviour of the fractions of vertex types along a random downward path in an infinite Galton-Watson tree by deriving a large deviation principle as the branching depth grows. The rate function is characterised through a variational problem involving relative entropy under a linear constraint. We discuss its properties in the case of binary branching. Based on joint work with Frank den Hollander.