# A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral
Sparsifiers from a few Random Spanning Trees

Rasmus Kyng
<EMAIL_ADDRESS>
Harvard University Supported by ONR grant N00014-17-1-2127. Zhao Song
<EMAIL_ADDRESS>
Harvard University & UT-Austin

Strongly Rayleigh distributions are a class of negatively dependent
distributions of binary-valued random variables [Borcea, Brändén, Liggett JAMS
09]. Recently, these distributions have played a crucial role in the analysis
of algorithms for fundamental graph problems, e.g. Traveling Salesman Problem
[Gharan, Saberi, Singh FOCS 11]. We prove a new matrix Chernoff bound for
Strongly Rayleigh distributions.

As an immediate application, we show that adding together the Laplacians of
$\epsilon^{-2}\log^{2}n$ random spanning trees gives an $(1\pm\epsilon)$
spectral sparsifiers of graph Laplacians with high probability. Thus, we
positively answer an open question posed in [Baston, Spielman, Srivastava,
Teng JACM 13]. Our number of spanning trees for spectral sparsifier matches
the number of spanning trees required to obtain a cut sparsifier in [Fung,
Hariharan, Harvey, Panigraphi STOC 11]. The previous best result was by
naively applying a classical matrix Chernoff bound which requires
$\epsilon^{-2}n\log n$ spanning trees. For the tree averaging procedure to
agree with the original graph Laplacian in expectation, each edge of the tree
should be reweighted by the inverse of the edge leverage score in the original
graph. We also show that when using this reweighting of the edges, the
Laplacian of single random tree is bounded above in the PSD order by the
original graph Laplacian times a factor $\log n$ with high probability, i.e.
$L_{T}\preceq O(\log n)L_{G}$.

We show a lower bound that almost matches our last result, namely that in some
graphs, with high probability, the random spanning tree is not bounded above
in the spectral order by $\frac{\log n}{\log\log n}$ times the original graph
Laplacian. We also show a lower bound that in $\epsilon^{-2}\log n$ spanning
trees are necessary to get a $(1\pm\epsilon)$ spectral sparsifier.

###### Contents

  1. 1 Introduction
    1. 1.1 Previous work
    2. 1.2 Our results and techniques
  2. 2 Notation
  3. 3 Preliminaries
    1. 3.1 Useful facts and tools
    2. 3.2 Strongly Rayleigh distributions
    3. 3.3 Random spanning trees
  4. 4 A Matrix Chernoff Bound for Strongly Rayleigh Distributions
    1. 4.1 Main result
  5. 5 Applications to Random Spanning Trees
  6. 6 Lower bounds
    1. 6.1 Single spanning tree, low probability
    2. 6.2 Single spanning tree, high probability
    3. 6.3 Sum of a batch of spanning trees
  7. 7 Shrinking Marginals Lemma
  8. Acknowledgements
  9. A Omitted Proofs
    1. A.1 Reverse Chernoff bound

##  1 Introduction

The study of concentration of sums of random variables dates back to Central
Limit Theorems, and hence de Moivre and Laplace [Tij], while modern
concentration bounds for sums of random variables were perhaps first
established by Bernstein [Ber24], and a popular variant now known as Chernoff
bounds was introduced by Rubin and published by Chernoff [Che52].

Concentration of measure for matrix-valued random variables is the phenomenon
that many matrix valued distributions are to close their mean with high
probability, closeness usually being measured by spectral norm. Modern
quantitative bounds of the form often used in theoretical computer science
were derived by Rudelson [Rud99], while Ahlswede and Winter [AW02] established
a useful matrix-version of the Laplace transform that plays a central role in
scalar concentration results such as those of Bernstein. [AW02] combined this
with the Golden-Thompson trace inequality to prove matrix concentration
results. Tropp refined this approach, and by replacing the use of Golden-
Thompson with deep a theorem on concavity of certain trace functions due to
Lieb, Tropp was able to recover strong versions of a wide range of scalar
concentration results, including matrix Chernoff bounds, Azuma and Freedman’s
inequalities for matrix martingales [Tro12].

Matrix concentration results have had an enormous range of applications in
computer science, and are ubiquitous throughout spectral graph theory [ST04,
SS11, CKP+17], sketching [Coh16], approximation algorithms [HSSS16], and deep
learning [ZSJ+17, ZSD17]. Most applications are based on results for
independent random matrices, but more flexible bounds, such as Tropp’s Matrix
Freedman Inquality [Tro11a], have been used to greatly simplify algorithms,
e.g. for solving Laplacian linear equations [KS16] and for semi-streaming
graph sparsification [AG09, KPPS17]. Matrix concentration results are also
closely related to other popular tools sampling tools, such as Karger’s
techniques for generating sparse graphs that approximately preserve the cuts
of denser graphs [BK96].

Negative dependence of random variables is an appealing property that
intuition suggests should help with concentration of measure. Notions of
negative dependence can be formalized in many ways. Roughly speaking, these
notions characterize distributions where where some event occurring ensures
that other events of interest become less likely. A simple example is the
distribution of a sequence of coin flips, conditioned on the total number of
heads in the outcome. In this distribution, conditioning on some coin coming
out heads makes all other coins less likely to come out heads. Unfortunately,
negative dependence phenomena are not as robust as positive association which
can be established from local conditions using the powerful FKG theorem
[FKG71].

Strongly Rayleigh distributions were introduced recently by Borcea, Brändén,
and Liggett [BBL09] as a class of negatively dependent distributions of
binary-valued random variables with many useful properties. Strongly Rayleigh
distributions satisfy useful negative dependence properties, and retain these
properties under natural conditioning operations. Strongly Rayleigh
distributions also satisfy a powerful stability property under conditioning
known as _Stochastic Covering_ [PP14], which is useful for analyzing them
through martingale techniques. A measure on $\\{0,1\\}^{n}$ is said to be
Strongly Rayleigh if its generating polynomial is real stable [BBL09]. There
are many interesting examples of Strongly Rayleigh distributions [PP14]: The
example mentioned earlier of heads of independent coin flips conditional on
the total number of heads in the outcome; symmetric exclusion processes;
determinental point processes and determinental measures on a boolean lattice.
An example of particular interest to us is the edges of uniform or weighted
random spanning trees, which form a Strongly Rayleigh distribution.

We prove a Matrix Chernoff bound for the case of $k$-homogeneous Strongly
Rayleigh distributions. Our bound is slightly weaker than the bound for
independent variables. We give lower bounds that show our bounds are close to
tight in some regimes, but importantly, our lower bounds do not establish
separation from the behaviour of indepedent random matrices, leaving open the
question of whether the true bound should match the independent case in all
regimes – which seems plausible. We use our bound to show new concentration
results related to random spanning trees of graphs. An open question is to
find other interesting applications of our concentration result, e.g. by
analyzing concentration for matrices generated by exclusion processes.

Random spanning trees are one among the most well-studied probabilistic
objects in graph theory, going back to the work of Kirchoff [Kir47] in 1847,
who gave formula relating the number of spanning trees in a graph to the
determinant of the Laplacian of the same graph.

Algorithms for sampling of random spanning trees have been studied
extensively, [Gue83, Bro89, Ald90, Kul90, Wil96, CMN96, KM09, MST15, HX16,
DKP+17, DPPR17, Sch18], and a random spanning tree can now be sampled in
almost linear time [Sch18].

In theoretical computer science, random spanning trees have found a number of
applications, most notably in breakthrough results on approximating the
traveling salesperson problem with symmetric [GSS11] and asymmetric costs
[AGM+10]. Goyal et al. [GRV09] demonstrated that adding just two random
spanning trees sampled from a bounded degree graph gives a $O(\log n)$ cut
sparsifier with probability $1-o(1)$. Later, it was shown by Fung, Hariharan,
Harvey, Panigraphi [FHHP11], that if we sample $O(\epsilon^{-2}\log^{2}n)$
random spanning trees from a graph, reweight the tree edges by the inverse of
their leverage scores in the original graph, and average them together, then
whp. we get a graph where every the weight of edges crossing every cut is
approximately the same in as in the original graph, up to a factor
$(1\pm\epsilon)$. We refer to this as an $\epsilon$-cut sparsifier. The
techniques of Fung et al. unfortunately do not extend to proving spectral
sparsifiers.

Spectral graph sparsifiers were introduced by Spielman and Teng [ST04], who
for any graph $G$ showed how to construct a another graph $H$ with
$\epsilon^{-2}n\operatorname{poly}\log n$ edges s.t. $(1-\epsilon)L_{G}\preceq
L_{H}\preceq(1+\epsilon)L_{G}$, which we refer to as an $\epsilon$-spectral
sparsifier. The construction was refined by Spielman and Srivastava [SS11],
who suggested sampling edges independently111[SS11] analyzed sampling with
replacement, but based on [Tro12], a folklore result shows the same behavior
can be obtained by doing independent coin flips for every edge with low
leverage score, again with inclusion probabilities proportional to leverage
scores. with probability proportional to their _leverage scores_ , and brought
the number of required samples down to $\epsilon^{-2}n\log n$. This analysis
is tight in the sense that if fewer than $o(\epsilon^{-2}n\log n)$ samples are
used, there will be at least a $1/\operatorname{poly}(n)$ probability of
failure. Meanwhile, $\epsilon^{-2}n\frac{\log n}{\log\log n}$ independent
samples in a union of cliques can be shown whp. to fail to give a cut
sparsifier. This can be observed directly from the degree distribution of a
single vertex in the complete graph. For a variant of [SS11] sampling based on
flipping a single coin for each edge to decide whether to keep it or not, it
can also be shown that when the expected number of edges is
$\epsilon^{-2}n\frac{\log n}{\log\log n}$, whp. the procedure fails to give a
cut sparsifier. For arbitrary sparsification schemes, bounds in [BSS12] show
that $\Theta(\epsilon^{-2}n)$ edges are necessary and sufficient to give an
$\epsilon$-spectral sparsifier.

The marginal probability of an edge being present in a random spanning tree is
exactly the leverage score of the edge. This seems to suggest that combining
$\epsilon^{-2}\operatorname{poly}\log n$ spanning trees might give a spectral
sparsifier, but the lack of independence between the sampled edges means the
process cannot be analyzed using existing techniques. Observing this, Baston,
Spielman, Srivastava, Teng [BSST13] in their excellent 2013 survey on
sparsification noted that “it remains to be seen if the union of a small
number of random spanning trees can produce a spectral sparsifier.” We answer
this question in the affirmative. In particular, we show that adding together
$O(\epsilon^{-2}\log^{2}n)$ spanning trees with edges scaled proportional to
inverse leverage scores in the original graph leads to an $\epsilon$-spectral
sparsifier. This matches the bound obtained for cut sparsifiers in [FHHP11].
Our result also implies their earlier bound since a spectral sparsifier is
always a cut sparsifier with the same approximation quality. Before our
result, only a trivial bound on the number of spanning trees required to build
a spectral sparsifier was known. In particular standard matrix concentration
arguments like those in [SS11] prove that $O(\epsilon^{-2}n\log n)$ spanning
trees suffice. Lower bounds in [FHHP11] show that whp. $\Omega(\log n)$ random
spanning trees are required to give a constant factor spectral sparsifier.

We show that whp. $\epsilon^{-2}\frac{\log n}{\log\log n}$ random spanning
trees do not give an $\epsilon$-spectral sparsifier. We also show that the
Laplacian of a single random tree with edges weighted as above satisfies
$L_{T}\preceq O(\log n)L_{G}$ whp., and we give an almost matching lower
bound, showing that in some graphs whp. $L_{T}\not\prec\frac{1}{8}\frac{\log
n}{\log\log n}L_{G}$. Before our work, the main result known about
approximating graphs using $O(1)$ random spanning trees is due to Goyal,
Rademacher, Vempala [GRV09], who showed that surprisingly, when the original
graph has bounded degree, adding two random spanning trees gives a graph whose
cuts approximate the cuts in the original graph up to a factor $O(\log n)$
with good probability. As our result for a single tree establishes only a one-
sided bound an interesting open question remains: Does sampling $O(1)$ random
spanning trees give a $\log n$-factor spectral sparsifier with, say, constant
probability?

###  1.1 Previous work

#### Chernoff-type bound for matrices.

Chernoff-like bounds for matrices appear in Rudelson [Rud99] and Ahlswede and
Winter [AW02]. The latter introduced a useful matrix-variant of the Laplace
transform that is central in concentration bounds for scalar-valued matrices.
Their bounds restricted to iid random matrices, an artifact of their use of
the Golden-Thompson inequality for bounding traces. In contrast, Tropp
obtained more flexible concentration bounds for random matrices by using a
result of Lieb to bound the expected trace of various operators [Tro12],
including bounds for matrix martingales [Tro11b].

In a recent work by Garg, Lee, Song and Srivastava [GLSS18], they show a
Chernoff bound for sums of matrix-valued random variables sampled via a random
walk on an expander graph. This work confirms a conjecture due Wigderson and
Xiao. The proof of Garg et al. is also concerned with matrices that are not
fully independent. In this case the matrices are generated from random walks
on an expander graph. The main idea to deal with dependence issue is using a
new multi-matrix extension of the Golden-Thompson inequality and an adaptation
of Healy’s proof of the expander Chernoff bound in the scalar’s case [Hea08]
to matrix case. Their techniques deal with fairly generic types of dependence,
and cannot leverage the very strong stability properties that arise from the
negative dependence and stochastic covering properties of Strongly Rayleigh
distributions. Harvey and Olver [HO14] proved a matrix concentration result
for randomized pipage rounding, which can be used to show concentration
results for random spanning trees obtained from pipage rounding, but not for
(weighted) uniformly random spaning trees. The central technical element of
their proof is a new variant of a theorem of Lieb on concavity of certain
matrix trace functions.

