2.1. Number of descendants

Fix a positive integer r and let X(t) denote the number of descendants of r at time t. Here r is a descendant of r, and x is a descendant of r if and only if x chooses to attach itself to at least one descendant of r in step x. In other words, if we think of the graph as a directed graph with edges oriented towards the smaller vertices, vertex x is a descendant of r if and only if there is a directed decreasing path from x to r. In [Reference Pittel36] X(t) was proposed as an influence measure of vertex r at time t.

We prove two theorems.

Theorem 2.1. Suppose that r is fixed, $m=1$ and $\delta>-1$ , and set $p_X(t)\,:\!=\, X(t)/t$ . Then almost surely (i.e. with probability $\textrm{1}$ ) $\lim p_X(t)$ exists, and its distribution is the mixture of two beta distributions, with parameters

\[a=1,\ b=r-\dfrac{1}{2+\delta}\quad {and}\quad a=\dfrac{1+\delta}{2+\delta},\ b=r,\]

weighted by

\[\dfrac{1+\delta}{(2+\delta)r-1}\quad {and}\quad \dfrac{(2+\delta)(r-1)}{(2+\delta)r-1}\]

respectively. Consequently almost surely $\lim_{t\to\infty}p(t)>0$ .

Note.

1. (i) The proof is based on a new family of martingales

   \[M_{\ell}(t)\,:\!=\, \dfrac{(X(t)+{{\gamma}/{(2+\delta)}})^{(\ell)}}{(t+\beta)^{(\ell)}},\]
   where $(z)^{(\ell)}$ stands for the rising factorial. This family definitely resembles the martingales used in [Reference Móri30, Reference Móri31] for the individual vertices’ degrees. For instance, if $D_j(t)$ is the degree of vertex j at time $t\ge j$ , then for some deterministic $\gamma_k(t)$ , $Z_{j,k}(t)\,:\!=\, \gamma_k(t)(D_j(t)+\delta)^{(k)}$ is a martingale [Reference van der Hofstad23]. However, $M_{\ell}(t)$ depends on X(t), a global parameter of the PAM graph. Our initial proof was quite technical. We owe a debt of gratitude to an anonymous referee who was able to condense our argument to a few lines.

2. (ii) With high probability $G_{1,\delta}$ is a forest of $\Theta(\!\log t)$ trees rooted at vertices with loops. For the preferential attachment tree (no loops), Janson [Reference Janson24] recently proved that the scaled sizes of the principal subtrees, those rooted at the root’s children and ordered chronologically, converge almost surely (a.s.) to the GEM-distributed random variables. His techniques differ significantly from ours.

For $m>1$ we use Theorem 2.1 to prove a somewhat surprising result that, for fixed r, almost surely all but a vanishingly small fraction of vertices are descendants of the vertex r (see [Reference Janson24]).

For the case of UAM we have the following result.

2.2. Greedy matching algorithm

We analyze a greedy matching algorithm; a.s. it delivers a surprisingly large matching set even for relatively small m. This algorithm generates the increasing sequence $\{ M(t)\}$ of partial matchings on the sets [t], with $ M(1)=\emptyset$ . Suppose that X(t) is the set of unmatched vertices in [t] at time t. If $t+1$ attaches itself to a vertex $u\in X(t)$ , then $M(t+1)=M(t)\cup\{\{u,t+1\}\}$ , otherwise $M(t+1)=M(t)$ . (If $t+1$ chooses multiple vertices from X(t), then we pick one of those as u arbitrarily.)

First consider the PAM graph. Let

\[h(z)=h_{m,\delta}(z)\,:\!=\, 2\biggl[1-\biggl(\dfrac{m+\delta}{2m+\delta}\biggr)z\biggr]^m-z-1,\]

and let $\rho=\rho_{m,\delta}$ be the unique solution of $h(z)=0$ in the interval [0, 1]. (We have $\rho_{m,\delta}\in (0,1)$ if $\delta>-m$ .)

Theorem 2.4. Let $M\big(t\big)$ and $X\big(t\big)$ , respectively, be the set of greedy matchings and the set of uncovered vertices at time t, and let $x(t)=X(t)/t$ . For any $\delta>-m$ and $\alpha<1/3$ , almost surely

\[\lim_{t\to\infty} t^{\alpha}\max\{0, x(t)-\rho_{m,\delta}\}=0.\]

In consequence, the greedy matching algorithm a.s. finds a sequence of nested matchings $\{M(t)\}$ , where the number of vertices in $M\big(t\big)$ is asymptotically at least $(1-\rho_{m,\delta})t$ .

Remark 2.4. Consider the case $\delta=0$ . Let $r_m\,:\!=\, 1-\rho_{m,0}$ ; some values of $r_m$ are

(2.3) \begin{equation} \begin{aligned}r_1&=0.5000, \ &r_2&=0.6458, \ &r_5&=0.8044,\\r_{10}&=0.8863,&r_{20}&=0.9377, &r_{70}&=0.9803. \end{aligned} \end{equation}

With a bit of calculus, we obtain $r_m=1- 2m^{-1}\log2 +{\textrm{O}}\big(m^{-2}\big)$ .

Theorem 2.5. Let $M\big(t\big)$ denote the greedy matching set after t steps of the UAM process. Let $r_m$ denote the unique positive root of $2(1-z^m) -z=0$ , i.e. $r_m=1-m^{-1}\log 2+{\textrm{O}}\big(m^{-2}\big)$ . Then, for any $\alpha<1/3$ , almost surely

\[\lim_{t\to\infty} t^{\alpha}\bigg| \dfrac{2|M(t)|}{t}-r_m\bigg|=0.\]

Some values of $r_m$ in this case are

\begin{alignat*}{5}r_1&=0.6667, \quad &r_2&=0.7808, \quad &r_5&=0.8891,\\*r_{10}&=0.9386, &r_{20}&=0.9674, &r_{35}&=0.9809.\end{alignat*}

2.3. Greedy independent set algorithm

The algorithm generates an increasing sequence of independent sets $\{I(t)\}$ on vertex sets [t]. Namely, $I(1)=\{1\}$ , and $I(t+1)=I(t)\cup\{t+1\}$ if $t+1$ does not select any of the vertices in I(t); if it does, then $I(t+1)=I(t)$ . I(t) is also a dominating set for the PAM/UAM graph with vertex set [t]; indeed, if a vertex $\tau\in [t]\setminus I(t)$ did not have any neighbor in I(t), then vertex $\tau$ would have been added to $I(\tau-1)$ at step $\tau$ . (Pittel [Reference Pittel33] analyzed the performance of this algorithm applied to the Erdős–Rényi random graph with a large but fixed vertex set.)

For the PAM case we prove the following.

Theorem 2.6. Let $w_m$ denote the unique root of $(1-w)^m-w$ in $ (0,1)$ . For any

\[ \chi\in \biggl(0,\min\biggl\{\dfrac{1}{3},\dfrac{2m+2\delta}{3(2m+\delta)}\biggr\}\biggr), \]

almost surely

\begin{equation*} \lim_{t\to\infty}t^{\chi}\bigg|\dfrac{|I(t)|}{t}-w_m\bigg|=0.\end{equation*}

For the UAM case we prove an almost identical result.

Theorem 2.7. Let $w_m$ be the unique positive root of $-w+(1-w)^m$ in $ (0,1)$ . Then, for any $\alpha<1/3$ , almost surely

\[\lim_{t\to\infty}t^{\alpha}\bigg|\dfrac{|I(t)|}{t} - w_m\bigg|=0.\]

Remark 2.6. Let $w_m$ be the unique positive root of $(1-w)^m-w$ in (0, 1). As $m\to\infty$ ,

\[w_m= \dfrac{\log m}{m}+{\textrm{O}}\left(m^{-1}\log\log m\right).\]

