## On the evolution in the configuration model ∗

Ton´ ci Antunovi´ c University of California, Los Angeles tantunovic@math.ucla.edu

## Abstract

We give precise estimates on the number of active/inactive half-edges in the configuration model used to generate random regular graphs. This is obtained by analyzing a more general urn model with negative eigenvalues.

## 1 Introduction and statements or results

Random d -regular graph, a random graph obtained by sampling uniformly a d -regular vertex labeled simple graph on n vertices (for even nd ), is an important random graph model. While for d = 2 the resulting graph is a union of disjoint cycles (and in particular disconnected with high probability), for d ≥ 3 the random regular graph, with probability converging to 1 (as n → ∞ ) is connected, and even has Hamiltonian cycles. Furthermore, for d ≥ 3 it looks fundamentally different from a d -dimensional torus, in particular it is an expander, locally tree-like and has bounded number of cycles of fixed length (for more properties, proofs and references to the original work see [4, 5]). One of the main tools used for both generating and studying random regular graphs is the configuration model introduced by Bollob´s in [3]. This is an algorithm which can be described as follows. a Start with n disconnected labeled vertices each equipped with d half-edges. Select an arbitrary vertex and mark it and it's half-edges as active, and label all other vertices and half-edges as inactive. At each stage of the algorithm choose in some way a labeled half-edge e and connect it with a uniformly selected half-edge f (active or not), and mark them both as used. If f corresponds to an inactive vertex, also label this vertex and all its half-edges (except f ) as active. When all half-edges are connected, collapse the connected half-edges to edges. The algorithm generates a random graph which might not be simple if two half-edges incident to the same vertex get connected, or there are two connections of half-edges incident to the same pair of vertices. However, conditioned on the event that the random graph is simple, it has the distribution of the random regular graph. Moreover, the probability that the graph produced by the configuration model is simple, is bounded away from zero as n →∞ and d is fixed (see [3], and an earlier related work [2]).

Denote by A n and I n the number of active and inactive half-edges after the n -th step respectively (the number of used half-edges is clearly 2 n ). Then it is easy to see that when I n ≥ 1, A n ≥ 1

$$\mathbb { P } ( I _ { n + 1 } = I _ { n } - d, A _ { n + 1 } = A _ { n } + d - 2 ) = \frac { I _ { n } } { A _ { n } + I _ { n } - 1 }$$

∗ Keywords: random regular graphs, configuration model. MSC classification: 05C80, 60J10

and

$$\mathbb { P } ( I _ { n + 1 } = I _ { n }, A _ { n + 1 } = A _ { n } - 2 ) = \frac { A _ { n } - 1 } { A _ { n } + I _ { n } - 1 }.$$

Therefore the process ( I n , A n -1) n is an urn model with the replacement matrix

$$A = \left ( \begin{array} { c c } - d & d - 2 \\ 0 & - 2 \end{array} \right ) \.$$

In the present paper we will give precise estimates on the behavior of the process ( I n , A n ). The results will be indispensable for the analysis of a competing multi-type version of a first passage percolation process on random regular graphs performed in [1]. To analyze the process ( I n , A n ) we will consider a more general urn model with the replacement matrix

$$A = \left ( \begin{array} { c c } - b & b - a \\ 0 & - a \end{array} \right )$$

for real valued 0 &lt; a &lt; b . The corresponding urn process ( X ,Y n n n ) (which has the same distribution as ( I n , A n -1) n for a = 2 and b = d ) is a Markov chain with the transition probabilities

$$\mathbb { P } ( X _ { n + 1 } = X _ { n } - b, Y _ { n + 1 } = Y _ { n } + b - a ) & = \frac { X _ { n } } { X _ { n } + Y _ { n } } \\ \mathbb { P } ( X _ { n + 1 } = X _ { n }, Y _ { n + 1 } = Y _ { n } - a ) & = \frac { Y _ { n } } { X _ { n } + Y _ { n } }.$$

The process stops at a random time ρ defined as the first time n such that X n &lt; 0 or Y n &lt; 0 or X n + Y n = M -an ≤ 0, where M = X 0 + Y 0 ( X n = X ρ , Y n = Y ρ for n ≥ ρ ). Observe that ρ is a stopping time with respect to the natural filtration F n induced by the outcomes of the first n draws.

When a and b are integers it can be described as follows. Start with X 0 blue and Y 0 red balls in an urn. Draw a ball from the urn uniformly at random. If the drawn ball is blue return it into the urn and then add b -a red balls into the urn and remove b blue balls. If the drawn ball is red return it into the urn and remove a red balls from the urn. Stop when the urn contains no more balls, or when the number of balls of some type in the urn becomes 'negative'. Then X n and Y n stand for the number of blue and red balls in the urn after n draws. In the discussion that follows we will use 'the ball terminology' even when dealing with non-integer values of a and b .

Since the number of blue balls X n can decrease only by b , we will always assume that X 0 is a multiple of b (this in particular holds in the configuration model where X 0 = ( n -1) d is divisible by d ). Having this assumption, the value of X n can not become negative, and then ρ is the smallest integer n such that either Y n &lt; 0 or X n + Y n = M -an ≤ 0. Observe that at each step the sum X n + Y n decreases by a (we remove exactly a balls), that is X n + Y n = M -an , so a natural assumption could be that M = X 0 + Y 0 is a multiple of a . However, as Corollary 1.3 shows with probability converging to 1 (as M → ∞ and a and b stay fixed) blue balls indeed get exhausted before the red ones, after which the process is deterministic and consists of removing the leftover red balls. Therefore, with probability converging to 1 we have M -aρ ≤ 0 and then the assumption that M is a multiple of a only affects the final number of balls M -aρ by being either equal to zero or negative. For these reasons we will not assume that M is a multiple of a . The configuration model does not satisfy the assumption that M = nd -1 is a multiple of a = 2 anyway. Furthermore,

