# Depth-First Search performance in random digraphs

Philippe Jacquet, Svante Janson

► To cite this version:

Philippe Jacquet, Svante Janson. Depth-First Search performance in random digraphs. AofA 2024 - 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2024, Bath (UK), United Kingdom. 10.4230/LIPIcs.AofA.2024 . hal-04888842

HAL Id: hal-04888842

https://hal.science/hal-04888842v1

Submitted on 15 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Depth-First Search performance in random digraphs

Philippe Jacquet

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

Inria Saclay Ile de France, [1 Rue Honoré d'Estienne d'Orves, 91120 Palaiseau], France

Svante Janson

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

Department of Mathematics, Uppsala University, [PO Box 480, SE-751 06 Uppsala], Sweden

## Abstract

We present an analysis of the depth-first search algorithm in a random digraph model with independent outdegrees having an arbitrary distribution with finite variance. The results include asymptotics for the distribution of the stack index and depths of the search. The search yields a series of trees of finite size before and after the exploration of a giant tree. Our analysis mainly concerns the giant tree. Most results are first order. This analysis proposed by Donald Knuth in his next to appear volume of *The Art of Computer Programming* gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan.

2012 ACM Subject Classification Mathematics of computing → Trees

Keywords and phrases Depth First Search, random digraph, Analysis of Algorithms

Digital Object Identifier 10.4230/LIPIcs...8

Funding Svante Janson: Supported by the Knut and Alice Wallenberg Foundation and the Swedish Research Council (VR)

## 1 Introduction

This paper is a continuation of our earlier paper [1], which studies a special case using a simpler method. The motivation of both papers is a new section in Donald Knuth's *The Art of Computer Programming* [3], which is dedicated to Depth-First Search (DFS) in a digraph. The DFS is an important computing tool dedicated to the exploration of large unstructured dataset, mostly organised as large directed graphs, and the DFS is the foundation of the daily crawling process of the graph of the Web performed by Google [2]. Briefly, the DFS starts with an arbitrary vertex, and explores the arcs from that vertex one by one. When an arc is found leading to a vertex that has not been seen before, the DFS explores the arcs from it in the same way, in a recursive fashion, before returning to the next arc from its parent. This eventually yields a tree containing all descendants of the first vertex (which is the root of the tree). If there still are some unseen vertices, the DFS starts again with one of them and finds a new tree, and so on until all vertices are found. We refer to [3] for details as well as for historical notes. (See also S1-S2 in Section 2.) Note that the digraphs in [3] and here are multi-digraphs, where loops and multiple arcs are allowed. (Although in our random model they are few and usually not important.) The DFS algorithm generates a spanning forest (the *depth-first forest*) in the digraph, with all arcs in the forest directed away from the roots. Our main purpose is to study the properties of the depth-first forest, starting with a random digraph *G*; in particular we study the distribution of the stack index and the depth of vertices in the depth-first forest.

The random digraph model that we consider has *n* vertices and a given outdegree distribution *P*. The outdegrees (number of outgoing arcs) of the *n* vertices are independent random numbers with this distribution. The endpoint of each arc is uniformly selected at random among the *n* vertices, independently of all other arcs. (Therefore, an arc can loop

<figure><img src="image_8.png" /></figure>

© Philippe Jacquet and Svante Janson;
licensed under Creative Commons License CC-BY 4.0

Leibniz International Proceedings in Informatics

LIPICS Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 8:2 Depth-First Search performance in random digraphs

back to the starting vertex, and multiple arcs can occur.) We consider asymptotics as $n \to \infty$ for a fixed outdegree distribution. In [1], we studied the case when the outdegree distribution is geometric. In the present paper, we generalise this and let $\mathbf{P}$ be an arbitrary distribution; however, we assume throughout the paper that the outdegree distribution $\mathbf{P}$ has a finite second moment.

**Remark 1.** Related results are proved by (author?) [5] for DFS in an undirected Erdős–Rényi graph $G(n, \lambda/n)$; the case when $\lambda = 1 + \varepsilon$ for small $\varepsilon > 0$ is studied further by another argument by (author?) [8]. DFS in the random digraph $D(n, p)$ has also been considered previously, for example in the proof of [4, Theorem 3]. Although this is for a different random graph model, DFS on $G(n, \lambda/n)$ is the same as DFS on the Erdős–Rényi digraph $D(n, \lambda/n)$, which is essentially the same as the digraph studied in the present paper with outdegree distribution $\text{Po}(\lambda)$. Hence, the main result of [5], which shows convergence of the depth profile in the depth-first forest to a certain deterministic limit, is essentially the special case $\mathbf{P} = \text{Po}(\lambda)$ of our result for the depths (Theorem 6). The proofs are quite different. See also (author?) [6], where related results are given for the (undirected) configuration model.

We analyze the process $d(t)$ of depths of the vertices, in the order they are found by the DFS. For the geometric outdegree distribution studied in [1], $d(t)$ is a Markov chain, which was used in our proofs. For general outdegree distributions, this is no longer true. We show in Section 2 that we can use the size $I(t)$ of the stack of arcs kept by the DFS as a substitute; this is a Markov chain, and we obtain limit results for the stack size with deviation in $O_L^2(n^{1/2})$. (See Section 1.1 below for notation.) In a second step (Section 3), this is used to derive limit results for the depths $d(t)$, but the results obtained are within deviation in $o_p(n)$ which is close to the order of the result. We give also an alternative approach in Section 4 where the depths $d(t)$ are analysed directly by a different method; the results there are preliminary and less complete, but it seems that this method yields sharper results than the method in Section 3, with deviation within $O_p(n^\beta)$ with $\beta$ arbitrary close to 4/5; thus the worst case error is now negligible compared to the main order.

Many details and further results will be given in the forthcoming full paper.

### 1.1 Some notation

We denote the given outdegree distribution by $\mathbf{P}$. We let $\eta$ denote random variables with this distribution. In particular, we denote the outdegree of vertex $v$ by $\eta(v)$. Recall that our standing assumption is that these outdegrees are i.i.d. (independent and identically distributed) with $\eta(v) \sim \mathbf{P}$. We let $v_t$ denote the $t$-th vertex found by the DFS, and simplify notation by letting $\eta_t := \eta(v_t)$ be its outdegree. It follows from the construction of the DFS that also the random variables $\eta_t$, $t = 1, \dots, n$ are i.i.d. with distribution $\mathbf{P}$; this fundamental property will be used repeatedly without further mention.

We assume throughout that the second moment $\mathbb{E}\eta^2 < \infty$. This is essential for some results (e.g. results on asymptotic normality), but we conjecture that many results hold assuming only that the first moment $\mathbb{E}\eta < \infty$.

The mean outdegree, i.e., the expectation $\mathbb{E}\eta$ of $\mathbf{P}$, is denoted by $\lambda$. In analogy with branching processes, we say that the random digraph is *subcritical* if $\lambda < 1$, *critical* if $\lambda = 1$, and *supercritical* if $\lambda > 1$.

Let $d(v)$ be the depth of vertex $v$, and let $d(t) := d(v_t)$.

As usual, w.h.p. means *with high probability*, i.e., with probability $1 - o(1)$ as $n \to \infty$.

For random variables $X_n$ and positive numbers $a_n$, we write $X_n = o_p(a_n)$ if, as $n \to \infty$, $X_n/a_n \xrightarrow{p} 0$, i.e., if for every $\varepsilon > 0$, we have $\mathbb{P}(|X_n| > \varepsilon a_n) \to 0$. Furthermore, $X_n = O_p(a_n)$
means that the family {$X_n/a_n$} is bounded in probability, i.e., if for every $\varepsilon > 0$ there exists $C$ such that $\mathbb{P}(|X_n| > C a_n) < \varepsilon$ for all $n$. $X_n = o_{L^2}(a_n)$ means $\mathbb{E}[|X_n/a_n|^2] \to 0$, and $X_n = O_{L^2}(a_n)$ means $\mathbb{E}[|X_n/a_n|^2] = O(1)$.

Ge($p$) denotes the geometric distribution with parameter $p \in (0, 1]$; thus $\xi \sim \text{Ge}(p)$ means that $\xi$ is a random variable with

$$ \mathbb{P}(\xi = k) = (1-p)^k p, \quad k = 0, 1, 2, \dots \qquad (1.1) $$

We write $x^+ := \max(x, 0)$.

## 2 Stack index analysis

As said above, unlike the special case $\mathbf{P} = \text{Ge}(1-p)$ studied in [1], in general the depth $d(t)$ does not follow a Markov chain. Therefore, we instead first consider the stack index $I(t)$ defined below, which does evolve as a Markov chain; many arguments for $I(t)$ below are similar to arguments for $d(t)$ in [1, Section 2].

The DFS can be regarded as keeping a stack of unexplored arcs, for which we have seen the start vertex but not the endpoint. The stack evolves as follows:

1. If the stack is empty, pick a new vertex $v$ that has not been seen before (if there is no such vertex, we have finished). Otherwise, pop the last arc from the stack, and reveal its endpoint $v$ (which is uniformly random over all vertices). If $v$ already is seen, repeat.

2. ($v$ is now a new vertex) Reveal the outdegree $\eta(v)$ of $v$ and add to the stack $\eta(v)$ new arcs from $v$, with unspecified endpoints. GOTO S1.

Let $I(t)$ be the size of the stack when $v_t$ is found (but before we add the arcs from $v_t$). After $v_t$ is found, and the $\eta_t$ arcs from $v_t$ have been added to the stack, the stack size is thus $I(t) + \eta_t$. We next perform step S1 one or several times. As long as the stack is not empty, we find each time an already seen vertex with probability $t/n$, and in this case we repeat S1. Hence, conditioned on $I(t)$ and $\eta_t$, for $k \ge 1$, the probability that S1 is performed exactly $k$ times is

$$ \left(\frac{t}{n}\right)^{k-1}\left(1-\frac{t}{n}\right), \qquad (2.1) $$

provided $1 \le k \le I(t) + \eta_t$, and if none of these events occur, then S1 is repeated a last time and a new vertex is picked that will be the root of a new tree in the depth-first forest (unless we have finished the DFS). Note that (2.1) equals the probability $\mathbb{P}(\xi = k)$ with $\xi_t \sim \text{Ge}(1 - t/n)$, see (1.1). Thus, we can write

$$ I(t+1) = (I(t) + \eta_t - 1 - \xi_t)^+, \quad 1 \le t < n, \qquad (2.2) $$

where $\xi_t \sim \text{Ge}(1 - t/n)$ is a random variable independent of the history; more precisely, the random variables $\eta_t$ ($1 \le t \le n$) and $\xi_t$ ($1 \le t < n$) are all independent. We start the stochastic recursion (2.2) with $I(1) = 0$.

We define

$$ \zeta_t := \eta_t - \xi_t - 1. \qquad (2.3) $$

Thus, (2.2) can be written $I(t+1) = (I(t) + \zeta_t)^+$. We see also that, for $1 \le t < n$,

$$ v_{t+1} \text{ is a root} \iff I(t) + \zeta_t < 0 \iff I(t+1) > I(t) + \zeta_t. \qquad (2.4) $$
8:4 Depth-First Search performance in random digraphs

Note that the random variables $\zeta_t$ are independent, but have different distributions. We define also

$$130 \qquad \tilde{I}(t) := \sum_{i=1}^{t-1} (\eta_i - 1 - \xi_i) = \sum_{i=1}^{t-1} \zeta_i \qquad (2.5)$$

and

$$132 \qquad I_*(t) := \min_{1 \le j \le t} \tilde{I}(j). \qquad (2.6)$$

It follows from the recursion (2.2) and induction that

$$134 \qquad I(t) = \tilde{I}(t) - I_*(t). \qquad (2.7)$$

By (2.5) and (2.7),

$$136 \qquad \tilde{I}(t+1) = \tilde{I}(t) + \zeta_t = I_*(t) + I(t) + \zeta_t \qquad (2.8)$$

and thus it follows from (2.4) and (2.6) that, for $1 \le t < n$,

$$138 \qquad v_{t+1} \text{ is a root} \iff I(t) + \zeta_t < 0 \iff \tilde{I}(t+1) < I_*(t) \iff I_*(t+1) < I_*(t). \qquad (2.9)$$

Obviously, $v_1$ is also a root, with $I(1) = \tilde{I}(1) = I_*(1) = 0$.

We have

$$141 \qquad \mathbb{E} \zeta_t = \mathbb{E} \eta_t - \mathbb{E} \xi_t - 1 = \lambda - \frac{t/n}{1-t/n} - 1 = \lambda - \frac{1}{1-t/n}. \qquad (2.10)$$

Hence, uniformly in $t/n \le \theta^*$ for any fixed $\theta^* < 1$,

$$143 \qquad \mathbb{E} \tilde{I}(t) = \sum_{i=1}^{t-1} \mathbb{E} \zeta_i = (t-1)\lambda - \sum_{i=1}^{t-1} \frac{1}{1-i/n} = n\tilde{\iota}(t/n) + O(1), \qquad (2.11)$$

where

$$145 \qquad \tilde{\iota}(\theta) := \int_{0}^{\theta} \left( \lambda - \frac{1}{1-x} \right) dx = \lambda\theta + \log(1-\theta). \qquad (2.12)$$

Let, as in [1],

$$147 \qquad \theta_0 := (1 - \lambda^{-1})^+ = \begin{cases} 1 - \lambda^{-1}, & \lambda > 1, \\ 0, & \lambda \le 1, \end{cases} \qquad (2.13)$$

and let $\theta_1$ is the largest root in $[0, 1)$ of $\tilde{\iota}(\theta_1) = 0$; thus

$$149 \qquad \log(1 - \theta_1) = -\lambda\theta_1 \qquad (2.14)$$

and $\theta_1$ equals the survival probability of a Bienayme-Galton-Watson (BGW) process with $\text{Po}(\lambda)$ offspring distribution. Define

$$152 \qquad \tilde{\iota}^+(\theta) := [\tilde{\iota}(\theta)]^+ = \begin{cases} \lambda\theta + \log(1-\theta), & 0 \le \theta \le \theta_1, \\ 0, & \theta_1 \le \theta \le 1, \end{cases} \qquad (2.15)$$

It is easy to see that if $\lambda \le 1$, then $\tilde{\iota}^+(\theta) = 0$ for all $\theta \in [0, 1]$, while if $\lambda > 1$, then $\tilde{\iota}^+(\theta) > 0$ for $0 < \theta < \theta_1$ (where $0 < \theta_1 < 1$), with a maximum at $\theta_0 = 1 - \lambda^{-1}$.

We now can argue similarly to [1], using $I(t)$ instead of $d(t)$. The proof of [1, Theorem 2.4] applies with very minor differences, and yields:
► **Theorem 2.** Suppose that the outdegree distribution has finite variance. Then

157

158

$$ \max_{1 \le t \le n} |I(t) - n\tilde{t}^+(t/n)| = O_{L^2}(n^{1/2}). \qquad (2.16) $$

Furthermore, for every $\varepsilon > 0$, we also have

159

160

$$ \max_{1 \le t \le (1-\varepsilon)n} |\tilde{I}(t) - n\tilde{t}(t/n)| = O_{L^2}(n^{1/2}). \qquad (2.17) $$

161

162

163

We can use Theorem 2 to show the following results, extending [1, Theorems 4.1 and 4.3] to general outdegree distributions. The proofs are similar to the ones in [1]; details will be given in the full paper.

164

165

► **Theorem 3.** Suppose that the outdegree distribution has finite variance. Let $N$ be the number of trees in the depth-first forest. Then

166

$$ N = \psi n + O_{L^2}(n^{1/2}), \qquad (2.18) $$

167

where

168

$$ \psi := 1 - \theta_1 - \frac{\lambda}{2}(1 - \theta_1)^2. \qquad (2.19) $$

Figure 1 shows the parameter $\psi$ as a function of the average degree $\lambda$.

<figure><img src="image_9.png" /><figcaption>Figure 1 $\psi$, as function of $\lambda$.</figcaption></figure>

169

► **Theorem 4.** Suppose that the outdegree distribution has finite variance. Let $\mathbf{T}_1$ be the largest tree in the depth-first forest.

170

171

172

(i) If $\lambda \le 1$, then $|\mathbf{T}_1| = o_p(n)$.

173

(ii) If $\lambda > 1$, then the largest tree in the depth-first forest has order $|\mathbf{T}_1| = \theta_1 n + O_{L^2}(n^{1/2})$.

174

Furthermore, the second largest tree has order $|\mathbf{T}_2| = o_p(n)$.

175

More precise results will be given in the full paper.
### 3 Stack size and depth

176

We can recover the depth of the vertices from the stack size process, or more precisely, from the process $\tilde{I}(t)$ defined above; this uses a method that has been used by several authors in the study of other random trees, see for example [9, (1.1)] and [7, Proposition 4].

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

When vertex $v_t$ is found by the DFS, the stack consist of all future arcs from the ancestors of $v_t$ in the depth-first forest. Hence, the stack size $I(t)$ is the total number of future arcs from the ancestors of $v_t$. As the DFS continues, it first explores the descendants of $v_t$. During this period, the ancestors of $v_t$ are still ancestors of the current vertex, and their future arcs remain the same as when $v_t$ was found. Hence, if $v_s$ is a descendant of $v_t$, then $I(s) \ge I(t)$. Moreover, we then also have $I_*(s) = I_*(t)$ by (2.9), since no new root has been found, and thus, by (2.7), $\tilde{I}(s) \ge \tilde{I}(t)$. On the other hand, when the DFS has finished exploring descendants of $v_t$, then it has explored all arcs from $v_t$ and the DFS next backtracks to the ancestors of $v_t$ by exploring the future edges of the ancestors of $v_t$ one by one. If another vertex $v_u$ is found in this way, then $I(u) < I(t)$; furthermore, $I_*(u) = I_*(t)$ as above, and thus $\tilde{I}(u) < \tilde{I}(t)$. Finally, if no further new vertex is found in the same tree as $v_t$, then the DFS next finds a new root $v_u$; in this case, $I(u) = 0 \le I(t)$, and, by (2.9), $I_*(u) < I_*(t)$. Hence, $\tilde{I}(u) < \tilde{I}(t)$ holds in this case too. This leads to the following characterisation. (Details will be given in the full paper.)

194

► Lemma 5. (i) For any $s, t \in [n]$, $v_s$ is a descendant of $v_t$ if and only if $s > t$ and

195

$$ \min_{t \le i \le s} \tilde{I}(i) = \tilde{I}(t). \qquad (3.1) $$

196

197

198

(ii) For any $t \ge 1$, the ancestors of $v_t$ are the vertices $v_s$ corresponding to the weak right-to-left minima of $(\tilde{I}(s))_{1 \le s \le t}$, excluding $s = t$. Hence the depth $d(t)$ of $v_t$ is the number of such right-to-left minima.

199

200

201

Let $G_\eta(z) := \sum_k \mathbb{P}(\eta = k)z^k$ be the probability generating function of $\eta$. For $\theta \in [0, 1]$, let $\eta_\theta$ be a random variable obtained by thinning the outdegree $\eta$ and keeping each arc with probability $1 - \theta$, independently; thus $\eta_\theta$ has probability generating function

202

$$ G_{\eta_{\theta}}(z) = G_{\eta}(\theta + (1-\theta)z) = G_{\eta}(1 - (1-\theta)(1-z)). \qquad (3.2) $$

203

204

205

206

Note that the number of outgoing arcs from $v_t$ to vertices that are not discovered earlier has the distribution of $\eta_\theta$ with $\theta = t/n$. Let $\rho(\theta)$ be the survivability probability that the Bienayme-Galton-Watson (BGW) process with offspring distribution $\eta_\theta$ has infinite size. It satisfies the identity:

207

$$ 1 - \rho(\theta) = G_{\eta_{\theta}}(1 - \rho(\theta)) = G_{\eta}(\theta + (1-\theta)(1-\rho(\theta))) = G_{\eta}(1 - (1-\theta)\rho(\theta)). \qquad (3.3) $$

208

209

We have $\mathbb{E}\eta_\theta = (1-\theta)\lambda$. Hence, if $(1-\theta)\lambda > 1$, then $\rho(\theta) > 0$; otherwise $\rho(\theta) = 0$.

Define

210

$$ \tilde{\ell}(\theta) := \int_{0}^{\theta} \rho(x) dx, \quad 0 \le \theta \le \theta_{0}, \qquad (3.4) $$

211

and

212

$$ \tilde{\ell}^{+}(\theta) := \begin{cases} \tilde{\ell}(\theta) = \int_{0}^{\theta} \rho(x) dx, & 0 \le \theta \le \theta_{0}, \\ \tilde{\ell}(\tilde{\theta}), & \text{where } \tilde{\theta} \in (0, \theta_{0}) \text{ and } \tilde{\zeta}(\tilde{\theta}) = \tilde{\zeta}(\theta), \\ 0, & \theta_{1} \le \theta \le 1. \end{cases} \qquad (3.5) $$
If $\lambda \le 1$, this simply means $\tilde{l}(\theta) := 0$ for all $\theta \in [0, 1]$.

Using Lemma 5 and Theorem 2 we can obtain the following result; the detailed argument (given in the full paper) is unfortunately rather long.

► **Theorem 6.** We have

$$ \max_{1 \le t \le n} |d(t) - n\tilde{l}^+(t/n)| = o_{L^2}(n). \qquad (3.6) $$

# 4 Depth analysis

In this section we sketch an alternative approach where we study the depth directly, without using the stack index. Details will be given in the full paper. In particular, for simplicity we approximate below generating functions and other quantities by their limits as $n \to \infty$, sometimes omitting careful estimates of the errors. We consider only the case $\lambda > 1$, since otherwise there is no giant tree and the depth $d_t$ is small for all $t$.

Recall that the outdegree $\eta$ has the p.g.f. $G_{\eta}(z) = \sum_k \mathbb{P}(\eta = k)z^k$, and that at time $t$, the number of outgoing arcs from $v_t$ that lead to vertices not already seen has the distribution $\eta_{\theta}$ with p.g.f. $G_{\eta_{\theta}}(z) = \eta(\theta + (1 - \theta)z)$, see (3.2).

## 4.1 Splitting the giant tree

Recall the definitions of $\theta_0$ and $\theta_1$ from (2.13)–(2.14). It is easily seen that these are, roughly, the proportions of discovered nodes when we find the top of the giant tree, and when we leave the giant tree, respectively. Let $\varepsilon \in (0, 1)$ be a fixed number which will be specified later. We divide the interval $[0, n\theta_1]$ into three intervals: $U_n = [0, \theta_0n - n^{1-\varepsilon}]$ called the *climbing zone*, $D_n = [\theta_0n + n^{1-\varepsilon}, \theta_1n]$, called the *descending zone*, and the band $B_n = [\theta_0n - n^{1-\varepsilon}, \theta_0n + n^{1-\varepsilon}]$, called the *neutral zone*.

For $t \in U_n$, we say that $v_t$ is a *ladder vertex* if for all $t' \in U_n: t' > t \Rightarrow d(t') \ge d(t)$. In other words, $t$ is a right minimum of the function $d(t)$ in $U$. For an integer $i$, we define $d_i^{-1}(i)$ as the last integer $t$ in $U_n$ such that $d(t) = i$ (provided such a $t$ exists); note that then $v_t$ is a ladder vertex. Also, we say that $t$ is an *up-time* if $v_t$ is a ladder vertex and $t$ is the first time it is visited.

As a property of DFS, the ladder vertices are also revisited in the descending zone. Let $v$ be a ladder vertex visited at time $t$ in the climbing zone. When revisited the depth would be back at $d(t)$, see Figure 2.

## 4.2 Average interval between two up-times

Assume that $t \in U_n$ is an up-time of a ladder vertex $v_t$ with depth $d(t) = i$. Then (assuming that $v_t$ is not the last ladder vertex) the next up-time $t'$ finds the next ladder vertex $v_{t'}$. Clearly, $v_{t'}$ must be a child of $v_t$ in the DFS, so its depth $d(t') = i + 1$, and it is the first child such that the DFS does not return to $v_t$ before the end of $U_n$. Given an up-time $t$, the future events in $U_n$, including the value of $t'$, are independent of the past history of the DFS. If we ignore the variation of $\theta$ in the interval $[t, t']$, then the DFS there can be regarded as a BGW tree $T_{\theta}$ (rooted at $v_t$) with offspring distribution $\eta_{\theta}$; since we assume that $\theta < \theta_0$, the BGW tree $T_{\theta}$ is supercritical. We denote by $g_{\theta}(z)$ the generating function of the total number of vertices in $T_{\theta}$ when the number is finite; it satisfies the fixed point equation:

$$ g_{\theta}(z) = zG_{\eta_{\theta}}(g_{\theta}(z)). \qquad (4.1) $$
8:8 Depth-First Search performance in random digraphs

<figure><img src="image_10.png" /><figcaption>■ **Figure 2** The DFS in the giant tree: the climbing phase (left) and the descending phase (right) through ladder vertices.</figcaption></figure>

thus $g_{\theta}(1) = 1 - \rho(\theta)$, the BGW tree extinction probability in (3.3).

We denote by $H(z, \theta)$ the probability generating function of the number of visited nodes in the subtrees of the root of $\mathcal{T}_{\theta}$ before hitting an infinite subtree, under the condition that the root has indeed an infinite subtree. Let $H'$ denote the derivative with respect to the first variable $z$.

► **Theorem 7.** We have the identity

$$H(z, \theta) = 1 + \frac{z-1}{1 - g_{\theta}(z)} \qquad (4.2)$$

and thus the expected number of visited nodes in the BGW tree is

$$H'(1, \theta) = \frac{1}{1 - g_{\theta}(1)} = \frac{1}{\rho(\theta)} = O((\theta_0 - \theta)^{-1}). \qquad (4.3)$$

The p.g.f. of the number of visited vertices between two consecutive up-times $t$ and $t'$ is thus asymptotically, with $\theta = t/n$

$$H\left(z, \theta \pm O\left(\frac{1}{n(\theta_0 - \theta)^2}\right)\right) \qquad (4.4)$$

and the average number of new visited vertices is $H'(1, \theta) + O(\frac{1}{n(\theta_0 - \theta)^4})$.

**Proof.** If $k$ is the number of children of the root in the BGW tree $\mathcal{T}_{\theta}$, then the generating function of the number of subtrees before finding an infinite one is $\sum_{\ell<k} z^{\ell} (1 - \rho(\theta))^{\ell} \rho(\theta)$. The generating function of the number of visited vertices in the BGW tree before finding an infinite subtree is thus $z\rho(\theta) \sum_{\ell<k} (g_{\theta}(z))^{\ell}$. Summing over the offspring distribution we get the unconditional generating function

$$z \frac{\rho(\theta)}{1 - g_{\theta}(z)} (G_{\eta_{\theta}}(1) - G_{\eta_{\theta}}(g_{\theta}(z))) = \frac{\rho(\theta)}{1 - g_{\theta}(z)} (z - g_{\theta}(z)) \\ = \rho(\theta) \left( \frac{z-1}{1 - g_{\theta}(z)} + 1 \right). \qquad (4.5)$$

To get the p.g.f. $H(z, \theta)$ of the number of discovered nodes conditioned on $\mathcal{T}_{\theta}$ having at least one infinite subtree, one must divide by $\rho(\theta)$, which is the probability that the BGW tree is
infinite. The error term comes from the fact that the fraction of discovered vertices varies during the interval in the proportion of the size of the interval divided by $n$. If we look at the generating function $H(z, \theta)$ it turns out (see the appendix) that the interval multiplied by $(\theta_0 - \theta)^2$ is bounded in probability, thus a variation of $\theta$ of order $O((\theta_0 - \theta)^{-2}/n)$. ◀

Let $\Delta_i$ be the time interval between two consecutive up-times $t$ and $t'$ such that $d(t) = i$. To get the number $u(t, t')$ of up-times in an interval $(t, t']$ one must find the probability that $\Delta_i + \Delta_{i+1} + \cdots + \Delta_{i+k} \le t' - t$. Since the up-times are renewal points in the interval $U_n$, we have, given that $t$ is an up-time,

$$ \begin{cases} \mathbb{P}(\Delta_i + \Delta_{i+1} + \cdots + \Delta_{i+k} > t' - t) = \mathbb{P}(u(t, t') < k) \\ \mathbb{P}(\Delta_i + \Delta_{i+1} + \cdots + \Delta_{i+k} \le t' - t) = \mathbb{P}(u(t, t') \ge k). \end{cases} \quad (4.6) $$

Thus by Chebychev's inequality, we have the Chernoff type bounds

$$ \forall x > 0: \begin{cases} \mathbb{P}(u(t, t') < k) \le H(e^x, t/n)^k e^{-(t'-t)x} \\ \mathbb{P}(u(t, t') \ge k) \le H(e^{-x}, t'/n)^k e^{(t'-t)x} \end{cases} \quad (4.7) $$

The estimate of these probabilities will come from an easy application of generating functions.

**Lemma 8.** When the quantity $\theta$ is smaller than but close to $\theta_0$, we have $\rho(\theta) = 1 - g_\theta(1) = 2\frac{\lambda_2^3}{\lambda_2}(\theta_0 - \theta) + O((\theta_0 - \theta)^2)$ where $\lambda_2 = G_\eta''(1)$. Furthermore the generating function $g_\theta(z)$ has a radius of convergence which is $1 + \frac{\lambda_2^4}{2\lambda_2^3}(\theta_0 - \theta)^2 + O((\theta_0 - \theta)^3)$, and for $z$ such that $|z - 1| \ll (\theta_0 - \theta)^2$ we have

$$ g_\theta(z) = 1 - 2\frac{\lambda_2^3}{\lambda_2}(\theta_0 - \theta) + \frac{z-1}{\lambda(\theta_0 - \theta)} + O\left(\frac{(z-1)^2}{(\theta_0 - \theta)^3} + (\theta_0 - \theta)^2\right). \quad (4.8) $$

$$ H(z, \theta) = 1 + \frac{\lambda_2(z-1)}{2\lambda^3(\theta_0 - \theta)} + O\left(\frac{(z-1)^2}{(\theta_0 - \theta)^3} + (\theta_0 - \theta)^2\right) \quad (4.9) $$

$$ H'(1, \theta) = \frac{\lambda_2}{2\lambda^3(\theta_0 - \theta)} + O(1). \quad (4.10) $$

**Proof.** In Appendix A. ◀

**Lemma 9.** Let $\varepsilon > 0$ and $\frac{1-\varepsilon}{2} < \alpha < 1 - \varepsilon$. For $a, A > 0$ there exist $B > 0$ and $C > 0$ such that for $t < t' \in U_n$ with $an^{1-\varepsilon} \le t' - t \le An^{1-\varepsilon}$ we have

$$ \mathbb{P} \left( u(t, t') \ge \frac{1}{H'(1, \theta)} (t' - t + Bn^\alpha) \right) < \exp(-Cn^{2\alpha-1-\varepsilon}), \quad (4.11) $$

$$ \mathbb{P} \left( u(t, t') < \frac{1}{H'(1, \theta')} (t' - t - Bn^\alpha) \right) < \exp(-Cn^{2\alpha-1-\varepsilon}). \quad (4.12) $$

**Proof.** Now $t$ and $t'$ can be within $n^{1-\varepsilon}$ from $n\theta_0$ which has an impact on the estimate of $\log H(e^x, \theta)$. For the super-critical BGW tree, we know from Lemma 8 and its proof that $H'(1, \theta) = O((\theta_0 - \theta)^{-1})$ and that, for $|x| \ll (\theta_0 - \theta)^2$,

$$ H(e^x, \theta) \le \exp \left( xH'(1, \theta) + D \frac{x^2}{(\theta_0 - \theta)^3} \right) \quad (4.13) $$

for some $D > 0$.
8:10 Depth-First Search performance in random digraphs

For (4.11), let $t' - t = kH'(1,\theta) - Bn^\alpha$ for some $B > 0$ and $0 < \alpha < 1 - \varepsilon$. Thus $k = \frac{1}{H'(1,\theta)}(t' - t - Bn^\alpha)$ which makes $k$ of the order $n^{1-\varepsilon}(\theta_0 - \theta) \gtrsim n^{1-2\varepsilon}$. We use the estimates (4.7). The quantity $H(e^x, \theta)^k e^{-(t'-t)x}$ in (4.7) is smaller than $\exp(\frac{Dkx^2}{(\theta_0-\theta)^3} - Bxn^\alpha)$, since the terms in $kxH'(1,\theta)$ cancel. The minimal value of this quantity is reached for $x = \frac{B}{2Dk}n^\alpha(\theta_0-\theta)^3$ which is of order $\frac{B}{2D(t'-t)}n^\alpha(\theta_0-\theta)^3H'(1,\theta) \lesssim n^{\alpha-1+\varepsilon}(\theta_0-\theta)^2 \ll (\theta_0-\theta)^2$. This minimal value is $\exp(-\frac{B^2}{4kD}(\theta_0-\theta)^3H'(1,\theta)n^{2\alpha}) \lesssim \exp(-Cn^{2\alpha-1-\varepsilon})$ for some $C > 0$. The proof of (4.12) is essentially the same. ◀

At this point it is tempting to take the optimal value for $\alpha$ to be $(1 - \varepsilon)/2$ with $\varepsilon$ close to 0. But in fact this would ignore that the quantities $H'(1,\theta)$ and $H'(1,\theta')$ may differ by a factor bounded away from 1, which would introduce an error greater than the term $Bn^\alpha$. This in fact reduce the possibilities for $1 - \varepsilon$ and $\alpha$ for a consistent deviation probability. The values $\varepsilon = 1/5$ and $\alpha = 3/5$ seem to be the limiting values that we can achieve as we show next.

**Theorem 10.** For all $\beta > \frac{4}{5}$ for all $t \in U_n$ we have $d(t) = n \int_0^{t/n} \rho(\theta)d\theta + o_p(n^\beta)$.

**Proof.** Assume first that $t$ is an up-time, and that there is an increasing sequence of up-times (not necessarily consecutive) $t_0, t_1, \dots, t_\ell$ with $t_0 = 0$ and $t_\ell = t$ with the constraint that for all $i < \ell$: $t_{i+1} - t_i \le An^{1-\varepsilon}$. Since $u(0,t) = \sum_i u(t_i, i+1)$, it turns out that the probability that there exists $i$ such that $u(t_i, t_{i+1}) > \frac{1}{H'(1,t_i/n)}(t_{i+1} - t_i + Bn^\alpha)$ is smaller than $n \exp(-Cn^{2\alpha-1-\varepsilon})$ as shown in Lemma 9. Therefore with high probability $\sum_i u(t_i, t_{i+1}) \le \sum_i \frac{t_{i+1}-t_i}{H'(1,t_i/n)} + O(n^{\alpha+\varepsilon})$, provided that $2\alpha - 1 - \varepsilon > 0$. Similarly with high probability $\sum_i u(t_i, t_{i+1}) \ge \sum_i \frac{t_{i+1}-t_i}{H'(1,t_{i+1}/n)} - O(n^{\alpha+\varepsilon})$. Since both

$$ \sum_i \frac{t_{i+1} - t_i}{H'(1, t_i/n)} = n \int_0^{t/n} \frac{d\theta}{H'(1, \theta)} + O(n^{1-\varepsilon}) \quad (4.14) $$

$$ \sum_i \frac{t_{i+1} - t_i}{H'(1, t_{i+1}/n)} = n \int_0^{t/n} \frac{d\theta}{H'(1, \theta)} - O(n^{1-\varepsilon}) \quad (4.15) $$

it follows that with high probability $u(0,t) = n \int_0^{t/n} \frac{d\theta}{H'(1,\theta)} + O(n^{1-\varepsilon}) + O(n^{\alpha+\varepsilon})$, provided that $2\alpha - 1 - \varepsilon > 0$. The smallest error order is when $1 - \varepsilon = \alpha + \varepsilon$, thus when $1 - \varepsilon = \alpha + \varepsilon > 4/5$. When $t$ is not an up-time, the same result holds since the extra depth explored after the last up-time is $O_p(n^{2\varepsilon})$, well within the error term $O(n^\beta)$. ◀

## 4.3 Average interval between two down times

During the descent phase of the giant tree (i.e. the values of $t$ in $D_n$), the DFS revisits all ladder vertices met during the ascending phase. The process consists of exploring the remaining outgoing neighbours of the ladder vertices that have not been visited during the ascending phase.

We notice that given the ladder times, the remaining outdegrees of the ladder vertices form a sequence of independent random variable.

Let $t$ the time at which a ladder vertex is again revisited. Let $t'$ be the first time at which it was visited during the ascending period, thus $d(t') = d(t)$. Let $\theta = t/n \in (\theta_0, \theta_1)$ and $u(\theta) = t'/n$. We have the following theorem.

**Theorem 11.** The p.g.f. of the remaining degree is asymptotically

$$ \tilde{\eta}_{\theta}(z) = (1 - u(\theta)) \frac{G_{\eta}(z) - 1 + \rho(u(\theta))}{z - 1 + (1 - u(\theta))\rho(u(\theta))}. \quad (4.16) $$
**Proof.** Let $\tilde{\eta}_{\theta,k}(z)$ be the generating function of the remaining degree of the vertex $v_t$ assuming the latter has outdegree $k$. Then, asymptotically,

346

347

348

$$ \tilde{\eta}_{\theta,k}(z) = \sum_{\ell<k} (1-a(u(\theta))^{\ell} a(u(\theta)))z^{k-1-\ell} \quad (4.17) $$

349

$$ = a(u(\theta)) \frac{z^k - (1 - a(u(\theta)))^k}{z - 1 + a(u(\theta))} \quad (4.18) $$

350

351

where $a(\theta) = (1 - \theta)\rho(\theta)$ is the probability that a new vertex has not yet been visited and is the root of an infinite BGW tree.

Summing over all outdegrees weighted by their probabilities we get the unconditional generating function of the remaining outdegree: $a(u(\theta)) \frac{G_{\eta}(z)-G_{\eta}(1-a(u(\theta)))}{z-1+a(u(\theta))}$ which is equal to $a(u(\theta)) \frac{G_{\eta}(z)-1+\rho(u(\theta))}{z-1+a(u(\theta))}$ since (3.3) yields $G_{\eta}(1-a(u(\theta))) = G_{\eta_{u(\theta)}}(1-\rho(u(\theta))) = 1-\rho(u(\theta))$. The above expression has value $\rho(u(\theta))$ at $z=1$ and therefore must be divided by this factor in order to get the p.g.f. $\tilde{\eta}_{\theta}(z)$. ◀

352

353

354

355

356

The “down-times” in $D_n$ bear some symmetries with the up-times in $U_n$, with time reversed.

357

360

**▶ Theorem 12.** *The p.g.f. of the number of visited vertices between two consecutive down-times is asymptotically*

361

$$ \bar{H}_{\theta}(z) = (1 - u(\theta)) \frac{\frac{g_{\theta}(z)}{z} - 1 + \rho(u(\theta))}{(1 - \theta)(g_{\theta}(z) - 1) + (1 - u(\theta))\rho(u(\theta))} \quad (4.19) $$

362

and the average number of visited vertices is $\bar{H}'_{\theta}(1) = \frac{1}{\rho(u(\theta))} \frac{\lambda - \frac{1}{1-u(\theta)}}{\frac{1}{1-\theta} - \lambda}$.

363

**Proof.** We have $\bar{H}_{\theta}(z) = \tilde{\eta}_{\theta}(\theta + (1-\theta)g_{\theta}(z))$, which simplifies using (3.2) and (4.1). ◀

364

365

366

Let $\bar{\Delta}_i$ be the number of new visited nodes between two consecutive down-times $t$ and $t'$ such that $d(t') = i$. To get the number $d(t, t')$ of down-times between $t$ and $t'$ we use the renewal property of the sequence of down-times. With a similar reasoning as in (4.6)–(4.7) we get

$$ \left\{ \begin{array}{l} \mathbb{P}(\bar{\Delta}_i + \bar{\Delta}_{i-1} + \cdots + \bar{\Delta}_{i-k} > t' - t) = \mathbb{P}(d(t, t') < k) \\ \mathbb{P}(\bar{\Delta}_i + \bar{\Delta}_{i-1} + \cdots + \bar{\Delta}_{i-k} \le t' - t) = \mathbb{P}(d(t, t') \ge k). \end{array} \right. \quad (4.20) $$

367

368

and

$$ \forall x > 0 : \left\{ \begin{array}{l} \mathbb{P}(d(t, t') < k) \le (\bar{\Delta}_{t'/n}(e^x))^k e^{-(t'-t)x} \\ \mathbb{P}(d(t, t') \ge k) \le (\bar{\Delta}_{t'/n}(e^{-x}))^k e^{(t'-t)x}. \end{array} \right. \quad (4.21) $$

369

370

We have a theorem whose proof is absolutely similar to the proof of Theorem 10:

**▶ Theorem 13.** For all $\beta > \frac{4}{5}$ with high probability for all $t \in D_n$ we have $d(t) = n \int_{t/n}^{\theta_1} \frac{d\theta}{\bar{H}'_{\theta}(1)} + O(n^{\beta})$.

371

372

For $\theta \in [\theta_0, \theta_1]$, define $\hat{\ell}(\theta) = \int_{\theta}^{\theta_1} \frac{d\tau}{\bar{H}'_{\theta}(1)}$. Since $d(t) = d(t')$, where asymptotically $t/n = \theta \in [\theta_0, \theta_1]$ and $t'/n = u(\theta) \in [0, \theta_0]$, we obtain from Theorems 10 and 13, recalling (3.4),

373

374

$$ \hat{\ell}(\theta) = \int_{0}^{u(\theta)} \rho(x) \, dx = \tilde{\ell}(u(\theta)). \quad (4.22) $$

375

376

**▶ Theorem 14.** We have the identity $u(\theta) = \tilde{\theta}$ in (3.5).
8:12 Depth-First Search performance in random digraphs

377 **Proof.** Theorem 12 yields

$$
378
\begin{equation}
\hat{\ell}'(\theta) = - \frac{1}{\bar{H}_{\theta}'(1)} = - \frac{\rho(u(\theta))}{\lambda - \frac{1}{1-u(\theta)}} \frac{1-(1-\theta)\lambda}{1-\theta}. \tag{4.23}
\end{equation}
$$

379 Furthermore $\tilde{\ell}'(\theta) = \rho(\theta)$ by (3.4). Hence, (4.22) implies

$$
380
\begin{equation}
\frac{du(\theta)}{d\theta} = \frac{\hat{\ell}'(\theta)}{\tilde{\ell}'(u(\theta))} = \frac{\frac{1}{1-\theta} - \lambda}{\frac{1}{1-u(\theta)} - \lambda}. \tag{4.24}
\end{equation}
$$

381 Similarly, the identity $\tilde{\iota}(\tilde{\theta}) = \tilde{\iota}(\theta)$ in (3.5) yields, recalling (2.12),

$$
382
\begin{equation}
\frac{d\tilde{\theta}}{d\theta} = \frac{\tilde{\iota}'(\theta)}{\tilde{\iota}'(\tilde{\theta})} = \frac{\frac{1}{1-\tilde{\theta}} - \lambda}{\frac{1}{1-\tilde{\theta}} - \lambda}. \tag{4.25}
\end{equation}
$$

383 Since $u(\theta_0) = \tilde{\theta}_0 = \theta_0$, the differential equations (4.24) and (4.25) have the same solution.
384 We call the function $\theta \mapsto \tilde{\theta}$ the mirror function; note that it only depends of average
385 outdegree without any further consideration on the details of the outdegree distribution. All
386 computations done we have $\tilde{\theta} = 1 + \frac{1}{\lambda}W_{-1}(-(1-\theta)e^{(\theta-1)\lambda})$ using the branch $W_{-1}(\cdot)$ of the
387 Lambert W function, see Figure 3 for $\lambda = 2$. ◀

<figure><img src="image_11.png" /><figcaption>■ **Figure 3** The mirror function for $\lambda = 2$.</figcaption></figure>

388 ▶ Remark 15. Theorems 6 and 13 show that $\hat{\ell}(\theta) = \tilde{\ell}^{+}(\theta)$ for $\theta \in [\theta_0, \theta_1]$. Furthermore, the
389 identity $u(\theta) = \tilde{\theta}$ follows also directly from Theorem 6 and (3.5) together with $d(t) = d(t')$.

390 **5** An example

391 We take the example of a constant outdegree. In the case of outdegree 2, $G_\eta(z) = z^2$, $\lambda = 2$, 392 and $\theta_0 = \frac{1}{2}$. Consider for simplicity only $\theta \in [0, \theta_0]$. Then, (3.3) has the explicit solution 393 $\rho(\theta) = 1 - \left(\frac{\theta}{1-\theta}\right)^2$, and Theorems 2 and 6 show that if $t/n \to \theta$, then

$$
394
\begin{equation}
\frac{1}{n} I(t) \xrightarrow{L^2} \tilde{\iota}^{+}(\theta) = 2\theta + \log(1-\theta), \tag{5.1}
\end{equation}
$$

$$
395
\begin{equation}
\frac{1}{n} d(t) \xrightarrow{L^2} \tilde{\ell}^{+}(\theta) = -2 \log(1-\theta) - \frac{\theta}{1-\theta}, \tag{5.2}
\end{equation}
$$
In the case of higher constant outdegree, say 8, $\rho$ must be calculated from the implicit formula (3.3), for $\theta \le \theta_0 = 1 - \frac{1}{8}$. Larger outdegrees can be treated similarly. Figure 4 displays the average depth and index for constant outdegree 2 and 8. We notice that for $\eta = 2$, the stack size is smaller than the depth. This might be a surprise because at each new discovered node the stack stores the whole set of outgoing arcs, while the depth increases by at most 1. The reason is that in this case $\eta = 2$, and thus, although the stack keeps all unexplored arcs for all ancestors, this is at most one arc for each ancestor and many ancestor have no arc left. For $\eta$ larger this disappears, and the stack size becomes larger than the depth.

# 6 Conclusion

We have presented an analysis of the Depth-First Search algorithm by Tarjan in a model of random graphs recently introduced by Don Knuth. We have presented a version of the stack model which can be analyzed as a Markov chain and is much easier to analyse than the real depth. The latter requires new insights in a model of Bienaymé-Galton-Watson trees with a varying extinction probability, in particular when close to the sub-critical case.

<figure><img src="image_12.png" /><figcaption>Figure 4 The limit of $\frac{1}{n}I(t)$ (dashed) and $\frac{1}{n}d(t)$ (solid) as functions of $\theta = t/n$ for $\theta \in [0, \theta_0]$, for the example $\eta = 2$ (left), $\eta = 8$ (right).</figcaption></figure>

# References

## References

1. Philippe Jacquet and Svante Janson. Depth-first search performance in a random digraph with geometric outdegree distribution. *La Matematica*, 2024.

2. Łucja Kot Vignesh Ganapathy Alex Rasmussen Jayant Madhavan, David Ko and Alon Halevy. Google's deep web crawl. *Proceedings of the VLDB Endowment*, (2):1241–1252, 2016.

3. Donald E. Knuth. *The Art of Computer Programming*. Preliminary draft, http://cs.stanford.edu/~knuth/fasc12a.ps.gz, 2022.

4. Michael Krivelevich and Benny Sudakov. The phase transition in random graphs: a simple proof. *Random Structures Algorithms*, (2):131–138, 2013.

5. Gabriel Faraud Nathanaël Enriquez and Laurent Ménard. Limiting shape of the depth first search tree in an erdős-rényi graph. *Random Structures Algorithms*, (2):501–516, 2020.
8:14 REFERENCES

424

425

6 Laurent Ménard Nathan Noiry Nathanaël Enriquez, Gabriel Faraud. Depth first exploration of a configuration model. Electron. J. Probab., (53), 2022.

426

427

7 Jürgen Bennies Götz Kersting. A random walk approach to galton-watson trees. J. Theoret. Probab., (3):777-803, 2000.

428

429

8 Sahar Diskin Michael Krivelevich. On the performance of the depth first search algorithm in supercritical random graphs. Electron. J. Combin., (3), 2022.

430

431

9 Jean-François Le Gall Yves Le Jan. Branching processes in lévy processes: the exploration process. Ann. Probab., (1):213-252, 1998.

432

A

433

434

**Proof of Lemma 8.** We want first to determine the first fixed point $g_{\theta}(1)$ of $G_{\eta_{\theta}}$. We have the expansion

435

$$G_{\eta}(y) = 1 + \lambda(y-1) + \frac{\lambda_2}{2}(y-1)^2 + O((y-1)^3) \quad (A.1)$$

436

where $\lambda_2$ is $G''_{\eta}(1)$. Thus

437

$$G_{\eta_{\theta}}(y) = G_{\eta}(\theta + (1-\theta)y) = 1 + (1-\theta)\lambda(y-1) + (1-\theta)^2 \frac{\lambda_2}{2}(y-1)^2 + O((y-1)^3) \quad (A.2)$$

438

We look at the fixed point equation $G_{\eta_{\theta}}(y) - y = 0$ which is equivalent to

439

$$\lambda(\theta_0 - \theta)(y-1) + \frac{\lambda_2(1-\theta)^2}{2}(y-1)^2 + O((y-1)^3) = 0 \quad (A.3)$$

440

441

The natural root is 1 but the other root is $1 - 2\frac{\lambda(\theta_0 - \theta)}{\lambda_2(1-\theta)^2} + O((\theta_0 - \theta)^2)$ which yields the claimed result since $\frac{1}{1-\theta} = \lambda + O(\theta_0 - \theta)$.

442

To determine the function $g_{\theta}(z)$ one must solve the equation $zG_{\eta_{\theta}}(y) = y$ which writes:

443

$$1 - \frac{1}{z} + (1 + \lambda(\theta_0 - \theta) - \frac{1}{z})(y-1) + \frac{\lambda_2(1-\theta)^2}{2}(y-1)^2 + O((y-1)^3) = 0. \quad (A.4)$$

444

445

446

447

Retaining only the second order (the extra order will be in $O((\theta_0 - \theta)^3)$ we get an equation which is degenerate when $(1 + \lambda(\theta_0 - \theta) - \frac{1}{z})^2 - 2\lambda_2(1 - \theta)^2(1 - \frac{1}{z}) = 0$, i.e. when $1 - \frac{1}{z} = \frac{\lambda^2(\theta_0 - \theta)^2}{2\lambda_2(1-\theta)^2} + O((\theta_0 - \theta)^3)$. In the above expression we can substitute $(1 - \theta)$ with $\frac{1}{\lambda}$ to a $O((\theta_0 - \theta)^3)$ error term.

448

Assuming $|z - 1| \ll (\theta_0 - \theta)^2$ we have the expression of the root $y = g_{\theta}(z)$:

449

$$y = 1 - 2\frac{\lambda^3}{\lambda_2}(\theta_0 - \theta) + \frac{z-1}{\lambda(\theta_0 - \theta)} + O\left(\frac{(z-1)^2}{(\theta_0 - \theta)^3} + (\theta_0 - \theta)^2\right). \quad (A.5)$$
Now the expression of $H(z, \theta)$ satisfies

450

$$H(z, \theta) = 1 + \frac{z-1}{1 - g_{\theta}(z)} \qquad (A.6)$$

451

$$= 1 + \frac{z-1}{2\lambda_2^3(\theta_0 - \theta) - \frac{z-1}{\lambda(\theta_0 - \theta)} + O\left(\frac{(z-1)^2}{(\theta_0 - \theta)^3} + (\theta_0 - \theta)^2\right)} \qquad (A.7)$$

452

$$= 1 + \frac{\lambda_2(z-1)}{2\lambda^3(\theta_0 - \theta)} \left( \frac{1}{1 - \frac{\lambda_2(z-1)}{2\lambda^4(\theta_0 - \theta)^2} + O\left(\frac{(z-1)^2}{(\theta_0 - \theta)^4} + (\theta_0 - \theta)\right)} \right) \qquad (A.8)$$

453

$$= 1 + \frac{\lambda_2(z-1)}{2\lambda^3(\theta_0 - \theta)} + \frac{\lambda_2^2(z-1)^2}{4\lambda^7(\theta_0 - \theta)^3} + O\left(\frac{|z-1|^3}{(\theta_0 - \theta)^5} + |z-1|\right) \qquad (A.9)$$

454

$$= 1 + \frac{\lambda_2(z-1)}{2\lambda^3(\theta_0 - \theta)} + O\left(\frac{(z-1)^2}{(\theta_0 - \theta)^3} + |z-1|\right) \qquad (A.10)$$

455

In particular,

456

$$H'(1, \theta) = \frac{\lambda_2}{2\lambda^3(\theta_0 - \theta)} + O(1). \qquad (A.11)$$

457

Since the terms added after the unity are small compared to 1 we can equivalently state that

458

$$H(z, \theta) = \exp\left(\frac{\lambda_2(z-1)}{2\lambda^3(\theta_0 - \theta)} + O\left(\frac{(z-1)^2}{(\theta_0 - \theta)^3} + |z-1|\right)\right). \qquad (A.12)$$

459

We also have by (4.2), still assuming $|z-1| \ll (\theta_0 - \theta)^2$,

460

$$H(z, \theta) - 1 - (z-1)H'(1, \theta) = \frac{z-1}{1 - g_{\theta}(z)} - \frac{z-1}{1 - g_{\theta}(1)} \\ = (z-1) \frac{g_{\theta}(z) - g_{\theta}(1)}{(1 - g_{\theta}(z))(1 - g_{\theta}(1))} \qquad (A.13)$$

461

462

Furthermore, by taking the derivative of the fixed point equation $zG_{\eta\theta}(g_{\theta}(z)) = g_{\theta}(z)$, we find, using (A.2) and (A.5),

463

464

$$g'_{\theta}(z) = \frac{G_{\eta\theta}(g_{\theta}(z))}{1 - zG'_{\eta\theta}(g_{\theta}(z))} = \frac{g_{\theta}(z)/z}{-\lambda(\theta_0 - \theta) - (1 - \theta)^2\lambda_2(g_{\theta}(z) - 1) + o(|\theta_0 - \theta|^2)} \\ = \frac{1}{\lambda(\theta_0 - \theta) + o(|\theta_0 - \theta|^2)} = O((\theta_0 - \theta)^{-1}). \qquad (A.14)$$

465

466

Thus (A.13) and the mean-value theorem together with (A.5) yield

467

$$H(z, \theta) - 1 - (z-1)H'(1, \theta) = O\left(\frac{|z-1|^2}{(\theta_0 - \theta)^3}\right). \qquad (A.15)$$

468

We can rewrite this as, for $|x| \ll (\theta_0 - \theta)^2$, using the estimate (A.11),

469

$$H(e^x, \theta) = \exp\left(xH'(1, \theta) + O\left(\frac{x^2}{(\theta_0 - \theta)^3}\right)\right). \qquad (A.16)$$

470

471

<figure><img src="image_13.png" /></figure>