On the method of typical bounded differences

Introduction

While the simplicity of (L) makes this inequality very intuitive and easy to apply, its perhaps main drawback is that it considers worst case changes. In particular, the resulting concentration bounds are rather weak (or even trivial) in situations where the worst case $c_{k}$ are much larger than the typical changes. A standard example is $f(X)$ counting the number of triangles in the binomial random graph $G_{n,p}$: since every pair of vertices has up to $n-2$ common neighbours the worst case is $c_{k}=\Theta(n)$, which is much larger than we expect from the $\Theta(np^{2})$ common neighbours we usually have for $p\geq n^{-1/2+\varepsilon}$. In fact, here Theorem 1 only gives trivial estimates for $p=O(n^{-1/3})$, but it seems plausible that concentration should hold in such applications where the typical changes are much smaller than the worst case ones.

In contrast, much less research has been devoted to developing easy-to-use tools for proving concentration results in such situations. The Hoeffding–Azuma inequality implies, for example, that (2) essentially remains true if we relax (1) to worst case conditional expected changes:

While this might be useful in certain textbook examples, it typically has two main drawbacks in involved combinatorial applications: (a) conditional expectations are usually difficult to calculate and (b) it often yields no substantial improvement (for, say, $k\geq N/2$ the worst case in (3) over all choices of $X_{1},\ldots,X_{k}$ is often comparable to (1)). There are also some approaches which allow (3) to be violated occasionally , but these usually require knowledge about conditional probability distributions, making them particularly difficult to apply when $f(X)$ is defined in an indirect or complicated way.

In this paper we develop a variant of the bounded differences inequality which can be used to establish concentration of functions $f(X)$ where (i) the typical changes are small although (ii) the worst case changes might be very large. One key aspect of this inequality is that it relies on a simple and attractive condition that (a) is easy to check and (b) coincides with heuristic considerations why concentration should hold. Indeed, given a ‘good’ event $\Gamma$ that holds with very high probability, we essentially relax the Lipschitz condition (L) to situations where $\Gamma$ occurs. More precisely, for the sake of proving concentration the following inequality usually allows us to restrict our attention to such typical changes, which are often much smaller than the worst case ones.

For any numbers $(\gamma_{k})_{k\in[N]}$ with $\gamma_{k}\in(0,1]$ there is an event ${\mathcal{B}}={\mathcal{B}}(\Gamma,(\gamma_{k})_{k\in[N]})$ satisfying

If each $X_{k}$ takes only two values (i.e., when $|\Lambda_{k}|=2$) the exponent in (6) may be multiplied by factor of $4$, analogous to the standard bound (2).

If the underlying probability space is generated by independent Bernoulli random variables we establish much stronger estimates. For example, in the common situation where the success probabilities are all equal to $p$ (as in $G_{n,p}$) the following natural extension of Theorem 2 essentially allows us to multiply the denominator of (6) with an extra factor of $p$ (on an intuitive level one can perhaps think of this as applying Theorem 2 after conditioning on $\Theta(Np)$ variables being ‘relevant’).

where $e_{k}=\gamma_{k}(d_{k}-c_{k})$ and $C=\max_{k\in[N]}(c_{k}+e_{k})$.

If $f(X)$ and $\Gamma$ are either both monotone increasing or decreasing we have

In typical applications of this inequality we hope to be able to ignore the ‘error term’ $2Ct/3$ (and select $\gamma_{k}$ such that $c_{k}+e_{k}\approx c_{k}$, as before). In this case (7) is close $e^{-t^{2}/(2\sum p_{k}c_{k}^{2})}$, which for $p_{k}=o(1)$ is a significant improvement of the corresponding $e^{-2t^{2}/(\sum c_{k}^{2})}$ from Remark 3. For example, in the case of triangles in $G_{n,p}$ this allows us to extend the concentration result of the previous section to edge probabilities satisfying $p\geq n^{-4/5+\varepsilon}$. In fact, the estimates implied by (8) are sometimes comparable to those of Janson’s inequality , see Section 1.2.2.

Ignoring the ‘good’ event $\Gamma$ in Theorem 4 we also obtain a strengthening of Theorem 1. Since this natural variant of the bounded differences inequality does not seem to be as widely known, we explicitly state it for ease of reference (if each $(1-p_{k})p_{k}$ is weakened to $\max_{i}\min\{1-p_{i},p_{i}\}$ then (9) follows from Theorem 3.9 in McDiarmid’s survey ; Alon, Kim and Spencer also proved a comparable inequality that applies to small values of $t$ only: for those the contribution of $Ct$ to the denominator of (9) is negligible).

Apply Theorem 4 with $\Gamma=\{0,1\}^{N}$ and $d_{k}=c_{k}$. ∎