the discussion above shows that the process is most interesting when the initial number of blue balls X 0 is large.

Using the notation and terminology described above we state our results. Our first result concerns with the number of blue balls in the urn. It provides estimates on the time when the blue balls are exhausted, as well as the number of balls except shortly before the exhaustion time. In particular it shows that blue blue balls get exhausted when the number of leftover red balls is O (1) MX -a/b 0 . Furthermore, as long as the number of blue balls X n is large, it behaves as X n = (1 ± o (1)) X 0 (1 -an/M ) b/a .

In the rest of the paper we use the notation C = C a, b ( ) for a strictly positive finite constant C which only depends on the values of parameters a and b .

## Theorem 1.1. Consider the process

$$K _ { n } = \frac { X _ { n } } { X _ { 0 } ( 1 - a n / M ) ^ { b / a } }$$

and the stopping time τ X ,M 0 ≤ ∞ as the smallest integer n such that X n = 0 . For fixed ε &lt; 1 2 / and t &gt; 0 define the integer

$$n _ { t } = \lfloor M ( 1 - t X _ { 0 } ^ { - a / b } ) / a \rfloor.$$

and the event

$$\mathbf K _ { X _ { 0 }, M, t, \varepsilon } = \{ \rho > n _ { t } \ a n d \ | K _ { n } - 1 | \leq \varepsilon \text{ for all } 0 \leq n \leq n _ { t } \}.$$

Then there exists a constant C = C a, b ( ) such that

$$\mathbb { P } ( \mathbf K _ { X _ { 0 }, M, t, \varepsilon } ) \geq 1 - \frac { C } { t ^ { b / a } \varepsilon ^ { 2 } }, \text{ for all } \ t \geq \frac { C X _ { 0 } ^ { a / b } } { M \varepsilon },$$

and

$$\mathbb { P } ( \tau _ { X _ { 0 }, M } \geq n _ { t } ) \leq C t ^ { b / ( 2 b - a ) }, \text{ for all } \ t \geq \frac { b X _ { 0 } ^ { a / b } } { M }.$$

The above estimates can be stated without introducing the variable t . The estimate in (1.3) can be written as follows: for any n such that M -an ≥ C/glyph[epsilon1] we have both ρ &gt; n and | K k - | ≤ 1 glyph[epsilon1] for all 0 ≤ k ≤ n with probability at least

$$1 - \frac { C } { X _ { 0 } ( 1 - a n / M ) ^ { b / a } \epsilon ^ { 2 } }.$$

The estimate in (1.4) can be written as follows: for any n such that M -an ≥ b we have

$$\mathbb { P } ( \tau _ { X _ { 0 }, M } \geq n ) \leq C X _ { 0 } ^ { a / ( 2 b - a ) } ( 1 - a n / M ) ^ { b / ( 2 b - a ) }.$$

In particular the estimate (1.6) gives the bound for all relevant values of n .

The following two corollaries are straightforward from Theorem 1.1.

Corollary 1.2. For a positive real number m define σ m as the first time n such that X n ≤ m . There is a constant C = C a, b ( ) such that for every glyph[epsilon1] &lt; 1 2 / with probability at least 1 -C mε 2 hold both ρ &gt; σ m and that

$$( 1 - \epsilon ) X _ { 0 } \left ( 1 - \frac { a k } { M } \right ) ^ { b / a } \leq X _ { k } \leq ( 1 + \epsilon ) X _ { 0 } \left ( 1 - \frac { a k } { M } \right ) ^ { b / a }, \text{ \ for all } k \leq \sigma _ { m }.$$

Denote by R the event that the process doesn't end before blue balls are exhausted, that is R = { M -aρ ≤ } 0 .

Corollary 1.3. There exist a positive constant C = C a, b ( ) such that

$$\mathbb { P } ( \mathbf R ) \geq 1 - \frac { C X _ { 0 } ^ { a / ( 2 b - a ) } } { M ^ { b / ( 2 b - a ) } } \geq 1 - \frac { C } { M ^ { ( b - a ) / ( 2 b - a ) } }.$$

The second result gives the estimate on the number of red balls Y n . As the previous theorem shows it is close to

$$( M - a n ) - X _ { 0 } \left ( 1 - \frac { a n } { M } \right ) ^ { b / a }.$$

The following result shows that this estimate holds throughout the process life-time and, as in the previous theorem does not depend on the starting configuration.

## Theorem 1.4. Consider the process

$$L _ { n } = \frac { Y _ { n } } { ( M - a n ) - X _ { 0 } ( 1 - a n / M ) ^ { b / a } },$$

and the event

$$\mathbf L _ { X _ { 0 }, M, \varepsilon } = \left \{ \left | L _ { n } - 1 \right | \leq \varepsilon, \text{ for all } 0 \leq n < M / a \right \}.$$

For any ε &gt; 0 there is a positive sequence ( λ ε,M ) M converging to 0 as M → ∞ such that for all starting configurations 0 &lt; X 0 &lt; M

$$\mathbb { P } ( \mathbf L _ { X _ { 0 }, M, \varepsilon } ) \geq 1 - \lambda _ { \varepsilon, M }.$$

