Directed Acyclic Graph-Type Distributed Ledgers via Young-Age Preferential Attachment

1. Motivation and Background

1.1. Introduction

Distributed ledger technologies (DLTs), which are based on directed acyclic graphs (DAGs) such as the Tangle (Popov 2016) or Coordicide (Popov et al. 2020), generalize blockchain-based DLTs by weakening the ordering among the transaction blocks that constitute the ledger. Blockchain-based DLTs achieve total ordering of the transactions contained by the ledger through the rule of the longest chain as coined in Nakamoto (2006). Here, transactions are collected into blocks that each include a reference to the previous block such that a chain of ordered transactions emerges. When blocks are created concurrently such that only a partial order exists, the rule of the longest chain dictates that blocks that do not belong to the longest chain are discarded. This is a major factor that impairs the scalability of blockchain-based DLTs in terms of the rate of adding transactions to the ledger.

DAG-type distributed ledgers achieve scalability through allowing partially ordered transaction blocks (i.e., transaction blocks may reference more than one previous block). In this paper, we study the relation of design parameters for DAG-type DLTs based on the transient and limiting properties of the underlying transaction graph. We consider the graph of transaction blocks that emerges through block attachment (i.e., new blocks referencing preceding ones). We focus on two design choices for DAG-type DLTs.

• How many preceding blocks should a new block reference?

• How should the age of a preceding block impact the reference choice of a new block?

The rationale behind these two choices lies in the formulation of simple, probabilistic block reference rules that guarantee the existence of a giant forward component based on (i) a simple function of the number of preceding blocks to reference and (ii) an age preference parameter. A preference for old or high-degree vertices creates a graph architecture that is locally tree like and features vertices of arbitrary high degree, which differs extremely from the linear structure of blockchain-based DLT. Young-age preferential attachment (YAPA) interpolates between these two structural extremes and generates a sparse, locally tree-like graph in which there are no hubs (i.e., the maximal degree grows only weakly with the system). We provide a simple reference rule that allows us to study the two questions analytically and investigate some transient and asymptotic properties of the transaction block graph, such as the reference degree distribution, degree evolutions, the existence of a giant forward component, and the size of the “detached surface” of vertices in the transaction graph that do not connect to any previous transactions.

1.2. Related Literature About DLTs

Blockchain technology is based on the following fundamental principles. (i) Decentralization. Because of its distributed architecture, a blockchain does not rely on a central server but rather, stores data in a decentralized manner, and it can be updated by any node in the network. (ii) Transparency. Each node (peer) has a local copy of the blockchain, and updates are sent as a broadcast to all nodes. Therefore, any change to the blockchain is transparent to all members of the network. (iii) Open source. The original blockchain protocol introduced with Bitcoin is publicly available and can be used for development. (iv) Autonomy. All peers can update or transmit the stored data. Each node can verify the accuracy of all data received. This eliminates the need for trust between participants. (v) Immutability. Once a transaction block is part of the blockchain, it is stored publicly forever, and its contents (i.e., transactions) cannot be edited without changing the hash value stored in all subsequent blocks. (vi) Anonymity. Data transmission in the blockchain is done via addresses, and therefore, user identities remain hidden.

Current blockchain-based cryptocurrencies are often presented as an alternative to traditional currencies. However, there are questions about the scalability and performance of distributed ledgers compared with established payment systems (Croman et al. 2016, Pappalardo et al. 2017). Currently, the Bitcoin network is only capable of processing very few transactions per second (Blockchain Luxembourg S.A. 2021c), and it takes up to 20 minutes for a newly posted transaction to be processed (Blockchain Luxembourg S.A. 2021b). Established payment processors, on the other hand, process up to four orders more transactions per second, and new transactions are usually processed within a few seconds. A significant influence on the performance of the globally distributed peer-to-peer Bitcoin system (Donet et al. 2014) is the propagation speed of the blocks in the network (Decker and Wattenhofer 2013). For example, for a 1-MB block, which is roughly the average block size (Blockchain Luxembourg S.A. 2021a), it takes about 2.4 minutes (Croman et al. 2016) for 90% of the nodes to receive this block. With the block interval of 15 minutes used by the Bitcoin network, this poses a significant problem, which increasingly leads to the splitting of the blockchain—the so-called blockchain forks (Decker and Wattenhofer 2013). The emergence of such forks significantly decreases the performance of the distributed ledger system.

Although approaches already exist to optimize the propagation speed of information in the distributed ledger network (Fadhil et al. 2016, 2017), these also do not reach the performance of current financial transaction systems. In addition to optimizing the propagation speed, other improvements arise in the communication protocol used (Croman et al. 2016, Gobel and Krzesinski 2017). One way to optimize the current Bitcoin protocol in terms of transmission speed is to minimize unnecessary transmissions by adjusting the sequence of exchanged messages needed to transmit new blocks. Instead of first publishing the availability of information, blocks that do not exceed a certain threshold in terms of size can thus be distributed directly to neighboring nodes. This can increase the effective transmission speed especially for small blocks, where the protocol overhead has a particularly large impact. Decker and Wattenhofer (2013) have shown that such protocol adaptations can reduce blockchain forks by about 50%.

To increase scalability and transaction throughput, nonlinear graph-based distributed ledgers (Lewenberg et al. 2015, Popov 2016, Sompolinsky et al. 2016, Yeow et al. 2017, Sompolinsky et al. 2021) replace the traditional blockchain with a global DAG that contains all recorded transactions. In this graph, the nodes are transaction blocks (consisting of one or more transactions), whereas the edges indicate the validation of previous blocks/transactions. Each added node should validate $k\ge 1$ transactions, where k can be fixed or random. A key advantage of DAG-based systems is that by deviating from the linear longest blockchain rule, scalability can be greatly improved. The longest blockchain rule essentially requires all nodes to know about newly created blocks quickly, thus limiting the creation of blocks to allow for the propagation of this knowledge before a new block is created. Instead of trusting the longest-chain rule as given in blockchain-distributed ledgers, DAG-based distributed ledgers rely on metrics, such as the largest strongly connected cluster of transaction nodes in the transaction graph, to determine the trusted transactions (Sompolinsky et al. 2021).

Beyond financial transactions, there exist many application areas for distributed ledgers; for example, in the context of distributed and secure storage of personal data (Zyskind et al. 2015) or for asynchronous messaging services in the context of distributed computing (Yin et al. 2018). Particularly, the former use case is of high relevance because of increasingly frequent incidents in which personal data are publicly accessible because of security breaches or data misuse. Here, the use of distributed ledgers as a system for distributed access control offers a potential solution. Instead of storing data centrally and granting direct access, queries are mapped as well as sharing information via transactions. Combined with off-chain storage of sensitive data, it is thus possible to develop a distributed ledgers system in which each user retains full control over their own data. In addition to increased security, this has the advantage that laws and other regulations can be implemented directly in the protocol used in the form of policies (Zyskind et al. 2015).

1.2.1. Organization of the Paper.

In the following section, we introduce the model formally and present our mathematical main results. Section 3 contains further discussion of how our results relate to previous work and of the practical implication of our results for DLT applications. Section 5 contains numerical simulations. Finally, detailed proofs of our main results are provided in Section 6.

2. Model and Main Results

2.1. Model Definition

The model we propose is based on young-age preferential attachment. We study a recursive growth parametrized by two numbers, the edge density parameter $\alpha >0$ and the reinforcement bias $\beta >0$. We use the shorthand notations $[n]$ for $\{1,\dots ,n\}$ and $x\wedge y,x\vee y$ to denote $\min (x,y)$ and $\max (x,y)$, respectively. At step n = 1, the graph G₁ is initialized with a vertex labeled one. At any step n > 1, one vertex labeled n is added to the system, and G_n is obtained recursively from $G_{n-1}$ according to the following attachment rule. For each $m\in [n-1]$, n sends an arc to m independently of everything else with probability

We formally write $G_n=([n],E_n)$ with $E_n\subset [n]\times [n]$ for the graph obtained upon adding the nth vertex. If n sends an arc to $m\in [n-1]$, we denote this event by $n\to m$. The notation $n\twoheadrightarrow m$ is shorthand for the existence of a directed path from n to $m\in [n-1]$. Note that the direction of the arcs along any path can be recovered from the labels of the vertices that belong to the path (Figure 1).

2.2. Key Properties of the YAPA Model

Ignoring the dynamical aspect of our model, it can be viewed as an instance of the directed inhomogeneous random graph model proposed in Cao and Olvera-Cravioto (2020), which allows us to infer some basic properties of the network from known results about this model class. We first establish that the young-age preferential attachment model produces a sparse graph (i.e., the number of arcs is of the same order as the number of vertices).

Proposition 1

(Sparsity). It holds that

$$\underset{N\to \infty }{\lim }\frac{|E_N|}{N}=\frac{\alpha }{\beta +1} in L^1 \mathit{\text{and}} \mathit{\text{almost}} \mathit{\text{surely}}.$$

Next, we determine the distributional limit of the vertex degrees in G_n. For any vertex $m\in [n]$, we denote by $D_n(m)=(D_n^{\mathsf{\text{in}}}(m),D_n^{\mathsf{\text{out}}}(m))$ its degree (vector) in G_n: that is,

Note that the outdegree of a vertex is determined once and for all upon its insertion (i.e., $D_n^{\mathsf{\text{out}}}(m)=D_m^{\mathsf{\text{out}}}(m)≕D^{\mathsf{\text{out}}}(m)$ for all $n\ge m$). As can be guessed from the fact that connections occur independently and with probability of order $1/n$, the asymptotic degree distribution is bivariate Poisson.

Theorem 1

(Limiting Degree Distribution and Rate of Convergence). Let G_N denote the young-age preferential attachment graph on N vertices. For $U\in [N]$ uniformly chosen among the vertices of G_N, the following asymptotic results hold:

