Analysis of a class of Recursive Distributional Equations Including the Resistance of the Series-parallel graph
Peter S. Morfe · 2025
Read Analysis of a class of Recursive Distributional Equations Including the Resistance of the Series-parallel graph by Peter S. Morfe (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-11036.txt.
Introduction
Peter Morfe analyzes a family of recursive rules for random values that was proposed by Gurel-Gurevich and involves a bias setting. One member of the family gives the log of the electrical resistance of a series-parallel graph, a network built by joining parts in line and side by side. Understanding such rules helps predict how random network traits behave at large size.
He derives a time-step equation, much like a Fisher-KPP wave equation, that tracks the spread of solutions. At the middle bias setting, that equation has a clean large-scale limit. Applied to the graph, the results confirm the limit that Addario-Berry and colleagues had conjectured for the scaled log resistance.
Catalog record
| CREATOR | Peter S. Morfe |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 115 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-11036
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Analysis of a class of Recursive Distributional Equations Including the Resistance of the Series-parallel graph Peter S. Morfe Abstract . This paper analyzes a class of recursive distributional equations (RDE’s) proposed by Gurel-Gurevich [ 17 ] and involving a bias parameter p p , which includes the logarithm of the resistance of the series-parallel graph. A discrete-time evolution equation resembling a nonlinear, fractional Fisher-KPP equation is derived to describe the CDF’s of solutions. When the bias parameter p = 1 2 p=\frac{1}{2} , this equation is shown to have a PDE scaling limit, from which distributional limit theorems for the RDE are derived. Applied to the series-parallel graph, the results imply that N − 1 / 3 log R ( N ) N^{-1/3}\log R^{(N)} has a nondegenerate limit when p = 1 2 p=\frac{1}{2} , as conjectured by Addario-Berry, Cairns, Devroye, Kerriou, and Mitchell [ 1 ] . 1. Introduction 1.1. Resistance of the Series-Parallel Graph This paper seeks to address an old problem, namely, the asymptotic analysis of the resistance of the series-parallel graph. This is the random hierarchical lattice introduced by Hambly and Jordan [ 18 ] and constructed as follows: Start with a graph G^{(0)} consisting of one edge connecting two nodes, A and B . At step n of the construction, obtain G^{(n)} from G^{(n-1)} by replacing every edge by two edges, either in series or in parallel, the result being decided by independent coin flips. Interpreting G^{(n)} as a resistor network where each edge has resistance one, one can study the effective resistance R^{(n)} between A and B . The asymptotic analysis of R^{(n)} as n\to\infty was initiated in [ 18 ] . Since G^{(n)} can be realized by combining two independent copies G^{(n-1)}_{1} and G^{(n-1)}_{2} of G^{(n-1)} , say, in series with probability p and in parallel with probability 1-p , the law of the resistance R^{(n)} is a solution of the recursive distributional equation (RDE) \displaystyle R^{(n)}\overset{d}{=}\left\{\begin{array}[]{r l}R^{(n-1)}_{1}+R^{(n-1)}_{2},&\text{with probability}\,\,p,\\ \left(\frac{1}{R_{1}^{(n-1)}}+\frac{1}{R_{2}^{(n-1)}}\right)^{-1},&\text{with probability}\,\,1-p.\end{array}\right. Using this fact, a number of results were proved in [ 18 ] : When p>\frac{1}{2} , the logarithm \log R^{(n)} grows linearly in n . More precisely, there is a constant \lambda(p)>0 such that (1) \displaystyle\mathbb{P}\left\{(2p-1)\log 2\leq\frac{1}{N}\log R^{(N)}\leq\lambda(p)\right\}\to 1\quad\text{as}\,\,N\to\infty. Due to symmetry, this implies that \log R^{(n)}\to-\infty linearly when p<\frac{1}{2} . At the critical point p=\frac{1}{2} , Hambly and Jordan instead proved that \log R^{(n)} exhibits sublinear growth. The main results of this paper (see Theorem 1 and Corollary 1 below) show that, in fact, \log R^{(N)} grows like N^{\frac{1}{3}} . Specifially, \displaystyle\frac{1}{(72\zeta(3))^{\frac{1}{3}}N^{\frac{1}{3}}}\log R^{(N)}+\frac{1}{2}\overset{d}{\to}\text{Beta}(2,2)\quad\text{as}\,\,N\to\infty, where \zeta is the Riemann zeta function. This confirms a conjecture of Addario-Berry, Cairns, Devroye, Kerriou, and Mitchell [ 1 ] . The starting point for this work is an observation made by Gurel-Gurevich during a presentation at the open problem session at the Workshop for Disordered Media at the Rényi Institute in Budapest in January 2025 [ 17 ] . He noted that the transformation X^{(n)}=\log R^{(n)} leads to an RDE of the form (2) \displaystyle X^{(n)}=\Phi(X^{(n-1)}_{1},X^{(n-1)}_{2}), where \Phi is the random function defined by \displaystyle\Phi(x,y)=\left\{\begin{array}[]{r l}\max\{x,y\}+f(|y-x|),&\text{with probability}\,\,p,\\ \min\{x,y\}-f(|y-x|),&\text{with probability}\,\,1-p,\end{array}\right. and f(u)=\log(1+e^{-u}) . This led him to pose the following problem: Problem . Consider the RDE ( 2 ) with forcing \Phi given by ( 1.1 ) under general assumptions on the nonincreasing function f:[0,+\infty)\to[0,+\infty) . What can be said about the long-time behavior of the law of solutions? This paper endeavors to address this problem in some generality when p=\frac{1}{2} , focusing on the distributional limit of n^{-1/3}X^{(n)} . The general framework developed here applies not only to the resistance of the critical series-parallel graph, but also to some other RDE’s considered recently in the literature. For instance, as is shown in Section 4 below, the class of RDE’s determined by ( 2 ) and ( 1.1 ) includes the symmetric hipster random walk from [ 1 ] and two-player symmetric cooperative motion, one of the RDE’s analyzed very recently by Addario-Berry, Beckman, and Lin in [ 3 ] . While the analysis of the asymptotic behavior in the case p\neq\frac{1}{2} is not touched on here, the framework developed in this paper suggests that it is related to the singular limit of certain fractional, quasilinear variants of the Fisher-KPP equation. This is made precise in Section 1.3.4 below. 1.2. General Setting Consider the following general setting, which generalizes the forcing \Phi in ( 2 ). Given a Bernoulli random variable \Theta and random nonincreasing functions f_{+},f_{-}:\mathbb{R}\to[0,+\infty) , define \Phi by \displaystyle\Phi(x,y)=\left\{\begin{array}[]{r l}\max\{x,y\}+f_{+}(|x-y|),\quad\text{if}\,\,\Theta=1,\\ \min\{x,y\}-f_{-}(|x-y|),\quad\text{if}\,\,\Theta=0.\end{array}\right. For simplicity, the pair (f_{+},f_{-}) will be assumed to be independent of \Theta henceforth. The object of interest in this paper is the RDE determining the law of random variables (X^{(n)})_{n\in\mathbb{N}} through the recursion (7) \displaystyle X^{(n)}\overset{d}{=}\Phi(X^{(n)}_{1},X^{(n)}_{2}), where X^{(n)}_{1},X^{(n)}_{2} are i.i.d. copies of X^{(n-1)} , which are independent of \Phi . Throughout the paper, equality is only required to hold in law; questions of couplings or constructions of \{X^{(n)}\} will not be treated. The form ( 1.2 ) of \Phi is not just a repackaging of ( 1.1 ). In the asymmetric setting where f_{+}\neq f_{-} , this class of RDE’s includes the one associated with Pemantle’s min-plus binary tree, the asymptotics of which were analyzed by Auffinger and Cable [ 5 ] , as well as certain versions of the asymmetric hipster random walk from [ 1 ] and two-player totally asymmetric, q -lazy cooperative motion, one of the RDE’s analyzed by Addario-Berry, Beckman, and Lin in [ 2 ] . In all of these examples, as well as the symmetric models from [ 1 , 3 ] already mentioned above, the asymptotic analysis carried out here generalizes the limit theorems previously obtained within a unified setting. Henceforth define the bias parameter p by p=\mathbb{P}\{\Theta=1\}. The joint law of the functions (f_{+},f_{-}) will be denoted by \mathbf{P} in what follows. \mathbf{P} is assumed to be a Borel probability measure on the space BC([0,\infty))\times BC([0,\infty)) of pairs of bounded continuous functions in [0,\infty) with the uniform norm topology. In most of the examples of interest here, however, f_{+} and f_{-} are deterministic; see the discussion in Section 4 . 1.3. Evolution of the CDF The main results of this paper are obtained by treating the evolution of the law of X^{(n)} as if it were governed by a parabolic partial differential equation (PDE). Following [ 2 , 3 ] , this is done at the level of cumulative distribution functions (CDF’s) rather than probability measures. In particular, in what follows, define the operator T by taking a CDF F , letting X_{1},X_{2} be i.i.d. random variables distributed according to F , and defining TF to be the CDF of the random variable Y determined by (8) \displaystyle Y=\Phi(X_{1},X_{2}), where \Phi is sampled independently of (X_{1},X_{2}) . With this notation, it follows that the random variables \{X^{(n)}\} solve the RDE ( 7 ) if and only if the corresponding CDF’s \{F_{n}\} solve the recursive equation F_{n+1}=TF_{n}. In the first step of this work, a discrete-time evolution equation is derived to describe the evolution of the CDF of X^{(n)} . Namely, there is a nonlinear operator \mathscr{L} defined on the space of CDF’s such that the recursive equation F_{n+1}=TF_{n} can be rewritten in the