Both of the above theorems can be applied to the configuration model. See Figure 1 for the ratio of active and inactive half-edges in the configuration model used to generate the random regular graph of degree d = 20 as predicted by the above theorems. In particular they imply that when inactive vertices get exhausted (and all the vertices get connected) there are still roughly n 1 -2 /d active half-edges left. While to generate random regular graphs one usually runs the configuration model with X 0 = d n ( -1), Y 0 = d , the urn model with general positive integer X 0 and Y 0 corresponds to a configuration model in which the graph is partially constructed in the beginning. This generalization is relevant for the analysis of a competing first passage percolation model in [1].

## 2 Proofs

First we give an elementary technical estimate.

Lemma 2.1. For any positive integer n such that M -an ≥ 2 b we have

$$e ^ { - \frac { b ^ { 2 } } { a ( M - a n ) } } \left ( 1 - \frac { a n } { M } \right ) ^ { b / a } \leq \prod _ { k = 0 } ^ { n - 1 } \left ( 1 - \frac { b } { M - a k } \right ) \leq e ^ { \frac { b } { M - a n } } \left ( 1 - \frac { a n } { M } \right ) ^ { b / a }.$$

Figure 1: Proportion of active half-edges ( A /nd k ) in the configuration model for d = 20 as predicted by theorems 1.1 and 1.4 represented by the blue line. Horizontal axis represents rescaled values of 2 k/nd ∈ [0 , 1]. Diagonal line represents the number of unused half-edges A k + I k = nd -2 k .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0559v1-figure-58f02645-805a-4d2b-8408-ecde5602d4e1.jpg)

## Proof. Denote

$$S _ { n } = \sum _ { k = 0 } ^ { n - 1 } \log \left ( 1 - \frac { b } { M - a k } \right ).$$

For 0 ≤ t ≤ 1 / 2 it holds that - -t t 2 ≤ log(1 -t ) ≤ -t and so we have

$$- \sum _ { k = 0 } ^ { n - 1 } \frac { b } { M - a k } - \sum _ { k = 0 } ^ { n - 1 } \frac { b ^ { 2 } } { ( M - a k ) ^ { 2 } } \leq S _ { n } \leq - \sum _ { k = 0 } ^ { n - 1 } \frac { b } { M - a k }.$$

Comparing the sum and the integral

$$\frac { b } { a } \int _ { M - a n } ^ { M } \frac { d t } { t } - \frac { b } { M - a n } + \frac { b } { M } \leq \sum _ { k = 0 } ^ { n - 1 } \frac { b } { M - a k } \leq \frac { b } { a } \int _ { M - a n } ^ { M } \frac { d t } { t },$$

gives

$$\frac { b } { a } \log \left ( 1 - \frac { a n } { M } \right ) - \frac { b ^ { 2 } } { a ( M - a n ) } \leq S _ { n } \leq \frac { b } { a } \log \left ( 1 - \frac { a n } { M } \right ) + \frac { b } { M - a n },$$

which implies the claim.

Remark 2.2 . While by definition M -an t ≥ MtX -a/b 0 the condition t ≥ aX -a/b 0 /M , which is satisfied for all t appearing in (1.3) and (1.4) implies M -an t ≤ 2 MtX -a/b 0 . This will be used in estimates below.

Proof of Theorem 1.1, inequality (1.3) . Recall the definitions of the σ -algebra F n and the stopping time ρ , and consider the random variable ξ n = 1 { ρ&gt;n } which is the indicator of the event that

ρ &gt; n . Since X n + Y n = M -a n ( ∧ ρ ), for all n , the assumption M -aρ &gt; 0 implies that M -aρ &lt; X ρ &lt; M -aρ + . It is an easy computation that a

$$\mathbb { E } [ X _ { n + 1 } | \mathcal { F } _ { n } ] = \left ( 1 - \frac { b \xi _ { n } } { M - a n } \right ) X _ { n },$$

which shows that the process

$$M _ { n } = \frac { X _ { n } } { X _ { 0 } } \prod _ { k = 0 } ^ { n - 1 } \left ( 1 - \frac { b \xi _ { k } } { M - a k } \right ) ^ { - 1 } = \frac { X _ { n \wedge \rho } } { X _ { 0 } } \prod _ { k = 0 } ^ { ( n \wedge \rho ) - 1 } \left ( 1 - \frac { b } { M - a k } \right ) ^ { - 1 }.$$

is a martingale with M 0 = 1. To estimate the variance observe that for ρ &gt; n we have

$$X _ { 0 } ^ { 2 } \prod _ { k = 0 } ^ { n } & \left ( 1 - \frac { b \xi _ { k } } { M - a k } \right ) ^ { 2 } \mathbb { E } [ ( M _ { n + 1 } - M _ { n } ) ^ { 2 } | \mathcal { F } _ { n } ] \\ & = \left ( X _ { n } - b - X _ { n } ( 1 - \frac { b \xi _ { n } } { M - a n } ) \right ) ^ { 2 } \frac { X _ { n } } { X _ { n } + Y _ { n } } + \left ( X _ { n } - X _ { n } ( 1 - \frac { b \xi _ { n } } { M - a n } ) \right ) ^ { 2 } \frac { Y _ { n } } { X _ { n } + Y _ { n } } \\ & = \frac { b ^ { 2 } X _ { n } } { M - a n } - \frac { b ^ { 2 } X _ { n } ^ { 2 } \xi _ { n } } { ( M - a n ) ^ { 2 } } \leq \frac { b ^ { 2 } X _ { n } } { M - a n }, \ \ ( 2. 2 ) \\ \text{while} \, \text{for} \, \alpha < \mathfrak { n } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h } \, \mathfrak { h }$$

while for ρ ≤ n the left hand side is equal to 0. In any case for M -an ≥ 2 b we have

