betaFeedback

WorksMathematics

Cumulant Generating Function of the Hill-Lane-Sudderth urn model

Abstract

We consider the Hill, Lane and Sudderth urn, in which a black or white ball is added at each step with probabilities depending on the current proportion of black balls. We solve the equation for the limiting normalized cumulant generating function when the urn function is invertible on the outer branches beyond the fixed points and the corresponding inverses are Lipschitz. The solution has a parametric representation through three quadratures of the urn function and a limit of compositions of radicals, with no derivatives or inverses of the urn function in the final formula. We prove an error bound that does not accumulate along the partition and remains valid when starting from the initial singularity. Four examples with exact solutions illustrate the two orientations of the construction, the non-affine case and the presence of zeros.

Introduction

The Hill, Lane and Sudderth (HLS) urn is a two-color reinforcement model: one ball is added at each step, and the probabilities of the two colors depend on the current composition [1]. The current proportion thus summarizes the past additions, while the urn function determines how this history influences the next addition. Varying this response gives a common mathematical description of growth processes arising in different settings [2, 3].

Among these processes are leaf counts in random trees [4] and elephant random walks with either one or a fixed number of draws with replacement from the past [5, 6]. Nonlinear responses arise naturally when past choices affect subsequent preferences. In technological diffusion, current market shares influence later adoptions through positive or negative feedback [7]; increasing returns and social influence can produce competing long-run outcomes [8]. When return weights are proportional to a common power of wealth, the two-agent model with wages [9] also has an autonomous urn description. Each allocation of the capital return is an urn addition, with a probability determined by the current wealth shares. Deterministic wages make accumulated wealth an affine transformation of the urn count, so its fluctuations can be studied through the same process [3].

In irreversible magnetic growth, spins are added with probabilities determined by the accumulated magnetization [10]. A nonlinear response can sustain competing magnetizations, making the distribution of growth histories relevant even when the fixed points are known. Related competition occurs between two growing neuronal extensions, or neurites [11]. Pólya urn models have also been used to describe distributions of enantiomeric excess in asymmetric autocatalysis [12]. The review [3] develops cooperative nonlinear production rules as further illustrative urn models with several possible final compositions.

Nonlinear urns also describe the accumulation of information. In broadcasting on growing recursive graphs, a new vertex samples a fixed odd number of earlier vertices, at least three, uniformly with replacement. Each sampled color is independently flipped with a probability strictly between zero and one half, and the new color is chosen by majority vote [13]. The probability of choosing a given color is therefore a polynomial of its current fraction, and the urn records the number of vertices of each color. In reinforced recommendation, the reduction to one user and two items gives an urn with power-law reinforcement [14, 3]. Related feedback rules govern which new observations are added to a stored memory, as discussed in the review. A different response arises in urns with triggering: discovering an element expands the set of available elements [15]. This mechanism leads to a rational limiting urn response for the count of distinct discoveries, such as new words in a text. The comparison of history probabilities in [3] justifies transferring the limiting free energy to this autonomous HLS description.

For random walks and polymers, the accumulated observable can also be geometric. The range counts distinct visited sites; at a fixed length it determines the number of steps returning to old sites. Conditional continuation probabilities reproduce this return-count distribution, linking urns to the Stanley polymer model [16]. The same range statistics determine survival in the Rosenstock problem with random traps, while the zero-return sector selects self-avoiding walks [3]. Attractive interactions require the additional contact statistic, as in the study of interacting self-avoiding polymers [17]. These correspondences concern the distributions of counts; applying the autonomous HLS theory requires control of the limiting urn function and of the relevant boundary regimes [3].

For continuous urn functions, the basic asymptotic picture is given by almost sure convergence of the color proportion to a fixed point [1, 18]. Which limiting behaviors are possible depends on the local shape of the response, as illustrated by convergence to points of tangency [19] and by critical behavior in nonlinear urns [20]. Together with the characterization of the exchangeable cases [21], these results describe typical outcomes and special structures of reinforced growth. The fixed points alone do not determine the exponential cost of other final compositions. Our concern is how weighting these compositions changes the balance between growth histories. This leads to the growth of exponential moments and hence to the free energy studied below.

We consider two colors, black and white, and a continuous urn function

π:[0,1]→[0,1].(1)\pi: [0,1] \to[0,1]. \tag*{(1)}

When the urn contains nn balls, we denote the proportion of black balls by ψn\psi_n; the numbers of balls of the two colors are thus nψnn\psi_n and n(1−ψn)n(1-\psi_n). The new ball is black with probability π(ψn)\pi(\psi_n) and white with probability 1−π(ψn)1-\pi(\psi_n). The urn function is evaluated before the addition and remains the same throughout the evolution. The rule includes nonlinear reinforcement and may admit several fixed points, that is, compositions at which the probability of adding a black ball equals the current proportion.

The urn starts with M≥1M \ge1 balls and grows until it contains T>MT > M. We assume a uniform distribution over the initial compositions:

P(ψM=j/M)=1M+1,j=0,…,M.(2)\mathbb{P}(\psi_M=j/M)=\frac{1}{M+1},\qquad j=0,\ldots,M. \tag*{(2)}

We assume that MM is sufficiently large to avoid pathological evolutions caused by the initial condition, that is, to keep the outer branches considered in Theorem 1 accessible with positive probability [22 Corollary 2]. In the limit T→∞T \to\infty, MM remains fixed.

We denote the increment in the number of black balls by σn+1\sigma_{n+1}: it equals one if the new ball is black and zero if it is white. For M≤n<TM \le n < T, the process is defined by

(n+1)ψn+1=nψn+σn+1,σn+1∈{0,1},(3)(n+1)\psi_{n+1}=n\psi_n+\sigma_{n+1},\qquad\sigma_{n+1}\in\{0,1\}, \tag*{(3)}
P(σn+1=1∣ψM,…,ψn)=π(ψn).(4)\mathbb{P}(\sigma_{n+1}=1\mid\psi_M,\ldots,\psi_n)=\pi(\psi_n). \tag*{(4)}

When 0<π<10 < \pi< 1 throughout [0,1][0,1], the limiting function (6) does not depend on the initial composition or the finite initial number of balls [22 Lemma 16].

For this process, the normalized cumulant generating function (CGF) of the final black mass is

ζT(β):=1Tlog⁡E[eβTψT],β∈R.(5)\zeta_T(\beta) := \frac{1}{T}\log\mathbb{E}\left[e^{\beta T\psi_T}\right], \qquad\beta\in\mathbb{R}. \tag*{(5)}

The expectation includes both the initial composition and the subsequent additions. The exponential factor weights histories according to their final composition: positive values of β\beta favor more black mass, while negative values favor less. This weighted sum over histories is a partition function, whose normalized logarithm defines the free energy in the convention used here. We study the limiting CGF

ζ(β):=lim⁡T→∞ζT(β),(6)\zeta(\beta) := \lim_{T\to\infty}\zeta_T(\beta), \tag*{(6)}

which describes the exponential growth of these moments as the urn grows. In the Stanley model, exponentially weighting the return count determines the polymer partition function, giving this correspondence a direct thermodynamic meaning [16]. Magnetization and wealth are affine functions of the appropriate urn count, so their free energies follow by rescaling the conjugate parameter and adding the deterministic contribution. Varying β\beta probes fluctuations through the response of the free energy. This connects the construction to large-deviation studies of growing systems [23].

Large deviation theory supplies the probabilistic basis for this free energy. Bryc, Minda and Sethuraman [4] establish a path large deviation principle and compute the limiting CGF for a family of affine processes related to random trees. For urn functions in the class U\mathcal{U}, recalled in § 2.1, the large deviation principle of Ref. [22] ensures the existence of ζ\zeta; the equation (13) and the slope conditions selecting the solution are established in Ref. [22], Eq. (2.31) and Theorem 9. In Ref. [8], this theory is applied to increasing returns, and the equation is studied for nonlinear responses. The broader theory also includes strong laws for nonbinary increments [24], under conditions on the conditional mean and moments, and large deviations for integer increments from zero to KK, with K≥1K \ge1 [25]. For the binary model considered here, the differential equation and slope conditions provide the characterization from which we construct the limiting CGF.

Although this equation is of first order, it couples the derivative through the nonlinear urn function to an exponential of the CGF itself. Inverting the urn function therefore does not by itself give an integral representation. At β=0\beta= 0, the equation is singular and the condition ζ(0)=0\zeta(0)=0 must be supplemented by the slopes prescribed by the extreme fixed points. The slopes can differ on the two sides of the origin, while the accessible endpoints determine the slopes at infinity. The task is thus to construct a globally convex solution satisfying these conditions on both half-lines, for either orientation of the outer branches.