This extends Bernstein’s inequality (a strengthening of the Chernoff bounds for small deviations, see e.g. Remark 2.9 in ), which applies to sums of independent random variables. One key aspect of (9) is that it is almost tight when $f(X)=\sum_{k}X_{k}$, in which case $V=\operatorname{Var}f(X)=\sum_{k}p_{k}(1-p_{k})$ and $c_{k}=1$. Indeed, the estimate of Corollary 6 is then close to $e^{-t^{2}/(2V)}$ for $t$ not too large, which is exactly the tail behaviour predicted by the central limit theorem.

Our arguments in fact yield a slightly stronger form of (7)–(9), analogous to Bennet’s sharpening of the Chernoff bounds (see e.g. Remark 2.9 in ). Indeed, for $\phi(x)=(1+x)\log(1+x)-x$ we can improve terms of the form $e^{-t^{2}/(2V+2Ct/3)}$ to $e^{-V/C^{2}\cdot\phi(Ct/V)}$, where $V$ equals $\sum_{k}(1-p_{k})p_{k}(c_{k}+e_{k})^{2}$ and $\sum_{k}(1-p_{k})p_{k}c_{k}^{2}$ in (7) and (9). For $t=\omega(V/C)$ these refined estimates sharpen the exponents from order $\Theta(t/C)$ to $\Theta(t/C\cdot\log(Ct/V))$, i.e., yield a logarithmic improvement.

1.2 Two-sided Lipschitz conditions

Theorem 11 also allows us to routinely apply certain truncation arguments (without ad-hoc calculations). A typical example is $f(X)=\sum_{k}X_{k}$ with $X_{k}$ having exponential tails, where one often first proves concentration of, say, $\sum_{k}\min\{X_{k},C\log N\}$, and then transfers this result to the original sum, see e.g. . Here (11) almost immediately yields concentration of $f(X)$ via the local events $\Gamma_{k}$ that $X_{k}\leq C\log N$ occurs (setting $\Gamma=\prod_{j}\Gamma_{j}$, $d_{k}=c_{k}=C\log N$ and $\gamma_{k}=1$).

1.3 Dynamic exposure of the variables

The previous inequalities can be refined by exposing the values of the random variables $X_{i}$ one by one in an adaptive order. Intuitively this allows us to exploit that after having learned the values of certain variables, some other $X_{j}$ may not any more influence the value of $f(X)$. This approach was introduced by Alon, Kim and Spencer , and is particularly useful whenever we can determine $f(X)$ without knowing the value of all random variables. More formally, a strategy sequentially exposes $X_{q_{1}},X_{q_{2}},\ldots$, where each index $q_{i}=q_{i}(X_{q_{1}},\ldots,X_{q_{i-1}})$ may depend on the previous outcomes and indices (we use the convention that $q_{k+1}=q_{k}$ if $f(X)$ is determined by $(X_{q_{1}},\ldots,X_{q_{k}})$ with $k<N$); every strategy has a natural representation in form of a decision tree. With a fixed strategy in mind, for every possible outcome $X=(X_{1},\ldots,X_{N})$ we obtain a set of queried indices $Q\subseteq[N]$, and by ${\mathcal{Q}}$ we denote the set of all possible such query sets $Q$. The resulting key improvement is that in most inequalities we essentially may replace $k\in[N]$ with $k\in Q$ for some ‘worst case’ set of indices $Q\in{\mathcal{Q}}$ (note that $\gamma_{k}=\gamma$ is a typical choice in applications).

Suppose that $\gamma_{k}=\gamma$ for all $k\in[N]$. For any strategy Theorems 1, 2, 4, 9, 11, Corollary 6 and Remarks 3, 7, 8, 12 remain valid with $\sum_{k\in[N]}$ replaced by $\max_{Q\in{\mathcal{Q}}}\sum_{k\in Q}$ and $\max_{k\in[N]}$ replaced by $\max_{Q\in{\mathcal{Q}}}\max_{k\in Q}$, with the addition that ${\mathcal{B}}$ depends on the query strategy.

Consider any strategy satisfying $q_{i+1}\geq q_{i}$ in each step. Then Theorems 1, 2, 4, 9, 11, Corollary 6 and Remarks 3, 5, 7, 8, 12 remain valid with $\sum_{k\in[N]}$ replaced by $\max_{Q\in{\mathcal{Q}}}\sum_{k\in Q}$ and $\max_{k\in[N]}$ replaced by $\max_{Q\in{\mathcal{Q}}}\max_{k\in Q}$, with the exception that (5) remains unchanged.

Applied to Corollary 6, Theorem 4 and Remark 7 these results tighten and extend an inequality of Alon, Kim and Spencer , which is based on the Lipschitz condition (L). In certain applications dynamic exposure yields significant improvements, and for an illustrating example we refer to Claim 2 in , where it is crucial to reduce (the order of magnitude of) the number of queried variables. Further refinements are possible by using adaptive Lipschitz bounds $c_{k}$, which is perhaps most easily exploited by tailoring the arguments of Section 2 to the specific application.

1.4 Weakening the independence assumption