$$\mathbb { E } [ ( M _ { n + 1 } - M _ { n } ) ^ { 2 } ] \leq \frac { b ^ { 2 } \mathbb { E } [ M _ { n } ] } { ( M - a n - b ) X _ { 0 } \prod _ { k = 0 } ^ { n } ( 1 - b / ( M - a k ) ) },$$

and by Lemma 2.1 there is a constant C 1 = C 1 ( a, b ) such that

$$\mathbb { E } [ ( M _ { n + 1 } - M _ { n } ) ^ { 2 } ] \leq \frac { C _ { 1 } } { ( M - a n ) X _ { 0 } ( 1 - a n / M ) ^ { b / a } }.$$

Since by the assumptions

$$M - a n _ { t } \geq t M X _ { 0 } ^ { - a / b } \geq C / \epsilon \geq 2 C,$$

choosing the value C in the statement larger than b , and using the fact that M n is a martingale yields

$$\mathbb { E } [ ( M _ { n _ { t } } - 1 ) ^ { 2 } ] \leq \frac { C _ { 1 } M ^ { b / a } } { X _ { 0 } } \sum _ { k = 0 } ^ { n _ { t } - 1 } \frac { 1 } { ( M - a k ) ^ { b / a + 1 } } \leq \frac { C _ { 1 } M ^ { b / a } } { b X _ { 0 } ( M - a n _ { t } ) ^ { b / a } } \leq \frac { C _ { 1 } } { b ^ { b / a } }.$$

Combining this with the Doob's maximal inequality we have that the event | M n - | ≤ 1 ε/ 2 for all n ≤ n t has probability at least

$$1 - 2 \frac { \mathbb { E } [ ( M _ { n _ { t } } - 1 ) ^ { 2 } ] } { ( \varepsilon / 2 ) ^ { 2 } } \geq 1 - \frac { 8 C _ { 1 } } { b t ^ { b / a } }.$$

Now we need to replace the process M n with the process K n and account for the event ρ &lt; n t . First observe that the above bound on the process extends to the process K ′ n = K n ∧ ρ . This follows directly from the second equality in (2.1) and Lemma 2.1, using the inequality M -an t ≥ C/glyph[epsilon1] ≥ 2 C .

′

To further replace the process K n with K n and account for the event ρ &lt; n t , it suffices to show that P ( ρ &lt; n t ) ≤ C 2 t b/a glyph[epsilon1] 2 , for a constant C 2 = C 2 ( a, b ), and the rest of the proof of (1.3) is devoted

to this. Note that without loss of generality we can assume that t ≤ X a/b 0 , otherwise n t &lt; 0. This assumption in turn implies t -b/a ≥ X -1 0 ≥ M -1 , and since glyph[epsilon1] &lt; 1 2, it actually suffices to prove / that P ( ρ &lt; n t ) ≤ 4 C 2 M , for all CX a/b 0 Mε ≤ t ≤ X a/b 0 .

Now if ρ &lt; n t , the fact that X &gt; M ρ -aρ and the estimate K ′ n t = K ρ ≤ 1 + glyph[epsilon1] would imply

$$1 - \frac { a \rho } { M } \geq \left ( \frac { M } { ( 1 + \epsilon ) X _ { 0 } } \right ) ^ { a / ( b - a ) }.$$

By the proven estimate for the process K ′ n

$$\mathbb { P } \Big ( \rho < n _ { t }, 1 - \frac { a \rho } { M } < \Big ( \frac { M } { ( 1 + \epsilon ) X _ { 0 } } ) ^ { a / ( b - a ) } \Big ) \leq \mathbb { P } ( K ^ { \prime } _ { n _ { t } } > 1 + \varepsilon ) \leq \frac { C } { t ^ { b / a } \epsilon ^ { 2 } }.$$

In particular this completely handles the case when X &lt; M/ 0 (1 + glyph[epsilon1] ), so from now on assume that X 0 ≥ M/ (1 + glyph[epsilon1] ) (that is Y 0 ≤ glyph[epsilon1]M / (1 + glyph[epsilon1] )). Note that in order to prove the bound (1.3) we can assume glyph[epsilon1] to be bounded from above by a constant smaller than 1 / 2 (we simply need to adjust the constant C to extend the bound to all glyph[epsilon1] &lt; 1 2). / For the computations that follow it is convenient to assume that glyph[epsilon1] &lt; b/a -1, so we will assume this to hold until the end of the proof of (1.3). Let κ = b/ (1 + glyph[epsilon1] ) -a &gt; 0.

Consider the stopping time τ 3 as the first index n such that X &lt; M/ n (1 + glyph[epsilon1] ) -1 . We will prove that P ( ρ &lt; τ 3 ) ≤ C /M 3 for some positive constant C 3 = C 3 ( a, b ). The analysis will be split into three parts: bounding the probabilities of the events { ρ &lt; τ 1 } , { τ 1 ≤ ρ &lt; τ 2 } and { τ 2 ≤ ρ &lt; τ 3 } where τ 1 and τ 2 are stopping times defined as the first times n ≥ 0 such that Y n &gt; a (that is X &lt; M n -an -a ) and Y n &gt; M 1 3 / (that is X &lt; M n -an -M 1 3 / ).

First for ρ ≤ τ 1 assume that Y 0 ≤ a (so that τ 1 &gt; 0) and observe that (for some positive C 3 1 , = C 3 1 , ( a, b )) with probability at least 1 -C 3 1 , /M initial glyph[ceilingleft] a/ b ( -a ) glyph[ceilingright] steps result in drawing a blue ball. After this the number of red balls will be strictly larger than a , and thus this handles the case n &lt; τ 1 .