Theorem 1 gives an exact constructive representation of this CGF, and hence of the asymptotic free energy, under the assumptions of Ref. [22], Theorem 9. These require invertibility with Lipschitz inverses on the outer branches beyond the fixed points, without imposing monotonicity between the extreme fixed points. Under these assumptions, three ordinary quadratures of the urn function and a convergent limit of compositions of radicals yield a solution parametrized by ζ′(β)\zeta'(\beta). Evaluation at a prescribed β\beta therefore requires only one scalar inversion, while the formula itself contains no derivatives or inverses of the urn function. The representation covers both increasing and decreasing branches, including urn functions with zeros and interior accessible endpoints. It therefore supplies a common route from an admissible nonlinear response to the free energy, without solving a new differential equation for each model.

The radical construction is obtained from a transformation to the real form of the chordal Loewner equation. Integration with a piecewise constant driving function and compositions of radicals are classical [26, 27]; here we derive the quadratures of the HLS transformation and identify the branch corresponding to the CGF. To control the resulting construction, we prove, with exact quadratures, an error bound for the reduced variable that is uniform at the partition nodes from the initial point up to each interior point of the branch. The estimate remains valid at the initial singularity and does not sum the errors over successive steps.

An exact CGF is also useful for assessing approximations to the history law. In connection with lattice field theory descriptions of neural activity [28], the HLS comparison developed in [3] shows that truncating the action to pair interactions can preserve the mean activity while changing the free energy. The present construction provides a reference for testing such reductions for admissible nonlinear responses. The variational balance between the action and entropy of histories also connects this description to formulations of active inference [29, 3].

Because the representation is expressed directly in terms of a fixed urn function, it can also be applied conditionally when that function is random. In the quenched setting, the response is sampled once, from a law independent of TT, and kept fixed throughout growth, as in a magnetic model with a frozen random field. Different field values give different nonlinear responses, each with its own free energy. Urns in such fixed random environments are investigated in [30], while the HLS formulation and affine examples are discussed in [3]. If the theorem’s hypotheses, including accessibility, hold for almost every realization, the construction gives the corresponding conditional CGF. Each is evaluated at a common value of β\beta before averaging over disorder, since the parametrization and its inversion depend on the realization. The construction thus provides the conditional free energies needed to extend the affine calculations to admissible nonlinear responses. The distinction between conditional growth and averages over systems also underlies the review’s discussion of replica symmetry breaking. Within such a history measure, exponential weighting changes the relative weights of the trajectory components through their conditional partition functions. This connects free-energy calculations to overlaps between independently sampled histories [3].

In § 4, we illustrate the construction with two affine urns, a non-affine urn and an urn with zeros. Their exact solutions allow the values obtained from the representation to be checked directly.

Main result

Assumptions and fixed points

We assume π∈U\pi\in\mathcal{U}, the class of Ref. [22]: there is a modulus bound f:(0,1]→(0,∞)f:(0,1]\to(0,\infty) such that

∣π(α)−π(α′)∣≤f(∣α−α′∣)(7)\lvert\pi(\alpha)-\pi(\alpha')\rvert\le f(\lvert\alpha-\alpha'\rvert) \tag*{(7)}

for sufficiently small positive distances, uniformly in α,α′∈[0,1]\alpha,\alpha' \in[0,1], and

lim⁡ε↓0∫ε1f(u)u2 du=0.(8)\lim_{\varepsilon\downarrow0}\int_{\varepsilon}^{1}\frac{f(u)}{u^2}\,\mathrm{d}u=0. \tag*{(8)}

In particular, all Hölder continuous urn functions belong to U\mathcal{U}. Define

C:={α∈[0,1]:π(α)=α},c−:=min⁡C,c+:=max⁡C.(9)C:=\{\alpha\in[0,1]:\pi(\alpha)=\alpha\},\qquad c_-:=\min C,\qquad c_+:=\max C. \tag*{(9)}

The case π≡0\pi\equiv0 gives ζ≡0\zeta\equiv0, whereas π≡1\pi\equiv1 gives ζ(β)=β\zeta(\beta)=\beta. In all other cases, the accessible endpoints are defined by

z−∗:=inf⁡{α∈[0,1]:π(α)<1},(10)z_-^*:=\inf\{\alpha\in[0,1]:\pi(\alpha)<1\}, \tag*{(10)}
z+∗:=sup⁡{α∈[0,1]:π(α)>0}.(11)z_+^*:=\sup\{\alpha\in[0,1]:\pi(\alpha)>0\}. \tag*{(11)}

The differential equation, the limiting conditions and uniqueness of the CGF are established in Ref. [22], Eq. (2.31) and Theorem 9.

Representation of the CGF

Theorem 1 (Solution of the CGF equation). Let π∈U\pi\in\mathcal{U}, with the model and initialization of § 1. Excluding the two constant cases already mentioned, suppose that π\pi is injective on each nonempty interval among

[z−∗,c−),(c+,z+∗](12)[z_-^*,c_-),\qquad(c_+,z_+^*] \tag*{(12)}

and that the inverse of each such restriction, defined on the corresponding image, is Lipschitz. No monotonicity is required between c−c_- and c+c_+.

The limit (1.6) exists and is finite. The CGF ζ\zeta is continuous and convex on R\mathbb{R} and is C1C^1 on the two open half-lines. It solves the equation