There are numbers $(c_{k})_{k\in[N]}$ and $(d_{k})_{k\in[N]}$ with $c_{k}\leq d_{k}$ such that the following holds for any two possible sequences of outcomes $a_{1},\ldots,,a_{k-1},a$ and $a_{1},\ldots,a_{k-1},b$ of $X_{1},\ldots,X_{k}$. Defining

there is an injection $\rho_{k}=\rho_{k}(\Sigma_{a},\Sigma_{b}):\Sigma_{a}\to\Sigma_{b}$ such that for all $x\in\Sigma_{a}$ we have

The proof shows that $\rho_{k}$ must be a bijection with equality in (13). Furthermore, if $X_{k}$ takes at most two values conditioned on $X_{1},\ldots,X_{k-1}$, then the exponent in (6) may be multiplied by factor of $4$. In fact, (2) holds if $\Gamma=\prod_{j\in[N]}\Lambda_{j}$ (or $r_{k}=0$ below). In addition, for (6) to hold with $e_{k}=\gamma_{k}r_{k}\geq 0$ it suffices if we relax (GL) to the average Lipschitz condition

To illustrate the application of the (GL) condition we consider uniform permutations $\pi\in S_{n}$, which are generated by sequentially choosing each $\pi(k)$ randomly from $[n]\setminus\{\pi(1),\ldots,\pi(k-1)\}$. Here $\Sigma_{z}$ contains all $\pi$ with $\pi(k)=z$ and $\pi(j)=a_{j}$ for $1\leq j<k$. In this case a bijection $\rho_{k}:\Sigma_{a}\to\Sigma_{b}$ is defined by the transposition of $a$ and $b$, so that $\pi^{\prime}=\rho_{k}(\pi)$ satisfies $\pi^{\prime}(k)=b$, $\pi^{\prime}(\pi^{-1}(b))=a$ and $\pi^{\prime}(i)=\pi(i)$ for $\pi(i)\notin\{a,b\}$. Using $|\Sigma_{a}|=|\Sigma_{b}|=(n-k)!$ and the uniform measure it is not hard to check that (13) holds with equality. We see that for establishing (12) it suffices to bound $|f(\pi)-f(\pi^{\prime})|$ whenever $\pi$ and $\pi^{\prime}$ are related via a transposition, which is an intuitive and easy to check condition (this may correspond to changing two coordinates).

Several extensions of Theorem 2 carry over to Theorem 15 with some minor modifications, and results analogous to those of Sections 1.1.1 and 1.1.2, including a two-sided Lipschitz condition, are stated below (Remark 7 also applies to (15) after adjusting $V$ accordingly).

where $e_{k}=\gamma_{k}(d_{k}-c_{k})$ and $C=\max_{k\in[N]}(c_{k}+e_{k})$.

In addition, $q_{k}\leq|\Lambda_{k}|^{-1}$ suffices when all possible outcomes occur with the same probability.

The sufficient condition $q_{k}\leq|\Lambda_{k}|^{-1}$ often makes the two-sided Lipschitz condition of Theorem 18 easy to apply. For example, in case of random permutations $\pi\in S_{n}$ and random graphs $G_{n,m}$ (or the random graph process) we may take $q_{k}=n^{-1}$ and $q_{k}=n^{-2}$, respectively.

2 Discussion and applications

As discussed, in probabilistic combinatorics and the analysis of randomized algorithms we frequently need to prove that a random function is not too far from its mean, e.g., that $f(X)\approx\mu$ or $f(X)\leq 2\mu$ holds. A common feature of many recent applications is that the functions of interest are only ‘smooth enough’ on a high probability event, whereas their deterministic worst case changes are too large for the standard bounded differences inequality (Theorem 1) to be effective.

One aim of this paper is to provide easy-to-apply tools which can routinely deal with such situations, establishing concentration in a rather simple way. For example, in the frequent case where the good event $\Gamma$ holds with probability at least $1-N^{-\omega(1)}$ we can typically choose $\gamma_{k}^{-1}=\max|f(X)|$ and then completely ignore the worst case effects, see e.g. the proof of Theorem 28 (this approach also applies, for example, to Lemma 14 in and parts of the martingale-based proof of Theorem 2.2 in ). In other words, the crucial advantage of our new inequalities is that they can often remove the need for sometimes difficult ad-hoc arguments using only a minimum amount of calculations (which typically even coincide with heuristic considerations).

2.2 Comparison with Janson’s inequality

In this section we demonstrate that in certain applications our inequalities give exponential estimates that (i) are tight and (ii) successfully compete with the well known Janson’s inequality. To this end we focus on subgraph counts in the binomial random graph $G_{n,p}$ since a concrete example seems more illustrative to us. Henceforth we assume that $H$ is a fixed $2$-balanced graph, i.e., where $H$ has $e_{H}\geq 2$ edges and all its proper subgraphs $G\subsetneq H$ with $v_{G}\geq 3$ vertices satisfy