Matrix martingales have played a central role in a number of algorithmic
results in theoretical computer science [KS16, CMP16, KPPS17], but beyond a
reliance on Tropp’s Matrix Freedman Inequality, these works have little in
common with our approach. However, our bound does share a technical similarity
with [KS16], namely that a sequence of increasingly restricted random choices
in a martingale process lead to a $\log n$ factor in a variance bound.

#### Strongly Rayleigh Distributions in Theoretical Computer Science.

Perhaps the most prominent result on Strongly Rayleigh distributions in
theoretical computer science is the generalization of [MSS13] to Strongly
Rayleigh distributions.

The central technical result of [MSS13] essentially shows that given a
collection of independent random vectors $v_{1},\ldots,v_{m}$ with finite
support in $\mathbb{C}^{n}$ s.t.
$\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}[v_{i}v_{i}^{*}]=I$ and for all
$i$, $\left\lVert v_{i}\right\rVert^{2}\leq\epsilon$, then
${\Pr[\left\lVert\sum_{i=1}^{m}v_{i}v_{i}^{*}\right\rVert\leq(1+\sqrt{\epsilon})^{2}]}>0$.
[AG15] establishes a related result for $k$-homogeneous Strongly Rayleigh
distributions, though they require an additional constraint on the marginal
probability that any given random variable is non-zero being bounded above by
$\delta$, and then establish
${\Pr[\left\lVert\sum_{i=1}^{m}v_{i}v_{i}^{*}\right\rVert\leq
4(\epsilon+\delta)+2(\epsilon+\delta)^{2}]}>0$. Based on this, [AG15]
shows222Their full statement is more general, see [AG15] Corollary 1.9. that
given an unweighted $k$-edge connected graph $G$ where every edge has leverage
score at most $\epsilon$, there exists an unweighted spanning tree s.t.
$L_{T}\preceq O(\frac{1}{k}+\epsilon)\cdot L_{G}$. This is referred to as a
spectrally thin tree with parameter $O(\frac{1}{k}+\epsilon)$.

[AGR16] showed how to algorithmically sample from $k$-homogeneous
Determinental Point Process in time $\operatorname{poly}(k)n\log(n/\epsilon)$,
where $n$ is the dimension of matrix giving rise to the determinental point
process and $\epsilon$ is the allowed total variation distance. Their
techniques are based on generalization proofs of expansion in the base graph
associated with a balanced matroid, a result first established by [FM92].

#### Random spanning trees.

Algorithms for sampling random spanning trees have a long history, but only
recently have they explicitly used matrix concentration [DKP+17, DPPR17,
Sch18]. The matrix concentration arguments in these papers, however, deal
mostly with how modifying a graph results in changes to the distribution of
random spanning trees in the graph. We instead study how closely random
spanning trees resemble the graph they were initially sampled from. Whether
our result in turn has applications for improving sampling algorithms for
random spanning trees is unclear.

The fact that spanning tree edges exhibit negative dependence has been used
strikingly in concentration arguments by Goyal et al. [GRV09] to show that two
random spanning trees gives $O(\log n)$-factor approximate cut sparsifier in
bounded degree graphs, with good probability. This is clearly false when
sampling the same number of edges independently, because this graph has large
probability of having isolated vertices. Goyal et al. improve over independent
sampling by leveraging the fact that for a fixed tree, in some sense, very few
cuts of a given size exist. This is a variant of Karger’s famous cut-counting
techniques [Kar93, KS96] specialized to unweighted trees.

Uses of negatively dependent Chernoff bounds applied to tree edges also
appeared in works on approximation algorithms for TSP problems [GSS11,
AGM+10], where additionally the connectivity properties of the tree play an
important role

In contrast, the techniques of Fung et al. [FHHP11] show that
$O(\epsilon^{-2}\log^{2}n)$ spanning trees suffice to give a
$(1\pm\epsilon)$-cut sparsifier, but they do not show that tree-based
sparsifiers improve over independent sampling, The focus of their paper is to
establish that wide range of different techniques for choosing sampling
probabilities all give cut sparsifiers, by establishing a more flexible
framework than the original cut-sparsifier results of Benczur-Karger [BK96],
using related cut-counting techniques (see [Kar93, KS96]). To extend their
results to spanning trees, they simply observe that the (scalar-valued)
Chernoff bounds they use directly apply to negatively dependent variables, and
hence edges in spanning trees.

Fung et at. [FHHP11] also establish a lower bound, showing that for any
constant $c$, there exists a graph for which obtaining a factor $c$-cut
sparsifier by averaging trees requires using at least $\Omega(\log n)$ trees
to succeed with constant probability.

###  1.2 Our results and techniques

######  Theorem 1.1.

(First main result, a Matrix Chernoff Bound $k$-homogeneous Strongly Rayleigh
Distributions). Suppose $(\xi_{1},\ldots,\xi_{m})\in\\{0,1\\}^{m}$ is a random
vector of $\\{0,1\\}$ variables whose distribution is $k$-homogeneous and
Strongly Rayleigh.

Given a collection of PSD matrices $A_{1},\ldots A_{m}\in\mathbb{R}^{n\times
n}$ s.t. for all $e\in[m]$ we have $\left\lVert A_{e}\right\rVert\leq R$ and
$\left\lVert\operatorname*{{\mathbb{E}}}[\sum_{e}\xi_{e}A_{e}]\right\rVert\leq\mu$.

Then for any $\epsilon>0$,

$\displaystyle\Pr\left[\left\lVert\sum_{e}\xi_{e}A_{e}-\operatorname*{{\mathbb{E}}}\left[\sum_{e}\xi_{e}A_{e}\right]\right\rVert\geq\epsilon\mu\right]\leq
n\exp\left(-\frac{\epsilon^{2}\mu}{R(\log k+\epsilon)}\Theta(1)\right)$

This Matrix Chernoff bound matches the bounds due to Tropp [Tro12], up to the
$\log k$ factor in the exponent. Our lower bounds rule out that a much
stronger bound is true in the $\epsilon\approx\log k$ regime, since the level
of concentration we prove at this $\epsilon$ is stronger than what is ruled
out for $\epsilon\approx\frac{\log k}{\log\log k}$ by the lower bound in
Theorem 1.5. However, this does _not_ rule out that the $\log k$ factor in our
bound is unnecessary. I.e. we cannot rule out that a stronger concentration
statement might match the bound for the independent case given by Tropp
[Tro12].

######  Remark 1.2.

When the Strongly Rayleigh distribution is in fact a product distribution on a
collection of $l$ Strongly Rayleigh distributions that are each
$t$-homogeneous, then the joint distribution is $lt$-homogeneous Strongly
Rayleigh, but in Theorem 1.1, the factor $\log(lt)$ can be replaced by a
factor $\log t$. This applies to the case of independent random spanning
trees, but only gives a constant factor improvement in the number of trees
required.

Our work is related to the concentration inequality of Peres and Pemantle
[PP14], who showed a concentration result for scalar-valued Lipschitz
functions of Strongly Rayleigh distributions. They used Doob martingales
(martingales constructed from sequences of conditional expectations) to prove
their result. We use a similar approach for matrices, constructing Doob matrix
martingales from our Strongly Rayleigh distributions. In addition, we use the
stochastic covering property of Strongly Rayleigh distributions observed by
Peres and Pemantle, but implicitly derived in [BBL09]. This property leads to
bounded differences in Doob martingale sequences for scalars. As in the scalar
setting, it is possible to show concentration results for matrix-valued
martingales. We use the Matrix Freedman inequality333Note, however, that we
are able to prove deterministic bounds on the _predictable quadratic variation
process_ , which means the bound we use is more analogous to a matrix version
Bernstein’s inequality, adapted to martingales. We resort to the more
complicated Freedman’s inequality only because it gives a directly applicable
statement that is known in the literature.  of Tropp. This inequality allows
makes it possible to establish strong concentration bounds based on control of
sample norms and control of the _predictable quadratic variation process_ of
the martingale, a matrix-valued object that is used to measure variance (see
[Tro11b]). We show that as in the scalar setting, the stochastic covering
property of Strongly Rayleigh distributions leads to bounded differences for
Doob matrix martingales. But, we also combine the stochastic covering property
with deceptively simple matrix martingale properties and a negative dependence
condition to derive additional bounds on the predictable quadratic variation
process of the martingale. The key negative dependence property we use is a
simple observation that generalizes, to $k$-homogeneous Strongly Rayleigh
distributions, the fact that in a random spanning tree, conditioning on the
presence of a set of edges lowers the marginal probability of every other
graph edge being in the tree (see Lemma 1.10). While we frame it differently,
it is essentially an immediate consequence of statements in [BBL09]. The
surprise here is how useful this simple observation is for removing issues
with characterizing conditional $k$-homogeneous Strongly Rayleigh
distributions. As a corollary we get our second main result.

######  Theorem 1.3.

(Second main result, concentration bound of a batch of independent random
spanning trees). Given as input a weighted graph $G$ with $n$ vertices and a
parameter $\epsilon>0$, let $T_{1},T_{2},\cdots,T_{t}$ denote $t$ independent
inverse leverage score weighted random spanning trees, if we choose
$t=O(\epsilon^{-2}\log^{2}n)$ then with probability
$1-1/\operatorname{poly}(n)$,

$\displaystyle(1-\epsilon)L_{G}\preceq\frac{1}{t}\sum_{i=1}^{t}L_{T_{i}}\preceq(1+\epsilon)L_{G}.$

Prior to our work, only a trivial bound on the number of spanning trees
required to build a spectral sparsifier was known, namely that standard matrix
concentration arguments like those in [SS11] prove that $O(\epsilon^{-2}n\log
n)$ spanning trees suffice. Note that, the number of spanning trees required
to build spectral sparsifier in our Theorem 1.3 matches the number of spanning
trees required to construct cut sparsifier in previous best result [FHHP11].
The total edge count we require is $\Theta(\epsilon^{-2}n\log^{2}n)$, worse by
a factor $\log n$ than the bound for independent edge sampling obtained in
[SS11]. It is not clear whether this factor in necessary.

######  Remark 1.4.

Suppose we apply our Theorem 1.5 to show that any single random spanning tree
satisfies $L_{T}\preceq O(\log n)\cdot L_{G}$ whp. This is tight up a
$\log\log n$ factor. Then, one can from use this to derive Theorem 1.3 based
on a standard (and tight) Matrix Chernoff bound, and a (laborious) combination
of Doob martingales and stopping time arguments similar to those found in
[Tro12, KS16]. This line of reasoning will lead to the same bounds as Theorem
1.5. Thus, unless one proves more than just a norm bound for each individual
tree, it is not possible improve over our result, except for $\log\log n$
factors.

Like the work of Fung et al. our results for spanning trees do not improve
over the independent case. Fung et al. achieved their result by combining cut
counting techniques with Chernoff bounds for scalar-valued negatively
dependent variables. In our random matrix setting, there are no clear
candidates for a Chernoff bound for negatively dependent random matrices that
we can adopt, and this type of bound is exactly what we develop in the
Strongly Rayleigh case.

We establish a one-sided concentration result for a single tree, namely that
whp. $L_{T}\preceq O(\log n)\cdot L_{G}$. Again, this is a direct application
of Theorem 1.1.

######  Theorem 1.5.

(Third main result, upper bound for the concentration of one random spanning
tree). Given a graph $G$, let $T$ be a random spanning tree, then with
probability at least $1-1/\operatorname{poly}(n)$

$\displaystyle L_{T}\preceq O(\log n)\cdot L_{G}.$

This upper bound is tight up to a factor $\log\log n$ as shown by our almost
matching lower bound stated below.

######  Theorem 1.6.

(Lower bound for the concentration of one random spanning tree). For any
$n\geq 2^{2^{6}}$, there is an unweighted graph $G$ with $n$ nodes, s.t. if we
sample an inverse leverage score weighted random spanning tree $T$, then with
probability at least $1-e^{-n^{.4}}$,

$\displaystyle L_{T}\not\prec\frac{\log n}{8\log\log n}\cdot L_{G}.$

Trivially, the presence of degree one nodes in $L_{T}$ means that in a
complete graph, $L_{G}\not\prec L_{T}$. So choosing any other scaling of the
tree will make at least one of the inequalities $L_{T}\not\prec\frac{1}{8}\log
n/\log\log n\cdot L_{G}$ and $L_{G}\not\prec L_{T}$ true with a larger gap.
Note that in the complete unweighted graph the trees we consider have weight
$\Theta(n)$ on each edge. A random spanning tree in the complete graph has
diameter about $\sqrt{n}$ [RS67]. This can be shown to imply that for an
_unweighted_ random tree $\widehat{T}$,
$L_{G}\not\prec\sqrt{n}L_{\widehat{T}}.$ But once we scale up every edge of
the tree by a factor $\Theta(n)$, the diameter bound no longer directly
implies a spectral gap of the form $L_{G}\not\prec\alpha L_{T}$ for some
$\alpha$. In a ring graph, we get $L_{G}\not\prec(n-2)L_{T}$ and
$L_{T}\not\prec L_{G}$.

We can also show in general that $L_{T}\not\prec 10\log n\cdot L_{G}$, but
with a much smaller probability.

######  Theorem 1.7.

(Lower bound for the concentration of one random spanning tree). For any
$n\geq 4$, there is an unweighted graph $G$ with $n$ nodes, s.t. if we sample
an inverse leverage score weighted random spanning tree $T$, then with
probability at least $2^{-150\log n\log\log n}$,