π(ζ′(β))=eζ(β)−1eβ−1,β≠0,(13)\pi\bigl(\zeta'(\beta)\bigr)=\frac{e^{\zeta(\beta)}-1}{e^\beta-1},\qquad\beta\ne0, \tag*{(13)}

with the normalization

ζ(0)=0(14)\zeta(0)=0 \tag*{(14)}

and the slope conditions

lim⁡β↑0ζ′(β)=c−,lim⁡β↓0ζ′(β)=c+,(15)\lim_{\beta\uparrow0}\zeta'(\beta)=c_{-},\qquad\lim_{\beta\downarrow0}\zeta'(\beta)=c_{+}, \tag*{(15)}
lim⁡β→−∞ζ′(β)=z−∗,lim⁡β→+∞ζ′(β)=z+∗.(16)\lim_{\beta\to-\infty}\zeta'(\beta)=z_{-}^{*},\qquad\lim_{\beta\to+\infty}\zeta'(\beta)=z_{+}^{*}. \tag*{(16)}

Within the class of functions with this regularity and convexity, the problem (13)–(16) has a unique solution.

On the half-line β>0\beta>0, if c+=1c_{+}=1, then ζ(β)=β\zeta(\beta)=\beta. If c+<1c_{+}<1, fix α∈(c+,z+∗)\alpha\in(c_{+},z_{+}^{*}) and set

(a,ε)={(1,−1),π increasing on the upper branch,(c+,1),π decreasing on the upper branch.(17)(a,\varepsilon)= \begin{cases} (1,-1), & \pi\text{ increasing on the upper branch},\\ (c_{+},1), & \pi\text{ decreasing on the upper branch}. \end{cases} \tag*{(17)}

In the first case, z+∗=1z_{+}^{*}=1. On the closed interval JαJ_{\alpha} with endpoints aa and α\alpha, the following integrals are oriented from aa:

m(u):=π(u)u[1−π(u)]1−uπ(a)a[1−π(a)]1−aexp⁡[−∫aulog⁡π(t)1−π(t) dt],(18)m(u):=\frac{\pi(u)^{u}[1-\pi(u)]^{1-u}}{\pi(a)^{a}[1-\pi(a)]^{1-a}}\exp\left[-\int_{a}^{u}\log\frac{\pi(t)}{1-\pi(t)}\,\mathrm{d}t\right], \tag*{(18)}
U(u):=2u−1m(u)−a+1−∫audtm(t),(19)U(u):=\frac{2u-1}{m(u)}-a+1-\int_{a}^{u}\frac{\mathrm{d}t}{m(t)}, \tag*{(19)}
R(u):=u(1−u)m(u)2−a(1−a)−∫au1−2tm(t)2 dt.(20)R(u):=\frac{u(1-u)}{m(u)^{2}}-a(1-a)-\int_{a}^{u}\frac{1-2t}{m(t)^{2}}\,\mathrm{d}t. \tag*{(20)}

The three functions are continuous, m>0m>0, and RR is strictly increasing along JαJ_{\alpha} from aa to α\alpha.

Let P=(α0,…,αℓ)\mathcal{P}=(\alpha_{0},\ldots,\alpha_{\ell}) be a partition ordered along this path, with α0=a\alpha_{0}=a and αℓ=α\alpha_{\ell}=\alpha. Define

∣P∣:=max⁡1≤j≤ℓ∣αj−αj−1∣,W0:=a,(21)|\mathcal{P}|:=\max_{1\leq j\leq\ell}|\alpha_{j}-\alpha_{j-1}|,\qquad W_{0}:=a, \tag*{(21)}

and, for j=1,…,ℓj=1,\ldots,\ell,

Wj:=U(αj−1)+ε[Wj−1−U(αj−1)]2+R(αj)−R(αj−1).(22)W_{j}:=U(\alpha_{j-1})+\varepsilon\sqrt{[W_{j-1}-U(\alpha_{j-1})]^{2}+R(\alpha_{j})-R(\alpha_{j-1})}. \tag*{(22)}

The sign ε\varepsilon remains the one in (2.11) at every step. The following limit exists and is independent of the partitions:

W(α):=lim⁡∣P∣→0Wℓ.(23)W(\alpha) := \lim_{|\mathcal{P}|\to0} W_{\ell}. \tag*{(23)}

More precisely, setting, for h≥0h \ge0,

ωU,Jα(h):=sup⁡u,v∈Jα∣u−v∣≤h∣U(u)−U(v)∣,(24)\omega_{U,J_\alpha}(h) := \sup_{\substack{u,v\in J_\alpha\\ |u-v|\le h}} |U(u)-U(v)|, \tag*{(24)}

we have

max⁡0≤j≤ℓ∣Wj−W(αj)∣≤ωU,Jα(∣P∣),W(a):=a.(25)\max_{0\le j\le\ell} |W_j-W(\alpha_j)| \le\omega_{U,J_\alpha}(|\mathcal{P}|), \qquad W(a):=a. \tag*{(25)}

The bound concerns the exact quadratures (2.12)–(2.14); under these assumptions, UU need not be Lipschitz in the parameter α\alpha. Finally, define

v(α):=α+m(α)[W(α)−U(α)].(26)v(\alpha):=\alpha+m(\alpha)[W(\alpha)-U(\alpha)]. \tag*{(26)}

The solution is given parametrically by

β(α)=log⁡v(α)[1−π(α)]π(α)[1−v(α)],(27)\beta(\alpha)=\log\frac{v(\alpha)[1-\pi(\alpha)]}{\pi(\alpha)[1-v(\alpha)]}, \tag*{(27)}
ζ(β(α))=log⁡1−π(α)1−v(α).(28)\zeta(\beta(\alpha))=\log\frac{1-\pi(\alpha)}{1-v(\alpha)}. \tag*{(28)}

The map α↦β(α)\alpha\mapsto\beta(\alpha) is an increasing homeomorphism from (c+,z+∗)(c_+,z_+^*) onto (0,∞)(0,\infty), and

ζ′(β(α))=α.(29)\zeta'(\beta(\alpha))=\alpha. \tag*{(29)}

For a prescribed value of β>0\beta>0, it therefore suffices to invert this scalar map. On the increasing branch,

0<π(α)<v(α)<α<1;(30)0<\pi(\alpha)<v(\alpha)<\alpha<1; \tag*{(30)}

on the decreasing branch,

0<π(α)<α<v(α)<1.(31)0<\pi(\alpha)<\alpha<v(\alpha)<1. \tag*{(31)}

The negative half-line is obtained by applying the same construction to the reflected urn function:

π^(α):=1−π(1−α),(32)\widehat{\pi}(\alpha) := 1-\pi(1-\alpha), \tag*{(32)}
ζπ(β)=β+ζπ^(−β),β<0.(33)\zeta_{\pi}(\beta)=\beta+\zeta_{\widehat{\pi}}(-\beta),\qquad\beta<0. \tag*{(33)}

The subscript specifies the urn function. In particular, c−=0c_{-}=0 gives ζ(β)=0\zeta(\beta)=0 for β≤0\beta\leq0.

The quadratures are finite up to every interior point of the branch; at the endpoints, one takes the limits of the CGF without requiring RR to remain finite there.

Proof

Branch selection and parametrization

Uniqueness for the boundary value problem {(xref)}(2.7)–{(xref)}(2.10) is given by Theorem 9 of Ref. [22]. Let IπI_{\pi} be the rate function, with compact sublevel sets, for the paths in Theorem 1 of Ref. [22], on the set Q\mathcal{Q} of absolutely continuous paths φ:[0,1]→[0,1]\varphi:[0,1]\to[0,1] with φ(0)=0\varphi(0)=0 and 0≤φ˙≤10\leq\dot{\varphi}\leq1 almost everywhere. This set is compact in the uniform topology. We apply Corollary 2 of Ref. [22] to each initial composition with a nondegenerate accessible interval. If this interval reduces to a single value, the limiting conditional CGF is β\beta times that value, which is a fixed point of π\pi by the recursion for the mean. The limiting CGF of the finite mixture (1.2) is the maximum of the conditional CGFs, since its weights are positive and independent of TT. For β>0\beta>0, in the variational problem with cost IπI_{\pi}, it suffices to consider paths between the lines of slope c+c_{+} and z+∗z_{+}^{*}: raising the portions below the first line onto it makes their cost zero and does not decrease the final value; no path of finite cost exceeds the second line, since π=0\pi=0 above it. The accessibility assumed in § 1 allows us to use the same cost IπI_{\pi} on these paths. For β<0\beta<0, the argument is symmetric between the lines of slope z−∗z_{-}^{*} and c−c_{-}. Continuity of the endpoint evaluation map, the contraction principle and Varadhan’s lemma therefore give

ζ(β)=sup⁡φ∈Q{βφ(1)−Iπ[φ]}.(34)\zeta(\beta)=\sup_{\varphi\in\mathcal{Q}}\{\beta\varphi(1)-I_{\pi}[\varphi]\}. \tag*{(34)}

In particular, the limit exists and is finite and convex, with ζ(0)=0\zeta(0)=0 and slopes in [0,1][0,1]. The entropy integrand of IπI_{\pi} is nonnegative and vanishes exactly when φ˙(τ)=π(φ(τ)/τ)\dot{\varphi}(\tau)=\pi(\varphi(\tau)/\tau) almost everywhere. Thus the path φ(τ)=c+τ\varphi(\tau)=c_{+}\tau has zero cost. If c+=1c_{+}=1, {(xref)}(3.1) and ΨT≤1\Psi_{T}\leq1 give ζ(β)=β\zeta(\beta)=\beta for β>0\beta>0. Henceforth assume c+<1c_{+}<1.

No zero-cost path can end above c+c_{+}. Indeed, writing φ(τ)=τu(log⁡τ)\varphi(\tau)=\tau u(\log\tau) gives

u′(t)=π(u(t))−u(t),t<0.(35)u'(t)=\pi(u(t))-u(t),\qquad t<0. \tag*{(35)}

If u(0)=s>c+u(0)=s>c_{+}, the backward evolution makes uu increase at a rate bounded away from zero on [s,1][s,1], contradicting u≤1u\leq1. Compactness of the sublevel sets of IπI_{\pi} and (3.1) give

lim⁡β↓0ζ′(β)=c+.(36)\lim_{\beta\downarrow0}\zeta'(\beta)=c_{+}. \tag*{(36)}

For now, slope limits are taken through points of differentiability; the regularity proved below makes them ordinary limits. On the open upper branch, continuity and injectivity give 0<π(α)<α<10<\pi(\alpha)<\alpha<1. For the linear paths φ(τ)=ατ\varphi(\tau)=\alpha\tau, the cost is finite:

Iπ[φ]=αlog⁡απ(α)+(1−α)log⁡1−α1−π(α)<∞,c+<α<z+∗.(37)I_{\pi}[\varphi]=\alpha\log\frac{\alpha}{\pi(\alpha)}+(1-\alpha)\log\frac{1-\alpha}{1-\pi(\alpha)}<\infty,\qquad c_{+}<\alpha<z_{+}^{*}. \tag*{(37)}

Moreover,

TψT≤Tz+∗+M.(38)T\psi_{T}\leq Tz_{+}^{*}+M. \tag*{(38)}

If z+∗<1z_{+}^{*}<1, the bound follows by induction starting from T=MT=M because π=0\pi=0 above z+∗z_{+}^{*}; if z+∗=1z_{+}^{*}=1, it is immediate. Applying (3.1) to these linear paths and using the upper bound yields ζ(β)/β→z+∗\zeta(\beta)/\beta\to z_{+}^{*} as β→∞\beta\to\infty. Convexity then implies

lim⁡β→∞ζ′(β)=z+∗.(39)\lim_{\beta\to\infty}\zeta'(\beta)=z_{+}^{*}. \tag*{(39)}

Fix a point of differentiability β>0\beta>0 and define the probability measure Pβ,T\mathbb{P}_{\beta,T} by

dPβ,TdP=exp⁡{βTψT−TζT(β)}.(40)\frac{\mathrm{d}\mathbb{P}_{\beta,T}}{\mathrm{d}\mathbb{P}}=\exp\{\beta T\psi_{T}-T\zeta_{T}(\beta)\}. \tag*{(40)}

For every fixed neighborhood of ζ′(β)\zeta'(\beta), differentiability of ζ\zeta allows us to choose h>0h>0 small enough for the Chernoff bounds at β+h\beta+h and β−h\beta-h to make the probability of its complement under this measure exponentially small as T→∞T\to\infty. Hence ψT\psi_{T} converges in probability to ζ′(β)\zeta'(\beta) under Pβ,T\mathbb{P}_{\beta,T}. Continuity and boundedness of π\pi imply

lim⁡T→∞Eβ,T[π(ψT)]=π(ζ′(β)).(41)\lim_{T\to\infty}\mathbb{E}_{\beta,T}[\pi(\psi_{T})]=\pi(\zeta'(\beta)). \tag*{(41)}

The transition rule gives the exact recursion

(T+1)ζT+1(β)−TζT(β)=log⁡[1+(eβ−1)Eβ,T[π(ψT)]].(42)(T+1)\zeta_{T+1}(\beta)-T\zeta_{T}(\beta)=\log[1+(e^{\beta}-1)\mathbb{E}_{\beta,T}[\pi(\psi_{T})]]. \tag*{(42)}

The right-hand side converges by (3.8). Summing the recursion from T=MT=M and taking Cesàro averages identifies the limit as ζ(β)\zeta(\beta): the initial term, bounded in absolute value by ∣β∣M|\beta|M, vanishes after normalization. This yields (2.7) at every point of differentiability.

The slope bounds place ζ′\zeta' in [c+,z+∗][c_{+},z_{+}^{*}] almost everywhere. Let gg be the inverse on the upper branch, extended continuously to c+c_{+}; the extension remains Lipschitz. ratio in the following equation belongs to the closed image of the branch: this holds at points of differentiability by (2.7), and elsewhere by continuity. Therefore

ζ′(β)=g(eζ(β)−1eβ−1)for almost every β>0.(43)\zeta'(\beta)=g\left(\frac{e^{\zeta(\beta)}-1}{e^\beta-1}\right)\qquad\text{for almost every }\beta>0. \tag*{(43)}

The right-hand side is continuous. Since ζ\zeta is locally absolutely continuous, integration shows that it is C1C^1 on (0,∞)(0,\infty) and that (2.7) holds everywhere. The same argument applies to the reflected urn on the negative half-line. If c−=0c_-=0, the zero path has zero cost and (3.1) gives ζ(β)=0\zeta(\beta)=0 for β<0\beta<0. The upper branch is nonempty: otherwise, continuity and π(c+)=c+\pi(c_+)=c_+ would imply π≡0\pi\equiv0. On this branch,

0<π(α)<α,c+<α<z+∗.(44)0<\pi(\alpha)<\alpha,\qquad c_+<\alpha<z_+^*. \tag*{(44)}

The second inequality follows from the absence of fixed points beyond c+c_+; the first follows from strict monotonicity and the definition of z+∗z_+^*. If π\pi is increasing, an endpoint z+∗<1z_+^*<1 would force π(z+∗)=0\pi(z_+^*)=0, which is impossible. Thus z+∗=1z_+^*=1 and

0≤c+<π(1)<1.(45)0\leq c_+<\pi(1)<1. \tag*{(45)}

If π\pi is decreasing, instead,

0≤π(z+∗)<c+<1.(46)0\leq\pi(z_+^*)<c_+<1. \tag*{(46)}

In both cases 0<π(a)<10<\pi(a)<1 and 0<π<10<\pi<1 throughout JαJ_\alpha. The quadratures in the statement are therefore finite and continuous on this closed interval, with m>0m>0 and

m(a)=1,U(a)=a,R(a)=0.(47)m(a)=1,\qquad U(a)=a,\qquad R(a)=0. \tag*{(47)}

Set x(β):=ζ′(β)x(\beta):=\zeta'(\beta). The C1C^1 regularity of the CGF makes xx continuous, while convexity makes it nondecreasing. We show that

c+<x(β)<z+∗,β>0.(48)c_+<x(\beta)<z_+^*,\qquad\beta>0. \tag*{(48)}

If it reached either endpoint at a finite parameter value, it would be constant on an open interval extending towards zero or infinity. When the constant value is d∈(0,1)d\in(0,1), the equation would imply

ζ(β)=log⁡[1−π(d)+π(d)eβ](49)\zeta(\beta)=\log[1-\pi(d)+\pi(d)e^{\beta}] \tag*{(49)}

on that interval. For 0<π(d)<10<\pi(d)<1, the right-hand side is strictly convex, whereas ζ\zeta is affine. For π(d)=0\pi(d)=0 or 11, its derivative would be zero or one, respectively, still different from dd. Reaching z+∗=1z_+^*=1 would require π(1)=1\pi(1)=1, which is ruled out by c+<1c_+<1. It remains to rule out reaching c+=0c_+=0. In this case the branch is increasing. Its inverse gg extends to zero with g(0)=0g(0)=0, and a Lipschitz constant LL for it gives 0≤g(q)≤Lq0 \le g(q) \le Lq. If x(β0)=0x(\beta_0)=0, convexity and ζ(0)=0\zeta(0)=0 imply ζ(β0)=0\zeta(\beta_0)=0. For every B>β0B>\beta_0, the equation and 0≤ζ(β)≤β0\le\zeta(\beta)\le\beta give, on [β0,B][\beta_0,B],

0≤ζ′(β)≤LeBeβ0−1 ζ(β).(50)0 \le\zeta'(\beta) \le\frac{Le^B}{e^{\beta_0}-1}\,\zeta(\beta). \tag*{(50)}

Gronwall’s inequality forces ζ=0\zeta=0 on every such interval, contradicting (3.6). This proves (3.15).

Define

q(β):=π(x(β))=eζ(β)−1eβ−1,(51)q(\beta):=\pi(x(\beta))=\frac{e^{\zeta(\beta)}-1}{e^\beta-1}, \tag*{(51)}
vβ:=q(β)eβ1−q(β)+q(β)eβ.(52)v_\beta:=\frac{q(\beta)e^\beta}{1-q(\beta)+q(\beta)e^\beta}. \tag*{(52)}

We have 0<q<vβ<10<q<v_\beta<1, x=g(q)x=g(q), and qq is C1C^1 by the second expression in (3.18). Differentiating this expression gives

q′(β)=1−q(β)+q(β)eβeβ−1[x(β)−vβ].(53)q'(\beta)=\frac{1-q(\beta)+q(\beta)e^\beta}{e^\beta-1}[x(\beta)-v_\beta]. \tag*{(53)}

Moreover, qq is nondecreasing if π\pi is increasing and nonincreasing if π\pi is decreasing. The derivative q′q' cannot vanish. Indeed, if q′(β0)=0q'(\beta_0)=0, the Lipschitz property of gg implies x(β0+h)−x(β0)=o(h)x(\beta_0+h)-x(\beta_0)=o(h). Differentiating (3.19) at that point gives

ddβ[x(β)−vβ]∣β=β0=−vβ0(1−vβ0)<0.(54)\left.\frac{d}{d\beta}[x(\beta)-v_\beta]\right|_{\beta=\beta_0}=-v_{\beta_0}(1-v_{\beta_0})<0. \tag*{(54)}

Since (3.20) would imply x(β0)=vβ0x(\beta_0)=v_{\beta_0}, the sign of q′q' would change from positive to negative across β0\beta_0, contradicting the monotonicity of qq. Since q′q' does not vanish, x=g(q)x=g(q) is also strictly increasing in β\beta. This proves the required homeomorphism property for the parameter α=x(β)\alpha=x(\beta) and, by (3.20), the orderings (2.24) and (2.25).

Express the probability (3.19) as a function of the state by v(x(β))=vβv(x(\beta))=v_\beta. We will show below that this function satisfies the reconstruction formula (2.20). Set

A(q):=g(q)−qq(1−q).(55)A(q):=\frac{g(q)-q}{q(1-q)}. \tag*{(55)}

This function is continuous and positive in the interior. The logarithmic derivative of (3.19) gives

dvβdβ=vβ(1−vβ)[1+q′(β)q(β)[1−q(β)]].(56)\frac{dv_\beta}{d\beta}=v_\beta(1-v_\beta)\left[1+\frac{q'(\beta)}{q(\beta)[1-q(\beta)]}\right]. \tag*{(56)}

The definition of vβv_\beta also gives

1−q(β)+q(β)eβeβ−1=q(β)[1−q(β)]vβ−q(β).(57)\frac{1-q(\beta)+q(\beta)e^\beta}{e^\beta-1}=\frac{q(\beta)[1-q(\beta)]}{v_\beta-q(\beta)}. \tag*{(57)}

Dividing (56) by the nonzero derivative in (53), we obtain

ddqv(g(q))=A(q)v(g(q))[1−v(g(q))]g(q)−v(g(q)).(58)\frac{d}{dq}v(g(q))=A(q)\frac{v(g(q))[1-v(g(q))]}{g(q)-v(g(q))}. \tag*{(58)}

Quadratures and reduction

To differentiate the quadratures without differentiating π\pi, compose the functions m,U,Rm,U,R in the statement with gg. They are absolutely continuous on every closed interval between the initial point qa:=π(a)q_a:=\pi(a) and an interior point. Indeed, gg is Lipschitz and the primitives of the integrands in (18)–(20) are C1C^1 on JαJ_\alpha. The explicit terms are also absolutely continuous after the substitution π(g(q))=q\pi(g(q))=q. In the logarithmic derivative of (18), the terms containing g′g' cancel, leaving, almost everywhere,

ddqlog⁡m(g(q))=g(q)q−1−g(q)1−q=A(q).(59)\frac{d}{dq}\log m(g(q))=\frac{g(q)}{q}-\frac{1-g(q)}{1-q}=A(q). \tag*{(59)}

Thus

ddqm(g(q))=A(q)m(g(q)).(60)\frac{d}{dq}m(g(q))=A(q)m(g(q)). \tag*{(60)}

Similarly,

ddqU(g(q))=g′(q)−A(q)[2g(q)−1]m(g(q))(61)\frac{d}{dq}U(g(q))=\frac{g'(q)-A(q)[2g(q)-1]}{m(g(q))} \tag*{(61)}

almost everywhere, and

ddqR(g(q))=−2A(q)g(q)[1−g(q)]m(g(q))2.(62)\frac{d}{dq}R(g(q))=-\frac{2A(q)g(q)[1-g(q)]}{m(g(q))^2}. \tag*{(62)}

The identities (60) and (62) initially hold almost everywhere; their continuous right-hand sides then show that both compositions are C1C^1. Absolute continuity of π\pi is not required.

Introduce

w(q):=U(g(q))+v(g(q))−g(q)m(g(q)),(63)w(q):=U(g(q))+\frac{v(g(q))-g(q)}{m(g(q))}, \tag*{(63)}
c(q):=A(q)g(q)[1−g(q)]m(g(q))2.(64)c(q) := \frac{A(q)g(q)[1-g(q)]}{m(g(q))^2}. \tag*{(64)}

Using the algebraic identity

v(1−v)g−v=v+g−1+g(1−g)g−v,(65)\frac{v(1-v)}{g-v}=v+g-1+\frac{g(1-g)}{g-v}, \tag*{(65)}

the derivatives (3.25)–(3.28) give

dwdq=−c(q)w(q)−U(g(q)).(66)\frac{dw}{dq}=-\frac{c(q)}{w(q)-U(g(q))}. \tag*{(66)}

The identity holds almost everywhere; the denominator does not vanish in the interior, by (2.24)–(2.25), and the continuous right-hand side shows that ww is C1C^1.

On the increasing branch we move downwards in α\alpha from a=1a=1, that is, from infinity towards zero in β\beta; on the decreasing branch we move upwards in α\alpha from a=c+a=c_+, that is, from zero towards infinity in β\beta. Along both paths, qq decreases from qaq_a. Since c>0c>0 in the interior, (3.29) proves that RR is strictly increasing along the path. At the starting endpoints,

lim⁡β→∞vβ=1on the increasing branch,(67)\lim_{\beta\to\infty}v_\beta=1 \qquad\text{on the increasing branch}, \tag*{(67)}
lim⁡β↓0vβ=c+on the decreasing branch.(68)\lim_{\beta\downarrow0}v_\beta=c_+ \qquad\text{on the decreasing branch}. \tag*{(68)}

These formulas follow from (3.19) and the limits already established for qq. In both cases, ww extends continuously to the initial point with value aa.

We now use t=R(u)t=R(u), with u∈Jαu\in J_\alpha, as time. Since RR is continuous and strictly increasing along JαJ_\alpha, the identities

y(R(u)):=w(π(u)),ξ(R(u)):=U(u),(69)y(R(u)):=w(\pi(u)),\qquad\xi(R(u)):=U(u), \tag*{(69)}

define yy and ξ\xi uniquely on [0,R(α)][0,R(\alpha)]. Differentiating with respect to qq, with t=R(g(q))t=R(g(q)), equations (3.29) and (3.33) give

y′(t)=12∣y(t)−ξ(t)∣,0<t<R(α),(70)y'(t)=\frac{1}{2\lvert y(t)-\xi(t)\rvert},\qquad0<t<R(\alpha), \tag*{(70)}

with

y(0)=ξ(0)=a.(71)y(0)=\xi(0)=a. \tag*{(71)}

For t>0t>0, we have y<ξy<\xi on the increasing branch and y>ξy>\xi on the decreasing branch. The time is finite for every interior α\alpha, and the denominator does not vanish before that time is reached. The solution on the prescribed side of the driving function is obtained from the CGF. After rescaling time, (3.37) is the chordal Loewner equation in a real variable [26]. Integrating with ξ\xi constant on each step gives the radical used in the construction.

Comparison with a singular initial condition

We first treat y<ξy<\xi. For h≥0h\ge0, define

Pb,h(z):=b−(b−z)+2+h,r+:=max⁡{r,0},(72)P_{b,h}(z):=b-\sqrt{(b-z)^2_{+}+h},\qquad r_{+}:=\max\{r,0\}, \tag*{(72)}
Nb,h(Z):=b−(Z−b)2+h.(73)N_{b,h}(Z):=b-\sqrt{(Z-b)^2+h}. \tag*{(73)}

The first map is nondecreasing in zz and satisfies

Pb+d,h(z+d)=Pb,h(z)+d.(74)P_{b+d,h}(z+d)=P_{b,h}(z)+d. \tag*{(74)}

For h>0h>0, it is the solution with constant driving function bb starting from min⁡{z,b}\min\{z,b\}, including when the initial condition equals bb. The recursion uses Nb,hN_{b,h}.

Consider a step of duration h>0h>0, shifting its time origin to zero. Assume

y0:=y(0)≤b,∣ξ(t)−b∣≤δ,0≤t≤h.(75)y_0:=y(0)\le b,\qquad|\xi(t)-b|\le\delta,\qquad0\le t\le h. \tag*{(75)}

Then

Pb−δ,h(y0)≤y(h)≤Pb+δ,h(y0).(76)P_{b-\delta,h}(y_0)\le y(h)\le P_{b+\delta,h}(y_0). \tag*{(76)}

To verify the bound also for a singular initial condition, set B=b−δB=b-\delta, D=b+δD=b+\delta, and consider the functions l(t)=PB,t(y0)l(t)=P_{B,t}(y_0) and u(t)=PD,t(y0)u(t)=P_{D,t}(y_0). They are continuous at zero and smooth for t>0t>0, with l(0)=min⁡{y0,B}≤y0=u(0)l(0)=\min\{y_0,B\}\le y_0=u(0). Write

Fb(z):=12(z−b),z<b.(77)F_b(z):=\frac{1}{2(z-b)},\qquad z<b. \tag*{(77)}

The field FbF_b is decreasing in zz and increasing in bb wherever it is defined. If l(t)>y(t)l(t)>y(t), then y(t)<l(t)<B≤ξ(t)y(t)<l(t)<B\le\xi(t), hence

(l−y)′=FB(l)−Fξ(t)(y)≤FB(l)−FB(y)<0.(78)(l-y)'=F_B(l)-F_{\xi(t)}(y)\le F_B(l)-F_B(y)<0. \tag*{(78)}

If instead y(t)>u(t)y(t)>u(t), then u(t)<y(t)<ξ(t)≤Du(t)<y(t)<\xi(t)\le D and

(y−u)′=Fξ(t)(y)−FD(u)≤FD(y)−FD(u)<0.(79)(y-u)'=F_{\xi(t)}(y)-F_D(u)\le F_D(y)-F_D(u)<0. \tag*{(79)}

On every open component of the set where either difference is positive, that difference would therefore have a nonpositive initial value and a negative derivative, which is impossible. Continuity at zero allows the same argument for a component starting at zero, without requiring the solution to be differentiable there. This proves (76).

Now let ZZ be an approximate initial value with ∣Z−y0∣≤δ|Z-y_0| \le\delta. The triangle inequality and y0≤by_0 \le b give

(b−y0−δ)+≤∣Z−b∣≤b−y0+δ.(80)(b-y_0-\delta)_+ \le|Z-b| \le b-y_0+\delta. \tag*{(80)}

Therefore

Pb,h(y0−δ)≤Nb,h(Z)≤Pb,h(y0+δ).(81)P_{b,h}(y_0-\delta) \le N_{b,h}(Z) \le P_{b,h}(y_0+\delta). \tag*{(81)}

Identity (74) gives

Pb,h(y0−δ)=Pb+δ,h(y0)−δ,(82)P_{b,h}(y_0-\delta)=P_{b+\delta,h}(y_0)-\delta, \tag*{(82)}
Pb,h(y0+δ)=Pb−δ,h(y0)+δ.(83)P_{b,h}(y_0+\delta)=P_{b-\delta,h}(y_0)+\delta. \tag*{(83)}

Combining (76) with (81), we obtain

∣Nb,h(Z)−y(h)∣≤δ.(84)|N_{b,h}(Z)-y(h)|\le\delta. \tag*{(84)}

Thus the same error bound passes from one step to the next, even when Z>bZ>b.

Convergence and error control

For the partition in the statement, set

tj:=R(αj),δ:=ωU,Jα(∣P∣).(85)t_j:=R(\alpha_j),\qquad\delta:=\omega_{U,J_\alpha}(|\mathcal{P}|). \tag*{(85)}

During the step from tj−1t_{j-1} to tjt_j, the unique u∈Jαu\in J_\alpha satisfying R(u)=tR(u)=t lies between αj−1\alpha_{j-1} and αj\alpha_j. The definition of ξ\xi therefore gives

∣ξ(t)−U(αj−1)∣≤δ,tj−1≤t≤tj.(86)|\xi(t)-U(\alpha_{j-1})|\le\delta,\qquad t_{j-1}\le t\le t_j. \tag*{(86)}

On the increasing branch, ε=−1\varepsilon=-1, and the recursion (22) is precisely Nb,hN_{b,h} with b=U(αj−1)b=U(\alpha_{j-1}) and h=tj−tj−1h=t_j-t_{j-1}. Since W0=y(0)W_0=y(0), the bound (84) applies inductively to every step and gives

max⁡0≤j≤ℓ∣Wj−y(tj)∣≤δ.(87)\max_{0\le j\le\ell}|W_j-y(t_j)|\le\delta. \tag*{(87)}

On the decreasing branch, the substitution y↦−yy \mapsto-y, ξ↦−ξ\xi\mapsto-\xi preserves (70) and reduces the problem to the case just proved. Returning to the original sign gives exactly the positive square root prescribed by ε=1\varepsilon= 1, with the same bound.

Uniform continuity of UU on JαJ_\alpha implies δ→0\delta\to0 as ∣P∣→0|\mathcal{P}| \to0, without any condition on the ratios of the lengths of different steps. Hence the limit exists, is independent of the partitions, and is

W(α)=w(π(α))=y(R(α)).(88)W(\alpha) = w(\pi(\alpha)) = y(R(\alpha)). \tag*{(88)}

The same identification at each node turns (87) into the bound (25) in the statement.

The same comparison applies to any other continuous solution of (70) with the same initial value and lying strictly on the same side of ξ\xi for t>0t > 0. It satisfies (87) relative to the same radicals and therefore coincides with (88) as the mesh size tends to zero. The reduced solution is thus unique on this branch.

Reconstruction and reflection

The identities (63) and (88) recover (26). Solving (52) for the exponential and using (13), we obtain, respectively,

eβ=vβ[1−q(β)]q(β)(1−vβ).(89)e^\beta= \frac{v_\beta[1-q(\beta)]}{q(\beta)(1-v_\beta)}. \tag*{(89)}
eζ(β)=1−q(β)1−vβ.(90)e^{\zeta(\beta)} = \frac{1-q(\beta)}{1-v_\beta}. \tag*{(90)}

With α=x(β)\alpha= x(\beta), q(β)=π(α)q(\beta) = \pi(\alpha) and vβ=v(α)v_\beta= v(\alpha), these are precisely (27) and (28). The arguments of their logarithms are positive by the orderings already proved; β(α)>0\beta(\alpha) > 0 follows from v(α)>π(α)v(\alpha) > \pi(\alpha). Strict monotonicity and the limits (36)–(39) complete the parametrization of the entire positive half-line.

Finally, the proportion of white mass 1−ψn1-\psi_n has urn function π^\hat{\pi} and the same discrete uniform initialization (2). For every finite TT, we already have

ζπ,T(β)=β+ζπ^,T(−β).(91)\zeta_{\pi,T}(\beta) = \beta+ \zeta_{\hat{\pi},T}(-\beta). \tag*{(91)}

Passing to the limit gives (33). Reflection preserves the class U\mathcal{U} and the Lipschitz property of the inverses, interchanging the two outer branches. If c−=0c_- = 0, the largest fixed point of the reflected function is one, and the case already treated gives ζ(β)=0\zeta(\beta) = 0 for β<0\beta< 0. The normalization ζ(0)=0\zeta(0) = 0 completes the solution on R\mathbb{R}.

Examples and computation of the CGF

We compare the recursion (22) with four explicit CGFs.

Two affine urns

For comparison, we use two exact affine solutions from Corollary 12 of Ref. [22], as corrected in the accompanying corrigendum. We first consider

π(α)=1+α3.(92)\pi(\alpha) = \frac{1+\alpha}{3}. \tag*{(92)}

The fixed point is c−=c+=1/2c_- = c_+ = 1/2, the inverse is Lipschitz with constant 3, and the positive branch starts at a=1a = 1 with ε=−1\varepsilon= -1. The three quadratures become

m(α)=2(1+α)(2−α),(93)m(\alpha) = \frac{2}{(1+\alpha)(2-\alpha)}, \tag*{(93)}
U(α)=−5α36+5α24+α2+112,(94)U(\alpha) = -\frac{5\alpha^3}{6} + \frac{5\alpha^2}{4} + \frac{\alpha}{2} + \frac{1}{12}, \tag*{(94)}
R(α)=α22−5α36+α52−α66.(95)R(\alpha) = \frac{\alpha^2}{2} - \frac{5\alpha^3}{6} + \frac{\alpha^5}{2} - \frac{\alpha^6}{6}. \tag*{(95)}

The limit of the radicals is

W(α)=−α33+α2+13,1/2<α<1.(96)W(\alpha) = -\frac{\alpha^3}{3} + \alpha^2 + \frac{1}{3}, \qquad1/2 < \alpha< 1. \tag*{(96)}

Substitution into (26) gives

v(α)=1+α2(2−α),(97)v(\alpha) = \frac{1+\alpha}{2(2-\alpha)}, \tag*{(97)}

and reconstruction yields

ζ(β)=β−log⁡3−e−β2,β≥0.(98)\zeta(\beta) = \beta- \log\frac{3-e^{-\beta}}{2}, \qquad\beta\ge0. \tag*{(98)}

The function in (4.5), expressed in the time variable t=R(α)t = R(\alpha), satisfies (70), has W(1)=1W(1) = 1 and satisfies W<UW < U for 1/2<α<11/2 < \alpha< 1. By the uniqueness proved in § 3.4, this function coincides with the limit of the radicals; (4.7) is therefore the CGF. Since π(1−α)=1−π(α)\pi(1-\alpha) = 1-\pi(\alpha), reflection completes the solution:

ζ(β)=−log⁡3−eβ2,β≤0.(99)\zeta(\beta) = -\log\frac{3-e^\beta}{2}, \qquad\beta\le0. \tag*{(99)}

For the second example, take

π(α)=34−α2.(100)\pi(\alpha)=\frac{3}{4}-\frac{\alpha}{2}. \tag*{(100)}

The fixed point is again 1/21/2, but the inverse has Lipschitz constant 2 and the positive branch starts at a=1/2a=1/2, with ε=1\varepsilon=1. The first quadrature is

m(α)={4π(α)[1−π(α)]}3/2.(101)m(\alpha)=\{4\pi(\alpha)[1-\pi(\alpha)]\}^{3/2}. \tag*{(101)}

The exact solution is now

ζ(β)=β2+2log⁡cosh⁡β4,β∈R.(102)\zeta(\beta)=\frac{\beta}{2}+2\log\cosh\frac{\beta}{4},\qquad\beta\in\mathbb{R}. \tag*{(102)}

Indeed, setting t=eβ/2t=e^{\beta/2} gives

ζ′(β)=t1+t,eζ(β)=(1+t)24,(103)\zeta'(\beta)=\frac{t}{1+t},\qquad e^{\zeta(\beta)}=\frac{(1+t)^2}{4}, \tag*{(103)}

and equation (13) follows by substitution. For β>0\beta>0, the derivative is strictly increasing and (53) gives v>αv>\alpha; moreover, α\alpha and vv both tend to 1/21/2 as β↓0\beta\downarrow0. The transformed solution therefore starts at the prescribed initial point and remains above ξ\xi. Uniqueness from § 3.4 identifies the CGF on the positive half-line; the symmetry of the urn function gives the negative half-line by reflection. Figure 1 compares the two exact CGFs with the values obtained from the recursion.

Two affine urns and comparisons of the exact CGF with numerical points

Figure 1. Two affine urns. Top: the increasing function (92); bottom: the decreasing function (100). On the left, the urn function (solid line) and the diagonal (dotted line) intersect at the fixed point. On the right, the exact CGF is compared with the points obtained from (22) using ℓ=16\ell= 16 intervals (circles) and ℓ=128\ell= 128 (crosses), uniformly spaced in α\alpha between the initial point and the evaluation point. The quadratures are computed on a finer grid. The upper example starts at the boundary a=1a = 1 with the negative square root; the lower example starts at the fixed point a=1/2a = 1/2 with the positive square root.

A non-affine urn

Consider the increasing function

π(α)=α+1−α2+21−α,0≤α≤1.(104)\pi(\alpha)=\frac{\sqrt{\alpha}+\sqrt{1-\alpha}}{\sqrt{2}+2\sqrt{1-\alpha}},\qquad0\leq\alpha\leq1. \tag*{(104)}

It is Hölder continuous with exponent 1/21/2, hence belongs to U\mathcal{U}, and satisfies π(1−α)=1−π(α)\pi(1-\alpha)=1-\pi(\alpha). Its inverse is

g(q)=(−2q2+4q−1)22[q2+(1−q)2]2,1−12≤q≤12.(105)g(q)=\frac{(-2q^2+4q-1)^2}{2[q^2+(1-q)^2]^2},\qquad1-\frac{1}{\sqrt{2}}\leq q\leq\frac{1}{\sqrt{2}}. \tag*{(105)}

With u=2q−1u=2q-1, we obtain

g′(q)=4(1−6u2+u4)(1+u2)3,0≤g′(q)≤4.(106)g'(q)=\frac{4(1-6u^2+u^4)}{(1+u^2)^3},\qquad0\leq g'(q)\leq4. \tag*{(106)}

The inverse is therefore Lipschitz, although π\pi has no finite derivative at the endpoints. Moreover,

g(q)−q=u(3−6u2−u4)2(1+u2)2.(107)g(q)-q=\frac{u(3-6u^2-u^4)}{2(1+u^2)^2}. \tag*{(107)}

The factor in parentheses is positive throughout the interval under consideration: the unique fixed point is 1/21/2. For the positive half-line, we therefore use a=1a=1 and ε=−1\varepsilon=-1. The CGF is

ζ(β)=12log⁡1+e2β2,β∈R.(108)\zeta(\beta)=\frac{1}{2}\log\frac{1+e^{2\beta}}{2},\qquad\beta\in\mathbb{R}. \tag*{(108)}

To verify this, set t=eβt=e^\beta; then

α=ζ′(β)=t21+t2.(109)\alpha=\zeta'(\beta)=\frac{t^2}{1+t^2}. \tag*{(109)}

Rationalizing the quotient in the HLS equation gives

eζ(β)−1eβ−1=t+121+t2+2=π(α),β≠0.(110)\frac{e^{\zeta(\beta)}-1}{e^\beta-1}=\frac{t+1}{\sqrt{2}\sqrt{1+t^2}+2}=\pi(\alpha),\qquad\beta\ne0. \tag*{(110)}

On the positive half-line, q=π(α)q=\pi(\alpha) has positive derivative, so (53) gives v<αv<\alpha; moreover, α\alpha and vv both tend to one as β→∞\beta\to\infty. The transformed solution remains below ξ\xi and has the prescribed initial point. Uniqueness from § 3.4 therefore identifies this formula as the CGF; symmetry completes the negative half-line.

Zeros and an interior accessible endpoint

Take

π(α)=max⁡{1−2α,0}.(111)\pi(\alpha)=\max\{1-2\alpha,0\}. \tag*{(111)}

In this case

c−=c+=1/3,z−∗=0,z+∗=1/2.(112)c_-=c_+=1/3,\qquad z_-^*=0,\qquad z_+^*=1/2. \tag*{(112)}

The inverse on the two outer branches is g(q)=(1−q)/2g(q)=(1-q)/2 and is Lipschitz; injectivity in (12) is required only up to the endpoint z+∗=1/2z_+^*=1/2. On the positive half-line, the construction starts at a=1/3a=1/3 with ε=1\varepsilon=1 and remains in the interval (1/3,1/2)(1/3,1/2). The first quadrature becomes

m(α)=3α3(1−2α).(113)m(\alpha)=3\alpha\sqrt{3(1-2\alpha)}. \tag*{(113)}

The solution on the whole real line can be written as

e−ζ(β)=F(eβ−1),(114)e^{-\zeta(\beta)} = F(e^\beta-1), \tag*{(114)}
F(z):=∫01du1+zu2,z>−1.(115)F(z) := \int_0^1 \frac{du}{1+zu^2}, \qquad z>-1. \tag*{(115)}

In particular,

e−ζ(β)=arctan⁡eβ−1eβ−1,β>0,(116)e^{-\zeta(\beta)} = \frac{\arctan\sqrt{e^\beta-1}}{\sqrt{e^\beta-1}}, \qquad\beta>0, \tag*{(116)}
e−ζ(β)=artanh⁡1−eβ1−eβ,β<0,(117)e^{-\zeta(\beta)} = \frac{\operatorname{artanh}\sqrt{1-e^\beta}}{\sqrt{1-e^\beta}}, \qquad\beta<0, \tag*{(117)}

with ζ(0)=0\zeta(0)=0. Indeed, on the branches where π(α)=1−2α\pi(\alpha)=1-2\alpha, the HLS equation becomes

2zF′(z)+F(z)=11+z.(118)2zF'(z)+F(z)=\frac{1}{1+z}. \tag*{(118)}

The integral (115) satisfies this identity. On each half-line, the difference between two solutions is a constant divided by the square root of ∣z∣|z|; continuity at zero eliminates both constants. Moreover, F′<0F'<0 and

ζ′(β)=eβF(eβ−1)−12(eβ−1)F(eβ−1),β≠0,(119)\zeta'(\beta)=\frac{e^\beta F(e^\beta-1)-1}{2(e^\beta-1)F(e^\beta-1)}, \qquad\beta\ne0, \tag*{(119)}

which gives 0<ζ′(β)<1/20<\zeta'(\beta)<1/2: the derivative remains in the interval where the urn function is affine. We recover

ζ′(0)=1/3,lim⁡β→∞ζ′(β)=1/2.(120)\zeta'(0)=1/3,\qquad\lim_{\beta\to\infty}\zeta'(\beta)=1/2. \tag*{(120)}

At the interior endpoint, we also have

lim⁡β→∞[ζ(β)−β/2]=log⁡(2/π).(121)\lim_{\beta\to\infty}\left[\zeta(\beta)-\beta/2\right]=\log(2/\pi). \tag*{(121)}

In equations (121) and (123), π\pi is the circle constant. The constant term is finite even though π(z+)=0\pi(z_+)=0. Figure 2 compares the exact solutions with the values from the recursion for the non-affine urn and the urn with zeros. In the non-affine example, the urn function

A non-affine urn and an urn with zeros

Figure 2. A non-affine urn and an urn with zeros. Top: (104), an increasing function with a Lipschitz inverse and fixed point 1/21/2; the CGF (108) has limiting slope one. Bottom: (111) vanishes from 1/21/2 onwards; the fixed point is 1/31/3 and the limiting CGF slope is 1/21/2. Left: urn function and diagonal; right: exact CGF and points computed with ℓ=16\ell= 16 intervals (circles) and ℓ=128\ell= 128 (crosses), using the same conventions as in Figure 1. The upper example starts at a=1a = 1 with the negative square root, the lower example at a=1/3a = 1/3 with the positive square root.

remains positive and the slope of the CGF tends to one; for the urn with zeros, the range of slopes ends at the interior endpoint 1/21/2.

Numerical evaluation. Each approximate point in the figures is obtained by substituting WℓW_\ell for WW in formulas (26)–(28). We denote the coordinates by βP\beta_{\mathcal{P}} and ζP\zeta_{\mathcal{P}}. The vertical error relative to the exact curve is

∣ζP(α)−ζ(βP(α))∣.(122)\left|\zeta_{\mathcal{P}}(\alpha)-\zeta\left(\beta_{\mathcal{P}}(\alpha)\right)\right|. \tag*{(122)}

Comparison at a prescribed value of β\beta also requires inverting the parametrization. For the four points corresponding to the exact values β=0.25,1,2,4\beta= 0.25,1,2,4, with ℓ=2048\ell= 2048 intervals uniformly spaced in α\alpha, the maximum of (122) is less than 3.3⋅10−43.3 \cdot10^{-4} in all examples. The quadratures were computed using the trapezoidal rule after the substitution

u=a+(α−a)sin⁡2(πs/2),0≤s≤1.(123)u = a + (\alpha-a)\sin^{2}(\pi s/2), \qquad0 \le s \le1. \tag*{(123)}

In these checks, doubling the grid from 65536 to 131072 intervals changes the reconstructed coordinates by less than 8⋅10−98 \cdot10^{-9}. This comparison measures the numerical sensitivity of the quadratures; the theoretical bound (25) concerns exact quadratures. On an interior interval, the reconstruction formulas are regular functions of the admissible data. Notice that near the endpoints the logarithms may amplify the error and require a separate check.

Declaration of Generative AI

Research, writing, and proofreading of the present manuscript were performed with AI assistance (GPT-6 Astra) under strict human guidance and scrutiny. We independently checked all mathematical arguments and take full responsibility for the content of the publication.

References

  1. [1]B. M. Hill, D. Lane, W. Sudderth, A Strong Law for Some Generalized Urn Processes, Ann. Probab. 8(2), 214–226 (1980). https://doi.org/10.1214/aop/1176994772.
  2. [2]R. Pemantle, A survey of random processes with reinforcement, Probab. Surv. 4, 1–79 (2007). https://doi.org/10.1214/07-PS094.
  3. [3]S. Franchini, The Urn of Hill, Lane and Sudderth, arXiv:2506.20826 (2026). https://doi.org/10.48550/arXiv.2506.20826.
  4. [4]W. Bryc, D. Minda, S. Sethuraman, Large deviations for the leaves in some random trees, Adv. Appl. Probab. 41(3), 845–873 (2009). https://doi.org/10.1239/aap/1253281066.
  5. [5]E. Baur, J. Bertoin, Elephant random walks and their connection to Pólya-type urns, Phys. Rev. E 94, 052134 (2016). https://doi.org/10.1103/PhysRevE.94.052134.
  6. [6]M. Podder, A. Roy, Elephant Random Walks with Multiple Extractions and General Reinforcement Functions, J. Theor. Probab. 39(1), 17 (2026). https://doi.org/10.1007/s10959-025-01471-4.
  7. [7]G. Dosi, Y. Ermoliev, Y. Kaniovski, Generalized urn schemes and technological dynamics, J. Math. Econ. 23(1), 1–19 (1994). https://doi.org/10.1016/0304-4068(94)90032-9.
  8. [8]S. Franchini, R. Balzan, Large-deviation theory of increasing returns, Phys. Rev. E 107, 064142 (2023). https://doi.org/10.1103/PhysRevE.107.064142.
  9. [9]T. Gottfried, S. Grosskinsky, Wages and capital returns in a generalized Pólya urn, J. Econ. Interact. Coord. 20, 477–518 (2025). https://doi.org/10.1007/s11403-024-00437-9.
  10. [10]K. Klymko, J. P. Garrahan, S. Whitelam, Similarity of ensembles of trajectories of reversible and irreversible growth processes, Phys. Rev. E 96, 042126 (2017). https://doi.org/10.1103/PhysRevE.96.042126.
  11. [11]K. Khanin, R. Khanin, A probabilistic model for the establishment of neuron polarity, J. Math. Biol. 42, 26–40 (2001). https://doi.org/10.1007/PL00000071.
  12. [12]B. Barabás, L. Caglioti, K. Micskei, G. Pá lyi, Data-Based Stochastic Approach to Absolute Asymmetric Synthesis by Autocatalysis, Bull. Chem. Soc. Jpn. 82(11), 1372–1376 (2009). https://doi.org/10.1246/bcsj.82.1372.
  13. [13]S. Briend, L. Devroye, G. Lugosi, Broadcasting in random recursive dags, ESAIM Probab. Stat. 29, 184–203 (2025). https://doi.org/10.1051/ps/2025002.
  14. [14]A. Bellina, C. Castellano, P. Pineau, G. Iannelli, G. De Marzo, Effect of collaborative-filtering-based recommendation algorithms on opinion polarization, Phys. Rev. E 108, 054304 (2023). https://doi.org/10.1103/PhysRevE.108.054304.
  15. [15]F. Tria, V. Loreto, V. D. P. Servedio, S. H. Strogatz, The dynamics of correlated novelties, Sci. Rep. 4, 5890 (2014). https://doi.org/10.1038/srep05890.
  16. [16]S. Franchini, R. Balzan, Random polymers and generalized urn processes, Phys. Rev. E 98, 042502 (2018). https://doi.org/10.1103/PhysRevE.98.042502.
  17. [17]S. Franchini, R. Balzan, Energy of the interacting self-avoiding walk at the θ point, Phys. Rev. E 102, 032143 (2020). https://doi.org/10.1103/PhysRevE.102.032143.
  18. [18]W. B. Arthur, Yu. M. Ermoliev, Yu. M. Kaniovski, Strong laws for a class of path-dependent stochastic processes with applications, in Stochastic Optimization, Lecture Notes in Control and Information Sciences 81, 287–300 (1986). https://doi.org/10.1007/BFb0007105.
  19. [19]R. Pemantle, When are touchpoints limits for generalized Pólya urns?, Proc. Amer. Math. Soc. 113(1), 235–243 (1991). https://doi.org/10.1090/S0002-9939-1991-1055778-8.
  20. [20]K. Nakayama, S. Mori, Universal function of the nonequilibrium phase transition of a nonlinear Pólya urn, Phys. Rev. E 104, 014109 (2021). https://doi.org/10.1103/PhysRevE.104.014109.
  21. [21]B. M. Hill, D. Lane, W. Sudderth, Exchangeable urn processes, Ann. Probab. 15(4), 1586–1592 (1987). https://doi.org/10.1214/aop/1176991995.
  22. [22]S. Franchini, Large deviations for generalized Polya urns with arbitrary urn function, Stochastic Process. Appl. 127(10), 3372–3411 (2017). https://doi.org/10.1016/j.spa.2017.02.010; corrigendum: Stochastic Process. Appl. 189, 104745 (2025), https://doi.org/10.1016/j.spa.2025.104745.
  23. [23]R. L. Jack, Large deviations in models of growing clusters with symmetry-breaking transitions, Phys. Rev. E 100, 012140 (2019). https://doi.org/10.1103/PhysRevE.100.012140.
  24. [24]J. R. Blum, M. Brennan, On the strong law of large numbers for dependent random variables, Israel J. Math. 37(3), 241–245 (1980). https://doi.org/10.1007/BF02760965.
  25. [25]S. Franchini, Large deviations for Generalized Polya Urns with non-binary increments, arXiv:2506.22234 (2026). https://doi.org/10.48550/arXiv.2506.22234.
  26. [26]T. Kennedy, Numerical computations for the Schramm–Loewner Evolution, J. Stat. Phys. 137, 839–856 (2009). https://doi.org/10.1007/s10955-009-9866-2.
  27. [27]H. Tran, Convergence of an algorithm simulating Loewner curves, Ann. Acad. Sci. Fenn. Math. 40, 601–616 (2015). https://doi.org/10.5186/aasfm.2015.4037.
  28. [28]G. Bardella, S. Franchini, P. Pani, S. Ferraina, Lattice physics approaches for neural networks, iScience 27(12), 111390 (2024). https://doi.org/10.1016/j.isci.2024.111390.
  29. [29]K. Friston, T. FitzGerald, F. Rigoli, P. Schwartenbeck, G. Pezzulo, Active Inference: A Process Theory, Neural Comput. 29(1), 1–49 (2017). https://doi.org/10.1162/NECO_a_00912.
  30. [30]A. Bandyopadhyay, D. Thacker, A new approach to Pólya urn schemes and its infinite color generalization, Ann. Appl. Probab. 32(1), 46–79 (2022). https://doi.org/10.1214/21-AAP1671.

Paper details

vlnc:W_26m8kv47
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents