For a directed graph $G(V_n, E_n)$ on the vertices $V_n = {1,2, dots, n}$, we study the distribution of a Markov chain ${ {bf R}^{(k)}: k geq 0}$ on $mathbb{R}^n$ such that the $i$th component of ${bf R}^{(k)}$, denoted $R_i^{(k)}$, corresponds to the value of the process on vertex $i$ at time $k$. We focus on processes ${ {bf R}^{(k)}: k geq 0}$ where the value of $R_i^{(k+1)}$ depends only on the values ${ R_j^{(k)}: j to i}$ of its inbound neighbors, and possibly on vertex attributes. We then show that, provided $G(V_n, E_n)$ converges in the local weak sense to a marked Galton-Watson process, the dynamics of the process for a uniformly chosen vertex in $V_n$ can be coupled, for any fixed $k$, to a process ${ mathcal{R}_emptyset^{(r)}: 0 leq r leq k}$ constructed on the limiting marked Galton-Watson tree. Moreover, we derive sufficient conditions under which $mathcal{R}^{(k)}_emptyset$ converges, as $k to infty$, to a random variable $mathcal{R}^*$ that can be characterized in terms of the attracting endogenous solution to a branching distributional fixed-point equation. Our framework can also be applied to processes ${ {bf R}^{(k)}: k geq 0}$ whose only source of randomness comes from the realization of the graph $G(V_n, E_n)$.
Download