$\displaystyle L_{T}\not\prec 10\log n\cdot L_{G}.$

And we show a lower bound for $\epsilon$-spectral sparsifiers for random
spanning trees.

######  Theorem 1.8.

(Lower bound for the concentration of multiple random spanning trees). For any
$n\geq 2^{100}$, there is an unweighted graph $G$ with $n$ nodes, s.t. for any
accuracy parameter $\epsilon\in(5n^{-0.1},1/2)$, if we sample
$t=0.05\epsilon^{-2}\log n$ independent random spanning trees with edges
weighted by inverse leverage score, then with probability at least
$1-e^{-n^{.39}}$,

$\displaystyle(1-\epsilon)L_{G}\not\prec\frac{1}{t}\sum_{i=1}^{t}L_{T_{i}}\text{
and }\frac{1}{t}\sum_{i=1}^{t}L_{T_{i}}\not\prec(1+\epsilon)L_{G}.$

Our lower bound is incomparable with that of Fung et al.[FHHP11], who showed
that for any constant $c$, there exists a graph for obtaining a factor $c$-cut
sparsifier by averaging trees requires using at least $\Omega(\log n)$ trees
to succeed with constant probability. Where Fung et. al [FHHP11] used
triangles in their lower bound construction, our bad examples are based on
collections of small cliques, which lets us ensure cut differences in even a
single tree, by giving longer-tailed degree distributions. All of our lower
bounds are based on simple constructions from collections of edge disjoint
cliques, and use the fact that the exact distribution of degrees of a fixed
vertex in a random spanning tree of the complete graph is known. Note that a
lower bound for cut approximation implies a lower-bound for spectral
approximation, because the contrapositive statement is true: spectral
approximation implies cut approximation.

######  Remark 1.9.

In fact, all our lower bounds also directly apply for cut approximation, which
is a strictly stronger result. For example, there is an unweighted graph $G$,
s.t. if we sample an inverse leverage score weighted random spanning tree $T$,
then with probability at least $1-e^{-n^{.4}}$, $T$ has a cut which is larger
than the corresponding cut in $G$ by a factor $\frac{\log n}{8\log\log n}$.

#### Connection to Spectrally Thin Trees

Using their MSS-type existence proof for “small norm outcomes” of homogeneous
Strongly Rayleigh distributions, [AG15] showed that in an unweighted $k$-edge
connected graph $G$ where every edge has leverage score at most $\epsilon$,
there exists an unweighted spanning tree $\widehat{T}$ s.t.
$L_{\widehat{T}}\preceq O(\frac{1}{k}+\epsilon)\cdot L_{G}$. This is referred
to a spectrally thin tree with parameter $O(\frac{1}{k}+\epsilon)$.

In contrast, applying our $k$-homogeneous Strongly Rayleigh Matrix Chernoff
bound to an unweighted graph $G$ where every edge has leverage score at most
$\epsilon$, we can show that an unweighted _random_ spanning tree satisfies
$L_{T}\preceq O(\epsilon\log n)L_{G}$ with high probability. This follows
immediately from our Theorem 1.5, because if we let $T$ denote the unweighted
spanning tree and $\widehat{T}$ corresponding spanning tree with edges
weighted by inverse leverage scores, then

$\displaystyle L_{\widehat{T}}=$ $\displaystyle\leavevmode\nobreak\ \sum_{e\in
T}w(e)b_{e}b_{e}^{\intercal}$ $\displaystyle\preceq$
$\displaystyle\leavevmode\nobreak\ \epsilon\sum_{e\in
T}\frac{1}{l(e)}w(e)b_{e}b_{e}^{\intercal}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ \epsilon L_{\widehat{T}}$
$\displaystyle\preceq$ $\displaystyle\leavevmode\nobreak\ O(\epsilon\log
n)L_{G}$

whp.

The proof in [AG15] is based on an adaptation of the [MSS13] proof, and does
not have clear parallels with our approach. Whereas the key properties of
Strongly Rayleigh distributions that we use are stochastic covering (a
property that limits change in a distribution under conditioning) and
conditional negative dependence, the central element of their approach is a
proof that certain mixed characteristic polynomials associated with
$k$-homogeneous distributions are real stable when the original distribution
is Strongly Rayleigh.

The following Lemma captures a simple but crucial property of Strongly
Rayleigh distributions.

######  Lemma 1.10 (Shrinking Marginals).

Suppose $(\xi_{1},\ldots,\xi_{m})\in\\{0,1\\}^{m}$ is a random vector of
$\\{0,1\\}$ variables whose distribution is $k$-homogeneous and Strongly
Rayleigh, then any set $S\subseteq[m]$ with $|S|\leq k$ for all
$j\in[m]\setminus S$

$\Pr[\xi_{j}=1|\xi_{S}=\mathbf{1}_{S}]\leq\Pr[\xi_{j}=1].$

We provide a proof in Section 7.

##  2 Notation

We use $[n]$ to denote set $\\{1,2,\cdots,n\\}$. Given a vector $x$, we use
$\left\lVert x\right\rVert_{0}$ to denote the number of non-zero entries in
the vector.

#### Matrix and norms.

For a matrix $A$, we use $A^{\top}$ to denote the transpose of $A$. We say
matrix $A$ is positive semi-definite (PSD) if $A=A^{\top}$ and $x^{\top}Ax\geq
0$ for all $x\in\mathbb{R}^{n}$. We use $\succeq,\preceq$ to denote the
semidefinite ordering, e.g. $A\succeq 0$ denotes that $A$ is PSD, and
$A\succeq B$ means $A-B\succeq 0$. We say matrix $A$ is positive definite (PD)
if $A=A^{\top}$ and $x^{\top}Ax>0$ for all $x\in\mathbb{R}^{n}-\\{0\\}$.
$A\succ B$ means $A-B$ is PD.

For matrix $A\in\mathbb{R}^{n\times n}$, we define $\|A\|$ to be the spectral
norm of $A$, i.e.,

$\displaystyle\|A\|=\max_{\|x\|_{2}=1,x\in\mathbb{R}^{n}}x^{\top}Ax.$

Let $\operatorname{tr}(A)$ denote the trace of a square matrix $A$. We use
$\lambda_{\max}(A)$ to denote the largest eigenvalue of matrix $A$. For
symmetric matrix $A\in\mathbb{R}^{n\times n}$, $\lambda_{\max}(A)=\|A\|$ and
$\operatorname{tr}(A)\leq n\|A\|$.

#### The Laplacian matrix-related definitions.

Let $G=(V,E,w)$ be a connected weighted undirected graph with $n$ vertices and
$m$ edges and edge weights $w_{e}>0$. If we orient the edges of $G$
arbitrarily, we can write its Laplacian as $L=B^{\top}WB$, where
$B\in\mathbb{R}^{m\times n}$ is the signed edge-vertex incidence matrix and
defined as follows

$\displaystyle B(e,v)=\begin{cases}1,&\text{\leavevmode\nobreak\
if\leavevmode\nobreak\ }v\text{\leavevmode\nobreak\ is\leavevmode\nobreak\
}e\text{'s\leavevmode\nobreak\ head};\\\ -1,&\text{\leavevmode\nobreak\
if\leavevmode\nobreak\ }v\text{\leavevmode\nobreak\ is\leavevmode\nobreak\
}e\text{'s\leavevmode\nobreak\ tail};\\\ 0,&\text{otherwise.}\end{cases}$

and $W\in\mathbb{R}^{m\times m}$ is the diagonal matrix with $W(e,e)=w_{e}$.

##  3 Preliminaries

###  3.1 Useful facts and tools

This section, we provide some useful tools. For completeness, we prove the
following statement in Appendix A.

######  Fact 3.1.

For any two symmetric matrices

$\displaystyle(A-B)^{2}\preceq 2A^{2}+2B^{2}.$

###  3.2 Strongly Rayleigh distributions

This section provides definitions related to Strongly Rayleigh distributions.
For more details, we refer the readers to [BBL09, PP14].

Let $\mu:2^{[n]}\rightarrow\mathbb{R}_{\geq 0}$ denote a probability
distribution over $2^{[n]}$, and $\sum_{S\subseteq[n]}\mu(S)=1$.

Let $x_{1},x_{2},\cdots,x_{n}$ denote $n$ variables, we use $x$ to denote
$(x_{1},x_{2},\cdots,x_{n})$. For each set $S\subseteq[n]$, we define
$x_{S}=\prod_{i\in S}x_{i}$. We define the generating polynomial for $\mu$ as
follows

$\displaystyle f_{\mu}(x)=\sum_{S\subseteq[n]}\mu(S)\cdot x_{S}.$

We say distribution $\mu$ is $k$-homogeneous if the polynomial $f_{\mu}$ is a
homogeneous polynomial of degree $k$. In other words, for each
$S\in\operatorname{supp}(\mu)$, $|S|=k$.

We say a polynomial $p(x_{1},x_{2},\cdots,x_{n})$ is stable, if
$\text{Im}(x_{i})>0,\forall i\in[n]$, then $p(x_{1},\cdots,x_{n})\neq 0$. We
say polynomial $p$ is real stable, it is stable and all of its coefficients
are real. We say $\mu$ is a Strongly Rayleigh distribution if $f_{\mu}$ is a
real stable polynomial.

######  Fact 3.2 (Conditioning on subset of coordinates).

Consider a random vector $(\xi_{1},\ldots,\xi_{m})\in\\{0,1\\}^{m}$ whose
distribution is $k$-homogeneous Strongly Rayleigh. Suppose we get a binary
vector $\mathbf{b}=(b_{1},\ldots,b_{t})\in\\{0,1\\}^{t}$ with
$\left\lVert\mathbf{b}\right\rVert_{0}=l\leq k$, and we get a set
$S\subset[m]$ with $|S|=t$. Then conditional on $\mathbf{\xi}_{S}=\mathbf{b}$,
the distribution of $\mathbf{\xi}_{[m]\setminus S}$ is $(k-l)$-homogeneous
Strongly Rayleigh.

This fact tells us that if we condition on the value of some entries in the
vector, the remaining coordinates still have a Strongly Rayleigh distribution.

######  Fact 3.3 (Stochastic Covering Property).

Consider a random vector $(\xi_{1},\ldots,\xi_{m})\in\\{0,1\\}^{m}$ whose
distribution is $k$-homogeneous Strongly Rayleigh. Suppose we are given an
index $i\in[m]$. Let $\xi^{\prime}=\xi_{[m]\backslash\\{i\\}}$ be the
distribution on entries of $\xi$ except $i$. Let $\xi^{\prime\prime}$ be the
distribution of $\xi_{[m]\backslash\\{i\\}}$ _conditional_ on $\xi_{i}=1$.
Then, there exists a coupling between $\xi^{\prime}$ and $\xi^{\prime\prime}$
(i.e. a joint distribution the two vectors), s.t. in every outcome of the
coupling the value of $\xi^{\prime}$ can be obtained from the value of
$\xi^{\prime\prime}$ by either changing a single from $0$ to $1$ or by leaving
all entries unchanged.

This fact is known as the _Stochastic Covering Property_ (see [PP14]). It
gives us a convenient tool for relating the conditional distribution of a
subset of the coordinates of the vector to the unconditional distribution.

Note that by Fact 3.2, the distribution of $\xi^{\prime\prime}$ used in Fact
3.3 is $k-1$ homogeneous. In contrast, the outcomes of $\xi^{\prime}$ may have
$k$ or $k-1$ ones. Fact 3.3 tells us that we can pair up all the outcomes of
the conditional distribution $\xi^{\prime\prime}$ with outcome of the
unconditional distribution $\xi^{\prime}$ s.t. only a small change is required
to make them equal. This tells us that the distribution is in some sense not
changing too quickly under conditioning.

###  3.3 Random spanning trees

We provide the formal definition of random spanning tree in this section.

We use the same definitions about spanning trees as [DKP+17]. Let ${\cal
T}_{G}$ denote the set of all spanning subtrees of $G$. We now define a
probability distribution on these trees.

######  Definition 3.4 ($w$-uniform distribution on trees).

Let ${\cal D}_{G}$ be a probability distribution on ${\cal T}_{G}$ such that

$\displaystyle\Pr_{X\sim{\cal D}_{G}}[X=T]\propto\prod_{e\in T}w_{e}.$

We refer to ${\cal D}_{G}$ as the $w$-uniform distribution on ${\cal T}_{G}$.
When the graph $G$ is unweighted, this corresponds to the uniform distribution
on ${\cal T}_{G}$. Crucially, random spanning tree distributions are Strongly
Rayleigh, as shown in [BBL09].

######  Fact 3.5 (Spanning Trees are Strongly Rayleigh).

In a connected weighted graph $G$, the $w$-uniform distribution on spanning
trees is $(n-1)$-homogeneous Strongly Rayleigh.

######  Definition 3.6 (Effective Resistance).

The effective resistance of a pair of vertices $u,v\in V_{G}$ is defined as

$\displaystyle R_{\mathrm{eff}}(u,v)=b^{\top}_{u,v}L^{\dagger}b_{u,v},$

where $b_{u,v}$ is an all zero vector corresponding to $V_{G}$, except for
entries of $1$ at $u$ and $-1$ at $v$.

The a reference for following standard fact about random spanning trees can be
found in [DKP+17].

######  Definition 3.7 (Leverage Score).

The statistical leverage score, which we will abbreviate to leverage score, of
an edge $e=(u,v)\in E_{G}$ is defined as

$\displaystyle l_{e}=w_{e}R_{\mathrm{eff}}(u,v).$

######  Fact 3.8 (Spanning Tree Marginals).