This class of graphs includes, for example, complete graphs and cycles of arbitrary size. Let $Y_{H}$ count the number of $H$ copies in $G_{n,p}$. For $2$-balanced graphs it is well-known (see e.g. ) that Janson’s inequality gives

which asymptotically matches (18), i.e., the estimate of Janson’s inequality. In fact, for $t=\Theta(\mu)$ this bound is best possible (up to constants in the exponent) since $G_{n,p}$ contains no edges (and thus no copies of $H$) with probability $e^{-\Theta(n^{2}p)}$.

2.3 Application: the reverse H𝐻H-free process

The following variations of the classical random graph processes were proposed by Bollobás and Erdős at the 1990 Quo Vadis, Graph Theory conference in an attempt to improve Ramsey numbers . The $H$-free process, where, starting with an empty graph on $n$ vertices, in each step a new edge is added, chosen uniformly at random from all pairs whose addition does not complete a copy of $H$. The reverse $H$-free process, where, starting with a complete graph on $n$ vertices, in each step an edge is removed, chosen uniformly at random from all edges that are contained in a copy of $H$. The $H$-removal process, where, starting with a complete graph on $n$ vertices, in each step all $e_{H}$ edges of a copy of $H$ are removed, which is selected uniformly at random from all $H$ copies. All of these processes end with an $H$-free graph, and Bollobás and Erdős asked (among other structural properties) what their typical final number of edges is .

Using our typical bounded differences inequality, in Section 3 we show that the final number of edges in the reverse $H$-free process is sharply concentrated when $H$ is $2$-balanced (we do not assume strictly $2$-balanced), and also determine the likely number of edges up to constants. This is in contrast to all known results for the widely studied $H$-free and $H$-removal processes. Indeed, in these (a) no sharp concentration results are known, (b) the order of magnitude of the final number of edges is open for most strictly $2$-balanced graphs, and (c) no general results apply to the class of $2$-balanced graphs. As we shall see, when $H$ is a matching the expected final number of edges in the reverse $H$-free process is $\Theta(1)$. When it comes to concentration we thus restrict our main attention to all other $2$-balanced graphs $H$, which in fact satisfy $d_{2}(H)\geq 1$ (with equality for trees). Here our next result shows that the reverse $H$-free process typically ends with $\Theta(n^{2-1/d_{2}(H)})$ edges, answering (up to constant factors) the aforementioned question of Bollobás and Erdős from 1990.

Our arguments partially generalize to arbitrary graphs. Set $d_{2}(K_{2})=1/2$ and $m_{2}(H)=\max_{G\subseteq H,e_{G}\geq 1}d_{2}(G)$, so that $m_{2}(H)=d_{2}(H)$ for $2$-balanced graphs $H$. We show that for any graph the expected final number of edges in the reverse $H$-free process is $\Theta(n^{2-1/m_{2}(H)})$, and prove concentration under certain conditions (satisfied e.g. by a clique $K_{r}$ with an extra edge hanging off), see Section 3. The proof of Theorem 19 also extends to a finite family of forbidden graphs ${\mathcal{H}}$, which for the $H$-free process was considered in . Indeed, defining the reverse ${\mathcal{H}}$-free process in the obvious way (always removing a random edge that is contained in a copy of some $H\in{\mathcal{H}}$) we obtain, for example, the following generalization.

3 Organization of the paper

Section 2 is devoted to the proof of our new concentration inequalities, which are then illustrated by an application to the $H$-free process in Section 3.

Proofs of the concentration inequalities

We start by proving two general martingale inequalities. These are applied in Section 2.2, where we establish our variants of the bounded differences inequality.

Our concentration results are based on the following variants of Hoeffding–Azuma/Bernstein-type martingale inequalities. Since they are not stated exactly in this form in the literature, we give short proofs for the readers convenience (following the slick approach of Freedman ). In both we assume that $({\mathcal{F}}_{k})_{0\leq k\leq N}$ is an increasing sequence of $\sigma$-algebras, and $(M_{k})_{0\leq k\leq N}$ is an $({\mathcal{F}}_{k})_{0\leq k\leq N}$-adapted bounded martingale.

Let $L_{k}$ and $U_{k}$ be ${\mathcal{F}}_{k-1}$-measurable variables satisfying $L_{k}\leq M_{k}-M_{k-1}\leq U_{k}$. Set $S_{k}=\sum_{i\in[k]}(U_{i}-L_{i})^{2}$. For every $t\geq 0$ and $S>0$ we have

Let $U_{k}$ be an ${\mathcal{F}}_{k-1}$-measurable variable satisfying $M_{k}-M_{k-1}\leq U_{k}$. Set $C_{k}=\max_{i\in[k]}U_{i}$ and $V_{k}=\sum_{i\in[k]}\operatorname{Var}(M_{i}-M_{i-1}\mid{\mathcal{F}}_{i-1})$. Let $\phi(x)=(1+x)\log(1+x)-x$. For every $t\geq 0$ and $V,C>0$ we have