Now we consider the case τ 1 ≤ ρ &lt; τ 2 . Since we already analyzed the first case, by Markov property we can now assume that Y 0 &gt; a , so that τ 1 = 0. Moreover, assume that Y 0 ≤ M 1 3 / , so that τ 2 &gt; 0. Select an integer l 1 ≥ 2 such that ( l 1 -1)( b -a ) ≥ a +1 and define A as the event that for all integers 0 ≤ k ≤ M 1 3 / there is at most one red draw in the steps l 1 k +1 , l 1 k +2 , . . . , l 1 k + l 1 . By the definition of l 1 and since Y 0 &gt; a , this event implies that Y l 1 glyph[floorleft] M 1 / 3 glyph[floorright] + l 1 &gt; M 1 3 / , and in particular ρ ≥ τ 2 , so to handle this case we only need to show that the probability of A c is at most O (1 /M ). To end this observe that in this regime the value of Y n is always bounded from above by 2 bl 1 M 1 3 / and so the probability that for a fixed integer 0 ≤ k ≤ M 1 3 / more than two of the steps l 1 k +1 , l 1 k +2 , . . . , l 1 k + l 1 are red draws is at most

$$1 - \left ( 1 - \frac { 2 b l _ { 1 } M ^ { 1 / 3 } } { M } \right ) ^ { l _ { 1 } } - l _ { 1 } \frac { 2 b l _ { 1 } M ^ { 1 / 3 } } { M } \left ( 1 - \frac { 2 b l _ { 1 } M ^ { 1 / 3 } } { M } \right ) ^ { l _ { 1 } - 1 } \leq l _ { 1 } ( l _ { 1 } - 1 ) \left ( \frac { 2 b l _ { 1 } M ^ { 1 / 3 } } { M } \right ) ^ { 2 } = \frac { 4 b ^ { 2 } l _ { 1 } ^ { 3 } ( l _ { 1 } - 1 ) } { M ^ { 4 / 3 } }.$$

Now the expected number of steps 0 ≤ k ≤ M 1 3 / for which this happens is at most C 5 2 , /M , for some positive constant C 5 2 , = C 5 2 , ( a, b ), so the desired upper bound on the probability of A c follows by Markov inequality.

To handle the last case, by Markov property we can assume that Y 0 &gt; M 1 3 / , so that τ 2 = 0. Consider the process Y ′ n such that Y ′ 0 = Y 0 and such that at each step Y ′ n either decreases by a with probability glyph[epsilon1]/ (1 + glyph[epsilon1] ) or increases by b -a with probability 1 / (1 + glyph[epsilon1] ). It is a simple observation that

one can couple the processes Y n and Y ′ n so that Y ′ n ≤ Y n for all n ≤ τ 3 . Therefore, defining ρ ′ as the smallest index n such that Y ′ n ≤ Y / 0 2 it is clear that ρ &lt; τ 3 implies ρ ′ &lt; ∞ . Now the bound on the probability of ρ &lt; τ 3 follows from

$$\mathbb { P } ( \rho < \tau _ { 3 } ) \leq \mathbb { P } ( \rho ^ { \prime } < \infty ) \leq e ^ { - c Y _ { 0 } / 2 } \leq e ^ { - c M ^ { 1 / 3 } / 2 },$$

for a positive constant c = ( c a, b ). To justify the second inequality above choose the value of the constant c &gt; 0 so that

$$h ( c ) = \frac { 1 } { 1 + \epsilon } e ^ { - c ( b - a ) } + \frac { \epsilon } { 1 + \epsilon } e ^ { c a } = 1,$$

which exist since h (0) = 1, lim t →∞ h t ( ) = ∞ and h ′ (0) = -b/ (1 + glyph[epsilon1] ) + a = -κ &lt; 0. Such a choice then implies that e -cY ′ n is a martingale and since e -cY n ′ ∧ ρ ′ is bounded, optional stopping theorem implies that

$$e ^ { - c Y _ { 0 } } \geq \mathbb { P } ( \rho ^ { \prime } < \infty ) e ^ { - c Y _ { 0 } / 2 },$$

which yields the inequality.

Proof of Theorem 1.1, inequality (1.4) . It's clear that by taking C ≥ 1, it suffices to show the claim for t &lt; 1, so we will asume this throughout the proof. In the proof below we will assume that M is sufficiently large, so that the presented estimates hold. The constant C from (1.3) will be denoted by C 0 .

First define s = t -a/ (2 b -a ) . Since t &lt; 1, we have s ≥ 1 ≥ 2 C X 0 a/b 0 M -1 for M large enough (as X 0 ≤ M ), and by (1.3) we have

$$\mathbb { P } ( \mathbf K _ { X _ { 0 }, M, s, 1 / 2 } ^ { c } ) \leq 4 C _ { 0 } s ^ { - b / a } = 4 C _ { 0 } t ^ { b / ( 2 b - a ) }.$$

It is easy to check that the process X / M n ( -a n ( ∧ ρ )) is a supermartingale: For ρ ≤ n the value of the process remains unchanged, and when ρ &gt; n we have

$$\mathbb { E } \left ( \frac { X _ { n + 1 } } { M - a ( ( n + 1 ) \wedge \rho ) } \Big | \mathcal { F } _ { n } \right ) & = \frac { X _ { n } } { M - a ( n + 1 ) } - \frac { b } { M - a ( n + 1 ) } \frac { X _ { n } } { M - a n } \\ & = \frac { X _ { n } } { M - a ( n \wedge \rho ) } \Big ( 1 - \frac { b - a } { M - a ( n + 1 ) } \Big ).$$

Since n s ≤ n t , on the event K X ,M,s, / 0 1 2 we have