The probability $\Pr[e]$ that an edge $e\in E_{G}$ appears in a tree sampled
$w$-uniformly randomly from ${\cal T}_{G}$ is given by

$\displaystyle\Pr[e]=l_{e},$

where $l_{e}$ is the leverage score of the edge $e$.

##  4 A Matrix Chernoff Bound for Strongly Rayleigh Distributions

We first define a mapping which maps an element into a psd matrix.

######  Definition 4.1 ($Y$-operator).

We use $\Gamma$ to denote $[m]$, we define a mapping
$Y:\Gamma\rightarrow\mathbb{R}^{n\times n}$ such that $Y_{e}$ is a psd matrix
and $\|Y_{e}\|\leq R$.

Throughout this section, we will use $\xi\in\\{0,1\\}^{m}$ to denote a random
length $m$ boolean vector whose distribution is $k$-homogeneous Strongly
Rayleigh. For any set $S\subseteq[m]$, we use $\xi_{S}$ to denote the length
$|S|$ vector that only chooses the entry from indices in $S$.

We will frequently need to work with a different representation of the random
variable $\xi$. We use $\gamma$ to denote this second representation. The
random variable $\gamma$ is composed of a sequence of $k$ random indices
$\gamma_{1},\gamma_{2},\cdots,\gamma_{k}$, each of which takes a value
$e_{1},e_{2},\cdots,e_{k}\in[m]$. The indices give the locations of the ones
in $\xi$, i.e. in an outcome of the two variables $(\xi,\gamma)$, we always
have $\xi_{\\{\gamma_{1},\gamma_{2},\cdots,\gamma_{k}\\}}={\bf 1}$ and
$\xi_{[m]\setminus\\{\gamma_{1},\gamma_{2},\cdots,\gamma_{k}\\}}={\bf 0}$.
Additionally, we want to ensure that the distribution of $\gamma$ is invariant
under permutation: This can clearly be achieved by starting with any
distribution for $\gamma$ that satisfies the coupling with $\xi$ and the
applying a uniformly random permutation to reorder the $k$ indices of $\gamma$
(see [PP14] for a further discussion).

For convenience, for each $i\in[k]$, we define $\gamma_{\leq i}$ and
$\gamma_{\geq i}$ as abbreviated notation for

$\displaystyle\gamma_{1},\gamma_{2},\cdots,\gamma_{i}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }\gamma_{i},\gamma_{i+1},\cdots,\gamma_{k}$

respectively. Let $S=\\{e_{1},e_{2},\cdots,e_{i}\\}\subset[m]$ be one possible
assignment for indices of a subset of the ones in $\xi$, (we require $i\leq
k$). Then the distribution of $\xi_{[m]\setminus S}$ conditional on
$\xi_{S}={\bf 1}$ is the same as the the distribution of $\xi_{[m]\setminus
S}$ conditional on
$(\gamma_{1},\gamma_{2},\cdots,\gamma_{i})=(e_{1},e_{2},\cdots,e_{i})$. In
other words, in terms of the resulting distribution of $\xi_{[m]\setminus S}$,
it is equivalent to condition on either $\gamma_{\leq i}$ or
$\xi_{\gamma_{\leq i}}={\bf 1}$. We define matrix $Z\in\mathbb{R}^{n\times n}$
as follows.

######  Definition 4.2 ($Z$).

Let $Z$ denote $\sum_{e\in\Gamma}\xi_{e}\cdot Y_{e}$ where $\|\xi\|_{0}=k$.
Due to the relationship between $\xi$ and $\gamma$, we can also write $Z$ as

$\displaystyle Z=\sum_{i=1}^{k}Y_{\gamma_{i}}.$

For simplicity, for each $i\in[k]$, we define $Z_{\leq i}$ and $Z_{\geq i}$ as
follows,

$\displaystyle Z_{\leq
i}=\sum_{j=1}^{i}Y_{\gamma_{j}}\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }Z_{\geq i}=\sum_{j=i}^{k}Y_{\gamma_{j}}.$

We define a series of matrices $M_{i}\in\mathbb{R}^{n\times n}$ as follows

######  Definition 4.3 ($M_{i}$, martingale).

We define $M_{0}=\operatorname*{{\mathbb{E}}}[Z]$. For each
$i\in\\{1,2,\cdots,k-1\\}$, we define $M_{i}$ as follows

$\displaystyle M_{i}=\operatorname*{{\mathbb{E}}}_{\gamma_{\geq
i+1}}[Z\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{1},\cdots,\gamma_{i}].$

It is easy to see that

$\displaystyle\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}[M_{i+1}]=M_{i},$

which implies

$\displaystyle\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}[M_{i+1}-M_{i}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{1},\cdots,\gamma_{i}]=0.$ (1)

Note that we can split $Z$ up as

$\displaystyle Z=$ $\displaystyle\leavevmode\nobreak\
\sum_{j=i+2}^{k}Y_{{\gamma}_{j}}+Y_{{\gamma}_{i+1}}+\sum_{j=1}^{i}Y_{\gamma_{j}}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ {Z}_{\geq
i+2}+Y_{{\gamma}_{i+1}}+Z_{\leq i}$ (2)

And similarly $Z={Z}_{\geq i+1}+Z_{\leq i}$.

In order to relate $M_{i}$ and $M_{i+1}$, we will consider a fresh copy of
$\gamma_{\geq i+1}$ which we denote by $\widehat{\gamma}_{\geq i+1}$. We
denote the corresponding fresh copy of $Z_{\geq i+1}$, by $\widehat{Z}_{\geq
i+1}$. We can now give an equivalent definition of $M_{i}$ in terms of the
expectation over $\widehat{\gamma}_{\geq i+1}$, while $M_{i+1}$ is still
defined in terms of the expectation over ${\gamma}_{\geq i+2}$, so that

$\displaystyle M_{i}=\operatorname*{{\mathbb{E}}}_{\widehat{\gamma}_{\geq
i+1}}[\widehat{Z}_{\geq i+1}+Z_{\leq i}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{1},\cdots,\gamma_{i}]\text{ and
}M_{i+1}=\operatorname*{{\mathbb{E}}}_{{\gamma}_{\geq i+2}}[{Z}_{\geq
i+2}+Y_{{\gamma}_{i+1}}+Z_{\leq i}\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{1},\cdots,\gamma_{i},\gamma_{i+1}]$ (3)

Note that both still depend on the same $\gamma_{\leq i}$ vector, and
$M_{i+1}$ depends on $\gamma_{i+1}$, but $M_{i}$ does not. So far, we have
simply introduced a sligtly different notation for $M_{i}$, since the
expectation operation ensures that the value of $M_{i}$ is unchanged.

We let $\xi\in\\{0,1\\}^{m}$ denote the binary vector indicating the positions
of indices $\gamma_{1},\cdots,\gamma_{i},{\gamma}_{i+1},\cdots,$
${\gamma}_{k}$. while letting $\widehat{\xi}\in\\{0,1\\}^{m}$ indicate the
positions of indices of
$\gamma_{1},\cdots,\gamma_{i},\widehat{\gamma}_{i+1},\cdots,\widehat{\gamma}_{k}$.

Note that $k$-homogeneous Strongly Rayleigh implies the stochastic covering
property. By Fact 3.3, the stochastic covering property implies that a
coupling exists s.t. adding either _one_ or _no_ extra “ones” to the vector
$\xi_{[m]\setminus\gamma_{i+1}}$ results in the vector
$\widehat{\xi}_{[m]\setminus\gamma_{i+1}}$. But, since
$\xi_{[m]\setminus\gamma_{i+1}}$ is $k-1$ homogenous and $\widehat{\xi}_{[m]}$
is $k$-homogenous, we can conclude that
$\widehat{\xi}_{[m]\setminus\gamma_{i+1}}$ is obtained from
$\xi_{[m]\setminus\gamma_{i+1}}$ by adding _no_ ones, if and only
$\widehat{\xi}_{[m]}$ has a one at index $\gamma_{i+1}$. From this we conclude
a more helpful form of stochastic covering: we can construct an index
$\widetilde{\gamma}_{i+1}$ and a coupling s.t. conditional on $\gamma_{i+1}$,
the indices $\widetilde{\gamma}_{i+1},\gamma_{i+2},\cdots,{\gamma}_{k}$ have
the same distribution as
$\widehat{\gamma}_{i+1},\widehat{\gamma}_{i+2},\cdots,\widehat{\gamma}_{k}$.
Thus

$\displaystyle{Z}_{\geq i+2}+Y_{\widetilde{\gamma}_{i+1}}=\widehat{Z}_{\geq
i+1}.$ (4)

We define $X_{i+1}=M_{i+1}-M_{i}$ and then by Eq. (1)

$\displaystyle\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}[X_{i+1}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{1},\cdots,\gamma_{i}]=0.$ (5)

Then we can rewrite $X_{i+1}$ in the following way,

######  Claim 4.4.

Let ${\cal D}_{\gamma_{\leq i+1}}$ denote the coupling distribution between
${Z}_{\geq i+2}$ and $Y_{\widetilde{\gamma}_{i+1}}$ such that Eq. (4) holds.
Then

$\displaystyle
X_{i+1}=Y_{{\gamma}_{i+1}}-\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}[Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{\leq i+1}].$

###### Proof.

Note that in the following proof, we should think of $\gamma_{\leq i+1}$ as
fixed.

$\displaystyle X_{i+1}=$ $\displaystyle\leavevmode\nobreak\ M_{i+1}-M_{i}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\gamma_{\geq i+2}}\left[Z\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq
i+1}\right]-\operatorname*{{\mathbb{E}}}_{\gamma_{\geq
i+1}}\left[Z\leavevmode\nobreak\ |\leavevmode\nobreak\ \gamma_{\leq i}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{{\gamma}_{\geq i+2}}\left[{Z}_{\geq
i+2}+Y_{{\gamma}_{i+1}}+Z_{\leq i}\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\ \gamma_{\leq
i+1}\right]-\operatorname*{{\mathbb{E}}}_{\widehat{\gamma}_{\geq
i+1}}\left[\widehat{Z}_{\geq i+1}+Z_{\leq i}\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{{\gamma}_{\geq i+2}}\left[{Z}_{\geq
i+2}+Y_{{\gamma}_{i+1}}+Z_{\leq i}\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\ \gamma_{\leq
i+1}\right]-\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}\left[{Z}_{\geq i+2}+Y_{\widetilde{\gamma}_{i+1}}+Z_{\leq
i}\leavevmode\nobreak\ \bigg{|}\leavevmode\nobreak\ \gamma_{\leq i+1}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}\left[Y_{{\gamma}_{i+1}}-Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i+1}\right]$ (6)

where the first equality follows by definition of $X_{i+1}$, the second
equality follows by Definition 4.3, the third equality follows by Eq. (3), the
fourth equality follows by Eq. (4), and the fifth equality is by linearity of
expectation and cancellation of terms that agree.

Once we condition on $\gamma_{\leq i}$ and ${\gamma}_{i+1}$ being fixed, then
$Y_{\gamma_{i+1}}$ is also fixed. Thus in Eq. (4), we can move
$Y_{\gamma_{i+1}}$ out of Expectation, so that the right hand side of Eq. (4)
becomes

$\displaystyle\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}\left[Y_{\gamma_{i+1}}-Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq
i+1}\right]=Y_{{\gamma}_{i+1}}-\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}[Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{\leq i+1}].$ (7)

∎

######  Fact 4.5.

We condition on $\gamma_{\leq i+1}$. Let ${\cal D}_{\gamma_{\leq i+1}}$ denote
the coupling distribution such that ${Z}_{\geq
i+2}+Y_{\widetilde{\gamma}_{i+1}}=\widehat{Z}_{\geq i+1}$ holds. We define
$U_{{\gamma}_{i+1}}$ as follows

$\displaystyle U_{{\gamma}_{i+1}}=\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}[Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{\leq i+1}].$

Then, we have the following four properties,

$\displaystyle\mathrm{(\@slowromancap i@)}$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{{\gamma}_{i+1}}[U_{{\gamma}_{i+1}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq
i}]=\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}[Y_{{\gamma}_{i+1}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i}],$ $\displaystyle\mathrm{(\@slowromancap
ii@)}$ $\displaystyle\leavevmode\nobreak\ \|Y_{{\gamma}_{i+1}}\|\leq
R,\|U_{{\gamma}_{i+1}}\|\leq R,$ $\displaystyle\mathrm{(\@slowromancap iii@)}$
$\displaystyle\leavevmode\nobreak\ \|Y_{\gamma_{i+1}}-U_{\gamma_{i+1}}\|\leq
R,$ $\displaystyle\mathrm{(\@slowromancap iv@)}$
$\displaystyle\leavevmode\nobreak\ Y_{{\gamma}_{i+1}}^{2}\preceq R\cdot
Y_{{\gamma}_{i+1}},U_{{\gamma}_{i+1}}^{2}\preceq R\cdot U_{{\gamma}_{i+1}}.$

###### Proof.

Proof of (i@). We have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}[U_{\gamma_{i+1}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i}]=$ $\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}\left[\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}\left[Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \gamma_{\leq i+1}\right]\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}\left[\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}\left[Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \gamma_{\leq
i+1}\right]-Y_{\gamma_{i+1}}+Y_{\gamma_{i+1}}\leavevmode\nobreak\
\bigg{|}\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}\left[-X_{i+1}+Y_{\gamma_{i+1}}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}\left[-X_{i+1}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \gamma_{\leq
i}\right]+\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}\left[Y_{\gamma_{i+1}}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}\left[Y_{\gamma_{i+1}}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \gamma_{\leq i}\right],$