$$D_N(U)=(D_N^{\mathsf{\text{in}}}(U),D^{\mathsf{\text{out}}}(U))\to (Z^{\mathsf{\text{in}}},Z^{\mathsf{\text{out}}}) in \mathit{\text{distribution}} \mathit{\text{and}} in L^1 as N\to \infty .$$

Here, $Z^{\mathsf{\text{in}}}$ and $Z^{\mathsf{\text{out}}}$ are independent, and $Z^{\mathsf{\text{out}}}$ is $\mathrm{Poisson}(\alpha /(\beta +1))$ distributed. The limiting indegree $Z^{\mathsf{\text{in}}}$ has distribution $\text{mixed-Poisson}(\mathrm{\Lambda })$ with mixing random variable $\mathrm{\Lambda }=\alpha (1-V^{\beta })/\beta$, where V is $\mathrm{Uniform}[0,1]$. Moreover, we have that

$${\mathsf{d}}_{\text{TV}}(P^{\mathsf{in/out}}(N),p^{\mathsf{in/out}})=O\left(\sqrt{\frac{{(\mathrm{log\hspace{0.17em}}N)}^3}{N}}\right),\hspace{1em}\mathit{\text{almost}} \mathit{\text{surely}} as N\to \infty ,$$(2)

where $P^{\mathsf{in/out}}(N)={(P_k^{\mathsf{in/out}}(N))}_{k=0}^{\infty }$ denotes the empirical in- or outdegree distribution of G_N, $p^{\mathsf{in/out}}={(p_k^{\mathsf{in/out}})}_{k=0}^{\infty }$ denotes the distribution of $Z^{\mathsf{in/out}}$, and ${\mathsf{d}}_{\text{TV}}(·,·)$ denotes total variation distance.

Remark 1.

The form of the limiting degree distribution in Theorem 1 is obtained rather directly by applying the machinery of Cao and Olvera-Cravioto (2020), but the error bound (2) is new and does not follow from previous results about inhomogeneous random graphs. Inspection of the proof further yields that an error of the same order can be achieved for any graph on N vertices in which edges are drawn independently with probability at most c/N for some universal c (cf. Lemma 3). We do not believe that the logarithmic term is asymptotically sharp, but the polynomial order $1/\sqrt{N}$ is consistent with known results for other sparse models with independent edges, such as the Erdös–Rényi graph (cf. van der Hofstad 2017, theorem 5.12).

It follows from Theorem 1 that whereas the outdegree is asymptotically independent of the time at which a node enters the system, the indegree is not. Essentially, the limiting indegree distribution of a given node is also $\mathrm{Poisson}(\alpha /(\beta +1))$, but the time needed to collect all incoming links grows proportionally with network size. A node born at the beginning corresponds to V near zero, and a node born at a time close to the total age of the system corresponds to V close to one.

The indegree dynamics of fixed vertices are further characterized by the following bounds.

Proposition 2

(Degree Evolutions). The maximal (total) degree of any vertex in G_N is almost surely $O(\mathrm{log\hspace{0.17em}}N)$. We further have that

1. for any $n\ge m\ge 1$,

   $$\mathsf{P}[D_n^{\mathsf{\text{in}}}(m)>x]\le \exp \left[-\frac{\alpha }{\beta }-x\left(\mathrm{log\hspace{0.17em}}x+\log \frac{\beta }{\alpha }-\frac{\beta }{\alpha }\right)\right],x>\alpha /\beta ;$$

2. $\mathsf{E}[D^{\mathsf{\text{out}}}(m)]=\frac{\alpha }{\beta +1}+O(1/m)$ for any $m\ge 1.$

Let us now discuss the connectivity of the YAPA network. The forward component of $m\in [n-1]$ after the arrival of vertex n, $1\le m\le n$ is given by

and for the distributed ledger application discussed in Section 1, it is desirable that the network be rooted (i.e., $C_n(1)=[n]$). Because of the stochastic nature of the attachment mechanism, this is typically not the case but can formally be achieved by augmenting the network by some root vertex ρ that deterministically connects to precisely those vertices that have outdegree 0. Of course, the proportion of vertices that fail to connect to any existing vertices should be rather small, which is ensured by the light tails of the limiting Poisson distribution.

Corollary 1

(Detached Surface). We have that

$$\underset{N\to \infty }{\lim }\frac{|\{m\in \{2,\dots ,N\}:D^{\mathsf{\text{out}}}(m)=0\}|}{N}={\text{e}}^{-\alpha /(\beta +1)} \mathit{\text{almost}} \mathit{\text{surely}} \mathit{\text{and}} in L^1.$$

Although there is still a positive fraction of nodes with no left neighbors, this fraction is not very large; for instance, if we would like to make sure that with probability at least 0.995, a typical vertex sends an arc to at least one vertex, it suffices to choose $\alpha >\log (200)(\beta +1)\approx 5.3(\beta +1)$.

Next, we would like to ensure that the vast majority of vertices that do connect upon arrival in the system are contained in the forward component of only a handful of vertices. This can only be achieved if there exist vertices m such that $C_N(m)$ grows linearly with N. Our first result concerning such macroscopic components states that the forward component of a typical vertex is not of linear order.

Proposition 3

(No Giant Forward Components for Typical Vertices). Let $U\in [N]$ be uniformly chosen; then, for any $\epsilon >0$, we have

$$\underset{N\to \infty }{\lim }\mathsf{P}(|C_N(U)|\ge \epsilon N)=0.$$

Remark 2.

As for Theorem 1, the neighborhood around a typically chosen vertex can be described by the local limit approach used in Cao and Olvera-Cravioto (2020). It is not hard to see that the weak local limit of $C_N(U)$ is in fact the family tree obtained from the multitype Galton–Watson process given by the following recursion.

• Sample $V\in [0,1]$ uniformly. Generation 0 of the tree comprises the root, which has type V.

• For any $k\ge 1$, given generation k − 1 of the tree, each member m in generation k − 1 of type V_m independently produces a $\mathsf{\text{Poisson}}$($\alpha (1-V_m^{\beta })/\beta$)-distributed number of offspring to obtain the kth generation, and each of the offspring thus produced is independently assigned a type drawn uniformly from $[V_m,1]$.

The proof of Proposition 3 in Section 6 shows that the local limit tree dies out for any choice of $\alpha ,\beta >0$. Contrary to the local behavior near a typical vertex, if $\alpha >\beta +1$, most vertices indeed belong to the forward components of a few old vertices. More precisely, let $n_0=\lfloor 1/\alpha \rfloor$; then, the vertices $1,\dots ,n_0$ are always sequentially connected by construction, and we thus focus on the forward components of vertices added after n₀.

Theorem 2

(Existence of Giant Forward Components). Let $m>n_0$ be given. Then, almost surely,