Observe that we allow for (accumulative) random bounds on the one-step changes (and other quantities), which in case of Lemma 21 is the main difference to the usual formulation of the classical Hoeffding–Azuma inequality . Lemma 22 also extends the related Theorem 2.2.2 of Kim and Vu (see also Lemma 3.1 in Vu’s survey ), which assumes that the underlying probability space is generated by independent random variables (of a special form).

Note that $L_{k}$, $U_{k}$ are ${\mathcal{F}}_{k-1}$-measurable, whereas $M_{k}-M_{k-1}$ is ${\mathcal{F}}_{k}$-measurable. This difference sometimes causes subtle off-by-one errors. As pointed out by Oliver Riordan, for e.g. the estimate

In fact, assuming that $|M_{k}-M_{k-1}|\leq C_{k}$ always holds, the approach of e.g. implies (21) if

Our proofs use the following (standard) inequalities due to Hoeffding and Steiger ; they follow e.g. from the proofs of Lemmas 2.4, 2.6 and 2.8 in McDiarmid’s survey .

Furthermore, $g(x)$ is a non-negative increasing function. ∎

Set $\phi(x)=(1+x)\log(1+x)-x$. For all $x\geq 0$ we have $\phi(x)\geq x^{2}/(2+2x/3)$. ∎

Let ${\mathcal{E}}_{N}$ denote the event that $M_{k}\geq M_{0}+t$ and $S_{k}\leq S$ for some $k\in[N]$. Note that ${\mathcal{E}}_{N}$ implies $Y_{N\wedge T}=Y_{T}\geq e^{\lambda t-\lambda^{2}S/8}$. So, for $\lambda=4t/S$ Markov’s inequality gives

which establishes (19) and thus Lemma 21.

We proceed similarly for $(Z_{k\wedge T})_{0\leq k\leq N}$ and let ${\mathcal{E}}^{\prime}_{N}$ denote the event that $M_{k}\geq M_{0}+t$, $V_{k}\leq V$ and $C_{k}\leq C$ for some $k\in[N]$. Using $V_{k}\geq 0$ and monotonicity of $g(x)\geq 0$ we see that ${\mathcal{E}}^{\prime}_{N}$ implies $Z_{N\wedge T}\geq e^{\lambda t-\lambda^{2}g(\lambda C)V_{k}}\geq e^{\lambda t-\lambda^{2}g(\lambda C)V}$. Recall that $\phi(x)=(1+x)\log(1+x)-x$. For $\lambda=\log(1+Ct/V)/C^{2}$ Markov’s inequality and Lemma 25 now yield

which establishes (20) and thus Lemma 22. ∎

2 Bounded differences inequalities

The textbook proof of Theorem 1 is based on the Hoeffding–Azuma inequality , and essentially uses the ‘worst case’ Lipschitz condition (1) to apply Lemma 21 with $|U_{k}-L_{k}|\leq c_{k}$. We need some modifications to deal with the obstacle that the ‘good’ event $\Gamma$ and thus the ‘typical case’ in (4) does not always hold, and these are partially inspired by the seminal work of Shamir and Spencer from 1987.

We step aside these issues by noting that for good bounds on conditional expected one-step changes it suffices that the conditional probabilities of large changes are small. One key aspect of our approach is that we can always guarantee this via the ‘global’ event $\Gamma$ only, i.e., without having any knowledge about the corresponding conditional distributions.

Let the stopping time $T$ be the minimum of $N$ and the smallest $0\leq k<N$ for which ${\mathcal{B}}_{k}$ holds (note that $T\leq k-1$ is ${\mathcal{F}}_{k-1}$-measurable). Setting $M_{k}=Y_{k\wedge T}$, it follows that the sequence $(M_{k})_{0\leq k\leq N}$ is a martingale with $Y_{0}=M_{0}=\mu$. Since $T=N$ unless ${\mathcal{B}}$ holds, recalling $Y_{N}=f(X)$ we see that

It suffices to show ${\Delta M}_{k}\in[-\Delta_{k},\Delta_{k}]$ for each $k\in[N]$: then the claim follows by applying Lemma 21 with $S=\sum_{k\in[N]}(2\Delta_{k})^{2}$. The following argument is written with an eye on the upcoming proofs (where some modifications are needed). Note that ${\Delta M}_{k}=0$ if $T\leq k-1$ and ${\Delta M}_{k}={\Delta Y}_{k}$ if $T\geq k$. So it is enough to prove that $|{\Delta Y}_{k}|\leq\Delta_{k}$ whenever $T\geq k$. For brevity, for $z\in\Lambda_{k}$ and $y=(y_{k+1},\ldots,y_{N})\in\prod_{k<j\leq N}\Lambda_{j}$ we write $f_{y}(z)$ for $f(X_{1},\ldots,X_{k-1},z,y_{k+1},\ldots,y_{N})$. Note that

Defining $|{\Delta Y}_{k}(a,b)|$ via the next equation, since $X_{1},\ldots,X_{N}$ are independent it follows that