So, for m large and both models, a.s. for all large enough t the greedy algorithm delivers an independent set containing a fraction $\sim{{\log m}/{m}}$ of all vertices in [t]. It was proved in [Reference Frieze, Pérez-Giménez, Prałat and Reiniger21] that for each large t with probability $1-{\textrm{o}}(1)$ , the fraction of vertices in the largest independent set in the PAM graph process and in the UAM graph process is at most $(4+{\textrm{o}}(1))\,{{\log m}/{m}}$ and $(2+{\textrm{o}}(1))\,{{\log m}/{m}}$ , respectively. Since I(t) is dominating, our results prove a.s. existence for all large t of relatively small dominating sets, of cardinality $\le (1+\varepsilon_m) t\,{{\log m}/{m}}$ , ( $\varepsilon_m\to 0$ ).

Remark 2.7. Let $\mathcal I(t)$ denote the cardinality of the largest independent set. We conjecture that for each of the processes there exists a corresponding constant c(m) such that a.s. $\lim_{t\to\infty}t^{-1}\mathcal I(t)=c(m)$ ; of course, $c(m)\ge w_m$ .

Notice that, for the UAM process, the existence of a deterministic function c(m,t), bounded away from 0 and 1 as $t\to\infty$ , such that the distribution of $\mathcal I(t)$ is sharply concentrated around tc(m,t), is not difficult to prove. Indeed, $\mathcal I(t)$ is determined by $t-1$ independent selections of m neighbors among the older vertices made by vertices $2,\dots, t$ . Obviously, $\mathcal I(t)$ meets the following two conditions: (1) changing the outcome of any such selection can affect $\mathcal I(t)$ by at most 1; (2) if $\mathcal I(t)\ge s$ , then there are s vertices that form an independent set, which depends entirely on selections made by these vertices. Using Talagrand’s general inequality [Reference Talagrand37] (see also [Reference Molloy29]), we have, for $z\le \mathbb{E}[\mathcal I(t)]$ ,

\[\mathbb{P}\bigl(|\mathcal I(t)-\mathbb{E}[\mathcal I(t)]|>z+3\sqrt{\mathbb{E}[\mathcal I(t)]}\bigr)\le 2\exp\biggl(-\dfrac{z^2}{16 \mathbb{E}[\mathcal I(t)]}\biggr).\]

That does it, since by Theorem 2.7 $\mathbb{E}[\mathcal I(t)]\ge \mathbb{E}[I(t)]\ge 0.9 w_mt$ when t is large enough and, with exponentially high probability, we have $\mathcal I(t)\le (\sigma+{\textrm{o}}(1))t$ , where $\sigma=\sigma(m)\in (0,1)$ is the root of $\sigma\log\sigma+(1-\sigma)\log(1-\sigma)+\sigma^2m/2$ ; see Lemma 9 of [Reference Frieze, Pérez-Giménez, Prałat and Reiniger21].

3.1. Proof of Theorem 2.1

In this subsection we prove Theorem 2.1 restated below.

Theorem 2.1. Suppose that $m=1$ and $\delta>-1$ , and set $p_X(t)\,:\!=\, X(t)/t$ . Then almost surely (i.e. with probability $\textrm{1}$ ) $\lim p_X(t)$ exists, and its distribution is the mixture of two beta distributions, with parameters

\[a=1,\ b=r-\dfrac{1}{2+\delta}\quad {and}\quad a=\dfrac{1+\delta}{2+\delta},\ b=r,\]

weighted by

\[\dfrac{1+\delta}{(2+\delta)r-1}\quad {and}\quad \dfrac{(2+\delta)(r-1)}{(2+\delta)r-1}\]

respectively. Consequently a.s. $\lim_{t\to\infty}p_X(t)>0$ .

Proof. For $t\ge r>1$ , let $X(t)=X_{m,\delta}(t)=X_{m,\delta}(t,r)$ and $Y(t)=Y_{m,\delta}(t)=Y_{m,\delta}(t,r)$ denote the size and total degree of the vertices in the descendant set rooted at r; so $X(r)=1$ and $Y(r)\in [m,2m]$ , where m (resp. 2m) is attained when vertex r forms no loops (resp. forms m loops) at itself. Introduce $p_Y(t)={{Y(t)}/{(2mt)}}$ . This notation will be used in the proof of Theorem 2.2 as well, but of course $m=1$ in Theorem 2.1.

Here

\[Y(t)=\begin{cases}2X(t) &\text{if}\ {r}\ \text{looped on itself,}\\[4pt]2X(t)-1 &\text{if}\ {r}\ \text{selected a vertex in}\ [r-1].\end{cases}\]

$\big($ In particular, $p_Y(t) =p_X(t)+{\textrm{O}}\big(t^{-1}\big)$ . $\big)$ So, by (2.2),

\begin{align*} \mathbb P(X(t+1)&=X(t)+1\mid \circ)\\ &=\dfrac{Y(t)+\delta X(t)}{(2+\delta)t +(1+\delta)}\\[5pt] &= \begin{cases}\dfrac{(2+\delta)X(t)}{(2+\delta)t+(1+\delta)} &\text{if}\ {r}\ \text{looped on itself,}\\[12pt] \dfrac{(2+\delta)X(t)-1}{(2+\delta)t+(1+\delta)} &\text{if}\ {r}\ \text{selected a vertex in}\ [r-1],\end{cases}\end{align*}

where ‘ $\circ$ ’ indicates conditioning on prehistory (particularly X(t) and Y(t)). Thus we are led to consider the process X(t) such that

\begin{align*}\mathbb P(X(t+1)=X(t)+1 \mid \circ) &= \dfrac{(2+\delta)X(t)+\gamma}{(2+\delta)t+(1+\delta)},\\\mathbb P(X(t+1)=X(t) \mid \circ) &= 1 - \mathbb P(X(t+1)=X(t)+1 \mid \circ) ,\end{align*}

$\gamma=0$ if r looped on itself, $\gamma=-1$ if r selected a vertex in $[r-1]$ . So $\gamma$ is determined by $G_{1,\delta}(t)$ . Letting $\beta={{(1+\delta)}/{(2+\delta)}}$ , the above equation can be written as

(3.1) \begin{equation}\begin{aligned}\mathbb P(X(t+1)=X(t)+1 \mid \circ) &= \dfrac{X(t) + \gamma/(2+\delta)}{t+\beta},\\\mathbb P(X(t+1)=X(t) \mid \circ) &= 1 - \dfrac{X(t) + \gamma/(2+\delta)}{t+\beta}.\end{aligned}\end{equation}

For $\delta=0$ the following claim was proved in [Reference Pittel36]. We let $z^{(\ell)}$ denote the rising factorial $\prod_{j=0}^{\ell-1}(z+j)$ .

Lemma 3.1. Let $\beta={{(1+\delta)}/{(2+\delta)}}$ and $Z(t) = X(t) + {{\gamma}/{(2+\delta)}}$ . Then, conditioned on the attachment record during the time interval $\big[r, t\big]$ , i.e. starting with the attachment decision by vertex r, we have

\[{\mathbb{E}[{Z(t+1)^{(\ell)}\mid \circ}]}= \biggl(\dfrac{t+\beta+\ell}{t+\beta}\biggr) Z(t)^{(\ell)}.\]

Consequently

\[M_{\ell}(t)\,:\!=\, \dfrac{Z(t)^{(\ell)}}{(t+\beta)^{(\ell)}}\]

is a martingale.

We thank an anonymous referee for the following proof, which is much shorter than our original proof.

Proof. We have