$$\mathbb { E } \left ( \frac { X _ { n _ { t } } } { M - a ( n _ { t } \wedge \rho ) } \Big | \mathcal { F } _ { n _ { s } } \right ) \leq \frac { X _ { n _ { s } } } { M - a ( n _ { s } \wedge \rho ) } \leq \frac { 3 X _ { 0 } } { 2 M } \Big ( 1 - \frac { a n _ { s } } { M } \Big ) ^ { b / a - 1 }.$$

Observe that if τ X ,M 0 ≥ n t then either ρ ≤ n t which in turn implies X n t &gt; M -a n ( t ∧ ρ ) or ρ &gt; n t and X n t ≥ b . In either case we have

$$\frac { X _ { n _ { t } } } { M - a ( n _ { t } \wedge \rho ) } \geq \min \left \{ 1, \frac { b } { M - a n _ { t } } \right \} \geq \frac { b } { M - a n _ { t } },$$

since the assumption on t in (1.4) implies that M -an t ≥ b . Therefore, by Markov inequality

$$\mathbb { P } ( \tau _ { X _ { 0 }, M } \geq n _ { t } ) \leq \frac { M - a n _ { t } } { b } \mathbb { E } \left ( \frac { X _ { n _ { t } } } { M - a ( n _ { t } \wedge \rho ) } \mathbf 1 _ { \mathbf K _ { X _ { 0 }, M, s, 1 / 2 } } \right ) + \mathbb { P } ( \mathbf K _ { X _ { 0 }, M, s, 1 / 2 } ^ { c } ),$$

where 1 K X ,M,s, / 0 1 2 is the indicator of the event K X ,M,s, / 0 1 2 . Then by (2.3), (2.4) and Remark 2.2 we have

$$\mathbb { P } ( \tau _ { X _ { 0 }, M } \geq n _ { t } ) \leq \frac { 3 X _ { 0 } } { 2 b } \left ( 1 - \frac { a n _ { s } } { M } \right ) ^ { b / a - 1 } \left ( 1 - \frac { a n _ { t } } { M } \right ) + 4 C _ { 0 } t ^ { b / ( 2 b - a ) } \\ \leq \frac { 3 \cdot 2 ^ { b / a - 1 } } { b } t s ^ { b / a - 1 } + 4 C _ { 0 } t ^ { b / ( 2 b - a ) } = \left ( \frac { 3 \cdot 2 ^ { b / a - 1 } } { b } + 4 C _ { 0 } \right ) t ^ { b / ( 2 b - a ) },$$

which finishes the proof.

Proof of Corollary 1.2. This is immediate from Remark 2.2 and the fact that the event in the statement is implied by K X ,M,t,ε 0 for t = 2 -a/b -1 m a/b .

Proof of Corollary 1.3. This is immediate from the fact that the event in the statement is implied by τ X ,M 0 ≥ n t for t = X a/b 0 /M .

Proof of Theorem 1.4. We will assume that glyph[epsilon1] &lt; / 1 6 which is clearly sufficient. We will use different argument in cases when the 1 -an/M falls in the intervals

$$I _ { 1 } = \left ( 0, \frac { 1 } { X _ { 0 } ^ { a / b } \log M } \right ], \ I _ { 2 } = \left [ \frac { 1 } { X _ { 0 } ^ { a / b } \log M }, \frac { \log M } { X _ { 0 } ^ { a / b } } \right ], \ I _ { 3 } = \left [ \frac { \log M } { X _ { 0 } ^ { a / b } }, \left ( \frac { M } { 2 X _ { 0 } } \right ) ^ { \frac { a } { b - a } } \right ], \\ I _ { 4 } = \left [ \left ( \frac { M } { 2 X _ { 0 } } \right ) ^ { \frac { a } { b - a } }, 1 - \frac { \log M } { \sqrt { M } } \right ], \ I _ { 5 } = \left [ 1 - \frac { \log M } { \sqrt { M } }, 1 \right ].$$

First we will handle the cases I 1 , I 2 and I 3 . Then we will handle cases I 4 , and I 5 and for this we will assume that X 0 ≥ M/ 2 (that is Y 0 ≤ M/ 2), otherwise [0 , 1] ⊂ I 1 ∪ I 2 ∪ I 3 so there is no need to consider the intervals I 4 and I 5 . Note, that even though X 0 ≥ M/ 2, the interval I 4 might still be empty. In the case when Y 0 ≤ √ M (log M ) 2 we will further consider two subcases of I 5 , when 1 -an/M is in

$$I _ { 5, 1 } = \left [ 1 - \frac { \log M } { \sqrt { M } }, 1 - \frac { 1 } { \sqrt { M } ( \log M ) ^ { 3 } } \right ] \text{ and } I _ { 5, 2 } = \left [ 1 - \frac { 1 } { \sqrt { M } ( \log M ) ^ { 3 } }, 1 \right ].$$

We start by writing

$$L _ { n } = \frac { M - a ( n \wedge \rho ) - X _ { n } } { ( M - a n ) - X _ { 0 } \left ( 1 - \frac { a n } { M } \right ) ^ { b / a } },$$

from where we easily get

$$L _ { n } - 1 = \frac { X _ { 0 } \left ( 1 - \frac { a ^ { n } } { M } \right ) ^ { b / a } - X _ { n } } { ( M - a ^ { n } ) - X _ { 0 } \left ( 1 - \frac { a ^ { n } } { M } \right ) ^ { b / a } } + \xi _ { n }, \text{ and } \frac { | K _ { n } - 1 | } { | L _ { n } - 1 | } = \frac { M } { X _ { 0 } \left ( 1 - \frac { a ^ { n } } { M } \right ) ^ { b / a - 1 } } - 1 + \chi _ { n }, \text{ (2.5)}$$