By distinguishing between $X\in\Gamma$ and $X\notin\Gamma$, each time applying (4) as appropriate, we infer

As explained, this completes the proof. ∎

Here we could have used the classical Hoeffding–Azuma inequality since the proof yields (deterministic) bounds for each individual ${\Delta M}_{k}$. We decided to apply Lemma 21 since the forthcoming modifications needed for the ‘dynamic exposure’ of Section 1.1.3 do use its full strength, i.e., that accumulative estimates of the ${\Delta M}_{k}$ suffice.

So, since $X_{k}\in\{0,1\}$ takes only two values, using (28) and (30) we infer for $T\geq k$ that

This completes the proof (by applying Lemma 21 with $S=\sum_{k\in[N]}\Delta_{k}^{2}$). ∎

In fact, Theorem 1 follows by a similar modification (here (28) implies $\max_{a,b}|{\Delta Y}_{k}(a,b)|\leq c_{k}$).

Arguing as in (30) and (31) we readily obtain $|D_{k}|\leq\Delta_{k}$ when $T\geq k$, and thus infer

Using the independence of $X_{1},\ldots,X_{N}$ it follows that for $T\geq k$ we have

Note that (32) implies ${\Delta M}_{k}\leq\max\{1-p_{k},p_{k}\}\cdot\Delta_{k}$, but the resulting minor improvement of $C$ usually has negligible effect.

To bound $|D_{k}|$, first note that $T\geq k$ and independence of $X_{1},\ldots,X_{N}$ yields

So, using (28) and (34), for $T\geq k$ we infer

A similar argument shows that (9) holds after deleting $(1-p_{k})$. The point is that in Corollary 6 there is no ‘good’ event $\Gamma$. Consequently, when invoking (28) in (35) the standard line of reasoning (using (1) instead of (4)) yields $|D_{k}|\leq c_{k}$, and the claim follows. ∎

We start by modifying the proof of Theorem 2. Analogous to (34), if $T\geq k$ then for all $b\in\Lambda_{k}$ we have

Now, arguing as in (29) and using $1+q_{k}^{-1}\leq 2q_{k}^{-1}$, we obtain a natural analogue for $T\geq k$, namely

which establishes the claimed variant of Theorem 2.

In the proofs of Remark 3 and Theorem 4 we only need to adapt (31), and using (36) this follows by straightforward modifications. Similarly, in the proof of Remark 8 it suffices to modify (35), which is standard using (37) together with $(1-p_{k})^{-1}+q_{k}^{-1}\leq 2q_{k}^{-1}(1-p_{k})^{-1}$. ∎

2.2 Some extensions

Note that $f(X)\geq\mu+t$ is increasing (decreasing) if $f(X)$ is increasing (decreasing). Furthermore, in view of (24) it is easy to check that ${\mathcal{B}}_{k-1}$ is increasing (decreasing) if $\Gamma$ is decreasing (increasing). Using the definition ${\mathcal{B}}$ and the assumptions of Remark 5, it follows that $f(X)\geq\mu+t$ and $\neg{\mathcal{B}}$ are either both increasing or decreasing. So Harris’ inequality yields

The monotonicity property implies $\mu\geq\mu^{*}$ (writing $f(X)-f(X^{*})$ as a difference sequence of coordinate changes), so $\Delta=0$ suffices using $\mu+t\geq\mu^{*}+t$ in (39). Turning to the special case $\Gamma=\prod_{j\in[N]}\Gamma_{j}$, note that ${\mathcal{B}}=\neg\Gamma$ suffices to establish (39). Now, since $X^{*}=(X_{1}^{*},\ldots,X_{N}^{*})$ is a family of independent random variables with $X_{k}^{*}\in\Gamma_{k}$ satisfying (L), the claimed variant readily follows from Theorem 1. ∎

2.3 Variants using dynamic exposure

The remaining details for establishing Theorem 13 and 14 are rather straightforward: when invoking the martingale estimates we simply take the ‘worst case’ bounds for $S$, $V$ and $C$ over all possible sets of queried indices $Q\in{\mathcal{Q}}$ (where $Q$ and ${\mathcal{Q}}$ are as defined in Section 1.1.3); for example, using $S=\max_{Q\in{\mathcal{Q}}}\sum_{k\in Q}(2\Delta_{k})^{2}$ in case of Theorem 2. It is this last step where the accumulative random bounds in Lemmas 21 and 22 are crucial (the behaviour of each individual ${\Delta M}_{k}$ may vary significantly for different sample points due to the dynamic order in which the variables are queried).

2.4 Variants using the general Lipschitz condition

Finally, we discuss how to modify the proofs in Section 2.2.1 when the independence assumption is replaced by (GL). We first claim that $\rho_{k}=\rho_{k}(\Sigma_{a},\Sigma_{b}):\Sigma_{a}\to\Sigma_{b}$ is a bijection with equality in (13), i.e., satisfies

Indeed, using (13) and that $\rho_{k}$ is injective it follows that