where the third step follows by Eq. (7) and Eq. (4), the fourth step follows
by linearity of expectation, and the last step follows by
$\operatorname*{{\mathbb{E}}}_{\gamma_{i+1}}[-X_{i+1}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i}]=0$.

Proof of (ii@).

By definition of $Y$, we have $\|Y_{{\gamma}_{i+1}}\|\leq R.$

$\displaystyle\|U_{{\gamma}_{i+1}}\|=$ $\displaystyle\leavevmode\nobreak\
\left\|\operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}[Y_{\widetilde{\gamma}_{i+1}}\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{\leq i+1}]\right\|$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \operatorname*{{\mathbb{E}}}_{({Z}_{\geq
i+2},Y_{\widetilde{\gamma}_{i+1}})\sim{\cal D}_{\gamma_{\leq
i+1}}}\left[\left\|Y_{\widetilde{\gamma}_{i+1}}\right\|\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i+1}\right]$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ R.$

Proof of (iii@). For any two PSD matrices $A$ and $B$, we have
$\|A-B\|\leq\max(\|A\|,\|B\|)$. Because both $Y_{\gamma_{i+1}}$ and
$U_{\gamma_{i+1}}$ are PSD matrices and
$\max(\|Y_{\gamma_{i+1}}\|,\|U_{\gamma_{i+1}}\|)\leq R$, we get the desired
property.

Proof of (iv@).

It follows by (ii@) and that $Y_{{\gamma}_{i+1}}$ and $U_{{\gamma}_{i+1}}$ are
both PSD matrices. ∎

We can show

######  Claim 4.6.

$\displaystyle\operatorname*{{\mathbb{E}}}_{{\gamma}_{i+1}}\left[(Y_{{\gamma}_{i+1}}-U_{{\gamma}_{i+1}})^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i}\right]\preceq
4R\cdot\operatorname*{{\mathbb{E}}}_{{\gamma}_{i+1}}[Y_{{\gamma}_{i+1}}|\gamma_{\leq
i}]$

###### Proof.

$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{{\gamma}_{i+1}}\left[(Y_{{\gamma}_{i+1}}-U_{{\gamma}_{i+1}})^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle\preceq$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{{\gamma}_{i+1}}\left[2Y_{{\gamma}_{i+1}}^{2}+2U_{{\gamma}_{i+1}}^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle\preceq$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{{\gamma}_{i+1}}\left[2R\cdot
Y_{{\gamma}_{i+1}}+2R\cdot U_{{\gamma}_{i+1}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i}\right]$ $\displaystyle\preceq$
$\displaystyle\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{{\gamma}_{i+1}}\left[4R\cdot
Y_{{\gamma}_{i+1}}\leavevmode\nobreak\ |\leavevmode\nobreak\ \gamma_{\leq
i}\right],$

where the first step follows by Fact A.2, and the second step follows by
$U_{{\gamma}_{i+1}}^{2}\preceq R\cdot U_{{\gamma}_{i+1}}$ and
$Y_{{\gamma}_{i+1}}^{2}\preceq R\cdot Y_{{\gamma}_{i+1}}$. ∎

######  Lemma 4.7.

Let $\operatorname*{{\mathbb{E}}}[\sum_{e\in\Gamma}\xi_{e}Y_{e}]\preceq\mu I$.
For each $i\in\\{1,2,\cdots,k\\}$, we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{{\gamma}_{i}}\left[Y_{{\gamma}_{i}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i-1}\right]\preceq\frac{1}{k+1-i}\mu I.$

###### Proof.

We use ${\bf 1}$ to denote a length $i-1$ vector where each entry is one. We
can think of $\gamma_{\leq i-1}$ as having its values already set to some
edges in $\Gamma$, for example $\gamma_{1}=e_{1},\cdots,\gamma_{i-1}=e_{i-1}$.
Note that all of the $e_{1},\cdots,e_{i-1}$ must be distinct. Then we use
$\Gamma\backslash\gamma_{\leq i-1}$ to denote
$\Gamma\backslash\\{e_{1},\cdots,e_{i-1}\\}$.

$\displaystyle\operatorname*{{\mathbb{E}}}\left[Y_{{\gamma}_{i}}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i-1}\right]=$
$\displaystyle\leavevmode\nobreak\ \sum_{e\in\Gamma\backslash\gamma_{\leq
i-1}}\Pr[\gamma_{i}=e\leavevmode\nobreak\ |\leavevmode\nobreak\ \gamma_{\leq
i-1}]\cdot Y_{e}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{e\in\Gamma\backslash\gamma_{\leq
i-1}}\frac{\Pr[\xi_{e}=1\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{\leq i-1}]}{k-(i-1)}\cdot Y_{e}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ \sum_{e\in\Gamma\backslash\gamma_{\leq
i-1}}\frac{\Pr[\xi_{e}=1\leavevmode\nobreak\ |\leavevmode\nobreak\
\xi_{\gamma_{\leq i-1}}=\bf{1}]}{k-(i-1)}\cdot Y_{e}$ $\displaystyle\preceq$
$\displaystyle\leavevmode\nobreak\ \sum_{e\in\Gamma\backslash\gamma_{\leq
i-1}}\frac{\Pr[\xi_{e}=1]}{k-(i-1)}\cdot Y_{e}$ $\displaystyle\preceq$
$\displaystyle\leavevmode\nobreak\
\sum_{e\in\Gamma}\frac{\Pr[\xi_{e}=1]}{k-(i-1)}\cdot Y_{e}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{k-(i-1)}\operatorname*{{\mathbb{E}}}\left[\sum_{e}\xi_{e}Y_{e}\right]$
$\displaystyle\preceq$ $\displaystyle\leavevmode\nobreak\ \frac{1}{k+1-i}\mu
I$

where the first step follows by definition of expectation, the second step
follows by $\Pr[\gamma_{i}=e\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{\leq i-1}]=\Pr[\xi_{e}=1\leavevmode\nobreak\ |\leavevmode\nobreak\
\gamma_{\leq i-1}]/(k-(i-1))$, the third step follows because
$[\cdot|\gamma_{\leq i-1}]$ is equivalent to $[\cdot|\xi_{\gamma\leq i-1}={\bf
1}]$, the fourth step follows by ($\Pr[\xi_{e}=1\leavevmode\nobreak\
|\leavevmode\nobreak\ \xi_{\gamma\geq i-1}={\bf 1}]\leq\Pr[\xi_{e}=1]$) from
the Shrinking Marginals Lemma 1.10, the fifth step follows by relaxing
$\Gamma\backslash\gamma_{\leq i-1}$, the sixth step follows by
$\Pr[\xi_{e}=1]=\operatorname*{{\mathbb{E}}}[\xi_{e}]$ and linearity of
expectation, and the last step follows by
$\operatorname*{{\mathbb{E}}}[\sum_{e\in\Gamma}\xi_{e}Y_{e}]\preceq\mu I$.

∎

######  Lemma 4.8.

For each $i\in\\{1,2,\cdots,k\\}$

$\displaystyle\operatorname*{{\mathbb{E}}}_{\gamma_{i}}\left[X_{i}^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i-1}\right]\preceq 4\mu R\frac{1}{k+1-i}I.$

###### Proof.

It follows by combining Claim 4.6 and Lemma 4.7 directly. ∎

The above lemma implies this corollary directly

######  Corollary 4.9.

$\displaystyle\sum_{i=1}^{k}\operatorname*{{\mathbb{E}}}_{\gamma_{i}}\left[X_{i}^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i-1}\right]\preceq 10\mu R\log k\cdot I.$

###  4.1 Main result

Before finally proving our main theorem 1.1, we state a useful tool:
Freedman’s inequality for matrices

We state a version from [Tro11b], and there is also another version can be
found in [Oli09].

######  Theorem 4.10 (Matrix Freedman).

Consider a matrix martingale $\\{Y_{i}:i=0,1,2,\cdots\\}$ whose values are
self-adjoint matrices with dimension $n$, and let $\\{X_{i}:i=1,2,3,\cdots\\}$
be the difference sequence. Assume that the difference sequence is uniformly
bounded in the sense that

$\displaystyle\lambda_{\max}(X_{i})\leq R,\mathrm{\leavevmode\nobreak\
almost\leavevmode\nobreak\ surely\leavevmode\nobreak\
}\mathrm{\leavevmode\nobreak\ for\leavevmode\nobreak\ }i=1,2,3,\cdots.$

Define the predictable quadratic variation process of the martingale :

$\displaystyle
W_{i}=\sum_{j=1}^{i}\operatorname*{{\mathbb{E}}}_{j-1}[X_{j}^{2}],\mathrm{\leavevmode\nobreak\
for\leavevmode\nobreak\ }i=1,2,3,\cdots.$

Then, for all $t\geq 0$ and $\sigma^{2}>0$,

$\displaystyle\leavevmode\nobreak\ \Pr\left[\exists i\geq
0:\lambda_{\max}(Y_{i})\geq t\mathrm{\leavevmode\nobreak\
and\leavevmode\nobreak\ }\|W_{i}\|\leq\sigma^{2}\right]$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
n\cdot\exp\left(-\frac{t^{2}/2}{\sigma^{2}+Rt/3}\right).$

Now, we are ready to prove our main theorem,

######  Theorem 1.1.

(First main result, a Matrix Chernoff Bound $k$-homogeneous Strongly Rayleigh
Distributions). Suppose $(\xi_{1},\ldots,\xi_{m})\in\\{0,1\\}^{m}$ is a random
vector of $\\{0,1\\}$ variables whose distribution is $k$-homogeneous and
Strongly Rayleigh.

Given a collection of PSD matrices $A_{1},\ldots A_{m}\in\mathbb{R}^{n\times
n}$ s.t. for all $e\in[m]$ we have $\left\lVert A_{e}\right\rVert\leq R$ and
$\left\lVert\operatorname*{{\mathbb{E}}}[\sum_{e}\xi_{e}A_{e}]\right\rVert\leq\mu$.

Then for any $\epsilon>0$,

$\displaystyle\Pr\left[\left\lVert\sum_{e}\xi_{e}A_{e}-\operatorname*{{\mathbb{E}}}\left[\sum_{e}\xi_{e}A_{e}\right]\right\rVert\geq\epsilon\mu\right]\leq
n\exp\left(-\frac{\epsilon^{2}\mu}{R(\log k+\epsilon)}\Theta(1)\right)$

###### Proof.

We use $Y$ to denote $A$ and $\Gamma$ to denote $[m]$.

In order to use Theorem 4.10, we first we define $W_{i}$ as follows

$\displaystyle
W_{i}=\sum_{j=1}^{i}\operatorname*{{\mathbb{E}}}_{\gamma_{i}}\left[X_{i}^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \gamma_{\leq i-1}\right].$

According to definition of $M_{i}$, $\\{M_{0},M_{1},M_{2}\cdots\\}$ is a
matrix martingale and
$M_{k}-M_{0}=\sum_{e}\xi_{e}A_{e}-\operatorname*{{\mathbb{E}}}[\sum_{e}\xi_{e}A_{e}]$.

We have proved the following facts,

The first one is,
$\operatorname*{{\mathbb{E}}}_{\gamma_{i}}[X_{i}|\gamma_{\leq i-1}]=0$. It
follows by Eq. (5)

The second one is

$\displaystyle\lambda_{\max}(X_{i})\leq R$

It follows by combining Property (iii@) of Fact 4.5 and Claim 4.4.

The third one is

$\displaystyle\|W_{i}\|\leq\sigma^{2},\forall i\in[k]$

where $\sigma^{2}=10\mu R\log k$. It follows by Corollary 4.9.

Thus,

$\displaystyle\Pr\left[\lambda_{\max}(M_{k}-M_{0})\geq\epsilon\mu\right]\leq
n\exp\left(-\frac{(\epsilon\mu)^{2}/2}{\sigma^{2}+R(\epsilon\mu)/3}\right).$

We have

$\displaystyle\frac{t^{2}/2}{\sigma^{2}+Rt/3}=$
$\displaystyle\leavevmode\nobreak\ \frac{\epsilon^{2}\mu^{2}/2}{10\mu R\log
k+R\epsilon\mu/3}$ $\displaystyle\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ choosing\leavevmode\nobreak\ }t=\epsilon\mu$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{3\epsilon^{2}\mu}{(60\log k+2\epsilon)R}.$

Thus we prove one side of the bound. Since
$\operatorname*{{\mathbb{E}}}_{\gamma_{i}}[-X_{i}|\gamma_{\leq i-1}]=0$ and
$\operatorname*{{\mathbb{E}}}_{\gamma_{i}}[(-X_{i})^{2}|\gamma_{\leq
i-1}]=\operatorname*{{\mathbb{E}}}_{\gamma_{i}}[X_{i}^{2}|\gamma_{\leq i-1}]$,
then following the similar procedure as proving $\lambda_{\max}$, we have
bound for $\lambda_{\min}$

$\displaystyle\Pr[\lambda_{\min}(M_{k}-M_{0})\leq-\epsilon\mu]\leq
n\exp\left(-\frac{3\epsilon^{2}\mu}{(60\log k+2\epsilon)R}\right).$

Putting two sides of the bound together, we complete the proof. ∎

##  5 Applications to Random Spanning Trees

In this section, we show how to use Theorem 1.1 to prove the bound for one
random spanning and also summation of random spanning trees.

######  Theorem 1.5.

(Third main result, upper bound for the concentration of one random spanning
tree). Given a graph $G$, let $T$ be a random spanning tree, then with
probability at least $1-1/\operatorname{poly}(n)$

$\displaystyle L_{T}\preceq O(\log n)\cdot L_{G}.$

###### Proof.

Let $G=(V,E,w)$ be a undirected weighted graph, $w:E\to R$, which is
connected. The Laplacian of $G$ is $L_{G}=\sum_{e\in
E}w(e)b_{e}b_{e}^{\intercal}$.

Let $T\subseteq E$ be a random spanning tree of $G$ in the sense of Definition
3.4. Let the weights of the edges in $T$ be given by $w^{\prime}:T\to R$ where
$w^{\prime}(e)=w(e)/l_{e}$, where $l_{e}$ is the leverage score of $e$ in $G$.
Thus the Laplacian of the tree is $L_{T}=\sum_{e\in
T}w^{\prime}(e)b_{e}b_{e}^{\intercal}=\sum_{e\in
T}\frac{w(e)}{l_{e}}b_{e}b_{e}^{\intercal}$. Then by Fact 3.8, $Pr[e\in
T]=l_{e}$, and hence $\operatorname*{{\mathbb{E}}}[L_{T}]=L_{G}$.

Note also that for all $e\in E$,
$||(L_{G}^{\dagger})^{1/2}w(e)b_{e}b_{e}^{\intercal}(L_{G}^{\dagger})^{1/2}||=l_{e}$.
Consider the random matrix
$(L_{G}^{\dagger})^{1/2}L_{T}(L_{G}^{\dagger})^{1/2}$. The distribution of
edge in the spanning tree can be seen as an $n-1$ homogeneous vector in
$\\{0,1\\}^{m}$ where $m=|E|$. To apply Theorem 1.1, let $\xi_{e}$ be the
$e$th entry of this random vector, and

$A_{e}=(L_{G}^{\dagger})^{1/2}w^{\prime}(e)b_{e}b_{e}^{\intercal}(L_{G}^{\dagger})^{1/2}$

Note $A_{e}\succeq 0$. Now $||A_{e}||=1$ and
$\operatorname*{{\mathbb{E}}}\left[\sum_{e}\xi_{e}A_{e}\right]=\operatorname*{{\mathbb{E}}}[(L_{G}^{\dagger})^{1/2}L_{T}(L_{G}^{\dagger})^{1/2}]=(L_{G}^{\dagger})^{1/2}L_{G}(L_{G}^{\dagger})^{1/2}=\Pi=I-\frac{1}{n}\mathbf{1}\mathbf{1}^{\intercal}$,
where we used in the last equality that the null space of the Laplacian of a
connected graph is the span of the all ones vector. Thus, as each we get
$||\operatorname*{{\mathbb{E}}}\left[\sum_{e}\xi_{e}A_{e}\right]||=1$ This
means we can apply Theorem 1.1 with $R=1$, $\mu=1$ and $\epsilon=100\log n$ to
whp. $||(L_{G}^{\dagger})^{1/2}L_{T}(L_{G}^{\dagger})^{1/2}-\Pi||\leq 100\log
n$.

As $L_{T}$ is a Laplacian, it has $\mathbf{1}$ in the null space, so can
conclude that $(L_{G}^{\dagger})^{1/2}L_{T}(L_{G}^{\dagger})^{1/2}\preceq
100\log n\Pi$. Hence $L_{T}\preceq\log nL_{G}$.

∎

######  Theorem 1.3.

(Second main result, concentration bound of a batch of independent random
spanning trees). Given as input a weighted graph $G$ with $n$ vertices and a
parameter $\epsilon>0$, let $T_{1},T_{2},\cdots,T_{t}$ denote $t$ independent
inverse leverage score weighted random spanning trees, if we choose
$t=O(\epsilon^{-2}\log^{2}n)$ then with probability
$1-1/\operatorname{poly}(n)$,

$\displaystyle(1-\epsilon)L_{G}\preceq\frac{1}{t}\sum_{i=1}^{t}L_{T_{i}}\preceq(1+\epsilon)L_{G}.$

###### Proof.

The proof is similar to the proof of Theorem 1.5. Now we view the edges of
$t=O(\epsilon^{-2}\log^{2}n)$ independent random spanning trees as a
$t(n-1)$-homogeneous Strongly Rayleigh Distribution a vector in
$\\{0,1\\}^{t|E|}$ . Note that the product of independent Strongly Rayleigh
distributions is Strongly Rayleigh [BBL09]. Again we get
$||\operatorname*{{\mathbb{E}}}\left[\sum_{e}\xi_{e}A_{e}\right]||=1$, but now
we can take $R=\frac{1}{t}$, and hence we obtain the desired result by
plugging into Theorem 1.1. ∎

##  6 Lower bounds

###  6.1 Single spanning tree, low probability

The goal of this section is to prove Theorem 1.7. First, we recall a helpful
fact estbliashed by Prüfer [Prü18].

######  Fact 6.1.

If $T$ is a uniformly random spanning tree of the complete graph $G$ on $n$
vertices, the degree distribution of a fixed node $v$ in $T$ is
$1+\text{Binomial}(n-2,1/n)$.

We now prove two claims that will serve as helpful tools, Claims 6.2 and 6.3.

######  Claim 6.2.

Let $G$ be complete graph $K_{n}$ with $n\geq 4$, let $T$ denote a random
spanning tree, the probability that at least one node of the $T$ has degree at
least $b\log n$ is at least $2^{-b\log n\log(b\log n)-3}$.

###### Proof.

By Fact 6.1, the degree distribution of a fixed node in $T$ is,
$1+\text{Binomial}(n-2,1/n)$.

For a random variable $x$ sampled from $\text{Binomial}(n-2,1/n)$, we use
$q_{i}$ to denote the probability that $x=i$.

Let $p=1/n$. We consider $q_{b\log n}$, which is

$\displaystyle q_{b\log n}=$ $\displaystyle\leavevmode\nobreak\ {n-2\choose
b\log n}\cdot p^{b\log n}\cdot(1-p)^{n-2-b\log n}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ {n-2\choose b\log n}\cdot(1/n)^{b\log
n}\cdot(1-1/n)^{n-2-b\log n}$ $\displaystyle\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ }p=1/n$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ ((n-2)/(b\log n))^{b\log
n}\cdot(1/n)^{b\log n}\cdot(1-1/n)^{n-2-b\log n}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ (b\log n)^{-b\log n}\cdot((n-2)/n)^{b\log
n}\cdot(1-1/n)^{n-2-b\log n}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ (b\log n)^{-b\log n}\cdot(1-2/n)^{b\log
n}\cdot(1-2/n)^{n-2-b\log n}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ (b\log n)^{-b\log n}\cdot(1-2/n)^{n-2}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\ (b\log n)^{-b\log
n}\cdot\frac{1}{e^{2}}$ $\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
2^{-b\log n\cdot\log(b\log n)-3}.$

where the seventh step follows by $(1-2/n)^{n-2}\geq 1/e^{2}$ when $n\geq
4$.Then the desired probability is

$\displaystyle\sum_{i=b\log n}^{n}q_{i}\geq 2^{-b\log n\cdot\log(b\log n)-3}.$

∎

######  Claim 6.3.

Let $G$ be a complete graph $K_{n}$, let $T$ denote a random spanning tree, if
$T$ has a node with degree at least $d$, then the inverse leverage score
weighted Laplacian of the tree satisfies

$\displaystyle L_{T}\not\preceq(d/2)\cdot L_{G}.$

###### Proof.

There are $n(n-1)/2$ edges in the graph $G$. Let $l_{e}$ denote the leverage
of each $e\in G$. The the sum of the leverage scores is $\sum_{e\in
G}l_{e}=n-1$, e.g. see [SS11]. Since all the edges in the graph $G$ are
symmetric, we have $l_{e}=2/n$ for all edge $e$ in $G$.

Let $v$ denote a fixed node in graph $G$ and let $d$ be the degree of $v$. Let
$L_{v}$ denote the Laplacian matrix of the subgraph of $T$ consisting of edges
incident on $v$, i.e. the star of $d+1$ nodes with $v$ at the center, and with
edge weights as in $T$ (which differ from those in $G$). We should think of
$L_{v}$ as a $n\times n$ matrix with only $d+1$ nonzeros on the diagonal.

Observe that
$\lambda_{\max}(L_{v})\leq\frac{n}{2}\lambda_{\max}(L_{K_{d+1}})\leq\frac{n}{2}(d+1)$.
We can also exhibit a unit vector
$x=\frac{1}{\sqrt{d^{2}+d}}(d,-1,\cdots,-1)$, for which
$x^{\top}L_{v}x=\frac{n}{2}(d+1)$ which implies that
$\lambda_{\max}(L_{v})\geq\frac{n}{2}(d+1)$. Therefore
$\lambda_{\max}(L_{v})=\frac{n}{2}(d+1)$.

We can split the $L_{T}$ into two parts,

$\displaystyle L_{T}=L_{v}+L_{T\backslash v}$

and both parts are PSD matrices. We also know that $\lambda_{\max}(L_{G})=n$.
Thus,

$\displaystyle L_{T}\not\preceq(d/2)\cdot L_{G}.$

∎

######  Theorem 1.7.

(Lower bound for the concentration of one random spanning tree). For any
$n\geq 4$, there is an unweighted graph $G$ with $n$ nodes, s.t. if we sample
an inverse leverage score weighted random spanning tree $T$, then with
probability at least $2^{-150\log n\log\log n}$,

$\displaystyle L_{T}\not\prec 10\log n\cdot L_{G}.$

###### Proof.

The proof is a direct combination of Claim 6.2 and Claim 6.3.

The approximation ratio is

$\displaystyle\frac{d}{2}=\frac{b\log n}{2}=10\log n,$

where the last step follows by choosing $b=20$.

Then the probability is

$\displaystyle 2^{-b\log n\log(b\log n)-3}=$
$\displaystyle\leavevmode\nobreak\ 2^{-b\log n\log\log n-b\log n\log b-3}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\ 2^{-20\log n\log\log
n-20\log n\log 20-3}$ $\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
2^{-150\log n\log\log n}$

where the last step follows by $\log\log n\geq 1$ when $n\geq 4$. ∎

###  6.2 Single spanning tree, high probability

######  Theorem 1.6.

(Lower bound for the concentration of one random spanning tree). For any
$n\geq 2^{2^{6}}$, there is an unweighted graph $G$ with $n$ nodes, s.t. if we
sample an inverse leverage score weighted random spanning tree $T$, then with
probability at least $1-e^{-n^{.4}}$,

$\displaystyle L_{T}\not\prec\frac{\log n}{8\log\log n}\cdot L_{G}.$

###### Proof.

Let $C=4$, and let $\delta=1/(C\log\log n)$. Note we have assumed $n\geq
2^{2^{6}}$, which ensures that $\delta<0.05$.

We constuct a graph of size $n$ as a union of $n^{1-\delta}$ cliques of size
$n^{1-\delta}$ that are disjoint except they all share one central vertex.
Applying Claim 6.2 with $n$ replaced by $n^{\delta}$, and $b=1$, and assuming
$n^{\delta}\geq 8$, we get that for each clique, the probability that at least
one node has degree at least $\log n^{\delta}$ in $T$ is at least

$\displaystyle 2^{-\delta c_{0}\log n\cdot\log(\delta\log n)}$

where $c_{0}=2$. We can lower bound this probability:

$\displaystyle 2^{-\delta c_{0}\log n\cdot\log(\delta\log n)}=$
$\displaystyle\leavevmode\nobreak\ 2^{-\frac{c_{0}\log n}{C\log\log
n}\log(\frac{1}{C\log\log n}\log n)}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ 2^{-\frac{c_{0}\log n}{C\log\log n}\log\log
n}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\ 2^{-(c_{0}\log n)/C}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ n^{-c_{0}/C},$

where the first step follows by $\delta=1/(C\log\log n)$.

The probability that at least one node in $G$ has degree at least $\log
n^{\delta}$ in $T$ is at least

$\displaystyle 1-(1-2^{-\delta c_{0}\log n\log(\delta\log
n)})^{n^{1-\delta}}=$ $\displaystyle\leavevmode\nobreak\
1-\left(1-\frac{1}{n^{c_{0}/C}}\right)^{n^{1-\delta}}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
1-\left(1-\frac{1}{n^{c_{0}/C}}\right)^{n^{c_{0}/C}\cdot\frac{n^{1-\delta}}{n^{c_{0}/C}}}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
1-(1/e)^{n^{1-\delta-{c_{0}/C}}}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ 1-(1/e)^{n^{0.4}},$

where the last step follows by $\delta\leq 0.05$, $c_{0}=2$ and $C=4$. Thus,
we have the desired probability.

Using Claim 6.3, we have the approximation ratio

$\displaystyle\frac{d}{2}=\frac{\log(n^{\delta})}{2}=\frac{\delta\log
n}{2}=\frac{\log n}{2C\log\log n}=\frac{\log n}{8\log\log n}.$

Note that we still need to make sure $n^{\delta}\geq 8$, which is implied by
$2^{\log n/4\log\log n}\geq 2^{3}$ which is equivalent to $\log n\geq
12\log\log n$. This holds for all $n\geq 2^{2^{6}}$: At $n=2^{2^{6}}$, $\log
n=2^{6}>60=12\cdot 5=12\log\log n$, and as $n$ grows, the left hand side grows
faster than the right hand side.

∎

###  6.3 Sum of a batch of spanning trees

######  Theorem 1.8.

(Lower bound for the concentration of multiple random spanning trees). For any
$n\geq 2^{100}$, there is an unweighted graph $G$ with $n$ nodes, s.t. for any
accuracy parameter $\epsilon\in(5n^{-0.1},1/2)$, if we sample
$t=0.05\epsilon^{-2}\log n$ independent random spanning trees with edges
weighted by inverse leverage score, then with probability at least
$1-e^{-n^{.39}}$,

$\displaystyle(1-\epsilon)L_{G}\not\prec\frac{1}{t}\sum_{i=1}^{t}L_{T_{i}}\text{
and }\frac{1}{t}\sum_{i=1}^{t}L_{T_{i}}\not\prec(1+\epsilon)L_{G}.$

###### Proof.

We constuct a graph of size $n$ as a union of $n^{1-\delta}$ cliques of size
$n^{1-\delta}$ that are disjoint except they all share one central vertex. The
parameter $\delta\in(0,1)$ will be decided later.

We use $H$ to denote the graph formed by a collection of trees
$T_{1},T_{2},\cdots,T_{t}$. Let $L_{H}$ denote the Laplacian matrix of new
graph $H$.

We use $\deg(v)$ to denote the degree of a vertex $v$. We use
$\operatorname{wdeg}(v)$ to denote weighted degree (after re-weighting). In
the original graph $G$ and the new graph $H$, we have for each vertex $v$,
that

$\displaystyle\operatorname{wdeg}_{H}(v)=\frac{d}{2t}\deg_{H}(v),\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }\operatorname{wdeg}_{G}(v)=\deg_{G}(v).$

By our construction of the graph, it is easy to see that
$\deg_{G}(v)=n^{\delta}$ for all vertices $v$ except the special central
vertex that appears in all the cliques. Let $d=n^{\delta}$. Let $\xi_{1}$
denote the event that there exists a vertex $x\in V$ such that

$\displaystyle\operatorname{wdeg}_{H}(x)>(1+\epsilon)\operatorname{wdeg}_{G}(x),$

and let $\xi_{2}$ denote that there exists a vertex $y\in V$, such that

$\displaystyle\operatorname{wdeg}_{H}(y)<(1-\epsilon)\operatorname{wdeg}_{G}(y).$

We want to show that events $\xi_{1}$ and $\xi_{2}$ both occur simultaneously
with probability at least $1-e^{-n^{0.39}}$, which implies absence of spectral
$(1\pm\epsilon)$ approximation, as desired. We first bound the probability of
$\xi_{1}$. Note that

$\displaystyle\Pr[\operatorname{wdeg}_{H}(v)\geq(1+\epsilon)\operatorname{wdeg}_{G}(v)]=$
$\displaystyle\leavevmode\nobreak\
\Pr\left[\frac{d}{2t}\deg_{H}(v)\geq(1+\epsilon)\deg_{G}(v)\right]$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\Pr\left[\frac{d}{2t}\deg_{H}(v)\geq(1+\epsilon)d\right]$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ \Pr[\deg_{H}(v)\geq 2t(1+\epsilon)]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ \Pr[\deg_{H}(v)-t\geq
t(1+2\epsilon)].$

By Fact 6.1, the degree of a fixed node in $T_{i}$ is distributed as
$1+\text{Binomial}(d-2,1/d)$. Then as $H$ is a union of independent spanning
trees, the degree in $H$ of a fixed node is distributed as
$t+\text{Binomial}(t(d-2),1/d)$.

For a random variable $x$ sampled from $\text{Binomial}(t(d-2),1/d)$, we know
that $\operatorname*{{\mathbb{E}}}[x]=t(1-2/d)$. For $\epsilon>5/d$

$\displaystyle t(1+2\epsilon)=$ $\displaystyle\leavevmode\nobreak\
t(1-2/d)+(2t/d-2\epsilon t+8\epsilon t/d)+4\epsilon t(1-2/d)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
t(1-2/d)+(10t/d-2\epsilon t)+4\epsilon t(1-2/d)$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ }\epsilon\leq
1$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ t(1-2/d)+4\epsilon
t(1-2/d)$ $\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}\epsilon>5/d.$

So it suffices to calculate the probability that

$\displaystyle x\geq t(1-2/d)+4\epsilon t(1-2/d).$ (8)

For any $k\geq 10,p\in(0,1/2),\epsilon\in(0,1/2)$ with $\epsilon^{2}pk\geq 3$,
using Lemma A.4, we can prove the probability that Eq. (8) holds is at least
$2^{-c\epsilon^{2}kp}$, where $c=9$. We choose $k=t(d-2)$ and $p=1/d$, and get
that this probability is at least $2^{-c\epsilon^{2}t(d-2)/d}$. Now, the
probability that event $\xi_{1}$ holds is at least

$\displaystyle 1-(1-2^{-c\epsilon^{2}t(1-2/d)})^{n^{1-\delta}}$

We have

$\displaystyle 2^{-c\epsilon^{2}t(1-2/d)}\geq$
$\displaystyle\leavevmode\nobreak\ 2^{-c\epsilon^{2}t}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ 1/n^{0.5}$

where the last step follows by $t\leq 0.5\log n/(c\epsilon^{2})$.

Thus, we have

$\displaystyle 1-(1-2^{-c\epsilon^{2}t(1-2/d)})^{n^{1-\delta}}\geq$
$\displaystyle\leavevmode\nobreak\ 1-(1-1/n^{0.5})^{n^{1-\delta}}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
1-e^{-n^{1-\delta-0.5}}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
1-e^{-n^{0.4}}$ $\displaystyle\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ }\delta=0.1$

We summarize the conditions for $\epsilon$:

$\displaystyle\epsilon\geq$ $\displaystyle\leavevmode\nobreak\
\max(5/d,3/\sqrt{pn})$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\max(5/n^{0.1},3/\sqrt{pn})$ $\displaystyle\text{\leavevmode\nobreak\
by\leavevmode\nobreak\ }d=n^{0.1}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ \max(5/n^{0.1},5/\sqrt{t})$

Since we choose $t=0.05\epsilon^{-2}\log n$, then as long as $\log n\geq 100$
we have $\epsilon\geq 5/\sqrt{t}$.

Similarly, we can control the probability of event $\xi_{2}$ similarly,
completing the proof.

∎

##  7 Shrinking Marginals Lemma

######  Lemma 7.1 (Restatement of Lemma 1.10, Shrinking Marginals).

Suppose $(\xi_{1},\ldots,\xi_{m})\in\\{0,1\\}^{m}$ is a random vector of
$\\{0,1\\}$ variables whose distribution is $k$-homogeneous and Strongly
Rayleigh, then any set $S\subseteq[m]$ with $|S|\leq k$ for all
$j\in[m]\setminus S$

$\Pr[\xi_{j}=1|\xi_{S}=\mathbf{1}_{S}]\leq\Pr[\xi_{j}=1]$

###### Proof.

Note that by an immediate consequence of negative association, for any pair
$i,j\in[m]$, with $i\neq j$,

$\Pr[\xi_{j}=1\leavevmode\nobreak\ |\leavevmode\nobreak\
\xi_{i}=1]\leq\Pr[\xi_{j}=1\leavevmode\nobreak\ |\leavevmode\nobreak\
\xi_{i}=0].$

Hence

$\displaystyle\Pr[\xi_{j}=1\leavevmode\nobreak\ |\leavevmode\nobreak\
\xi_{i}=1]\leq$ $\displaystyle\leavevmode\nobreak\
\Pr[\xi_{j}=1|\xi_{i}=1]\cdot\Pr[\xi_{i}=1]+\Pr[\xi_{j}=1|\xi_{i}=0]\cdot(1-\Pr[\xi_{i}=1])$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ \Pr[\xi_{j}=1]$

By [BBL09], the distribution of $\xi_{[m]\backslash\\{i\\}}\in\\{0,1\\}^{m-1}$
conditional on $\xi_{i}=1$ is Strongly Rayleigh.

With loss of generality, let us order the indices s.t. $S=\\{1,\ldots,s\\}$,
where $s\leq k$. We use $[i]$ to denote $\\{1,2,\cdots,i\\}$. Using the above
observations, we can now prove the lemma by induction. The induction
hypothesis at the $i$-th step (where $i\leq k$), is that the following two
statements are true.

  1. 1.

$\forall j\in\\{i+1,\ldots,m\\}.\Pr[\xi_{j}=1\leavevmode\nobreak\
|\leavevmode\nobreak\ \xi_{[i]}=\mathbf{1}]\leq\Pr[\xi_{j}=1]$

  2. 2.

The distribution of the vector of random variables
$\xi_{m\backslash[i]}\in\\{0,1\\}^{m-i}$ conditional on $\xi_{[i]}=\mathbf{1}$
is Strongly Rayleigh.

∎

## Acknowledgements

We thank Yin Tat Lee, Jelani Nelson, Daniel Spielman, Aviad Rubinstein, and
Zhengyu Wang for helpful discussions regarding lower bound examples. We also
thank Neil Olver for pointing out that our current lower bounds cannot
separate the concentration behavior in the Strongly Rayleigh case from the
independent case, correcting a remark in an earlier version of this paper. We
thank Zhengyu Wang for proof-reading the proof of lower bound and provide some
useful comments for presentation.

We want to acknowledge Michael Cohen, who recently passed away. In personal
communication, Michael told Rasmus that he could prove a concentration result
for averaging of spanning trees, although losing several log factors.
Unfortunately, Michael did not relate the proof to anyone, but did say it was
not based on Strongly Rayleigh distributions. We hope he would appreciate our
approach.

We also want to acknowledge the Simons program “Bridging Continuous and
Discrete Optimization” and Nikhil Srivastava whose talks during the program
inspired us to study Strongly Rayleigh questions.

This work was done while Rasmus was a postdoc at Harvard, and Zhao was a
visiting student at Harvard, both hosted by Jelani Nelson. Rasmus was
supported by ONR grant N00014-17-1-2127.