$$\underset{N\to \infty }{\lim }\frac{|C_N(m)|}{N}=\{\begin{array}{ll}0,\hfill & if \alpha \le \beta +1,\hfill \\ Z(m),\hfill & if \alpha >\beta +1,\hfill \end{array}$$

where Z(m) is a nontrivial random variable that is concentrated on the two solutions 0 and $\gamma >0$ of the fixed point equation

$$x=1-{\text{e}}^{-\frac{\alpha }{\beta +1}x},\hspace{1em}x\in [0,\infty ).$$

Theorem 2 is the main result of this article. The apparent differences in the characterizations obtained in Proposition 3 and Theorem 2 are because of the reducibility of the graph. Proposition 3 is concerned with the forward component of a typical (i.e., uniformly chosen) vertex. Such a typical vertex has a birth time of order N and can simply not collect enough direct and indirect references up to time N to develop a large forward component. In particular, applying the machinery of Cao and Olvera-Cravioto (2020) (after some adaptations to account for irreducibility) yields that typical vertices do not have a giant forward component; see the proof of Proposition 3.

In contrast, Theorem 2 states that if an early vertex is kept fixed and the time horizon is extended to infinity, with positive probability, the selected vertex will be the root of a forward component of linear size eventually. We stress that it is not possible to derive statements of this type directly using the general theory of Cao and Olvera-Cravioto (2020), which uses the local weak limit of the graph (i.e., limit distributions of neighborhoods of typical vertices) and therefore, does not provide sufficient information about vertices with index $n=o(N)$.

3. Further Related Work and Discussion of Results

3.1. Design of Tip Selection for DAG-Type Distributed Ledgers

DAG-type distributed ledgers, such as IOTA (Popov 2016), utilize different algorithms for achieving consensus. State-of-the-art DAG-type DLTs repurpose the act of selecting transactions for validation (i.e., constructing arcs from an arriving node to previous ones for achieving consensus). In a nutshell, the tip selection algorithm in Popov (2016) is based on a biased random walk, and a transaction that is directly or indirectly validated by a large portion of the subsequent transactions is highly probable to be considered valid. Precisely, a tip on the surface of the DAG is selected based on a random walk from genesis to the surface. This random walk is biased in the sense that nodes possess a weight that resembles the number of subsequent nodes that are directly or indirectly attached to this node and that the jump probability of the random walk from a node i with weight w_i to a node j with weight w_j is $\text{exp}(-\eta (w_i-w_j))$ with a given constant $\eta >0$. For finite time, the value of the constant α may play a role to adjust the tip selection to mimic a uniformly random tip selection or to quickly concentrate the tip selection on a set of young nodes. However, this algorithm is different from our YAPA model as it concentrates the tip selection on certain walks where the node weights are large.

Further works, such as Kusmierz and Gal (2018) and Ferraro et al. (2020), analyze different properties of the DAG-type distributed ledgers, especially the IOTA DAG, which is denoted the Tangle. Kusmierz and Gal (2018) derive approximations of the probabilities that a node is left behind or that a node becomes a permanent tip. Specifically, the first approximation of the probability that a node is left behind is similar to the detached surface evolution in Corollary 1. Ferraro et al. (2020) provide a modified IOTA tip selection algorithm that is based on a combination of two Markov chain Monte Carlo algorithms with different parameters that aims to have all nodes validated. They prove this property using a fluid limit in the arrival rate of transactions.

In Coordicide (Popov et al. 2020), which is a follow-up work on IOTA constituting a modern DAG-type DLT, tip selection is fixed to validating two existing transactions. Here, the authors dispense with tip selection as a consensus mechanism and rather, consider it from a performance point of view (i.e., analyzing the impact of the tip selection on the DAG properties, especially in discouraging “lazy” behavior, which resembles the recurring validation of a fixed set of old transactions).

We consider this work in the same vein (i.e., our YAPA model provides a relationship between the parameters of the tip selection algorithm (that is, the edge density α and the reinforcement bias β) and the DAG-distributed ledger properties). We establish the YAPA model in (1) as a rule to encourage the validation of young transactions. From the calculation of the asymptotic distribution of the outdegree $Z^{\mathsf{\text{out}}}$ (which turns out to be $\mathrm{Poisson}(\alpha /(\beta +1))$) as well as the nonasymptotic expected outdegree at a given time point $\mathsf{E}[D_k^{\mathsf{\text{out}}}]$, we know the expected number of transactions that are validated given parameters α, β. Further, the reinforcement bias $\beta >0$ is understood as a forgetting factor, precisely a parameter to set the preference for validating young transactions (i.e., larger $\beta >0$ leads to a stronger preference of younger transactions over older ones). Hence, by choosing α, β while ensuring $\alpha >\beta +1$, the properties of the distributed ledger can be controlled. As is reflected in our results, we study the following properties: (i) the emergence of “giant” components (i.e., a linear increase of the number of direct and indirect validations that a transaction receives over time), (ii) the average number of direct validations received by a transaction over time, and (iii) the number of orphan transactions.

3.2. Related Mathematical Results

Our model is similar in spirit to the one introduced in Lyon and Mahmoud (2020) but with two important differences. First, their model produces a tree, whereas our model produces a directed acyclic graph that is typically not a tree. Second, we modulate the attachment via the parameters α and β to obtain a whole range of instances. This flexibility allows us to tune the model to specific applications and also allows us to observe the connectivity phase transition of Theorem 2. The young-age preferential attachment tree of Lyon and Mahmoud (2020) corresponds to running our model with β = 1 and conditioning on the creation of precisely one arc per time step. As explained in Section 2, our model can be analyzed in the general framework of Cao and Olvera-Cravioto (2020), who adapted the very general framework of inhomogeneous random graphs developed in Bollobás et al. (2007) to directed graphs, thereby generalizing earlier results of Bloznelis et al. (2012). We use some techniques from the (directed) inhomogeneous random graph world to obtain the degree sequence and analyze the emergence of a giant connected component for our model in Proposition 3. However, because $\kappa (·,·)$ is not reducible and we investigate connected components in terms of directed paths, our main result in Theorem 2 cannot be obtained by a direct application of the results in Bloznelis et al. (2012) and Cao and Olvera-Cravioto (2020). We also emphasize the dynamic nature of our model, which is not captured by the inhomogeneous random graph framework. Furthermore, if we were to ignore the direction of the arcs and consider G_N as an undirected graph, then it is straightforward to deduce that the limit ${\lim }_{N\to \infty }|C_N(U)|/N$ in Proposition 3 would be positive whenever $\alpha >\beta +1$ (cf. Bollobás et al. 2007).

The limiting case β = 0 of the YAPA model corresponds to a directed version of the uniformly grown random graph investigated in Bollobás and Riordan (2004) and Bollobás et al. (2005); this is a very natural recursive model that was first studied by Dubins in the 1980 s (cf. Kalikow and Weiss 1988, Shepp 1989, Durrett and Kesten 1990). Although we exclusively consider positive values of β, choosing $\beta <0$ would lead to a preference for old-age vertices and produce an effect similar to degree-based preferential attachment models, such as the Barabási–Albert model (Barabási and Albert 1999). Models of this type have been investigated thoroughly in the last 20 years (see, e.g., Bollobás et al. 2001; Dereich and Mörters 2009, 2013; and the references therein). Old-age preferential attachment models produce graphs with entirely different features, such as a scale-free degree distribution, whereas the degrees in the YAPA model are fairly sharply concentrated around their expectation as is exemplified by Proposition 2.

4. Simulation

In the following, we describe evaluation results that are based on simulating the model with attachment probabilities given by (1). Transaction blocks arrive according to a Poisson process with rate λ = 1. We fix the reinforcement bias β = 2 and variate the edge density parameter α. Figure 2 shows the evolution of the connected component size starting at the genesis node (transaction) for the first 10⁵ transactions for different α. Note the linear growth rate of the connected component for $\alpha >\beta +1$. The figure shows the empirical average in addition to the standard deviation (which is depicted as the shaded area) from 20 independent simulation runs. Note that the standard deviation for the subcritical regime α = 2 is large because there is no natural scaling (in N) for the component size.

Figure 3 shows the error $|C_N(m)|/N-Z(m)$ as calculated from Theorem 2 for $\alpha =4,\beta =2,m=10$. The figure shows clearly the convergence of the ratio $|C_N(m)|/N$ to Z(m) with a growing number of vertices N.

Figure 4 shows the properties of the shortest paths to the genesis node for various values of the reinforcement bias β and the edge density parameter α. In light of the impact of the tip selection algorithm parameterization through α and β, the figure reflects the shape of the transaction DAG (i.e., its depth and width in terms of the length of the shortest paths to genesis). In comparison, note that the extreme cases of a DAG of depth 1 or a totally ordered chain produce sum lengths of the shortest paths of size n and $n^2/2$, respectively. The figure also shows markers for the values of $(\alpha ,\beta )$ that correspond to a mean outdegree $\mathsf{E}[Z^{\mathsf{\text{out}}}]=2$, which is used in the context of DAG-type DLT (Popov 2016, Popov et al. 2020) as a deterministic guideline for the number of validated nodes per new node. Although the fraction of nodes not connected to genesis remains constant as given by the detached surface approximation in (5), the shape of the DAG DLT can be controlled by the choice of α, β. Note that a similar argument can be made in terms of the shortest paths to some arbitrary genesis cluster of nodes.

5. Implications for DLT Applications

Our work is motivated by questions on the design choices of DAG-based DLT applications, in particular on how the analyzed YAPA referencing scheme that relates newly generated blocks to previously generated ones affects the DLT properties. In the following, we discuss the implications of the obtained results for some design aspects of DLT applications.

5.1. Tip Selection

Tip selection is often convolved with consensus as in Popov (2016) and Müller et al. (2022). In Popov et al. (2020), tip selection is considered separately and set to referencing a fixed number of previous blocks. When tip selection is convolved with consensus, it is usually based on some aggregate weight of the blocks that must be tracked (Popov 2016, Müller et al. 2022). Some works also propose uniform random tip selection on a subset of (nonconflicting) blocks, such as Müller et al. (2022).

The first implication of the YAPA model definition is that users that generate blocks do not have to track or calculate block weights according to more or less complex and time-consuming algorithms. The configuration model is entirely determined by the YAPA parameters α, β. In turn, these determine the required storage and computation capacity for reference operations (i.e., the number of references (hashes) that are required on average as in Proposition 1). Note that each reference is usually tied to one hash operation as well as a linear growth of storage space. This stands in contrast to the deterministic number of references as well as the weight-based referencing methods.

5.2. Laziness and Permanent Tips

The reviewed state of the art makes great effort to avoid lazy behavior (i.e., preventing users from referencing a fixed set of old blocks). The temptation to do this is based on the reuse of computed hashes in old blocks in referencing for new blocks. The YAPA configuration readily dispenses with this problem for $\alpha ,\beta >0$. On the other hand, the risk of a block becoming a permanent tip is shown for our model in Corollary 1. This can be considered the cost of using the simple YAPA configuration model as the detached surface contains transaction blocks that are never verified.

5.3. Consensus and Time to Confirmation

The results of this work emphasize that consensus in a DAG-based DLT that uses the proposed YAPA configuration model can be reached. Theorem 2 shows that a consensus method based on the so-called heaviest weighted subchain (Wang et al. 2022) or the so-called heaviest sub-DAG (Müller et al. 2022) is viable under a proper YAPA configuration of $\alpha >\beta +1$. The simulation results validate this behavior for a range of realistic parameters (i.e., average number of references/hashes of $\alpha \in \{2,3,4\}$ and β = 2). Further, the simulation results provide insights in the form if the DLT is controlled by the YAPA configuration α, β. Related works, such as Popov (2016) and Müller et al. (2022), assume a constant Tangle width and that the numbers of tips of the Tangle are stationary with a given mean. Note that in Müller et al. (2022), this is justified by a number of chosen tips equal to one. Our simulations show, on the other hand, that the shape of the Tangle can be controlled by adjusting α and β at a fixed average outdegree (i.e., number of referenced previous blocks). In turn, the shape of the Tangle implicates the causal relations of transaction blocks (i.e., for a given number of blocks, N having a few long chains of blocks (approaching line topologies) with crossreferences is semantically different from having many short chains of blocks (approaching a star topology)). The former form distributes the cumulative weight required for consensus, whereas the latter concentrates this weight on a few blocks. Nevertheless, the result in Theorem 2 shows that consensus can be achieved after long-enough time.

Time to confirmation is a performance metric for the consensus protocol of the DLT. As discussed, the YAPA configuration model for a DLT provides two guarantees. First, the confirmation time in terms of the rate of convergence of the distribution of the number of direct block references received is bounded in Theorem 1. This stands in contrast to heuristics to obtain estimates of the time to confirmation as, for example, in Popov (2016) and Müller et al. (2022), where some difficulty stems from the intractability of the referencing rule.

6. Proofs

The proofs of our main results are divided into three sections. The first section contains the derivation of results that can be obtained in the general framework of Cao and Olvera-Cravioto (2020). The second section provides concentration bounds for degree properties, which are needed in the last section or are interesting in their own right, and the final section contains the proof of our main result, Theorem 2.

6.1. Directed Inhomogeneous Random Graphs and Branching Process Approximation

We call

the weight of vertex m upon the arrival of vertex n. An equivalent way of characterizing our model is to fix $N\in \mathbb{N}$ and rewrite the connection probabilities using the kernel $\kappa :{[0,1]}^2\to [0,\infty )$ given by

Then,

Setting also

the pair $(\kappa ,\varphi )$ parametrizes an instance of a directed inhomogeneous random graph in the sense of Cao and Olvera-Cravioto (2020). We can thus readily apply several results of Cao and Olvera-Cravioto (2020), by which we immediately establish sparsity of G_N and the form of the limiting degree distribution in the next subsection. Note that, however, κ is clearly a reducible kernel because it has no mass on the lower diagonal. Therefore, the connectivity results for irreducible kernels established in Cao and Olvera-Cravioto (2020) do not apply.

It is straightforward to verify the regularity assumptions listed in Cao and Olvera-Cravioto (2020, assumption 3.1) for our model using κ and $\varphi$ as defined and interpreting $[0,1]$ together with the Lebesgue measure as the ground space. Proposition 1 is now a special case of the corresponding statement in Cao and Olvera-Cravioto (2020).

Proof of Proposition 1.

By Cao and Olvera-Cravioto (2020, proposition 3.3), we have

$$\frac{|E_N|}{N}\to {\displaystyle {\int }_0^1{\displaystyle {\int }_0^1\kappa }}(x,y)\hspace{0.17em}\text{d}x\text{d}y=\frac{\alpha }{\beta +1}\hspace{1em}\text{in} L^1.$$

Each

$$X_n=|E_{n+1}|-|E_n|={\displaystyle \sum _{m=1}^n\mathsf{1}}\{n+1\to m\},\hspace{1em}n\in \mathbb{N},$$

is a sum of independent Bernoulli random variables with variance

$${\sigma }_n^2\le {\displaystyle \sum _{m=1}^n\frac{w_n(m)}{n}}\left[\left(1-\frac{w_n(m)}{n}\right)\vee 0\right],\hspace{1em}n\in \mathbb{N}.$$

In particular, because $w_n(m)\le \alpha$ for all m, n, we have

$${\displaystyle \sum _{n=1}^{\infty }\frac{{\sigma }_n^2}{n^2}}\le {\displaystyle \sum _{n=1}^{\infty }\frac{\alpha }{n^2}}<\infty ,$$

and Kolmogorov’s Strong Law of Large Numbers (see, e.g., Feller 1950, theorem 8.3) yields almost sure convergence. □

Proof of Limiting Distribution in Theorem 1.

The limiting distribution described in Theorem 1 is obtained as a special case of the statement of Cao and Olvera-Cravioto (2020, theorem 3.4) when applied to the kernel κ given in (3). □

Proof of Corollary 1.

The detached surface

$$\mathcal{D}(n)=\{1<k\le n:D^{\mathsf{\text{out}}}(k)=0\},\hspace{1em}n>2,$$

comprises all vertices that have arrived and do not attach to any previous vertices. We let ${\mathrm{\Delta }}_n=|\mathcal{D}(n)|$ denote the size of the detached surface at time n. L¹ convergence of ${\mathrm{\Delta }}_n/n$ to ${\text{e}}^{-\frac{\alpha }{\beta +1}}$ is a direct consequence of Theorem 1 because $\mathsf{E}[{\mathrm{\Delta }}_n/n]+1/n$ is precisely the probability that a uniformly chosen vertex has outdegree 0. Alternatively, we can calculate the asymptotic density of Δ_n directly. The probability that the kth arriving vertex does not attach to any previous vertex is

$$p_k^{\prime }={\displaystyle \prod _{i=1}^{k-1}(1-p_k(}i)),\hspace{1em}k>1.$$(4)

Using that $p_k(i)\le \frac{\alpha }{k-1}$, we obtain that $\log (1-p_k(i))=-p_k(i)+O(1/k^2)$ and thus,

$$\underset{k\to \infty }{\lim }{p}_k^{\prime }=\underset{k\to \infty }{\lim }{\text{e}}^{-{\sum }_{i=1}^{k-1}{p}_k(i)}={\text{e}}^{-\frac{\alpha }{\beta +1}}.$$(5)

The outdegrees of different vertices are independent, and therefore, Δ_n is a sum of independent $\mathrm{Bernoulli}(p_k^{\prime })$-distributed random variables. The corresponding variances $p_k^{\prime }(1-p_k^{\prime })$ are uniformly bounded by one; thus, another invocation of Kolmogorov’s Strong Law of Large Numbers yields almost sure convergence of ${\mathrm{\Delta }}_n/n$ to ${\text{e}}^{-\alpha /(\beta +1)}.$ □

Proof of Proposition 3.

In Cao and Olvera-Cravioto (2020, section 4.3.1), it is shown that the forward exploration started in a uniform vertex can be coupled to a multitype branching process with family tree $\mathcal{T}$. It is straightforward to deduce from the form of κ that this branching process is the Galton–Watson process described in Remark 2. It is well known and not hard to prove that if $|\mathcal{T}|<\infty$ almost surely, then we have $\mathsf{P}(C_N(U)>\epsilon N)\to 0$ as $N\to \infty$ for any $\epsilon >0,$ and additionally, see, for example, van der Hofstad (2021, corollary 2.27). The survival probability $\zeta =\mathsf{P}(|\mathcal{T}|=\infty )$ of the Galton–Watson process can be characterized via the Volterra-type operator $T=T(\kappa )$ on $L^2[0,1]$ given by

$$Tf(x)=\alpha x^{\beta }{\displaystyle {\int }_x^1{y}^{-\beta -1}}f(y)\hspace{0.17em}\text{d}y,\hspace{1em}x\in (0,1),$$

and see Bollobás et al. (2007) and Cao and Olvera-Cravioto (2020) for a general account of the connection between $\mathcal{T}$ and T. Note that T is an unbounded operator (because of the divergence of $y^{-\beta -1}$ at zero), which makes it necessary to use the approximating family of operators $\{T_{\delta },\delta >0\}$ given by

$$T_{\delta }f(x)=\alpha x^{\beta }{\displaystyle {\int }_{x\vee \delta }^1{y}^{-\beta -1}}f(y)\hspace{0.17em}\text{d}y,\hspace{1em}x\in (0,1),\delta >0.$$

Our goal is to show that for any choice of $\delta >0$, we have that $\zeta \le \delta$, and hence, ζ = 0. Let U_t denote the type of vertex $t\in \mathcal{T}$, and let U₀ denote the type of the root; then,

$$\mathsf{P}(|\mathcal{T}|=\infty )\le \delta +\mathsf{P}(|\mathcal{T}|=\infty ,U_0>\delta ).$$

Note that $\{U_0>\delta \}=\{U_t>\delta \hspace{0.17em}\forall t\in \mathcal{T}\}$ because types must increase along any genealogical path in $\mathcal{T}$. On the event $\{U_t>\delta \hspace{0.17em}\forall t\in \mathcal{T}\}$, the evolution of the branching process is represented by the operator $T_{\delta }$. More precisely, we have that $T_{\delta }^{k}1(x),k=1,2,\dots$, where $1(x)\equiv 1$ denotes constant unit function and describes the expected number of offspring of type $\text{d}x$ in the kth generation ${\mathcal{T}}^k$ of $\mathcal{T}$; hence,

$$\mathsf{E}(|{\mathcal{T}}^k||U_0>\delta )=\frac{1}{1-\delta }{\displaystyle {\int }_{\delta }^1{T}_{\delta }^k}1(x),\text{d}x.$$(6)

We assume for the moment that $T_{\delta }$ is quasinilpotent for any $\delta >0$ (i.e., ${\lim }_{k\to \infty }\Vert T_{\delta }^k\Vert =0$, where $\Vert ·\Vert$ denotes the operator norm on $L^2[\delta ,1]$). In particular, this implies that $\mathsf{E}(|{\mathcal{T}}^k||U_0>\delta )$ vanishes as $k\to \infty$, and hence,

$$\mathsf{P}(|\mathcal{T}|=\infty |U_0>\delta )=\underset{k\to \infty }{\lim }\mathsf{P}(|{\mathcal{T}}^k|\ge 1|U_0>\delta )\le \underset{k\to \infty }{\lim }\mathsf{E}(|{\mathcal{T}}^k||U_0>\delta )=0.$$

Thus, it only remains to show that for any fixed $\delta >0,\hspace{0.17em}{T}_{\delta }$ is quasinilpotent. Because $y^{-\beta -1}$ is bounded on $[\delta ,1]$, it is straightforward to verify that $T_{\delta }$ is a compact operator on $L^2[\delta ,1]$; hence, $T_{\delta }$ is quasinilpotent precisely if zero is its only eigenvalue (see, e.g., Dunford and Schwartz 1988, section VII 5.13). Assume for contradiction that $T_{\delta }$ has the eigenvalue $\lambda \ne 0$: that is, that there is some $f\in L^2[\delta ,1]\setminus \{0\}$ satisfying for almost every $x\in [\delta ,1]$

$$\lambda f(x)=T_{\delta }f(x)=\alpha x^{\beta }{\displaystyle {\int }_x^1{y}^{-\beta -1}}f(y)\hspace{0.17em}\text{d}y.$$(7)

Because f is integrable, the right-hand side is a continuous function of x by dominated convergence, and we may thus assume that f has a continuous version g that satisfies (7) for all $x\in (\delta ,1)$. Because g is continuous, it follows from Lebesgue’s differentiation theorem that $\text{d}/\text{d}x{\int }_x^1{y}^{-1-\beta }g(y)\hspace{0.17em}\text{d}y$ exists and is equal to $x^{-\beta -1}g(x)$ for every $x\in (\delta ,1)$. It follows that $T_{\delta }g$ is differentiable and thus, that $g={\lambda }^{-1}{T}_{\delta }g$ is differentiable (even smooth) on $(\delta ,1)$. In fact, we have, for $x\in (\delta ,1)$,

$$\begin{array}{ll}\lambda g\prime (x)=(Tg)\prime (x)\hfill & =\alpha {\beta }^{\beta -1}{\displaystyle {\int }_x^1{y}^{-\beta -1}}g(y)\hspace{0.17em}\text{d}y-\alpha x^{-1}g(x)\hfill \\ \hfill & =\frac{\beta }{x}Tg(x)-\frac{\alpha }{x}g(x)\hfill \\ \hfill & =\frac{\lambda \beta -\alpha }{x}g(x).\hfill \end{array}$$

Furthermore, we have

$$\underset{x\to 1}{\lim }g(x)=\frac{\alpha }{\lambda }\underset{x\to 1}{\lim }{\displaystyle {\int }_x^1{y}^{-1-\beta }}g(y)\hspace{0.17em}\text{d}y=0.$$

We conclude that g is a solution to the final value problem

$$u(1)=1,\hspace{1em}u\prime (x)=c\hspace{0.17em}{x}^{-1}u(x),\hspace{1em}\text{with} c=\beta -\frac{\alpha }{\lambda }$$

on $(\delta ,1]$. The Picard–Lindelöf theorem now yields that g is unique. If $\lambda =\frac{\alpha }{\beta }$, then g vanishes and cannot be an eigenfunction, thus contradicting our initial assumption. If $\lambda \ne \frac{\alpha }{\beta }$, then we have $g(x)=x^{\beta -\frac{\alpha }{\lambda }}-1,x\in (\delta ,1)$, implying that, for all $x\in (\delta ,1)$,

$$\begin{array}{ll}Tg(x)\hfill & =\alpha x^{\beta }{\displaystyle {\int }_x^1{y}^{-1-\frac{\alpha }{\lambda }}}\hspace{0.17em}\text{d}y-\alpha x^{\beta }{\displaystyle {\int }_x^1{y}^{-\beta -1}}\hspace{0.17em}\text{d}y\hfill \\ \hfill & =\lambda x^{\beta -\frac{\alpha }{\lambda }}-\lambda x^{\beta }+\frac{\alpha }{\beta }{x}^{\beta }-\frac{\alpha }{\beta }\hfill \\ \hfill & =\lambda g(x)+\left(\lambda -\lambda x^{\beta }+\frac{\alpha }{\beta }{x}^{\beta }-\frac{\alpha }{\beta }\right).\hfill \end{array}$$

Because g is an eigenfunction for λ, the term in parentheses must vanish (i.e., $\lambda =\frac{\alpha }{\beta }$, which is a contradiction). We conclude that $T_{\delta }$ has only the eigenvalue 0 and is thus, quasinilpotent. □

6.2. Concentration Bounds

We begin by stating a straightforward concentration bound on the maximal degree in G_N, which applies not only to our model but also, to any directed inhomogeneous random graph in which κ and $\varphi$ are bounded.

Lemma 1.

Let G_N denote a random graph in which each arc (m, n) is included independently with probability $p_{mn}^{(N)}.$ Suppose that $p_{mn}^{(N)}\le A/N$ uniformly in m, n for all sufficiently large N and some $A<\infty$; then, the maximal total degree Δ_N in G_N satisfies

$$\mathsf{P}({\mathrm{\Delta }}_N>2A+\lambda )\le N{\text{e}}^{-\frac{{\lambda }^2}{4A+2\lambda /3}}$$(8)

for any N. In particular, it follows that almost surely

$${\mathrm{\Delta }}_N\in O(\mathrm{log\hspace{0.17em}}N).$$

Proof.

Let D_n denote the total degree of $n\in V(G_N)$. By assumption, D_n is dominated by a $\mathrm{Bin}(2N,A/N)$ random variable; hence,

$$\mathsf{P}(D_n\ge 2A+\lambda )\le {\text{e}}^{-\frac{{\lambda }^2}{4A+\frac{2\lambda }{3}}},\hspace{1em}n=1,\dots ,N,$$

using a classical concentration inequality, such as Chung and Lu (2006, theorem 3.2). Summing over n yields (8), and we note that choosing $\lambda =\lambda (N)=C\mathrm{\hspace{0.17em}log\hspace{0.17em}}N$ implies that

$$N{\text{e}}^{-\frac{{\lambda }^2}{4A+2\lambda /3}}<\infty ,$$

if C is sufficiently large, which allows us to conclude the almost sure bound on Δ_N. □

Proof of Proposition 2.

The statement about the maximal degree is an immediate consequence of Lemma 1. Let us now establish the stated bounds on the degree evolutions. The evolution of the indegree $D_n^{\mathsf{\text{in}}}(m)$ of a fixed vertex m after the arrival of vertex k > m can be modeled using a counting process that jumps by one upon the arrival of the jth vertex after k if this vertex attaches to m. Hence, jumps occur with probability

$$p_{k+j}(m)=\frac{w_{k+j}(m)}{k+j-1}\wedge 1,\hspace{1em}j\in {\mathbb{N}}_0,$$(9)

for m and k > m fixed. The indegree of vertex m upon the arrival of vertex n is hence given by a generalized binomial distribution and satisfies

$$\mathsf{E}[D_n^{\mathsf{\text{in}}}(m)]={\displaystyle \sum _{j=m+1}^n{p}_j}(m).$$(10)

In particular, we have

$$\mathsf{E}[D_n^{\mathsf{\text{in}}}(m)]\le \frac{\alpha }{\beta }\left[1-{\left(\frac{m}{n-1}\right)}^{\beta }\right],\hspace{1em}1\le m<n,$$

and

$$\mathsf{E}[D_n^{\mathsf{\text{in}}}(m)]\ge \frac{\alpha }{\beta }\left[{\left(1-\frac{1}{m+1}\right)}^{\beta }-{\left(\frac{m+1}{n}\right)}^{\beta }\right],\hspace{1em}\lceil \alpha \rceil \le m<n.$$

The moment-generating function of $D_n^{\mathsf{\text{in}}}(m)$ is given as

$$\mathsf{E}[{\text{e}}^{\theta D_n^{\mathsf{\text{in}}}(m)}]={\displaystyle \prod _{j=m+1}^n(1+p_j(}m)({\text{e}}^{\theta }-1)),\hspace{1em}\theta >0.$$(11)

A bound on the tail of the indegree distribution can now be derived using Markov’s inequality

$$\mathsf{P}[D_n^{\mathsf{\text{in}}}(m)>x]\le \underset{\theta >0}{\inf }{\text{e}}^{-\theta x}{\displaystyle \prod _{j=m+1}^n(1+p_j(}m)({\text{e}}^{\theta }-1)).$$

We obtain

$$\begin{array}{ll}{\text{e}}^{-\theta x}{\displaystyle \prod _{j=m+1}^n(}1+p_j(m)({\text{e}}^{\theta }-1))\hfill & \le \exp \left(-\theta x+({\text{e}}^{\theta }-1){\displaystyle \sum _{j=m+1}^n{p}_j}(m)\right)\hfill \\ \hfill & \le \exp \left(-\theta x+({\text{e}}^{\theta }-1)\frac{\alpha }{\beta }\right),\hfill \end{array}$$

and the right-hand side is minimized by $\theta =\log \frac{x\beta }{\alpha }$. Thus, for any $n>m\ge 1$, we have the uniform upper tail bound

$$\mathsf{P}[D_n^{\mathsf{\text{in}}}(m)>x]\le \exp \left[-\frac{\alpha }{\beta }-x\left(\mathrm{log\hspace{0.17em}}x+\log \frac{\beta }{\alpha }-\frac{\beta }{\alpha }\right)\right],\hspace{1em}x>\alpha /\beta ,$$

which establishes part (i). Turning to part (ii), we recall that the probability that k attaches itself to $i\in [k-1]$ is given by (9). The expected outdegree is hence given by

$$\mathsf{E}[D^{\mathsf{\text{out}}}(k)]={\displaystyle \sum _{i=1}^{k-1}{p}_k}(i)=\frac{\alpha }{\beta +1}+O(1/k),$$

where the error term is simply because of approximating the sum by an integral. □

Proof of the Error Bound in Theorem 1.

We only provided the detailed calculation for the indegree distribution; a similar but simpler argument yields the same bound for the outdegree distribution. Let us set, for each $n\in \mathbb{N}$,

$$P_n(k)=\frac{1}{n}{\displaystyle \sum _{m=1}^n\mathsf{1}}\{D_n^{\mathsf{\text{in}}}(m)=k\},\hspace{1em}k=0,1,2,\dots ,$$

and denote the target distribution by ${(p(k))}_{k=0}^{\infty }$. We have

$$p(k)={\displaystyle {\int }_0^1{\text{e}}^{-\frac{\alpha }{\beta }(1-s^{\beta })}}{(\frac{\alpha }{\beta }(1-s^{\beta }))}^k\frac{1}{k!}\hspace{0.17em}\text{d}s,\hspace{1em}k=0,1,2,\dots ,$$

and applying the triangle inequality,

$${\displaystyle \sum _{k=0}^{\infty }|}{P}_n(k)-p(k)|\le {\displaystyle \sum _{k=0}^{\infty }|}{P}_n(k)-\mathsf{E}{P}_n(k)|+{\displaystyle \sum _{k=0}^{\infty }|}\mathsf{E}{P}_n(k)-p(k)|,\hspace{1em}n\in \mathbb{N}.$$(12)

Note that the first error is probabilistic and that the second error is essentially just a discretization error because

$$\mathsf{E}{P}_n(k)=\frac{1}{n}{\displaystyle \sum _{m=1}^n{\text{e}}^{-{\sum }_{j=m+1}^n\left(\alpha \frac{m^{\beta }}{{(j-1)}^{\beta +1}}\right)\wedge 1}}\frac{{\left(\sum _{j=m+1}^n\left(\alpha \frac{m^{\beta }}{{(j-1)}^{\beta +1}}\right)\wedge 1\right)}^k}{k!},\hspace{0.17em}k\le n,$$(13)

which can be obtained, for example, by differentiating (11). We calculate the bound for each error in the following two lemmas.

Lemma 2.

We have that

$${\displaystyle \sum _{k=0}^{\infty }|}\mathsf{E}{P}_n(k)-p(k)|=O\left(\frac{\mathrm{log\hspace{0.17em}}n}{n}\right).$$(14)

Proof.

First note that $\left(\alpha m^{\beta }/{(j-1)}^{\beta +1}\right)\wedge 1=1$ only if $m\le j-1\le n_0$, and thus, the error induced in the calculation of the probability weights by ignoring the truncation is $O(n^{-1})$ and may thus be ignored. A straightforward integral approximation yields

$$\alpha m^{\beta }{\displaystyle \sum _{j=m+1}^n{(j-1)}^{-\beta -1}}=\frac{\alpha }{\beta }\left(1-{\left(\frac{m}{n}\right)}^{\beta }\right)+O(m^{-1})$$

for all sufficiently large n. Because $\frac{\text{d}}{\text{d}x}{\text{e}}^{-x}{x}^k=(k-x){\text{e}}^{-x}{x}^{k-1}$, we obtain that, for any $C<\infty$, the function ${\text{e}}^{-x}{x}^k$ is uniformly Lipschitz continuous in x on $[-C/m,\alpha /\beta +C/m]$ with the m-independent Lipschitz constant

$$L_k={\mathcal{\ell }}_{1}k{\mathcal{\ell }}_2^{k-1},\hspace{1em}k\in \mathbb{N},$$

where ${\mathcal{\ell }}_1,{\mathcal{\ell }}_2$ are independent of k. Setting further $L_0=K$ for some sufficiently large K, we conclude that there is a k-independent constant $C<\infty$, such that

$$\begin{array}{ll}|\frac{1}{n}{\displaystyle \sum _{m=1}^n}\hfill & {\text{e}}^{-{\sum }_{j=m+1}^n\alpha \frac{m^{\beta }}{{(j-1)}^{\beta +1}}}{\left({\displaystyle \sum _{j=m+1}^n\alpha }\frac{m^{\beta }}{{(j-1)}^{\beta +1}}\right)}^k\hfill \\ \hfill & -\frac{1}{n}{\displaystyle \sum _{m=1}^n{\text{e}}^{-\frac{\alpha }{\beta }\left(1-{\left(\frac{m}{n}\right)}^{\beta }\right)}}{\left(\frac{\alpha }{\beta }\left(1-{\left(\frac{m}{n}\right)}^{\beta }\right)\right)}^k|\le \frac{C{L}_k}{n}{\displaystyle \sum _{m=1}^n\frac{1}{m}}.\hfill \end{array}$$

To approximate the discrete outer sum by an integral, we use that if $f:[a,b]\to \mathbb{R}$ is continuously differentiable, then

$$\left|\frac{1}{n}{\displaystyle \sum _{i=1}^{n}f}\left(\frac{i(b-a)}{n}\right)-{\displaystyle {\int }_a^{b}f}\left(s\right)\hspace{0.17em}\text{d}s\right|\le \frac{b-a}{2n}\underset{x\in [a,b]}{\sup }f\prime \left(x\right),$$

and hence, the constants $L_k,k\ge 0$ can be used to bound this approximation error as well; we end up with

$$\begin{array}{ll}|\frac{1}{n}{\displaystyle \sum _{m=1}^n}\hfill & {\text{e}}^{-{\sum }_{j=m+1}^n\alpha \frac{m^{\beta }}{{(j-1)}^{\beta +1}}}{\left({\displaystyle \sum _{j=m+1}^n\alpha }\frac{m^{\beta }}{{(j-1)}^{\beta +1}}\right)}^k\hfill \\ \hfill & -{\displaystyle {\int }_0^1{\text{e}}^{-\frac{\alpha }{\beta }\left(1-s^{\beta }\right)}}{\left(\frac{\alpha }{\beta }\left(1-s^{\beta }\right)\right)}^k\hspace{0.17em}\text{d}s|\le \frac{C_1{L}_k}{n}{\displaystyle \sum _{m=1}^n\frac{1}{m}}+\frac{C_2}{n},\hfill \end{array}$$

where C₁, C₂ are finite constants and independent of n, m, and k. Noting further that ${\sum }_{k=0}^{\infty }\frac{L_k}{k!}<\infty$, we arrive at (14) because

$${\displaystyle \sum _{k=1}^n|}\mathsf{E}{P}_n(k)-p(k)|+{\displaystyle \sum _{k=n}^{\infty }{p}_k}\le \frac{(C_1+C_2)}{n}{\displaystyle \sum _{m=1}^n\frac{1}{m}}{\displaystyle \sum _{k=1}^n\frac{L_k}{k!}}+{\displaystyle \sum _{k=n}^{\infty }{p}_k}=O(\mathrm{log\hspace{0.17em}}n/n)$$

because ${\sum }_{k=n}^{\infty }{p}_k$ decays exponentially in n. □

Lemma 3.

We have that almost surely

$${\displaystyle \sum _{k=0}^{\infty }|}{P}_n(k)-\mathsf{E}{P}_n(k)|=O\left(\frac{{\left(\mathrm{log\hspace{0.17em}}n\right)}^{3/2}}{\sqrt{n}}\right).$$

Proof.

Fix k, and write $X_i=\mathsf{1}\{D_n(i)=k\},i=1,\dots ,n$. Note that the $X_i,i=1,\dots ,n$ are independent, and thus, another invocation of Chernoff’s inequality (see, e.g., Chung and Lu 2006, theorem 3.2) yields that

$$\mathsf{P}\left(\left|{\displaystyle \sum _{i=1}^n{X}_i}-\mathsf{E}{X}_i\right|>n\lambda \right)\le 2\mathrm{\hspace{0.17em}exp}\left(-\frac{{\left(\lambda n\right)}^2}{2(\sum _{i=1}^n\mathsf{E}{X}_i+\frac{\lambda n}{3})}\right)=2\mathrm{\hspace{0.17em}exp}\left(-\frac{{\lambda }^{2}n}{2\left(\mathsf{E}{P}_n\right(k)+\frac{\lambda }{3})}\right),$$(15)

with $\lambda >0$. Let E_n denote the event in which there is no vertex $i\in [n]$ with $D_n\left(i\right)\ge C\mathrm{\hspace{0.17em}log\hspace{0.17em}}n$; then, for any $\lambda \prime >0$,

$$\begin{array}{ll}\mathsf{P}({\displaystyle \sum _{k=0}^{\infty }|}{P}_n\left(k\right)-\mathsf{E}{P}_n\left(k\right)|\ge \lambda \prime )\hfill & \le \mathsf{P}\left(\right\{{\displaystyle \sum _{k=0}^{\infty }|}{P}_n\left(k\right)-\mathsf{E}{P}_n\left(k\right)|\ge \lambda \prime \}\cap E_n)+\mathsf{P}\left(E_n^{\mathsf{c}}\right)\hfill \\ \hfill & \le \mathsf{P}({\displaystyle \sum _{k=0}^{C\mathrm{\hspace{0.17em}log\hspace{0.17em}}n}|}{P}_n\left(k\right)-\mathsf{E}{P}_n\left(k\right)|+{\displaystyle \sum _{k=C\mathrm{\hspace{0.17em}log\hspace{0.17em}}n}^{\infty }\mathsf{E}}{P}_n\left(k\right)\ge \lambda \prime )+\mathsf{P}\left(E_n^{\mathsf{c}}\right).\hfill \end{array}$$

Arguing as in the proof of Lemma 1, we may choose C so large that ${\sum }_{n=1}^{\infty }\mathsf{P}\left(E_n^{\mathsf{c}}\right)=B<\infty$ and such that

$${\displaystyle \sum _{k=C\log n}^{\infty }\mathsf{E}}{P}_n\left(k\right)\le \frac{1}{n}\mathsf{E}\#\{i\in [n]:D_n\left(i\right)\ge C\mathrm{\hspace{0.17em}log\hspace{0.17em}}n\}\le \frac{1}{n}$$

for all sufficiently large n. Observe further that

$${\displaystyle \sum _{k=0}^{C\log n}|}{P}_n(k)-\mathsf{E}{P}_n(k)|\ge \lambda \prime -1/n$$

is only possible if at least one of the terms $|P_n(k)-\mathsf{E}{P}_n(k)|$ exceeds $(\lambda \prime -1/n)/(C\log n)$, and we conclude that

$$\mathsf{P}({\displaystyle \sum _{k=0}^{\infty }|}{P}_n(k)-\mathsf{E}{P}_n(k)|\ge \lambda \prime )\le \mathsf{P}(E_n^{\mathsf{c}})+{\displaystyle \sum _{k=0}^{C\log n}\mathsf{P}}(|P_n(k)-\mathsf{E}{P}_n(k)|\ge \frac{\lambda \prime -1/n}{C\hspace{0.17em}\log \hspace{0.17em}n}).$$

Choosing now $\lambda =\lambda (N)=D\sqrt{\mathrm{log\hspace{0.17em}}n/n}$ for some sufficiently large D and setting $\lambda \prime =\lambda \prime (n)=\lambda C\mathrm{\hspace{0.17em}log\hspace{0.17em}}n+1/n$ allow us to apply (15) to obtain

$${\displaystyle \sum _{n=1}^{\infty }\mathsf{P}}\left({\displaystyle \sum _{k=0}^{\infty }|}{P}_n(k)-\mathsf{E}{P}_n(k)|\ge R\frac{{(\mathrm{log\hspace{0.17em}}n)}^{3/2}}{\sqrt{n}}\right)\le B+C{\displaystyle \sum _{n=1}^{\infty }{\text{e}}^{-{\lambda }^{2}n/(2+2\lambda /3)}}\mathrm{log\hspace{0.17em}}n<\infty$$

for some $R<\infty$, which implies that almost surely

$${\displaystyle \sum _{k=0}^{\infty }|}{P}_n(k)-\mathsf{E}{P}_n(k)|=O\left(\frac{\mathrm{log\hspace{0.17em}}{n}^{3/2}}{\sqrt{n}}\right).$$

 □

Combining the previous lemmas concludes the proof of Theorem 1.

6.3. Forward Component Size and Weight Evolution—Proof of Theorem 2

Let $A\subset [n]$; then,

and the weight of A upon arrival of vertex n + 1 essentially determines how likely it is that n + 1 connects to a vertex in A. Setand that is, ${\mathrm{\Gamma }}_n(m)$ counts how often m has been referenced (directly and indirectly). We have ${\mathrm{\Gamma }}_m(m)=0$ and

Hence, transitions of the processes $\mathrm{\Gamma }(m)={({\mathrm{\Gamma }}_n(m))}_{n\ge m}$ depend on the weight structure of the forward component of m, not only on its present size. In particular, each $\mathrm{\Gamma }(m)$ is a Markov process with respect to the filtration generated by the graph sequence ${(G_n)}_{n\ge m}$ but not with respect to the smaller filtration generated by the sequence ${({\mathrm{\Gamma }}_n(m))}_{n\ge m}$ itself. It is, therefore, more convenient to study the weight processes $W_n(m)=w_n(C_n(m)),n\ge m$, which have the dynamics

To eliminate the slightly unwieldy products structure of the transition probability, we formulate a stochastic domination result. We use the notation

for the increments of a random or deterministic sequence ${(a_n)}_{n\ge n_1}$ and further write $\{W_{n+1}\hspace{0.17em}\uparrow \}$ for the event that α is added to the score process in step n + 1. The complementary event is denoted by $\{W_{n+1}\hspace{0.17em}\downarrow \}$, and we extend this notation to all other processes $X=(X_n)$ for which $\mathrm{\Delta }{X}_n$ can attain precisely two values.

Lemma 4.

Let $Y_n(m)=Y_n(m;a,b,y)$ denote the Markov chain given by $Y_m(m)=y$ and

$$\mathrm{\Delta }{Y}_n(m)=\{\begin{array}{ll}-\frac{b+1}{n+1}{Y}_n(m)+\frac{a}{n+1},\hspace{0.17em}\hfill & \mathit{\text{with}} \mathit{\text{probability}} \left(1-{\text{e}}^{-Y_n(m)}\right),\hfill \\ -\frac{b+1}{n+1}{Y}_n(m),\hspace{0.17em}\hfill & \mathit{\text{with}} \mathit{\text{probability\hspace{0.17em}}}{\text{e}}^{-Y_n(m)},\hfill \end{array}\hspace{1em}n\ge m.$$

Then, ${(W_n(m)/n)}_{n\ge m}$ stochastically dominates ${(Y_n(m;\alpha ,\beta ,W_m(m)/m))}_{n\ge m}$.

Proof.

We start by analyzing the transition probabilities of $W_n=W_n(m):$

$$1-{\displaystyle \prod _{k\in C_n(m)}\left(1-\frac{w_n(k)}{n}\right)}=1-{\text{e}}^{{\sum }_{k\in C_n(m)}\log (1-w_n(k)/n)}$$

$$=1-\exp \left(-{\displaystyle \sum _{k\in C_n(m)}{\displaystyle \sum _{j=1}^{\infty }\frac{{\left(\frac{w_n(k)}{n}\right)}^j}{j}}}\right).$$

Noting that $w_n(k)/n$ is uniformly bounded by $\frac{\alpha }{n}$, we can estimate

$$\begin{array}{ll}1-{\text{e}}^{-{\sum }_{k\in C_n(m)}\frac{w_n(k)}{n}}\hfill & \le 1-\exp \left(-{\displaystyle \sum _{k\in C_n(m)}{\displaystyle \sum _{j=1}^{\infty }\frac{{\left(\frac{w_n(k)}{n}\right)}^j}{j}}}\right)\hfill \\ \hfill & \le 1-\exp \left(-{\displaystyle \sum _{k\in C_n(m)}\left(\frac{w_n(k)}{n}+(1+\epsilon )\frac{w_n{(k)}^2}{2n^2}\right)}\right),\hfill \end{array}$$(16)

for any $\epsilon >0$, if n is sufficiently large. Another Taylor expansion yields

$$1-\frac{\beta +1}{n+1}\le {\left(\frac{n}{n+1}\right)}^{\beta +1}\le 1-\frac{\beta +1}{n+1}+\frac{\beta (\beta +1)}{2{(n+1)}^2},\hspace{1em}n\ge m.$$(17)

We conclude that

$$\begin{array}{l}\mathrm{\Delta }\frac{W_n}{n}=\left(1-{\left(\frac{n}{n+1}\right)}^{\beta +1}\right)\frac{W_n}{n}+\frac{\alpha }{n+1}\mathsf{1}\{n+1 \text{connects} \text{to} C_n(m)\}\\ \ge -\frac{\beta +1}{n+1}\frac{W_n}{n}+\frac{\alpha }{n+1}\mathsf{1}\{n+1 \text{connects} \text{to} C_n(m)\},\end{array}$$

and because of the lower bound in (16), the event in the indicator occurs with probability at least

$$1-{\text{e}}^{-{\sum }_{k\in C_n(m)}\frac{w_n(k)}{n}}=1-{\text{e}}^{-W_n/n},$$

given $C_n(m)$, which proves the lemma. □

To obtain a stochastic upper bound is only slightly more tricky.

Lemma 5.

Let $Y_n(m;a,b,y)$ be defined as in Lemma 4, and let $a>\alpha ,b<\beta$. There exits n₁ such that for all $n\ge n_1$, we can couple $Y_n=Y_n(n_1;a,b,w)$ and $W_n=W_n(m)$ conditionally on $\frac{a}{\alpha n_1}{W}_{n_1}=w$ such that

$$Y_n\ge \frac{a}{\alpha n}{W}_n,\hspace{1em} \mathit{\text{for}} \mathit{\text{all}} n\ge n_1.$$

Proof.

We argue by induction. The claim holds by construction at any given initial time $n_1\ge m.$ Now, assume that the coupling has been established for times $n_1,\dots ,n$. Then,

$$Y_{n+1}=\left(1-\frac{b+1}{n+1}\right)Y_n+\frac{a}{n+1}\mathsf{1}\{Y_{n+1}\hspace{0.17em}\uparrow \}\ge \left(1-\frac{b+1}{n+1}\right)\frac{a}{\alpha }\frac{W_n}{n}+\frac{a}{\alpha }\frac{\alpha }{n+1}\mathsf{1}\{Y_{n+1}\hspace{0.17em}\uparrow \},$$

where we have used the definition of Y_n and the induction hypothesis. Now, note that

$$\mathsf{P}(Y_{n+1}\hspace{0.17em}\uparrow |W_n,Y_n)=1-{\text{e}}^{-Y_n}\ge 1-{\text{e}}^{-\frac{a}{\alpha n}{W}_n}\ge \mathsf{P}(W_{n+1}\hspace{0.17em}\uparrow |W_n,Y_n)$$

by the induction hypothesis and the upper bound in (16) if $n\ge n_1$ is sufficiently large. We conclude that $W_{n+1}$ and $Y_{n+1}$ can be coupled such that $\{W_{n+1}\hspace{0.17em}\uparrow \}\subset \{Y_{n+1}\hspace{0.17em}\uparrow \}$, and it follows that under this coupling,

$$\begin{array}{ll}{Y}_{n+1}\hfill & \ge \frac{a}{\alpha }\left[\left(1-\frac{b+1}{n+1}\right)\frac{W_n}{n}+\frac{\alpha }{n+1}\mathsf{1}\{Y_{n+1}\hspace{0.17em}\uparrow \}\right]\hfill \\ \hfill & \ge \frac{a}{\alpha }\left[{\left(\frac{n}{n+1}\right)}^{\beta +1}\frac{W_n}{n}+\frac{\alpha }{n+1}\mathsf{1}\{W_{n+1}\hspace{0.17em}\uparrow \}\right]\hfill \\ \hfill & =\frac{a}{\alpha }\frac{W_{n+1}}{n+1}\hfill \end{array},$$

where we have used (17) and once more that n₁ can be taken large. □

Lemmas 4 and 5 indicate that the dynamics of ${(C_n(m))}_{n\ge m}$ can be analyzed in the terms of the simple processes ${(Y_n(m))}_{n\ge m}$ defined in Lemma 4. To this end, fix $a,b>0$ and Y_m = y, and define for $n\ge m$,

and

It follows from a straightforward calculation or alternatively, by invoking Brightwell and Luczak (2012, lemmas 2.1 and 2.2) that ${(M_n)}_{n\ge m}$ is a martingale and that ${(Z_n)}_{n\ge m}$ is a supermartingale adapted to the filtration ${({\mathcal{F}}_n)}_{n\ge m}$ defined by ${\mathcal{F}}_n=\sigma (Y_j,m\le j\le n)$.

Lemma 6.

If $0<a<b+1$, then ${\lim }_{n\to \infty }{Y}_n=0$ almost surely.

Proof.

Because ${(Z_n)}_{n\ge m}$ is a nonnegative supermartingale, ${(Z_n)}_{n\ge m}$ converges almost surely to some random variable $Z_{\infty }$ satisfying $\mathsf{E}{Z}_{\infty }\le \mathsf{E}{Z}_m=1.$ Because $a<b+1$, it thus follows from

$$\begin{array}{llll}\hfill & \exp \left\{{\displaystyle \sum _{j=m}^{n-1}\left[\frac{b+1}{j+1}-\frac{\alpha }{j+1}\frac{1-{\text{e}}^{-Y_j}}{Y_j}\right]}\right\}\hfill & \hfill & \ge \exp \left\{{\displaystyle \sum _{j=m}^{n-1}\left[\frac{b+1}{j+1}-\frac{a}{j+1}\right]}\right\}=n^{1+b-a+o(1)}\hfill \end{array}$$

that $Z_{\infty }$ can only be finite if ${(Y_n)}_{n\ge m}$ converges to zero. Hence, ${\lim }_{n\to \infty }{Y}_n=0$ almost surely. □

Let us now focus on the case $a>b+1$. Performing a Taylor expansion, we see that

where $\xi (y)$ is some value between $y_{\ast }$ and y and $y_{\ast }=y_{\ast }(a,b)$ is the unique positive solution to

Using the Martingale ${(M_n)}_{n\ge m}$, we can represent Y_n as

In view of (18) and (19), the recursion (20) is a stochastic approximation of the stable point $y_{\ast }.$ We recall the following well-known result about stochastic approximations.

Lemma 7

(Special Case of Pemantle 2007, lemma 2.6). Suppose that ${(X_n)}_{n\in \mathbb{N}}$ is a stochastic process adapted to a filtration ${({\mathcal{G}}_n)}_{n\in \mathbb{N}}$ satisfying the recurrence relation

$$\mathrm{\Delta }{X}_n=c_n(f(X_n)+{\xi }_{n+1}),$$

where ${(c_n)}_{n\in \mathbb{N}}$ is a deterministic sequence, ${({\xi }_n)}_{n\in \mathbb{N}}$ is a ${({\mathcal{G}}_n)}_{n\in \mathbb{N}}$-adapted process, and f is a bounded function satisfying

• ${\sum }_{n\in \mathbb{N}}{c}_n=\infty ,\hspace{0.17em}{\sum }_{n\in \mathbb{N}}{c}_n^2<\infty$;

• $\mathsf{E}[{\xi }_{n+1}|{\mathcal{G}}_n]=0,\hspace{0.17em}\mathsf{E}[{\xi }_{n+1}^2|{\mathcal{G}}_n]\le B<\infty$ for all $n\in \mathbb{N}$; and

• either $f((l_0,r_0))\subset (-\infty ,-\delta )$ or $f((l_0,r_0))\subset (\delta ,\infty )$ for some $\delta >0$ and some open interval (l₀, r₀).

Then, we have for any interval $[l,r]\subset (l_0,r_0)$ that

$$\mathsf{P}(X_n \mathit{\text{visits}} [l,r] \mathit{\text{only}} \mathit{\text{finitely}} \mathit{\text{many}} \mathit{\text{times}})=1.$$

We now have all of the ingredients to complete the proof of Theorem 2.

Proof of Theorem 2.

Let ${\mathrm{\Gamma }}_n=|C_n(m)|,\hspace{0.17em}n\ge m$ and $W_n=w_n(C_n(m))$. We estimate

$$\frac{\alpha }{n^{\beta }}{\displaystyle \sum _{k=m}^{m+{\mathrm{\Gamma }}_n-1}{k}^{\beta }}\le W_n\le \frac{\alpha }{n^{\beta }}{\displaystyle \sum _{k=n-{\mathrm{\Gamma }}_n}^n{k}^{\beta }},\hspace{1em}n\ge m.$$

Approximating the sums by integrals yields

$$\frac{\alpha }{\beta +1}n{\left(\frac{{\mathrm{\Gamma }}_n}{n}\right)}^{\beta +1}+O(n^{-\beta })\le W_n\le \frac{\alpha }{\beta +1}n\left(1-{\left(1-\frac{{\mathrm{\Gamma }}_n}{n}\right)}^{\beta +1}\right)+O(n^{-\beta }),\hspace{1em}n\ge m,$$

from which we conclude that ${\lim }_{n\to \infty }\frac{{\mathrm{\Gamma }}_n}{n}=Z$ exists if and only if ${\lim }_{n\to \infty }\frac{W_n}{n}=w_{\infty }$ exists. □

6.3.1. The Subcritical Case $\alpha <\beta \hspace{0.17em}+1$.

By Lemma 5, $W_n/n$ is eventually dominated by $Y_n(n_1,\alpha \prime ,\beta \prime ,y)$ for some y if $\alpha <\alpha \prime <\beta \prime +1<\beta +1$. Because ${\lim }_{n\to \infty }{Y}_n=0$ almost surely by Lemma 6, we conclude that

6.3.2. The Supercritical Case $\alpha \hspace{0.17em}>\hspace{0.17em}\beta \hspace{0.17em}+\hspace{0.17em}1$.

We first employ Lemma 4 to dominate $w_{\infty }$ from below by the random limit

which we show to exist now. Rewriting (20), we obtain

We wish to apply Lemma 7 with $c_n={(n+1)}^{-1},{\xi }_{n+1}=(n+1)\mathrm{\Delta }{M}_n$, and

Let us first check that the condition on ξ_n is satisfied. Clearly, $\mathsf{E}[{\xi }_{n+1}|Y_n]=0$ because $\mathrm{\Delta }{M}_n$ is a martingale difference. To see that $\mathsf{E}[{\xi }_{n+1}^2|Y_n]$ is bounded, we simply note that

for some constant C by definition of Y_n and the fact that Y_n is bounded; hence, ξ_n is bounded. Let us now analyze the recursion function f. Note that the truncation of f is necessary because of the assumption of boundedness in Lemma 7, but this is not a problem because clearly, $Y_n>0$ for all n, $Y_n\le W_n/n$ because of the coupling, and $W_n/n$ is easily seen to be bounded by some deterministic value $K>\frac{\alpha }{\beta +1}$ (mind that $W_n/n\le \frac{\alpha }{\beta +1}+o(1)$). Note that f is continuous on $[0,K]$ with f(x) = 0 for $x\in [0,K]$ if and only if $x\in \{0,y_{\ast }\}$, where $y_{\ast }=y_{\ast }(\alpha ,\beta )$ is given in (19). Note further that f(x) > 0 if $x\in (0,y_{\ast })$ and f(x) < 0 if $x\in (y_{\ast },K)$. Continuity of f now implies that for any sufficiently small ${\epsilon }_0>0$, there exists a ${\delta }_0>0$ such thatwhere we note that $y_{\ast }<\alpha /(\beta +1)$ for any choice of $\alpha >\beta +1$. By Lemma 7, we deduce that any closed bounded interval not including either zero or $y_{\ast }$ is visited only finitely often, and hence, ${(Y_n)}_{n\ge m}$ converges almost surely to a random variable $Y_{\infty }$ with distribution

We say ${(Y_n)}_{n\ge m}$ survives if $Y_{\infty }=y_{\ast }$ and that it dies out if $Y_{\infty }=0$. We are going to show now that p > 0 (i.e., ${(Y_n)}_{n\ge m}$ survives with positive probability). Observe that we have

Note that if ${(Y_n)}_{n\ge m} \text{dies} \text{out}$ almost surely, then we have that ${\lim }_{k\to \infty }{\sup }_{n\ge k}\mathsf{E}[Y_n|{\mathcal{F}}_k]=0$ almost surely. Because $\mathsf{E}[1-{\text{e}}^{-Y_n}|{\mathcal{F}}_k]=\mathsf{E}[Y_n|{\mathcal{F}}_k]+O(\mathsf{E}{[Y_n|{\mathcal{F}}_k]}^2)$ as $\mathsf{E}[Y_n|{\mathcal{F}}_k]$ vanishes, it follows that for every $\epsilon \in (0,\alpha -\beta -1)$, there exists some K₀ such that

Denoting $\zeta =\alpha -\beta -1-\epsilon >0$ and setting $Y_k≕a(k)>0$, it follows that ${(\mathsf{E}[Y_n|{\mathcal{F}}_k])}_{n\ge k}$ dominates the unique solution of the difference equation

which satisfies ${\lim }_{n\to \infty }{a}_n=\infty$ for any initial condition a(k) > 0. This is a contradiction to ${\lim }_{k\to \infty }{\sup }_{n\ge k}\mathsf{E}[Y_n|{\mathcal{F}}_k]=0$, and we conclude that

Combining Lemmas 4 and 5, we obtain that

for all sufficiently small ε, and because the root $y_{\ast }(a,b)$ of (19) depends continuously on a and b, we conclude that $w_{\infty }={\lim }_{n\to \infty }{W}_n/n=y_{\ast }(\alpha ,\beta )>0$ almost surely on the event of survival. It follows that, almost surely on survival, ${\lim }_{n\to \infty }{\mathrm{\Gamma }}_n/n≕\gamma >0$. Let q_n denote the probability that a uniformly chosen vertex in G_n is contained in $C_n(m)$; then, ${\lim }_{n\to \infty }{q}_n=\gamma \mathsf{P}({\lim }_{n\to \infty }{\mathrm{\Gamma }}_n/n>0)$, and for any $m\ge n$,

Note that $\mathsf{E}[\mathsf{1}\{k+1\in C_{k+1}(m)\}|G_k]=1-{\text{e}}^{-W_k/k}$ and that for any $\epsilon \in (0,1)$,

if n is sufficiently large. We infer that $\gamma =(1+\beta ){\alpha }^{-1}{y}_{\ast }(\alpha ,\beta )$, and this concludes the proof of the critical case by establishing a one-to-one relation between $Y_{\infty }$ and the random variable $Z=Z(m)$ as defined in the theorem.

6.3.3. The Critical Case $\alpha =\beta +1$.

From the supercritical case, we infer that almost surely γ = 0 in this case because γ is a monotone function of α and ${\lim }_{\alpha \downarrow \beta +1}{y}_{\ast }(\alpha ,\beta )=0$.

Remark 3.

1. The original version of lemma 7 in Pemantle (2007) also allows us to include an error term R_n in the recursion as long as ${\sum }_n{c}_n{R}_n<\infty$. In principle, one can apply this version of the stochastic approximation result directly to $W_n/n$. We have chosen to include the intermediate step via Y_n because it breaks up the error estimates into several parts and makes the argument easier to follow because ${(Y_n)}_{n\ge m}$ has a rather simple form.

2. Note that the subcritical result also follows from the supercritical/critical case by monotonicity, but we gave a standalone argument because the supercritical case is more involved than the direct proof. Unfortunately, this simple argument does not carry over to the critical case.