We modify the proof of Theorem 2, where independence is only used to establish (27). Using (41) and that the bijection $\rho_{k}:\Sigma_{a}\to\Sigma_{b}$ satisfies (40), we obtain

which is the natural analogue of (27). The remainder of the argument carries over with minor modifications. Indeed, proceeding as in (28) (applying (12) instead of (4)) and then appealing to (41), we infer

Now, by arguing as in (29), when $T\geq k$ holds we also have

Remark 16 follows by similar reasoning (noting that the proof of Remark 3 carries over and that (42) equals (14) after replacing $(d_{k}-c_{k})$ with $r_{k}$).

Final number of edges in the reverse H𝐻H-free process

In our analysis of the reverse $H$-free process we use several equivalent definitions (with respect to the final graph). Recall that, starting with the complete graph on vertex set $[n]$, in each step an edge is removed, chosen uniformly at random from all edges contained in a copy of $H$. As in , a moment’s thought reveals that we may instead traverse all $\binom{n}{2}$ edges in random order, each time removing the current edge if and only if it is contained in a copy of $H$ in the evolving graph. As observed by Erdős, Suen and Winkler , after considering $e_{\binom{n}{2}},\ldots,e_{i+1}$ the decision whether $e_{i}$ is removed depends only on the later edges $e_{i-1},\ldots,e_{1}$ (all other ‘surviving’ ones are by construction not contained in a copy of $H$). This allows us to consider the edges in reverse order, where $e_{i}$ is added if and only if it does not complete a copy of $H$ together with $e_{1},\ldots,e_{i-1}$ (it does not matter whether these were added or not). Given a random permutation, we denote the corresponding random graph process after $i$ steps by $G_{n,i}(H)\subseteq G_{n,i}$, where $G_{n,i}$ is the uniform random graph with $n$ vertices and $i$ edges.

For technical reasons it will be convenient to also consider a continuous variant of the above process, where each edge is independently assigned a uniform birth time $B_{e}\in$; the edges are then traversed in ascending order of their birth times (which are all distinct with probability one). The resulting process that considers only those edges with $B_{e}\leq p$ is denoted by $G_{n,p}(H)\subseteq G_{n,p}$. So for $p=1$ all edges are traversed in random order, and it follows that

Conditioned on $B_{e}=q$, the decision whether $e$ is added only depends on the edges $f$ with $B_{f}\leq q$, which have the same distribution as $G_{n,q}$. As noted by Makai , this allows for the use of classical random graph theory when estimating the probability that an edge is added to the evolving graph. Recall that $m_{2}(H)=d_{2}(H)$ for $2$-balanced graphs $H$. For

the next lemma follows from the results of Spencer mentioned in Section 1.2.2. Note that in $G_{n,p}$ every pair of vertices is expected to have $\Theta((\log n)^{2(e_{H}-1)})$ ‘extensions’ to copies of $H$.

The point is that whenever ${\mathcal{I}}$ holds no further edges are added. This allows us to couple both variants of the reverse $H$-free process such that they agree with very high probability after considering only $m$ edges. So for our purposes they are interchangeable, and we obtain the corresponding formal statement by combining Lemma 26 with (44).

Let $H$ be a $2$-balanced graph. There is a coupling such that for every $c>0$ we have

with probability at least $1-n^{-c}$ for $n\geq n_{0}(c,H)$. ∎

Turning to the number of edges in $G_{n,m}(H)$, which we denote by $e(G_{n,m}(H))$, recall that each $e_{i}$ is added if and only if it does not complete a copy of $H$ together with $e_{1},\ldots,e_{i-1}$. So one edge can, in the worst case, influence the decisions of up to $O(\min\{m,n^{v_{H}-2}\})$ edges (whether they are added or not); however, on the ‘typical’ event ${\mathcal{D}}$ of Lemma 26 this is limited to at most $e_{H}\cdot\Psi_{H}=O((\log n)^{2e_{H}})$ edges. For this reason the standard bounded differences inequality fails to give useful bounds (due to large worst case $c_{k}$), whereas a routine application of the typical bounded differences inequality yields sharp concentration, illustrating its ease of use and effectiveness.

Let $H$ be a $2$-balanced graph. For every $c>0$ and $n\geq n_{0}(c,H)$ we have

To establish Theorem 19 it remains to bound the expected final number of edges up to constant factors. Our argument is inspired by Makai , who proved asymptomatically matching bounds in (46) for the class of strictly $2$-balanced graphs (the case $H=K_{3}$ is due to Erdős, Suen and Winkler ). In fact, here we determine the correct order of magnitude for all graphs.

Let $H$ be a graph with $e_{H}\geq 1$. There are $a,A>0$ such that

for $n\geq n_{0}(H)$, where the floor function is only needed when $e_{H}=1$.