## References

  * [AB09] Martin Anthony and Peter L Bartlett.  Neural network learning: Theoretical foundations.  cambridge university press, 2009.
  * [AG09] Kook Jin Ahn and Sudipto Guha.  Graph sparsification in the semi-streaming model.  In International Colloquium on Automata, Languages, and Programming (ICALP), pages 328–338. Springer, 2009.
  * [AG15] Nima Anari and Shayan Oveis Gharan.  Effective-resistance-reducing flows, spectrally thin trees, and asymmetric tsp.  In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 20–39. IEEE, 2015.
  * [AGM+10] Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi.  An ${O}(\log n/\log\log n)$-approximation algorithm for the asymmetric traveling salesman problem.  In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 379–389, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics.
  * [AGR16] Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei.  Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes.  In Conference on Learning Theory (COLT), pages 103–115, 2016.
  * [Ald90] David Aldous.  The random walk construction of uniform spanning trees and uniform labelled trees.  In SIAM Journal on Discrete Mathematics, pages 450–465, 1990.
  * [AW02] Rudolf Ahlswede and Andreas Winter.  Strong converse for identification via quantum channels.  IEEE Transactions on Information Theory, 48(3):569–579, 2002.
  * [BBL09] Julius Borcea, Petter Brändén, and Thomas Liggett.  Negative dependence and the geometry of polynomials.  Journal of the American Mathematical Society, 22(2):521–567, 2009\.
  * [Ber24] Sergei Bernstein.  On a modification of chebyshev’s inequality and of the error formula of laplace.  Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38–49, 1924.
  * [BK96] András A. Benczúr and David R. Karger.  Approximating s-t minimum cuts in $\widetilde{O}(n^{2})$ time.  In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing (STOC), pages 47–55, New York, NY, USA, 1996. ACM.
  * [Bro89] Andrei Broder.  Generating random spanning trees.  In Proceedings of the 30th annual Symposium on Foundations of Computer Science (FOCS), pages 442–447, 1989.
  * [BSS12] Joshua Batson, Daniel A Spielman, and Nikhil Srivastava.  Twice-ramanujan sparsifiers.  SIAM Journal on Computing, 41(6):1704–1721, 2012.
  * [BSST13] Joshua Batson, Daniel A Spielman, Nikhil Srivastava, and Shang-Hua Teng.  Spectral sparsification of graphs: theory and algorithms.  Communications of the ACM, 56(8):87–94, 2013.
  * [Che52] Herman Chernoff.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  The Annals of Mathematical Statistics, pages 493–507, 1952.
  * [CKP+17] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu.  Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 410–419. ACM, 2017.
  * [CMN96] Charles J Colbourn, Wendy J Myrvold, and Eugene Neufeld.  Two algorithms for unranking arborescences.  Journal of Algorithms, 20(2):268–281, 1996.
  * [CMP16] Michael B Cohen, Cameron Musco, and Jakub Pachocki.  Online row sampling.  In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). arXiv preprint arXiv:1604.05448, 2016.
  * [Coh16] Michael B Cohen.  Nearly tight oblivious subspace embeddings by trace inequalities.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 278–287. SIAM, 2016.
  * [DKP+17] David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva.  Sampling random spanning trees faster than matrix multiplication.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 730–742, New York, NY, USA, 2017. ACM.
  * [DPPR17] David Durfee, John Peebles, Richard Peng, and Anup B. Rao.  Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees.  In Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017.
  * [FHHP11] Wai Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi.  A general framework for graph sparsification.  In Proceedings of the forty-third annual ACM symposium on Theory of computing (STOC), pages 71–80. ACM, 2011.
  * [FKG71] Cees M Fortuin, Pieter W Kasteleyn, and Jean Ginibre.  Correlation inequalities on some partially ordered sets.  Communications in Mathematical Physics, 22(2):89–103, 1971.
  * [FM92] Tomás Feder and Milena Mihail.  Balanced matroids.  In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing (STOC), pages 26–38. ACM, 1992.
  * [GLSS18] Ankit Garg, Yin-Tat Lee, Zhao Song, and Nikhil Srivastava.  A matrix expander chernoff bound.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). arXiv preprint arXiv:1704.03864, 2018.
  * [GRV09] Navin Goyal, Luis Rademacher, and Santosh Vempala.  Expanders via random spanning trees.  In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 576–585. Society for Industrial and Applied Mathematics, 2009.
  * [GSS11] Shayan Oveis Gharan, Amin Saberi, and Mohit Singh.  A randomized rounding approach to the traveling salesman problem.  In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science (FOCS), pages 550–559, Washington, DC, USA, 2011\. IEEE Computer Society.
  * [Gue83] Alain Guenoche.  Random spanning tree.  Journal of Algorithms, 4(3):214–220, 1983.
  * [Hea08] Alexander D Healy.  Randomness-efficient sampling within nc.  Computational Complexity, 17(1):3–37, 2008.
  * [HO14] Nicholas JA Harvey and Neil Olver.  Pipage rounding, pessimistic estimators and matrix concentration.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 926–945. Society for Industrial and Applied Mathematics, 2014.
  * [HSSS16] Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer.  Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC), pages 178–191. ACM, 2016.
  * [HX16] Nicholas J. A. Harvey and Keyulu Xu.  Generating random spanning trees via fast matrix multiplication.  In LATIN 2016: Theoretical Informatics, volume 9644, pages 522–535, 2016.
  * [Kar93] David R Karger.  Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm.  In SODA, volume 93, pages 21–30, 1993.
  * [Kir47] Gustav Kirchhoff.  Uber die auflosung der gliechungen, auf welche man bei der undersuchung der linearen vertheilung galvanischer strome gefuhrt wird.  Poggendorgs Ann. Phys. Chem., pages 497–508, 1847.
  * [KM09] Jonathan Kelner and Aleksander Madry.  Faster generation of random spanning trees.  In Proceedings of the 50th annual Symposium on Foundations of Computer Science (FOCS), pages 13–21, 2009.  Available at https://arxiv.org/abs/0908.1448.
  * [KPPS17] Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva.  A framework for analyzing resparsification algorithms.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2032–2043. SIAM, 2017.
  * [KS96] David R Karger and Clifford Stein.  A new approach to the minimum cut problem.  Journal of the ACM (JACM), 43(4):601–640, 1996.
  * [KS16] Rasmus Kyng and Sushant Sachdeva.  Approximate gaussian elimination for laplacians-fast, sparse, and simple.  In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 573–582. IEEE, 2016.
  * [Kul90] Vidyadhar G. Kulkarni.  Generating random combinatorial objects.  Journal of Algorithms, 11(2):185–207, 1990.
  * [Mou10] Nima Mousavi.  How tight is chernoff bound, 2010.
  * [MSS13] Adam Marcus, Daniel A Spielman, and Nikhil Srivastava.  Interlacing families II: Mixed characteristic polynomials and the kadison-singer problem.  arXiv preprint arXiv:1306.3969, 2013.
  * [MST15] Aleksander Madry, Damian Straszak, and Jakub Tarnawski.  Fast generation of random spanning trees and the effective resistance metric.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2019–2036, 2015.  Available at http://arxiv.org/pdf/1501.00267v1.pdf.
  * [Oli09] Roberto Imbuzeiro Oliveira.  Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges.  arXiv preprint arXiv:0911.0600, 2009.
  * [PP14] Robin Pemantle and Yuval Peres.  Concentration of lipschitz functionals of determinantal and other strong rayleigh measures.  Combinatorics, Probability and Computing, 23(1):140–160, 2014.
  * [Prü18] Heinz Prüfer.  Neuer beweis eines satzes uber permutationen.  Arch. Math. Phys., 27:742–744, 1918.
  * [RS67] A Rényi and G Szekeres.  On the height of trees.  J. Austral. Math. Soc, 7(4):497–5, 1967.
  * [Rud99] Mark Rudelson.  Random vectors in the isotropic position.  Journal of Functional Analysis, 164(1):60–72, 1999.
  * [S+77] Eric V Slud et al.  Distribution inequalities for the binomial law.  The Annals of Probability, 5(3):404–412, 1977.
  * [Sch18] Aaron Schild.  An almost-linear time algorithm for uniform random spanning tree generation.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2018.
  * [SS11] Daniel A Spielman and Nikhil Srivastava.  Graph sparsification by effective resistances.  SIAM Journal on Computing, 40(6):1913–1926, 2011.
  * [ST04] Daniel A. Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing (STOC), pages 81–90, New York, NY, USA, 2004. ACM.
  * [Tij] H Tijms.  Understanding probability: Chance rules in everyday life. 2004.
  * [Tro11a] Joel A Tropp.  Freedman’s inequality for matrix martingales.  Electronic Communications in Probability, 16:262–270, 2011.
  * [Tro11b] Joel A Tropp.  User-friendly tail bounds for matrix martingales.  Technical report, CALIFORNIA INST OF TECH PASADENA, 2011.
  * [Tro12] Joel A Tropp.  User-friendly tail bounds for sums of random matrices.  Foundations of computational mathematics, 12(4):389–434, 2012.
  * [Wil96] David Bruce Wilson.  Generating random spanning trees more quickly than the cover time.  In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing (STOC), pages 296–303, New York, NY, USA, 1996. ACM.
  * [You12] Neal Young.  Reverse chernoff bound.  2012\.  URL:https://cstheory.stackexchange.com/q/14476 (version: 2012-11-26).
  * [ZSD17] Kai Zhong, Zhao Song, and Inderjit S Dhillon.  Learning non-overlapping convolutional neural networks with multiple kernels.  arXiv preprint arXiv:1711.03440, 2017.
  * [ZSJ+17] Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon.  Recovery guarantees for one-hidden-layer neural networks.  In ICML. https://arxiv.org/pdf/1706.03175.pdf, 2017.

##  Appendix A Omitted Proofs

######  Fact A.1.

For any two square matrices $A$ and $B$, we have

$\displaystyle\frac{1}{2}(A+B)^{2}+\frac{1}{2}(A-B)^{2}=A^{2}+B^{2}$

###### Proof.

$\displaystyle\frac{1}{2}(A+B)^{2}+\frac{1}{2}(A-B)^{2}=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{2}(A+B)(A+B)+\frac{1}{2}(A-B)(A-B)$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{2}(A^{2}+BA+AB+B^{2})+\frac{1}{2}(A^{2}-BA-AB+B^{2})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ A^{2}+B^{2},$

which completes the proof. ∎

######  Fact A.2.

For any two symmetric matrices

$\displaystyle(A-B)^{2}\preceq 2A^{2}+2B^{2}.$

###### Proof.

Using Fact A.1, we have

$\displaystyle(A+B)^{2}+(A-B)^{2}=2A^{2}+2B^{2}.$

Because $A$ and $B$ are symmetric matrices, then $(A+B)^{2}\succeq 0$. It
implies that

$\displaystyle(A-B)^{2}\preceq 2A^{2}+2B^{2},$

which completes the proof. ∎

###  A.1 Reverse Chernoff bound

In this Section, we prove that the classical Chernoff bound is tight in some
regimes. There are several different proofs, e.g. [Mou10, S+77, AB09, You12].
For completeness, we provide a proof from [You12].

######  Fact A.3.

If $1\leq l\leq k-1$, then

$\displaystyle{k\choose l}\geq\frac{1}{e\sqrt{2\pi
l}}(\frac{k}{l})^{l}(\frac{k}{k-l})^{k-l}.$

###### Proof.

By Stirling’s approximation, $i!=\sqrt{2\pi i}(i/e)^{i}e^{\lambda}$ for some
$\lambda\in[1/(12i+1),1/(12i)]$.

Thus,

$\displaystyle{k\choose l}=$ $\displaystyle\leavevmode\nobreak\
\frac{k!}{l!(k-l)!}$ $\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{2\pi k}(\frac{k}{e})^{k}}{\sqrt{2\pi
l}(\frac{l}{e})^{l}\sqrt{2\pi(k-l)}(\frac{k-l}{e})^{k-l}}\exp(\frac{1}{12k+1}-\frac{1}{12l}-\frac{1}{12(k-l)})$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\ \frac{\sqrt{2\pi
k}(\frac{k}{e})^{k}}{\sqrt{2\pi
l}(\frac{l}{e})^{l}\sqrt{2\pi(k-l)}(\frac{k-l}{e})^{k-l}}e^{-1}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\ \frac{1}{\sqrt{2\pi
l}}(\frac{k}{l})^{l}(\frac{k}{k-l})^{k-l}e^{-1}.$

where the first step follows by definition, the second step follows by
Stirling’s approximation, the third step follows by
$\frac{1}{1+a+b}+1\geq\frac{1}{a}+\frac{1}{b}$ for $a\geq 12,b\geq 12$.

∎

Now, we are ready to prove the following result

######  Lemma A.4 ([Mou10, S+77, AB09, You12]).

Let $X$ be the average of $k$ independent, Bernoulli random variables with
mean $p$. For any $\epsilon\in(0,1/2]$ and $p\in(0,1/2]$, assuming
$\epsilon^{2}pk\geq 3$, we have

$\displaystyle\Pr[X\leq(1-\epsilon)p]\geq\exp(-9\epsilon^{2}pk),$

and

$\displaystyle\Pr[X\geq(1+\epsilon)p]\geq\exp(-9\epsilon^{2}pk).$

###### Proof.

Note that $\Pr[X\leq(1-\epsilon)p]$ equals the sum
$\sum_{i=0}^{\lfloor(1-\epsilon)pk\rfloor}\Pr[X=i/k]$, and
$\Pr[X=i/k]={k\choose i}p^{i}(1-p)^{k-i}$.

Fix $l=\lfloor(1-2\epsilon)pk\rfloor+1$. The terms in the sum are increasing,
so the terms with index $i\geq\ell$ each have value at least $\Pr[X=l/k]$, so
their sum has total value at least $(\epsilon pk-2)\Pr[X=l/k]$. To complete
the proof, we show that

$\displaystyle(\epsilon pk-2)\Pr[X=l/k]\geq\exp(-9\epsilon^{2}pk).$

The assumptions $\epsilon^{2}pk\geq 3$ and $\epsilon\leq 1/2$ give $\epsilon
pk\geq 6$, so we have

$\displaystyle(\epsilon pk-2)\Pr[X=l/k]\geq$
$\displaystyle\leavevmode\nobreak\ \frac{2}{3}\epsilon pk{k\choose
l}p^{l}(1-p)^{k-l}$ $\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\underbrace{\frac{2}{3}\epsilon pk\frac{1}{\sqrt{2\pi
l}}}_{A}\cdot\underbrace{(\frac{k}{l})^{l}(\frac{k}{k-l})^{k-l}p^{l}(1-p)^{k-l}}_{B}$

Below, we will show that $A\geq\exp(-\epsilon^{2}pk)$ and
$B\geq\exp(-8\epsilon^{2}pk)$.

######  Claim A.5.

$A\geq\exp(-\epsilon^{2}pk)$.

###### Proof.

The assumptions $\epsilon^{2}pk\geq 3$ and $\epsilon\leq 1/2$ imply that
$pk\geq 12$.

By $l\leq pk+1$ (from definition), and $pk\geq 12$, thus $l\leq 1.1pk$.

Therefore, we have

$\displaystyle A\geq$ $\displaystyle\leavevmode\nobreak\
\frac{2}{3e}\epsilon\sqrt{pk/(2.2\pi)}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ \frac{2}{3e}\sqrt{3/(2.2\pi)}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
}\epsilon\sqrt{pk}\geq\sqrt{3}$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ 0.1$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ \exp(-3)$ $\displaystyle\geq$
$\displaystyle\leavevmode\nobreak\ \exp(-\epsilon^{2}pk).$

This completes the proof of the claim. ∎

######  Claim A.6.

$B\geq\exp(-8\epsilon^{2}pk)$.

###### Proof.

Fix $\delta$ such that $l=(1-\delta)pk$. The choice of $l$ implies $\delta\leq
2\epsilon$, so the claim will hold as long as $B\geq\exp(-2\delta^{2}pk)$.
Manipulting this latter inequality, we get

$\displaystyle\leavevmode\nobreak\ B^{-1/l}\leq\exp(\frac{2\delta^{2}pk}{l})$
$\displaystyle\iff$ $\displaystyle\leavevmode\nobreak\
\frac{l}{pk}(\frac{k-l}{(1-p)k})^{k/l-1}\leq\exp(\frac{2\delta^{2}pk}{l}).$

Substituting $l=(1-\delta)pk$ and simplifying, it is equivalent to

$\displaystyle(1-\delta)(1+\frac{\delta
p}{1-p})^{\frac{1}{(1-\delta)p}-1}\leq\exp(\frac{2\delta^{2}}{1-\delta}).$

Taking the logarithm of both sides, we have

$\displaystyle\ln(1-\delta)+(\frac{1}{(1-\delta)p}-1)(\ln(1+\frac{\delta
p}{1-p}))\leq\frac{2\delta^{2}}{1-\delta}$

Since $\ln(1+z)\leq z$, it suffices to prove

$\displaystyle\leavevmode\nobreak\
-\delta+(\frac{1}{(1-\delta)p}-1)(\frac{\delta
p}{1-p})\leq\frac{2\delta^{2}}{1-\delta}$ $\displaystyle\iff$
$\displaystyle\leavevmode\nobreak\
\frac{\delta^{2}}{(1-p)(1-\delta)}\leq\frac{2\delta^{2}}{1-\delta}.$

Since $p\leq 1/2$, this finishes the proof of the claim. ∎

Combining the above two claims, we obtain the desired probability lower bound
for the $(1-\epsilon)$ side. We can prove it for the $(1+\epsilon)$ side
similarly. ∎