Stochastic recursions on directed random graphs

This is the authors' abstract. We don't add key points for this paper.

For a directed graph G(Vₙ, Eₙ) on the vertices Vₙ = \1,2, , n\, we study the distribution of a Markov chain \ R⁽ᵏ⁾: k ≥ 0\ on Rⁿ such that the ith component of R⁽ᵏ⁾, denoted Rᵢ⁽ᵏ⁾, corresponds to the value of the process on vertex i at time k. We focus on processes \ R⁽ᵏ⁾: k ≥ 0\ where the value of Rᵢ⁽ᵏ⁺¹⁾ depends only on the values \ Rⱼ⁽ᵏ⁾: j → i\ of its inbound neighbors, and possibly on vertex attributes. We then show that, provided G(Vₙ, Eₙ) converges in the local weak sense to a marked Galton-Watson process, the dynamics of the process for a uniformly chosen vertex in Vₙ can be coupled, for any fixed k, to a process \ R_∅⁽ʳ⁾: 0 ≤ r ≤ k\ constructed on the limiting marked Galton-Watson tree. Moreover, we derive sufficient conditions under which R⁽ᵏ⁾_∅ converges, as k → ∞, to a random variable 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 \ R⁽ᵏ⁾: k ≥ 0\ whose only source of randomness comes from the realization of the graph G(Vₙ, Eₙ).