\begin{align*}\mathbb{E}[(Z(t+1)^{(\ell)} \mid \circ ]&= (Z(t)+1)^{(\ell)} \dfrac{Z(t)}{t+\beta} + Z(t)^{(\ell)} \biggl( 1- \dfrac{Z(t)}{t+\beta}\biggr)\\&= (Z(t)+\ell)\, Z(t)^{(\ell)} \dfrac{1}{t+\beta} + Z(t)^{(\ell)} - Z(t)^{(\ell)} \dfrac{Z(t)}{t+\beta}\\&= Z(t)^{(\ell)} \biggl(\dfrac{\ell+t+\beta}{t+\beta}\biggr).\end{align*}

The second part follows from this immediately.

To identify the $\lim_{t\to\infty} p(t)$ , recall that the classical beta probability distribution has density

\[f(x;a,b)=\dfrac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}x^{a-1}(1-x)^{b-1},\quad x\in (0,1),\]

parametrized by two parameters $a>0$ , $b>0$ , and moments

\begin{equation*} \int_0^1 x^{\ell} f(x;a, b)\,{\textrm{d}} x=\prod_{j=0}^{\ell-1}\dfrac{a+j}{a+b+j}.\end{equation*}

We can now complete the proof of Theorem 2.1. By Lemma 3.1, we have, for all $t\ge r$ , $\mathbb E [M_{\ell}(t)\mid \gamma]=M_{\ell}(r)$ , or explicitly

\begin{equation*} \mathbb E\biggl[\dfrac{(X(t)+{{\gamma}/{(2+\delta)}})^{(\ell)}}{(t+\beta)^{(\ell)}}\Bigm| \gamma\ \biggr]=\dfrac{(1+{{\gamma}/{(2+\delta)}})^{(\ell)}}{(r+\beta)^{(\ell)}}.\end{equation*}

Since $|\gamma/(2+\delta)|\le 1$ and $X(t)\le t$ , we obtain

\[|M_{\ell}(t)|\le \biggl[\max\biggl(\dfrac{t+1}{t+\beta},\,\dfrac{t+\ell}{t+\beta+\ell-1}\biggr)\biggr]^{\ell}\Longrightarrow \sup_{t\ge 0}|M_{\ell}(t)|\le\max(1,\beta^{-\ell}).\]

Therefore, for every $\ell\ge 1$ , by the martingale convergence theorem, conditioned on $\gamma$ , a.s. there exists

(3.2) \begin{equation}\lim_{t\to\infty}\dfrac{(X(t)+{{\gamma}/{(2+\delta)}})^{(\ell)}}{(t+\beta)^{(\ell)}}\,=\!:\, \mathcal M_{\gamma,\ell}\le \max(1,\beta^{-\ell}),\quad\mathbb E[\mathcal M_{\gamma,\ell}]=\dfrac{(1+{{\gamma}/{(2+\delta)}})^{(\ell)}}{(r+\beta)^{(\ell)}}.\end{equation}

Since $X(t)\le t$ , it follows from (3.2) that a.s. there exists $\lim_{t\to\infty}X(t)/t=\lim_{t\to\infty}p_X(t)$ , and

\begin{equation*} \lim_{t\to\infty}\mathbb{E}[p_X(t)^{\ell}]=\mathbb{E}[\mathcal M_{\gamma,\ell}]=\dfrac{(1+{{\gamma}/{(2+\delta)}})^{(\ell)}}{(r+\beta)^{(\ell)}}=\prod_{j=0}^{\ell-1}\dfrac{1+{{\gamma}/{(2+\delta)}}+j}{r+\beta+j}.\end{equation*}

The sequence of the right-hand side products is the sequence of moments of a unique distribution, which is the beta distribution with parameters $1+{{\gamma}/{(2+\delta)}}$ and $r+\beta-1-{{\gamma}/{(2+\delta)}}$ . By the definition of $\gamma$ and (2.2), we have

\[\mathbb P(\gamma=0)=\dfrac{1+\delta}{(2+\delta)(r-1)+(1+\delta)}=\dfrac{1+\delta}{2r-1+\delta r}.\]

We conclude that $\lim_{t\to\infty}p_X(t)$ has the distribution which is the mixture of the two beta distributions, with parameters

\[a=1,\ b=r-\dfrac{1}{2+\delta} \quad\text{and}\quad a=\dfrac{1+\delta}{2+\delta},\ b=r,\]

weighted by

\[\dfrac{1+\delta}{(2+\delta)r-1}\quad\text{and}\quad\dfrac{(2+\delta)(r-1)}{(2+\delta)r-1}\]

respectively. This completes the proof of Theorem 2.1.

3.2. Proof of Theorem 2.2

In this subsection we prove Theorem 2.2 restated below.

For the proof of this theorem, we need tractable formulas/bounds for the conditional distribution of $Y(t+1)-Y(t)$ . The existence of loops in a preferential attachment graph is a minor nuisance for stating exact conditional probabilities. Hence we will start with the scenario that we do not get a loop on vertex $t+1$ , in which case we can write the exact equations easily and we will then argue that the effect of loops is negligible. Let $\mathcal E_m(t)$ be the event that vertex $t+1$ has no loop. Conditioned on $G_{m,\delta}(t)$ and $\mathcal E_m(t)$ , by the transition probabilities given in (2.1), vertex $t+1$ chooses a vertex $x\in [t]$ with probability

\begin{equation*}\dfrac{d_{t, i-1}(x) +\delta}{(2m + \delta)t + i-1}.\end{equation*}

In the following lemma we use ‘ $ \mid \circ)$ ’ to denote conditioning on $G_{m,\delta}(t)$ and $\mathcal E_m(t)$ .

Lemma 3.2. For $a\in [m]$ ,

\begin{align*}\mathbb{P}({Y(t+1) =Y(t)+m+a \mid \circ})=\binom{m}{a} \dfrac{(Y(t)+\delta X(t))^{(a)} \cdot (2mt-Y(t)+\delta(t-X(t))^{(m-a)}} {((2m+\delta)t)^{(m)}}\end{align*}

and

\[\mathbb{P}({Y(t+1) =Y(t)\mid \circ}) = \dfrac{ (2mt-Y(t)+\delta(t-X(t))^{(m)}} {((2m+\delta)t)^{(m)}}.\]

Proof. Let V(t) denote the descendants of r at time t. Vertex $t+1$ selects, in m steps, a sequence $\{v_1,\dots, v_m\}$ of m vertices from [t], with t choices for every selection. Introduce $\textbf{I}=(\mathbb{I}_1,\dots,\mathbb{I}_m)$ , where $\mathbb{I}_i$ is the indicator of the event $\{v_i \in V(t)\}$ . The total vertex degree of [t] (resp. V(t)) right before step i is $2mt + i-1$ (resp. $Y(t)+\mu_i$ , $\mu_i\,:\!=\, |\{j<i\colon \mathbb{I}_j=1\}|$ ). Conditioned on $G_{m,\delta}(t)$ , $\mathcal E_m(t)$ , and the outcomes of the previous $i-1$ steps, we have

\begin{align*}\mathbb P(\mathbb{I}_i=1)&=\dfrac{Y(t)+\delta X(t)+\mu_i}{2mt+\delta t+i-1},\\[4pt] \mathbb P(\mathbb{I}_i=0)&=\dfrac{2mt-Y(t)+\delta(t-X(t))+i-1-\mu_i}{2mt+\delta t+ i -1}.\end{align*}

Therefore a sequence $(j_1,\dots,j_m)$ will be the outcome of the loopless m-step selection with probability

\begin{align*}& \mathbb P(\textbf{I} =(j_1,\dots,j_m)) \\&\quad=\prod_{i\in [m]} ((2m+\delta)t +i-1)^{-1}\\&\quad \quad \times\prod_{i\colon j_i=1}(Y(t)+\delta X(t)+\mu_i)\times \prod_{i\colon j_i=0}(2mt-Y(t)+\delta(t-X(t))+i-1-\mu_i).\end{align*}

For $j_1+\cdots+j_m = a \in [m]$ , the second product above equals $(Y(t)+\delta X(t))^{(a)}$ and the third product equals $(2mt-Y(t)+\delta(t-X(t))^{(m-a)}$ so that

\[\mathbb P(\textbf{I} =(j_1,\dots,j_m))= \dfrac{(Y(t)+\delta X(t))^{(a)} (2mt-Y(t)+\delta(t-X(t))^{(m-a)}}{((2m+\delta)t)^{(m)}}.\]

Since the total number of admissible sequences $(j_1,\dots,j_m)$ with $j_1+\cdots+j_m = a$ is $\binom{m}{a}$ , we obtain the first formula in Lemma 3.2. The second formula is the case of $\mathbb P(\textbf{I} = (0,\dots,0))$ .

Proof of Theorem 2.2. Lemma 3.2 gives the conditional probabilities for $Y(t+1)-Y(t)$ in the event that there is no loop on vertex $t+1$ . Now let us evaluate the probability that there is no loop on vertex $t+1$ . For $0\le i \le m$ , let $\mathcal E_{i}(t)$ denote the event that no loop has been formed on vertex $t+1$ in the first i steps when vertex $t+1$ is choosing its neighbors. On the event $\mathcal E_{i-1}(t)$ , as the ith edge incident to $t+1$ is about to attach its second end to a vertex in $[t]\cup\{t+1\}$ , the total degree of vertices in [t] is $2mt+i-1$ ( $1\le i\le m$ ). So, by the transition probabilities given in (2.1),

\[\mathbb P(\mathcal E_i(t) \mid \mathcal E_{i-1}(t))= \dfrac{2mt +i-1+t\delta}{2mt+2(i-1)+t\delta +1+{{i\delta}/{m}}} .\]

Hence

(3.3) \begin{equation}\mathbb P(\mathcal E_m(t)) =\prod_{i=1}^m\dfrac{2mt +i-1+t\delta}{2mt+2(i-1)+t\delta +1+{{i\delta}/{m}}} = \prod_{i=1}^m (1 - {\textrm{O}}(1/t))= 1-{\textrm{O}}\big(t^{-1}\big).\end{equation}

It is clear from the proof of Lemma 3.2 that, given X(t) and Y(t),

\[\mathbb P_m(a)\,:\!=\, \binom{m}{a}\dfrac{(Y(t)+\delta X(t))^{(a)} (2mt-Y(t)+\delta(t-X(t))^{(m-a)}}{((2m+\delta)t)^{(m)}}\]

is a probability distribution of a random variable D, a ‘rising-factorial’ counterpart of the binomial distribution $\mathcal D=\text{Bin}(m,p=Y(t)/2mt)$ . (We have not seen this distribution in the literature.) Define the falling factorial $(x)_{\ell}=x(x-1)\cdots (x-\ell+1)$ . It is well known that $\mathbb E[(\mathcal D)_{\mu}]=(m)_{\mu} p^{\mu}$ , $(\mu\le m)$ . For D we have

(3.4) \begin{align} \mathbb E[(D)_{\mu}]&=\sum_a(a)_{\mu} \mathbb P_m(a) \notag \\[3pt] &=\dfrac{(m)_{\mu}\,(Y(t)+\delta X(t))^{(\mu)}}{((2m+\delta)t)^{(\mu)}}\cdot \sum_{a\ge \mu}\binom{m-\mu}{a-\mu} \notag \\[3pt] &\quad \times \dfrac{(Y(t)+\delta X(t)+\mu)^{(a-\mu)}((2m+\delta)t+\mu-(Y(t)+\delta X(t)+\mu))^{((m-\mu)-(a-\mu))}}{(2mt+\mu)^{(m-\mu)}} \notag \\[3pt] &=\dfrac{(m)_{\mu}\,(Y(t)+\delta X(t))^{(\mu)}}{((2m+\delta)t)^{(\mu)}},\end{align}

since the sum over $a\ge \mu$ is $\sum_{\nu\ge 0}\mathbb P_{m-\mu}(\nu)=1$ .

By Lemma 3.2, (3.3), and (3.4),

(3.5) \begin{align}\mathbb E[Y(t+1)-Y(t)\mid\circ] &= \sum_{a=1}^m (a+m) \mathbb P_m(a) + {\textrm{O}}\big(t^{-1}\big) \notag \\[4pt]&= \biggl( \sum_{a=1}^m a \mathbb P_m(a) + \sum_{a=1}^m m \mathbb P_m(a) \biggr) + {\textrm{O}}\big(t^{-1}\big) \notag \\[4pt]&= \dfrac{m(Y(t)+\delta X(t))}{(2m+\delta)t}+ m\biggl(1-\dfrac{((2m+\delta)t-Y(t)-\delta X(t))^{(m)}}{((2m+\delta)t)^{(m)}}\biggr) +{\textrm{O}}\big(t^{-1}\big)\end{align}

and

\begin{equation*} \mathbb E[X(t+1)-X(t)\mid\circ]= 1-\dfrac{((2m+\delta)t-Y(t)-\delta X(t))^{(m)}}{((2m+\delta)t)^{(m)}} + {\textrm{O}}\big(t^{-1}\big),\end{equation*}

where ‘ $\circ$ ’ indicates conditioning on $G_{m,\delta}(t)$ . (Note that $X(t+1)=X(t)$ if and only if $Y(t+1)=Y(t)$ .)

To continue the proof of Theorem 2.2, we note first that $mX(t)\le Y(t)\le 2mX(t)$ . These inequalities follow from the fact that every time a vertex joins the descendant set, the total degree of the descendant set increases by an amount $m+a$ for some $a\in [m]$ . Let

\[p(t)\,:\!=\, \dfrac{2m}{2m+\delta}\,p_Y(t)+\dfrac{\delta}{2m+\delta}\,p_X(t),\]

where $p_Y(t)=Y(t)/(2mt)$ and $p_X(t)=X(t)/t$ as defined before. By the definition of p(t) and the above inequalities, we have

\begin{equation*} \dfrac{p_X(t)}{2}\le p_Y(t)\le p_X(t) \Longrightarrow \dfrac{m+\delta}{2m+\delta}\,p_X(t)\le p(t) \le p_X(t);\end{equation*}

in particular, $p(t)\in [0,1]$ since $\delta\ge -m$ . We will also need

\[\dfrac{((2m+\delta)t-Y(t)-\delta X(t))^{(m)}}{((2m+\delta)t)^{(m)}} = (1-p(t))^m +{\textrm{O}}\big(t^{-1}\big).\]

So, using (3.5), we compute

(3.6) \begin{equation} \begin{aligned}\mathbb E[p_Y(t+1) \mid \circ]&=\mathbb E\biggl[\dfrac{Y(t+1)}{2mt}\cdot \dfrac{t}{t+1}\Bigm| \circ\biggr] \\[3pt]&=\dfrac{t}{t+1} \biggl(p_Y(t)+\dfrac{1}{2t}\bigl[1+p(t)-(1-p(t))^m\bigr]+{\textrm{O}}\big(t^{-2}\big)\biggr) \\[3pt]&=p_Y(t)+q_Y(t), \\[3pt]q_Y(t)&\,:\!=\, \dfrac{1}{2(t+1)}\bigl[1+p(t)-2p_Y(t)-(1-p(t))^m\bigr]+{\textrm{O}}\big(t^{-2}\big).\end{aligned}\end{equation}

Likewise

(3.7) \begin{equation}\begin{aligned}\mathbb E[p_X(t+1)\mid\circ]&=p_X(t)+q_X(t),\\[3pt]q_X(t)&=\dfrac{1}{t+1}\bigl[1-p_X(t)-(1-p(t))^m\bigr]+{\textrm{O}}\big(t^{-2}\big).\end{aligned}\end{equation}

Multiplying (3.6) by ${{2m}/{(2m+\delta)}}$ and (3.7) by ${{\delta}/{(2m+\delta)}}$ , and adding them, we obtain

(3.8) \begin{equation}\begin{aligned}\mathbb E[p(t+1) \mid \circ]&=p(t) +q(t),\\[3pt]q(t)& \,:\!=\, \dfrac{m+\delta}{(2m+\delta)(t+1)}\bigl[1-p(t)-(1-p(t))^m\bigr]+{\textrm{O}}\big(t^{-2}\big).\end{aligned}\end{equation}

From the first line in (3.8) it follows that

\[\sum_{t=1}^{\tau}\mathbb{E}[p(t+1)]=\sum_{t=1}^{\tau}\mathbb{E}[p(t)]+\sum_{t=1}^{\tau}\mathbb{E}[q(t)],\]

implying that

\[\limsup_{\tau\to\infty}\sum_{t\le\tau} \mathbb E[q(t)]\le \limsup_{\tau\to\infty}\mathbb{E}[p(\tau+1)]\le 1.\]

Since $1-z-(1-z)^m\ge 0$ on [0, 1], the second line in (3.8) implies that $|q(t)|\le q(t)+{\textrm{O}}\big(t^{-2}\big)$ . Since $\sum_t t^{-2}<\infty$ , we see that $\sum_t\mathbb E[|q(t)|]<\infty$ .

So a.s. there exists $Q\,:\!=\, \lim_{\tau\to\infty}\sum_{1\le t\le \tau} q(t)$ , with $\mathbb E[|Q|]\le \sum_t\mathbb E[|q(t)|]<\infty$ , that is, a.s. $|Q|<\infty$ . Introducing $Q(t+1)=\sum_{\tau\le t}q(\tau) $ , we see from (3.8) that $\{p(t+1)-Q(t+1)\}_{t\ge 1}$ is a martingale with $\sup_t |p(t+1)-Q(t+1)|\le 1 + \sum_{\tau\ge 1} |q(\tau)|$ . By the martingale convergence theorem we obtain that there exists an integrable $\lim_{t\to\infty}(p(t)-Q(t))$ , implying that a.s. there exists a random $p(\infty)=\lim_{t\to\infty}p(t)$ . Equation (3.8) also implies that

\[1\ge \mathbb E[p(\infty)]=\dfrac{m+\delta}{2m+\delta}\sum_{t\ge 1}\dfrac{1}{t+1}\mathbb E\bigl[1-p(t)-(1-p(t))^m\bigr]+ {\textrm{O}}(1).\]

Since $m+\delta>0$ and

\[\lim_{t\to\infty} \mathbb E\bigl[1-p(t)-(1-p(t))^m\bigr] =\mathbb E\bigl[1-p(\infty)-(1-p(\infty))^m\bigr],\]

and the series $\sum_{t\ge 1} t^{-1}$ diverges, we obtain that $\mathbb P(p(\infty)\in \{0,1\})=1$ .

Recall that

\[p(t)\ge \frac{m+\delta}{2m+\delta}\, p_X(t).\]

If we show that a.s. $\liminf_{t\to\infty}p_X(t)>0$ , it will follow that a.s. $p(\infty)>0$ , whence a.s. $p(\infty)=1$ , implying (by $p(t)\le p_X(t)$ ) that a.s. $p_X(\infty)$ exists, and is 1, and consequently (by the formula for p(t)) a.s. $p_Y(\infty)$ exists, and is 1.

So let us prove that a.s. $\liminf_{t\to\infty}p_X(t)>0$ . Recall that we did prove the latter for $m=1$ . To transfer this earlier result to $m>1$ we need to establish some kind of monotonicity with respect to m. The coupling described in Section 2 comes to the rescue!

Proof. Let us simply write $G_1$ and $G_m$ for the two graphs $G_{1,\delta/m}(mt)$ and $G_{m,\delta}(t)$ , respectively. Similarly, write $T_1$ and $T_m$ , respectively, for the descendant tree in $G_{1,\delta/m}(mt)$ rooted at mr and the descendant tree in $G_{m,\delta}(t)$ rooted at r. If $v_a\in T_1$ , i.e. $v_a$ is a descendant of mr, then for $b=\lceil a/m \rceil $ we have $w_b=\{v_{m(b-1)+i}\}_{i\in [m]}\ni v_a$ , implying that $w_b$ is a descendant of r in $G_m$ , i.e. $w_b\in T_m$ . (The converse is generally false: if $w_b$ is a descendant of r, it does not mean that every $v_{m(b-1)+i}$ , ( $i\in [m]$ ), is a descendant of mr.) Therefore

\begin{equation*}\qquad\quad\qquad\qquad X_{m,\delta}(t,r)=|V(T_m)|\ge m^{-1} |V(T_1)|=m^{-1}X_{1,\delta/m}(mt,mr).\qquad\qquad\qquad\quad\end{equation*}

Thus, to complete the proof of the theorem, i.e. for $\delta>-m$ , we (a) use Theorem 2.1, to assert that for the process $\{G_{1,\delta/m}(t)\}$ , a.s. $\lim_{t\to\infty} p_X (t)>0$ , (b) use Lemma 3.3, to assert that a.s. $\liminf_{t\to\infty} p_X (t)>0$ for $\{G_{m,\delta}(t)\}$ as well. The proof of Theorem 2.2 is complete.

3.3. Proof of Theorem 2.3

Proof. By the definition of the UAM process, we have

(3.9) \begin{equation}\mathbb{P}(X(t+1)=X(t)+1 \mid \circ)= 1 - (1-p_X(t))^m.\end{equation}

Case (i). Consider $m=1$ . For $r=1$ , we have $p(t)\equiv 1$ . Consider $r\ge 2$ . Equation (3.9) is the case $\delta=-1$ , $\gamma=0$ of (3.1). By Lemma 3.1, we claim that

\[M(t)\,:\!=\, \dfrac{(X(t))^{(\ell)}}{t^{(\ell)}}\]

is a martingale. So arguing as in the proof of Theorem 2.1, we obtain that almost surely (a.s.) $\lim p_X(t)=p_X(\infty)$ exists, and the limiting distribution of $p_X(\infty)$ is a beta distribution with parameters $a=1$ and $b=r$ . That is, the limiting density is $r(1-x)^{r-1}$ , $x\in [0,1]$ . Therefore a.s. $\lim p_X(t)>0$ .

Case (ii). Consider $m>1$ . Clearly $G_1(t)\subset G_m(t)$ . Therefore a.s. $\liminf p_X(t)>0$ as well. Furthermore, it follows from (3.9) that

\[\mathbb{E}[p_X(t+1)\mid\circ]= p_X(t)+\dfrac{1}{t+1}\bigl[1-p_X(t)-(1-p_X(t))^m\bigr]\]

(as before, ‘ $ \mid \circ)$ ’ means conditioning on $G_m(t)$ ), which is a special case of (3.8), with ${\textrm{O}}\big(t^{-2}\big)$ dropped. So we obtain that $\mathbb{P}(p(\infty)\in \{0,1\})=1$ , which in combination with $\mathbb{P}(p_X(\infty)>0)=1$ implies that $\mathbb{P}(p_X(\infty)=1)=1$ .

5.1. The PAM case

Theorem 2.4. Let $X\big(t\big)$ be the number of unmatched vertices at time t in the greedy matching algorithm. For $\delta>-m$ , let $\rho_{m,\delta}$ be the unique root in $ (0,1)$ of

(5.1) \begin{equation}h(z)=h_{m,\delta}(z)\,:\!=\, 2\biggl[1-\biggl(\dfrac{m+\delta}{2m+\delta}\biggr) z\biggr]^m-z-1.\end{equation}

Then, for any $\alpha<1/3$ , almost surely

\begin{equation*} \lim_{t\to\infty} t^{\alpha}\max\{0, x(t)-\rho_{m,\delta}\}=0.\end{equation*}

In consequence, the greedy matching algorithm a.s. finds a sequence of nested matchings $\{M(t)\}$ , where the number of vertices in $M\big(t\big)$ is asymptotically at least $(1-\rho_{m,\delta})t$ .

Proof. Notice first that for $\delta>-m$ the function h(z) is decreasing on (0, 1) and $h(z)=0$ does have a unique solution in the same interval.

We will prove our claim first for a slightly different model that does not allow any loops other than at the first vertex. In this model, vertex 1 has m loops, and the ith edge of vertex $t+1$ attaches to $u\in [t]$ with probability

\[\dfrac{d_{t,i-1}(u)+\delta}{2mt+2(i-1)+t\delta}.\]

Loops not allowed except at vertex 1. In this case, since each degree is at least m, we have $Y(t)\ge mX(t)$ and hence $y(t)\ge x(t)/2$ . Also, since

\[X(t+1)=\begin{cases}X(t)+1 & \text{if $ U(t)=0$,}\\X(t)-1 & \text{if $ U(t)>0$,}\end{cases}\]

we have

(5.2) \begin{equation}\mathbb E[X(t+1) \mid \circ]= X(t)+ \mathbb P(U(t)=0 \mid \circ)-\mathbb P(U(t)>0 \mid \circ).\end{equation}

Since $\mathbb P(\text{vertex}\ t + 1\ \textrm{has some loop})= {\textrm{O}}\big(t^{-1}\big)$ , using $Y(t)\ge mX(t)$ in the last step below, by Lemma 3.2 we get

(5.3) \begin{align}\mathbb P(U(t)=0 \mid \circ)&= \mathbb P(U(t)=0 \text{ and vertex $t+1$ has no loop} \mid \circ) +{\textrm{O}}\big(t^{-1}\big) \notag\\&= (1-{\textrm{O}}\big(t^{-1}\big))\dfrac{(2mt-Y(t)+\delta t-\delta X(t))^{(m)}}{(2mt+\delta t)^{(m)}}+{\textrm{O}}\big(t^{-1}\big) \notag\\&=\dfrac{(2mt+\delta t-Y(t)-\delta X(t))^{m}}{(2mt+\delta t)^{m}}+{\textrm{O}}\big(t^{-1}\big) \notag\\&=\biggl( 1-\dfrac{2m}{2m+\delta}\,y(t)-\dfrac{\delta}{2m+\delta}\,x(t)\biggr)^m+{\textrm{O}}\big(t^{-1}\big) \notag \\&\le \biggl(1-\dfrac{m+\delta}{2m+\delta}\,x(t)\biggr)^m+ {\textrm{O}}\big(t^{-1}\big).\end{align}

Using (5.2) and (5.3) gives

(5.4) \begin{align}\mathbb E[x(t+1) \mid \circ] &\le x(t)+ \dfrac1t\biggl[2\biggl( 1-\dfrac{m+\delta}{2m+\delta}\,x(t)\biggr)^m-x(t)-1\biggr] +{\textrm{O}}\big(t^{-2}\big) \notag \\[3pt]&=x(t)+\dfrac{1}{t}h(x(t))+{\textrm{O}}\big(t^{-2}\big),\end{align}

where h(z) is as defined in (5.1). Note that $X(0) = 0$ and h(z) satisfies the conditions given in Lemmas 4.1 and 4.2, namely $h(0)>0$ , $h(1)<0$ , and $h'(z) <- 1$ for $z\in (0,1)$ . The conclusion of the theorem follows from the first part of Lemma 4.2 in this case.

Loops allowed everywhere. The above analysis is carried over to this more complicated case via an argument similar to that for the descendant trees in Section 2.1.Here is a proof sketch. First, the counterpart of (5.3) is

\begin{align*}&\mathbb P(\{U(t)=0\}\cap \{\text{no loops at }t+1\} \mid \circ)\\&\quad =\Pi_m(t)\prod_{j=0}^{m-1}\biggl(\dfrac{2mt-Y(t)+\delta t-\delta X(t)+j}{2mt+2j+1+\delta t+(j+1)\,\delta/m}\biggr)\\&\quad \le \Pi_m(t)\biggl[\biggl(1-\dfrac{m+\delta}{2m+\delta}\,x(t)\biggr)^m+ {\textrm{O}}\big(t^{-1}\big)\biggr]\\&\quad =\big(1-{\textrm{O}}\big(t^{-1}\big)\big)\biggl[\biggl(1-\dfrac{m+\delta}{2m+\delta}\,x(t)\biggr)^m+ {\textrm{O}}\big(t^{-1}\big)\biggr]\\&\quad = \biggl(1-\dfrac{m+\delta}{2m+\delta}\,x(t)\biggr)^m+{\textrm{O}}\big(t^{-1}\big);\end{align*}

see (3.3) for $\Pi_m(t)$ . Therefore we again obtain (5.4). The rest of the proof remains the same.

Remark 5.1. Let $r=r_{m,\delta}\,:\!=\, 1-\rho_{m,\delta}$ , where $\rho_{m,\delta}$ is the unique root in (0, 1) of

\[h(z)=h_{m,\delta}(z)\,:\!=\, 2\biggl[1-\biggl(\dfrac{m+\delta}{2m+\delta}\biggr)z\biggr]^m-z-1.\]

Then r is the unique root in (0, 1) of

\[f(z)=f_{m,\delta}(z)\,:\!=\, 2-z-2\biggl(\dfrac{m}{2m+\delta}+\dfrac{m+\delta}{2m+\delta}\,z\biggr)^m.\]

Thus, by Theorem 2.4, we have

\[\liminf (1-x(t)) \ge r\]

almost surely, where $1-x(t)$ is the fraction of the vertices in M(t). See (2.3) for various r values when $\delta=0$ .

5.2. The UAM case

Theorem 2.5. Let $M\big(t\big)$ denote the greedy matching set after t steps of the UAM process. Let $r_m$ denote the unique positive root of $2(1-z^m) -z=0$ , i.e. $r_m=1-m^{-1}\log 2+{\textrm{O}}\!\left(m^{-2}\right)$ . Then, for any $\alpha<1/3$ , almost surely

\[\lim_{t\to\infty} t^{\alpha}\bigg| \dfrac{2|M(t)|}{t}-r_m\bigg|=0.\]

Proof. Let $X(t) = t-2|M(t)|$ as before. In particular, we have $X(0)=0$ and $X(1)=1$ . At each step $t\ge 2$ we check the edges incident to vertex t. If some of the edges end at vertices that do not belong to M(t), then we choose the largest (youngest) of those vertices, say w, and set $M(t)\,:\!=\, M(t-1)\cup \{(t,w)\}$ and $X(t)=X(t-1)-1$ . Otherwise $M(t)=M(t-1)$ and $X(t)=X(t-1)+1$ . Let $x(t)=X(t)/t$ be the fraction of unmatched vertices after step t. Then X(t) is a Markov chain with

\[\mathbb{P}({X(t+1)-X(t) =1 \mid X(t)}) = (1-x(t))^m ,\]

since for $X(t+1)-X(t) =1$ to happen, each of the m choices made by vertex $t+1$ must lie outside of M(t), the probability of each such choice is $1-x(t)$ , and the choices are independent of each other. With the remaining probability vertex $t+1$ chooses at least one of m vertices from X(t), in which case X(t) decreases by 1. Consequently

\[{\mathbb{E}[{X(t+1)\mid \circ}]} = X(t) + (1-x(t))^m - \left(1-(1-x(t))^m\right) = X(t) +2(1-x(t))^m-1.\]

Dividing both sides by $t+1$ , we obtain

\[{\mathbb{E}[{x(t+1) \mid \circ}]} = x(t) + \dfrac{h(x(t))}{t+1} - {\textrm{O}}\!\left(1/t^2\right),\]

where $h(z) = 2(1-z)^m-z-1$ . The function h meets the conditions of the second part of Lemma 4.2. Hence $\lim_{t\to\infty} t^{\gamma}|x(t)-\rho_m| = 0$ a.s. On the other hand, if $\rho_m$ is the unique root of h in (0, 1), then $r_m\,:\!=\, 1-\rho_m$ is the unique root of $2(1-z^m)-z$ in (0, 1). Since $x(t)-\rho_m = (1 -2 |M(t)|/t) - (1-\rho_m) = \rho_m -2 |M(t)|/t$ , we also have a.s.

\[\lim_{t\to\infty} t^{\gamma}\bigl|2|M(t)|/t-r_m\bigr| = 0.\]

This completes the proof.

6.1. The PAM case

Theorem 2.6. Let $w_m$ denote the unique root of $-w+(1-w)^m$ in $ (0, 1)$ . For any

\[ \chi\in \biggl(0,\min\biggl\{\dfrac{1}{3},\dfrac{2m+2\delta}{3(2m+\delta)}\biggr\}\biggr), \]

almost surely

\begin{equation*} \lim_{t\to\infty}t^{\chi}\bigg|\dfrac{|I(t)|}{t}-w_m\bigg|=0.\end{equation*}

Proof. By the definition of the algorithm, we have

\[|I(t+1)|=\begin{cases}|I(t)|+1 &\text{with probability $\mathbb{P}(U(t)=0 \mid \circ)$,}\\|I(t)| &\text{with probability $\mathbb{P}(U(t)>0 \mid \circ)$.}\end{cases}\]

Now $U(t)=0$ means that vertex $t+1$ selects all m vertices from the outsiders set, so that

\begin{align*}\mathbb{P}(U(t)=0 \mid \circ)&=\dfrac{(Y(t)+\delta X(t))^{(m)}}{((2m+\delta)t)^{(m)}}+{\textrm{O}}\big(t^{-1}\big)\\&=\biggl(\dfrac{2my(t)+\delta x(t)}{2m+\delta}\biggr)^m +{\textrm{O}}\big(t^{-1}\big)\\&=\biggl(1-\dfrac{m+\delta}{2m+\delta}\, i(t)-\dfrac{m}{2m+\delta}\,z(t)\biggr)^m +{\textrm{O}}\big(t^{-1}\big).\end{align*}

The leading term in the first equality is the exact (conditional) probability of $\{U(t)=0\}$ when no loops at vertices other than the first vertex are allowed, and the extra ${\textrm{O}}\big(t^{-1}\big)$ is for our more general case when the loops are admissible. So, using $i(t)=|I(t)|/t$ , we have

(6.1) \begin{multline}\mathbb{E}[i(t+1) \mid \circ]=i(t)+\dfrac{1}{t+1}\biggl[-i(t)+\biggl(1-\dfrac{m+\delta}{2m+\delta} i(t)-\dfrac{m}{2m+\delta}z(t)\biggr)^m\biggr]+{\textrm{O}}\big(t^{-2}\big).\end{multline}

Now $Z(t+1)=Z(t)+U(t)$ , so that

\begin{align*}\mathbb{E}[Z(t+1) \mid \circ]&= Z(t) +\mathbb{E}[U(t) \mid \circ]\\&=Z(t)+m\dfrac{I(t)(m+\delta)+Z(t)}{(2m+\delta)t}+{\textrm{O}}\big(t^{-1}\big),\end{align*}

and using $z(t)=Z(t)/mt$ , we have

(6.2) \begin{align}\mathbb{E}[z(t+1) \mid \circ]=z(t) +\dfrac{1}{t+1}\biggl[-z(t) + \biggl(i(t)\dfrac{m+\delta}{2m+\delta}+z(t)\dfrac{m}{2m+\delta}\biggr)\biggr] +{\textrm{O}}\big(t^{-2}\big).\end{align}

Introduce

\[w(t)=i(t)\dfrac{m+\delta}{2m+\delta}+z(t)\dfrac{m}{2m+\delta}.\]

Multiplying (6.1) and (6.2) by ${{(m+\delta)}/{(2m+\delta)}}$ and ${{m}/{(2m+\delta)}}$ and adding the products, we obtain

(6.3) \begin{equation}\begin{aligned}\mathbb{E}[w(t+1) \mid \circ]&=w(t)+\dfrac{f(w(t))}{t+1}+{\textrm{O}}\big(t^{-2}\big),\\f(w)&\,:\!=\, \dfrac{m+\delta}{2m+\delta}\bigl[-w+(1-w)^m\bigr].\end{aligned}\end{equation}

The function f is qualitatively similar to the function h in the proof of Theorem 2.4. Indeed, f(w) is strictly decreasing, with $f(0)=1$ and $f(1)=-1$ . Therefore f(w) has a unique root $w_m\in (0,1)$ ; it is not difficult to see that

\[w_m=\dfrac{\log m}{m}[1+{\textrm{O}}(\!\log\log m/\log m)],\quad m\to\infty.\]

Let us prove that for any

\[\alpha< c(m,\delta)\,:\!=\, \min\biggl\{1,\dfrac{2m+2\delta}{2m+\delta}\biggr\}\quad (\subseteq (0,1])\]

and $A\ge A(\alpha)$ we have

(6.4) \begin{equation}\mathbb{E}\bigl[(w(t)-w_m)^2\bigr]\le A t^{-\alpha},\end{equation}

First

(6.5) \begin{align}|i(t+1)-i(t)|&=\bigg|\dfrac{|I(t+1)|}{t+1}-\dfrac{|I(t)|}{t}\bigg| \notag \\&\le \dfrac{1}{t+1}(|I(t+1)|-|I(t)|) +\dfrac{|I(t+1)|}{t+1}\notag \\&\le \dfrac{2}{t+1},\end{align}

and similarly

\begin{equation*}|z(t+1)-z(t)|\le \dfrac{2}{t+1}.\end{equation*}

Therefore $|w(t+1)-w(t)|\le 2/(t+1)$ , and consequently

\[(w(t+1)-w_m)^2\le (w(t)-w_m)^2+\dfrac{4}{t^2}+2(w(t)-w_m) (w(t+1)-w(t)).\]

So, conditioning on prehistory, we have

\begin{align*}\mathbb{E}\bigl[(w(t+1)-w_m)^2 \mid \circ\bigr]&\le (w(t)-w_m)^2+2(w(t)-w_m) \mathbb{E}[w(t+1)-w(t) \mid \circ] +{\textrm{O}}\big(t^{-2}\big)\\&=(w(t)-w_m)^2 +\dfrac{2(w(t)-w_m)}{t+1} f(w(t))+{\textrm{O}}\big(t^{-2}\big).\end{align*}

By (6.3),

\[f'(w)\le -\dfrac{m+\delta}{2m+\delta}.\]

Therefore, with

\[c(m,\delta)=\dfrac{2m+2\delta}{2m+\delta},\]

the last inequality gives

\[\mathbb{E}\bigl[(w(t+1)-w_m)^2 \mid \circ\bigr]\le \biggl(1-\dfrac{c(m,\delta)}{t+1}\biggr) (w(t)-w_m)^2 +{\textrm{O}}\big(t^{-2}\big),\]

leading to a recursive inequality

(6.6) \begin{equation}\mathbb{E}\bigl[(w(t+1)-w_m)^2\bigr]\le \biggl(1-\dfrac{c(m,\delta)}{t+1}\biggr)\mathbb{E}\bigl[(w(t)-w_m)^2\bigr] +{\textrm{O}}\big(t^{-2}\big).\end{equation}

The bound (6.4) follows from (6.6) by a straightforward induction on t. Next we use (6.4) to prove that, for $A_1$ large enough,

(6.7) \begin{equation}\mathbb{E}\bigl[(i(t+1)-w_m)^2 \mid \circ\bigr]\le A_1 t^{-\alpha}.\end{equation}

Using (6.5), we have

\[(i(t+1)-w_m)^2\le (i(t)-w_m)^2+\dfrac{4}{t^2}+2(i(t)-w_m) (i(t+1)-i(t)).\]

Consequently

\begin{align*}\mathbb{E}\bigl[(i(t+1)-w_m)^2 \mid \circ\bigr]&\le (i(t)-w_m)^2+2(i(t)-w_m) \mathbb{E}[i(t+1)-i(t) \mid \circ] +{\textrm{O}}\big(t^{-2}\big)\\&=(i(t)-w_m)^2 +\dfrac{2(i(t)-w_m)}{t+1} [-i(t)+(1-w(t))^m]+{\textrm{O}}\big(t^{-2}\big).\end{align*}

Taking expectations of both sides, and using Cauchy’s inequality and (6.4), we obtain

\begin{align*}\mathbb{E}\bigl[(i(t+1)-w_m)^2\bigr]&\le \biggl(1-\dfrac{2}{t+1}\biggr)\mathbb{E}\bigl[(i(t)-w_m)^2\bigr]\\&\quad\, +\dfrac{2}{t+1}\mathbb{E}^{1/2}\bigl[(i(t)-w_m)^2\bigr]\,\mathbb{E}^{1/2}\bigl[(w_m-(1-w(t))^m)^2\bigr]+{\textrm{O}}\big(t^{-2}\big)\\&\le \biggl(1-\dfrac{2}{t+1}\biggr)\mathbb{E}\bigl[(i(t)-w_m)^2\bigr] +\dfrac{2mA^{1/2}}{t^{1+\alpha/2}}\mathbb{E}^{1/2}\bigl[(i(t)-w_m)^2\bigr]+{\textrm{O}}\big(t^{-2}\big),\end{align*}

since $w_m=(1-w_m)^m$ , and

\[|(1-w(t))^m - (1-w_m)^m|\le m|w(t)-w_m|.\]

So it suffices to show the existence of $A_1$ such that

\[\biggl(1-\dfrac{2}{t+1}\biggr) A_1 t^{-\alpha}+\dfrac{2mA^{1/2} A_1^{1/2}t^{-\alpha/2}}{t^{1+\alpha/2}}+{\textrm{O}}\big(t^{-2}\big)\le A_1 (t+1)^{-\alpha}\]

holds for $t>t_0$ , where $t_0$ depends only on A and $\alpha$ . For large t, the above inequality becomes

\[2mA^{1/2}A_1^{1/2}+{\textrm{O}}(t^{-1-\alpha})\le A_1[(2-\alpha)+{\textrm{O}}\big(t^{-1}\big)]+{\textrm{O}}(t^{-1+\alpha}),\]

and

\[A_1> A\biggl(\dfrac{2m}{2-\alpha}\biggr)^2\]

does the job. So (6.7) is proved. Therefore, by Markov’s inequality,

(6.8) \begin{equation}\mathbb{P}(|i(t)-w_m|\ge t^{-\chi})\le At^{-\alpha+2\chi}\to 0,\quad\chi\in (0,\alpha/2).\end{equation}

This inequality already means that $i(t)\to w_m$ in probability. Let us show the considerably stronger statement that $i(t)\to w_m$ with probability 1, at least as fast as $t^{-\chi}$ , for any given $\chi<1/3$ . Pick $\beta>1$ and introduce a sequence $\{t_{\nu}\}$ , $t_{\nu}=\lfloor \nu^{\beta}\rfloor$ . By (6.8), we have

\begin{align*}\sum_{\nu\ge 1}\mathbb{P}(|i(t_{\nu})-w_m|\ge t_{\nu}^{-\chi})&\le \sum_{\nu\ge 1}A_1t_{\nu}^{-\alpha+2\chi}={\textrm{O}}\biggl(\,\sum_{\nu\ge 1}\nu^{-\beta (\alpha-2\chi)}\biggr)<\infty,\end{align*}

provided that $\beta>(\alpha-2\chi)^{-1}$ , which we assume from now. For such choice of $\beta$ , by the Borel–Cantelli lemma with probability 1 for all but finitely many $\nu$ , we have $|i(t_{\nu})-\rho|\le t_{\nu}^{-\chi}$ . Let $t\in [t_{\nu}, t_{\nu+1}]$ . By (6.5), we have

\[|i(t)-i(t_{\nu}))|={\textrm{O}}\biggl(\dfrac{t_{\nu+1}-t_{\nu}}{t_{\nu}}\biggr)\]

uniformly for all $\nu$ . So if $|i(t_{\nu})-\rho|\le t_{\nu}^{-\chi}$ , then (using $t_{\nu}=\Theta\big(\nu^{\beta}\big)$ ) we have, for $t\in [t_{\nu},t_{\nu+1}]$ ,

\begin{align*}|i(t)-w_m|&\le t_{\nu}^{-\chi}+{\textrm{O}}\biggl(\dfrac{t_{\nu+1}-t_{\nu}}{t_{\nu}}\biggr)\\&={\textrm{O}}\left(\nu^{-\beta\chi}+\nu^{-1}\right)\\&={\textrm{O}}\left(\nu^{-\min(\beta\chi,1)}\right)\\&={\textrm{O}}\left(t^{-\min(\chi,\beta^{-1})}\right).\end{align*}

Since $|i(t_{\nu})-w_m|\le t_{\nu}^{-\chi}$ holds almost surely (a.s.) for all but finitely many $\nu$ , we see then that a.s. so does the bound $|i(t)-w_m|={\textrm{O}}(t^{-\min(\chi,\beta^{-1})})$ for all but finitely many t. Now, by taking $\beta$ sufficiently close to $(\alpha-2\chi)^{-1}$ from above, we can make $\min(\chi,\beta^{-1})$ arbitrarily close to $\min(\chi, \alpha-2\chi)$ from below. It remains to notice that $\min(\chi, \alpha-2\chi)$ attains its maximum $\alpha/3$ at $\chi=\alpha/3$ . The proof of Theorem 2.6 is complete.

6.2. The UAM case

Theorem 2.7. Let $w_m$ be the unique root of $-w+(1-w)^m$ in $ (0, 1)$ . Then, for any $\alpha<1/3$ , almost surely

\[\lim_{t\to\infty}t^{\alpha}\bigg|\dfrac{|I(t)|}{t} - w_m\bigg|=0.\]

The following remark is already stated as Remark 2.3.

Proof. Let $i(t)=|I(t)|/t$ . From the definition of the UAM process and the greedy independent set algorithm, we obtain

\[|I(t+1)|=\begin{cases}|I(t)|+1 &\text{with conditional probability $ (1-i(t))^m$,}\\|I(t)| &\text{with conditional probability $ 1-(1-i(t))^m$.}\end{cases}\]

Therefore

\[\mathbb{E} [|I(t+1)|\mid \circ ]=|I(t)| +(1-i(t))^m,\]

or equivalently

\[\mathbb{E}[i(t+1) \mid \circ]=i(t)+\dfrac{1}{t+1} [-i(t)+(1-i(t))^m ].\]

The function $-x+(1-x)^m$ differs by a constant positive factor from the function f in (6.3). The function f meets the conditions of Lemma 4.1, and $r_m$ is a unique root of f. Therefore, for any $\alpha<1/3$ , a.s. $\lim_{t\to\infty} t^{\alpha}|i(t)-r_m|=0$ .