where ξ n and χ n are equal to zero if ρ ≥ n . For all n such that 1 -an/M ∈ I 3 , the right hand side of the second formula above without the χ n term is bounded from below by 1. The event K X ,M, 0 log M,ε from Theorem 1.1 implies that χ n = 0 and | K n - | ≤ 1 glyph[epsilon1] for all 0 ≤ n ≤ n log M , and in particular for

all n such that 1 -an/M ∈ I 3 . Therefore, it also implies that | L n - | ≤ 1 ε when 1 -an/M ∈ I 3 . Moreover, for a given ε &gt; 0 we can choose M large enough so that log M ≥ C M 1 -a/b ε ≥ CX a/b 0 Mε , where C is the constant from Theorem 1.1. Then by (1.3) we have that the probability of the event K X ,M, 0 log M,ε is bounded from below by

$$1 - \frac { C } { ( \log M ) ^ { b / a } \varepsilon ^ { 2 } },$$

which resolves the case when 1 -an/M ∈ I 3 .

Now we look at the case when 1 -an/M ∈ I 2 . By Remark 2.2, 1 -an log M /M ≤ 2 X -a/b 0 log M holds for M large enough, so the event K X ,M, 0 log M,ε implies that

$$X _ { n _ { \log M } } \leq ( 3 \log M ) ^ { b / a }.$$

Thus, on the event K X ,M, 0 log M,ε ∩ R , we have both 0 ≤ X n ≤ (3 log M ) b/a for all n such that 1 -an/M ∈ I 2 and ξ n = 0. From the first relation in (2.5) we get

$$- \frac { ( 3 \log M ) ^ { b / a } } { \frac { M } { X _ { 0 } ^ { a / b } \log M } - ( \log M ) ^ { b / a } } \leq L _ { n } - 1 \leq \frac { ( \log M ) ^ { b / a } } { \frac { M } { X _ { 0 } ^ { a / b } \log M } - ( \log M ) ^ { b / a } }.$$

The denominator above is bounded from below by M 1 -a/b / log M -(log M ) b/a , and so for M large enough both the lower and the upper bound on L n -1 above are smaller than glyph[epsilon1] in the absolute value. Since lim M →∞ P ( K X ,M, 0 log M,ε ∩ R ) = 1, we conclude that for any ε &gt; 0 with probability converging to 1 we have that | L n - | ≤ 1 ε , for all n satisfying 1 -an/M ∈ I 2 .

Next we consider n such that 1 -an/M ∈ I 1 , so in particular n ≥ n 1 / log M . By (1.4), with probability of at least 1 -C (log M ) b/ (2 b -a ) we have that X n = 0 and Y n = M -an for all these n . This in particular implies the event R and therefore, with probability converging to 1, for all such n , we have that

$$1 \leq L _ { n } = \frac { 1 } { 1 - \frac { X _ { 0 } } { M } \left ( 1 - \frac { a n } { M } \right ) ^ { b / a - 1 } } \leq \frac { 1 } { 1 - \frac { X _ { 0 } ^ { a / b } } { M ( \log M ) ^ { b / a - 1 } } } \leq \frac { 1 } { 1 - \frac { 1 } { M ^ { 1 - a / b } ( \log M ) ^ { b / a - 1 } } },$$

which converges to 1 as M →∞ .

We are done with the cases I 1 , I 2 and I 3 . As we said we now assume X 0 ≥ M/ 2. Consider the case when 1 -an/M ∈ I 4 . By the second relation in (2.5) the condition that both

$$| K _ { n } - 1 | \leq \varepsilon \left ( M X _ { 0 } ^ { - 1 } \left ( 1 - \frac { \log M } { \sqrt { M } } \right ) ^ { - b / a + 1 } - 1 \right )$$

and ρ &gt; n hold when 1 -an/M ∈ I 4 implies that | L n - | ≤ 1 ε holds for these n as well. Denote the right hand side of (2.6) by δ M . In particular the event K X ,M,t,δ 0 M , for t = ( MX -a/b 0 / 2) a/ b ( -a ) will imply that | L n - | ≤ 1 ε for 1 -an/M ∈ I 4 . To calculate the probability of K X ,M,t,δ 0 M we can apply (1.3). To justify this application we need to check that, for M large enough and ε &lt; 1 6 / fixed, δ M ≤ 1 2 and / t ≥ CX a/b 0 Mδ M . Both will follow if we prove that

$$\frac { 2 ^ { a / ( b - a ) } C } { M } \leq \delta _ { M } \leq 1 / 2.$$

Since we assumed that X 0 ≥ M/ 2 it is easy to show that

$$\epsilon \frac { b - a } { a } \frac { \log M } { \sqrt { M } } \leq \delta _ { M } \leq 2 \epsilon \left ( 1 - \frac { \log M } { \sqrt { M } } \right ) ^ { - b / a + 1 }.$$

These inequalities now immediately imply the ones in (2.7) for a fixed glyph[epsilon1] &lt; 1 6 and / M ≥ M glyph[epsilon1] ( ) large enough. Therefore we can apply the estimate in (1.3), and by the lower bound in (2.8), the probability that | L n - | ≤ 1 ε for all n such that 1 -an/M ∈ I 4 is at least

