The multi-level friendship paradox for sparse random graphs (Q6851243)

This paper is about the friendship paradox, which in its simplest form is the initially surprising idea that one's friends tend to have at least as many friends as one does oneself, an observation first made in sociology in the 1950s. Mathematically, representing individuals as vertices of a finite graph \(G\) and with (undirected) edges denoting friendships, one formulation of this is the statement that if \(G\) does not have isolated vertices, then if \(X_{0}\) is a uniformly at random (u.a.r) chosen vertex and \(X_{1}\) is a u.a.r. neighbour of \(X_{0}\) then \(\mathbb{E}(d(X_{1})-d(X_{0}))\geq 0\) where as usual \(d(x)\) is the degree of vertex \(x\) -- the proof is very short. Note that \(\mathbb{E}(d(X_{0})=\overline{d}\) denotes the average degree of the graph.\N\NIn [\textit{J. Brown Kramer} et al., Am. Math. Mon. 123, No. 9, 900--908 (2016; Zbl 1391.05232)] the multistep friendship paradox is introduced -- the question of whether friends of a friend ... of a friend have more friends than the average degree. The authors of that paper introduce a model whereby a vertex \(X_{0}\) is picked u.a.r., then a u.a.r. neighbour \(X_{1}\) of \(X_{0}\) is chosen, then a u.a.r. neighbour \(X_{2}\) of \(X_{1}\) is chosen, and so on. Thus, if we choose \(X_{0},\ldots X_{k}\), we have a random walk on the graph of length \(k\). They show the analogous result for \(\mathbb{E}(d(X_{k})\geq \overline{d}\).\N\N\par In the paper under review the authors focus on both the backtracking random walk (which is just the random walk on the graph as studied by Kramer et al. [loc. cit.]) and on the non-backtracking random walk (which is conditioned not to return to the vertex from which it just came), as well as lazy versions of these which have a positive probability of staying put. Whatever walk we are using, we use \(P_{n}^{(k)}(i,j)\) for the probability the relevant walk goes from \(i\) to \(j\) after \(k\) steps on an \(n\)-vertex random graph with no isolated vertics \(G_{n}\), though this is not a Markov chain for the non-backtracking walk. Now the \(k\)-level friendship bias for vertex \(i\) is \[\Delta_{i,n}^{k}=\sum_{j\in [n]}P_{n}^{(k)}(i,j)d_{G_{n}}(j)-d_{G_{n}}(i)\] and the \(k\)-level quenched friendship bias measure \(\mu_{n}^{(k)}\) is the average of the \(n\) Dirac measures at each \(\Delta_{i,n}(k)\). We can also take the average over \(i\), of the \(\Delta_{i,n}^{k}\), which we denote \(\Delta_{[n]}^{k}\), and the first result in the paper is that \(\Delta_{[n]}^{k}\geq 0\) with equality conditions provided.\N\N\par The graphs in the paper under review are locally tree-like, which essentially means that there is a limiting rooted random tree that the graph looks like on a large scale. However, a number of the limiting results to be proved depend on the nature of the limiting tree.\N\N\par Many results in the paper are about \(\mu_{n}^{(k)}\) and its convergence properties, as \(n\) and/or \(k\) tend to infinity. For example, when the walk is non-backtracking, the two limits commute, whereas when it is backtracking, they do not when the local limit is a subcritical tree.\N\N\par Regarding long-term behaviour, when \(G_{n}\) is almost surely connected and not bipartite, there is of course a stationary distribution for the backtracking case which gives rise to a stationary friendship bias as \(k\rightarrow\infty\). This allows the authors to find the limiting law in this case. They then extend this beyond the somewhat restrictive assumptions of connectedness and non-bipartiteness.\N\N\par There is also consideration of the case where \(k=k_{n}\) grows with \(n\) in various ways. The key tools in most of the proofs are the local convergence, analysis of what the local limit looks like, and exploration of the local limit.