For the lower bound in (46) fix $F\subseteq H$ with $d_{2}(F)=m_{2}(H)$ that satisfies $e_{F}\geq 2$ (this choice is possible as $e_{H}\geq 2$). Given $e$ there are at most $Dn^{v_{F}-2}$ extensions to $F$ for some $D=D(F)>0$, so whenever $q\leq n^{-1/m_{2}(H)}$ holds monotonicity and Harris’ inequality yield

Turning to the upper bound in (46), consider $q=\lambda n^{-1/m_{2}(H)}$ with $1\leq\lambda\leq n^{1/m_{2}(H)}$. We apply Janson’s inequality to $Y_{e,H,q}$, which counts the number of extensions of $e$ to $H$ (viewed as subgraphs these do not contain the edge $e$). Note that $e_{H}\geq 2$, $\lambda\geq 1$ and $m_{2}(H)\geq(e_{H}-1)/(v_{H}-2)$ imply

Define ${\mathcal{G}}$ as the set of all proper subgraphs graphs $G\subsetneq H$ with $e_{G}\geq 2$. Considering all possible ‘overlaps’ of extensions of $e$ to $H$ (analogous to the textbook proof of the small subgraphs theorem), the $\Delta$ term of Janson’s inequality satisfies

Linearity of expectation now yields the upper bound in (46). ∎

Our arguments partially generalize to arbitrary graphs, which we shall now briefly discuss. In this case Lemma 26 remains true if we modify ${\mathcal{D}}$ to at most, say, $\Psi_{H}=(\log n)n^{v_{H}-2}p^{e_{H}-1}$ copies, and so the coupling of Lemma 27 carries over (it only uses ${\mathcal{I}}$). With (44) in mind, Theorem 29 shows that the expected final number of edges is $\mu=\Theta(n^{2-1/m_{2}(H)})$. Adjusting the proof of Theorem 28 with $c_{k}=2e_{H}\Psi_{H}$, a short calculation shows that we obtain concentration on an interval of length $\mu n^{-\gamma}$ with $\gamma=\gamma(H)>0$ whenever

Perhaps surprisingly, this condition is satisfied by standard examples of ‘unbalanced’ graphs such as a clique $K_{r}$ with an extra edge hanging off.

The proofs in this section also extend with minor modifications to the more general reverse ${\mathcal{H}}$-free process considered in Theorem 20. In this case the ‘inverted’ processes ${\mathcal{G}}_{n,m}({\mathcal{H}})$ and ${\mathcal{G}}_{n,p}({\mathcal{H}})$ are defined in analogous ways, where an edge is added only when it closes no copy of some $F\in{\mathcal{H}}$. We need to modify ${\mathcal{D}}$ of Lemma 26 so that for all $F\in{\mathcal{H}}$ it ensures at most $\Psi_{F}=\max\{(\log n)n^{v_{F}-2}p^{e_{F}-1},(\log n)^{2}\}$ copies, whereas the corresponding ${\mathcal{I}}$ only applies to the distinguished graph $H$ with $m_{2}(H)=d_{2}(H)=\min_{F\in{\mathcal{H}}}d_{2}(F)$. As before, once ${\mathcal{I}}$ holds no more edges are added. With this in mind the coupling of Lemma 27 as well as the concentration result of Theorem 28 carry over in a straightforward way (noting that $d_{2}(H)\leq d_{2}(F)$ implies $\Psi_{F}\leq(\log n)^{2e_{F}}$ for all $F\in{\mathcal{H}}$). Turning to the expected final number of edges, for the lower bound of Theorem 29 we avoid all $F\in{\mathcal{H}}$ simultaneously. The resulting modification of (48) works for $q\leq n^{-1/m_{2}(H)}$ since $d_{2}(H)\leq d_{2}(F)$ implies $n^{v_{F}-2}q^{e_{F}-1}\leq 1$. For the upper bound it suffices to just avoid the distinguished $2$-balanced graph $H$, so we may reuse the estimates of (49) to establish Theorem 20.

Finally, note that every edge added by $G_{n,m}(H)$ is also added by the $H$-free process defined in Section 1.2.3 (where $e_{i}$ is added if and only if it does not complete a copy of $H$ together with the added edges among $e_{1},\ldots,e_{i-1}$). It follows from Theorem 29 that the expected final number of edges in the $H$-free process is at least $\Omega(n^{2-1/m_{2}(H)})$ for any graph $H$, which improves the $\Omega(n^{2-1/d_{2}(H)})$ bound resulting from the deletion argument of Osthus and Taraz . In fact, if the technical conditions in (50) are satisfied our earlier discussion implies that this lower bound also holds with probability tending to one (not only in expectation), which for ‘unbalanced’ graphs with $m_{2}(H)>d_{2}(H)$ does not follow from Theorem 1 in .

Acknowledgements. I am grateful to my supervisor Oliver Riordan for a very careful reading of an earlier version of this paper, and for many helpful comments. I would also like to thank Tamás Makai for sending me a preprint of , Matas Šileikis for remarks, and Colin McDiarmid for asking whether Theorem 2 extends to random permutations.

References