$$1 - \frac { C } { t ^ { b / a } \delta _ { M } ^ { 2 } } \geq 1 - \frac { 2 ^ { b / ( b - a ) } a ^ { 2 } C X _ { 0 } ^ { a / ( b - a ) } M } { \varepsilon ^ { 2 } ( b - a ) ^ { 2 } M ^ { b / ( b - a ) } ( \log M ) ^ { 2 } } \geq 1 - \frac { 2 ^ { b / ( b - a ) } a ^ { 2 } C } { \varepsilon ^ { 2 } ( b - a ) ^ { 2 } ( \log M ) ^ { 2 } }.$$

Since the right hand side converges to 1 when glyph[epsilon1] is fixed and M →∞ , we are only left to consider the final case when 1 -an/M ∈ I 5 . To this end write

$$L _ { n } = \frac { Y _ { n } } { \left ( 1 - \frac { a n } { M } \right ) \left ( Y _ { 0 } \left ( 1 - \frac { a n } { M } \right ) ^ { b / a - 1 } + M \left ( 1 - \left ( 1 - \frac { a n } { M } \right ) ^ { b / a - 1 } \right ) \right ) }.$$

First consider the case when Y 0 ≥ √ M (log M ) 2 so that Y 0 (1 -ε/ 3) ≤ Y n ≤ Y 0 (1+ ε/ 3), for M large enough and when 1 -an/M ∈ I 5 . Furthermore, for such n and M large enough the denominator satisfies

$$\left ( 1 - \frac { \log M } { \sqrt { M } } \right ) ^ { b / a } Y _ { 0 } & \leq \left ( 1 - \frac { a n } { M } \right ) \left ( Y _ { 0 } \left ( 1 - \frac { a n } { M } \right ) ^ { b / a - 1 } + M \left ( 1 - \left ( 1 - \frac { a n } { M } \right ) ^ { b / a - 1 } \right ) \right ) \\ & \leq Y _ { 0 } + 2 ( b - a ) n \leq Y _ { 0 } + 2 \frac { b - a } { a } \sqrt { M } \log M,$$

and so it is bounded by Y 0 (1 -ε/ 3) from below and by Y 0 (1+ ε/ 3) from above, for M large enough. This now implies the deterministic fact that | L n - | ≤ 1 ε when 1 -an/M ∈ I 5 . √

Now assume Y 0 ≤ M (log M ) 2 . Clearly, for M large enough, and all n which satisfy 1 -an/M ∈ I 5 we have Y n ≤ 2 √ M (log M ) 2 , and in particular the probability of drawing a red ball in this stage is at most 3(log M / ) 2 √ M , for M large enough. Therefore, the expected number of red balls drawn in the stage when 1 -an/M ∈ I 5 1 , is no more than 3(log M /a ) 3 , and in the the stage when 1 -an/M ∈ I 5 2 , is no more than 3( a log M ) -1 . By Markov inequality, with probability converging to 1 (as M →∞ ) we have both

$$Y _ { n } = Y _ { 0 } + ( b - a ) n, \text{   whenever } 1 - a n / M \in I _ { 5, 2 } \text{ } & & ( 2. 1 0 )$$

and

$$Y _ { 0 } + ( b - a ) n - ( \log M ) ^ { 4 } \leq Y _ { n } \leq Y _ { 0 } + ( b - a ) n, \text{ \ whenever } 1 - a n / M \in I _ { 5, 1 }. \text{ \quad \ \ (2.11) }$$

(Note that if (2.10) holds then (2.11) implies that the value of Y n is positive throughout the I 5 phase.) Moreover, for a fixed glyph[epsilon1] &gt; 0, M large enough, and any n such that 1 -an/M ∈ I 5

$$\frac { 1 } { 1 + \varepsilon / 2 } \leq \left ( 1 - \frac { a n } { M } \right ) ^ { b / a } \leq 1, \text{ and } \frac { ( b - a ) n } { 1 + \varepsilon / 2 } \leq M \left ( 1 - \left ( 1 - \frac { a n } { M } \right ) ^ { b / a - 1 } \right ) \leq \frac { ( b - a ) n } { 1 - \varepsilon / 2 }. \quad \text{ (2.12)}$$

In the view of (2.9), the case I 5 2 , follows from (2.10) and (2.12). For the case I 5 1 , we just need to argue about the lower bound and for this it suffices to show that for any 1 -an/M ∈ I 5 1 ,

$$\frac { ( \log M ) ^ { 4 } } { Y _ { 0 } + ( b - a ) n } < \epsilon / 2,$$

for M large enough which surely holds since for any n ∈ I 5 1 , we have n ≥ √ M a (log M ) 3 .

## Acknowledgments

This work was a part of a project, most of which was done in collaboration with Yael Dekel, Elchanan Mossel and Yuval Peres. The author would like to thank them for fruitful discussions, encouragement and support.

## References

- [1] Ton´ ci Antunovi´ c, Yael Dekel, Elchanan Mossel, and Yuval Peres. Competing first passage percolation on random regular graphs. preprint, available at arXiv:1109.4918 [math.PR].
- [2] Edward A. Bender and E. Rodney Canfield. The asymptotic number of labeled graphs with given degree sequences. J. Combinatorial Theory Ser. A , 24(3):296-307, 1978.
- [3] B. Bollob´s. a A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. , 1(4):311-316, 1980.
- [4] B´ ela Bollob´s. a Random graphs , volume 73 of Cambridge Studies in Advanced Mathematics . Cambridge University Press, Cambridge, second edition, 2001.
- [5] Svante Janson, Tomasz glyph[suppress] Luczak, and Andrzej Rucinski. Random graphs . Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
Tonći Antunović
On the evolution in the configuration model
We give precise estimates on the number of active/inactive half-edges in the
configuration model used to generate random regular graphs. This is obtained by
analyzing a more general urn model with negative eigenvalues.