A Matrix Expander Chernoff Bound
Ankit Garg∗

Yin Tat Lee†

Zhao Song‡

Nikhil Srivastava§

arXiv:1704.03864v2 [math.PR] 23 Nov 2017

November 27, 2017

Abstract
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via
a random walk on an expander, confirming a conjecture due to Wigderson and Xiao [WX].
Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which
improves in some ways the inequality in [SBT17] and may be of independent interest, as well
as an adaptation of an argument for the scalar case due to Healy [Hea08]. Secondarily, we
also provide a generic reduction showing that any concentration inequality for vector-valued
martingales implies a concentration inequality for the corresponding expander walk, with a
weakening of parameters proportional to the squared mixing time.

∗

Microsoft Research New England, garga@microsoft.com.
University Washington, yintat@uw.edu. This work was partially supported by NSF grant CCF-1740551.
‡
Harvard University & UT-Austin, zhaos@utexas.edu.
§
UC Berkeley, nikhil@math.berkeley.edu. This work was partially supported by NSF grant CCF-1553751 and
a Sloan Research Fellowship.
†

1

Introduction

The Chernoff Bound [Che52] is one of the most widely used probabilistic results in computer science.
It states that a sum of independent bounded random variables exhibits subgaussian concentration
around its mean. In particular, when the random variables are i.i.d. samples from a fixed distribution, it implies that the empirical mean of k samples is -close to the true mean with exponentially
2
small deviation probability proportional to e−Ω(k ) .
An important generalization of this bound was achieved by Gillman [Gil98] (with refinements
later by [Lez98, Kah97, LP04, WX05, Hea08, Wag08, CLLM12, RR17]), who significantly relaxed
the independence assumption to Markov dependence. In particular, suppose G is a regular graph
with vertex set V = [n], X : V → C is a bounded function, and v1 , . . . , vk is a stationary random
walk1 of length k on G. Then, even though the random variables X(vi ) are in not independent
(except when G is the complete graph with self loops), it is shown that:
"
#
k
1X
P
X(vi ) − E[X] >  ≤ 2 · exp(−Ω((1 − λ)k2 )),
(1)
k
i=1

where 1 − λ is the spectral gap of the transition matrix of the random walk. The gain here is
that sampling a stationary random walk of length k on a constant degree graph with constant
spectral gap requires log(n) + O(k) random bits, which is much less than the k log(n) bits required
to produce k independent samples. Since such graphs can be explicitly constructed, this leads to
a generic “derandomization” of the Chernoff bound, which has had several important applications
(see [WX05] for a detailed discussion). In particular, it leads to the following randomness efficient
sampler for scalar-valued functions ([Gil98]) using known strongly explicit constructions of expander
graphs [RVW00, LPS88]:
Theorem 1.1 ([Gil98]). For any  > 0 and k ≥ 1, there is a poly(r)-time computable sampler
σ : {0, 1}r → [n]k , where r = log(n) + O(k) s.t. for all functions f : [n] → [−1, 1] satisfying Ef = 0,
we have that
"
#
k

1X
Pw∈R {0,1}r
f (σ(w)i ) ≥  ≤ 2 exp −Ω −2 k
k
i=1

In many applications of interest k is about log(n), and going from O(log2 (n)) to O(log(n))
random bits leads to a complete derandomization by cycling over all seeds w ∈ {0, 1}r .
A different generalization of the Chernoff bound appeared in the works of Rudelson [Rud99],
Ahlswede-Winter [AW02], and Tropp [Tro12], who showed that a similar concentration phenomenon
is true for matrix-valued random variables. In particular, if X1 , . . . , Xk are independent d × d
complex Hermitian random matrices with kXi k ≤ 1, then the following is true:
#
"
k
1X
(2)
Xi − E[X] >  ≤ 2d · exp(−Ω(k2 )).
P
k
i=1

The only difference between this and the usual Chernoff bound is the factor of d in front of the
deviation probability; to see that it is necessary, notice that the diagonal case simply corresponds
to a direct sum of d arbitrarily correlated instances of the scalar Chernoff bound, so by the union
1

That is the first vertex v1 is chosen uniformly at random – which is the stationary distribution of the graph G.

1

bound the probability should be d times as large in the worst case. This so called “Matrix Chernoff
Bound” has seen several applications as well, notably in quantum information theory, numerical
linear algebra, and spectral graph theory; the reader may consult e.g. the book [Tro15] for many
examples.
We present two different extensions of the above results in this paper.

1.1

A Matrix Expander Chernoff Bound

It is natural to wonder whether there is a common generalization of (1) and (2), i.e., a “Matrix
Expander Chernoff Bound”. Such a result was conjectured by Wigderson and Xiao in [WX] — in
fact, [WX05] contained a proof of it, but the authors later discovered a gap in the proof. In this
paper, we prove the Wigderson and Xiao conjecture, namely:
Theorem 1.2. Let G = (V, E) be a regular undirected graph whose transition matrix has second
eigenvalue λ, and let f : V → Cd×d be a function such that:
1. For each v ∈ V , f (v) is Hermitian and kf (v)k ≤ 1.
P
2.
v∈V f (v) = 0.
Then, for a stationary random walk v1 , . . . , vk with  ∈ (0, 1) we have:




k
X

1
P λmax 
f (vj ) ≥  ≤ d · exp −Ω 2 (1 − λ)k ,
k
j=1




k
X

1
P λmin 
f (vj ) ≤ − ≤ d · exp −Ω 2 (1 − λ)k .
k
j=1

This theorem adds to the amazingly long list of pseudorandom properties of expander graphs.
By applying the theorem with a strongly explicit bounded degree expander, one obtains the following randomness-efficient sampler for matrix-calued functions conjectured in [WX].
Theorem 1.3. For any  > 0, k ≥ 1 and d ≥ 1, there is a poly(r)-time computable sampler
σ : {0, 1}r → [n]k , where r = log(n) + O(k) s.t. for all functions f : [n] → Cd×d satisfying Ef = 0
and for each v ∈ [n], f (v) is Hermitian and kf (v)k ≤ 1, we have that
#
"
k

1X
Pw∈R {0,1}r
f (σ(w)i ) ≥  ≤ 2d exp −Ω −2 k
k
i=1

We remark that while the derandomization applications studied in [WX05] were later recovered
in [WX08] using the method of pessimistic estimators, that method requires additional assumptions to be efficiently implementable (specifically, computability of the matrix moment generating
function, which is problem-dependent) and therefore does not constitute a truly black box derandomization of the matrix Chernoff bound, whereas Theorem 1.3 does. Given the increasing ubiquity
of applications of this bound, we therefore suspect that it will find further applications in the study
of derandomization and expander graphs, beyond the ones mentioned in [WX05].

2

Techniques
To describe the ideas that go into the proof of Theorem 1.2, let us begin by recalling how the usual
scalar Chernoff bound is proved, in the case when the random variables have mean zero. The key
observation is that if X1 , . . . , Xk are independent random variables, then the moment generating
function of the sum is equal to the product of the moment generating functions:
"
!#
k
k
X
Y
E exp t
=
Xi
E[exp(tXi )].
i=1

i=1

This is no longer true in case where the Xi come from a random walk, but we still have the algebraic
fact that
!
k
k
X
Y
exp t
Xi =
exp(tXi ),
(3)
i=1

i=1

which allows one to decompose the sum as a product. The latter allows one to consider the steps
of the random walk separately and analyze the change in the expectation inductively.
The analogue of the moment generating function in the matrix setting is
" "
!##
k
X
Xi
,
E tr exp t
i=1

and the main difficulty is that (3) no longer holds if the matrices Xi do not commute. A substitute
for this fact is given by the Golden-Thompson inequality [Gol65, Tho65], which states that for any
Hermitian A, B:
tr[exp(A + B)] ≤ tr[exp(A) exp(B)].
(4)
The latter expression may further be bounded by k exp(A)ktr[exp(B)], and this is sufficient to prove
(2) in the independent case as is done in [AW02], where an inductive application of it yields
" "
!##
k
k
X
Y
E tr exp t
Xi
≤ tr[I] ·
kE[exp(tXi )]k .
i=1

i=1

However, this approach is too crude to handle the Markov case, roughly because in the absence of
inependence, passing to the norm makes it difficult to utilize the fact that the expectation of each
Xi is zero.
The original proof of Wigderson-Xiao was based on the following plausible multi-matrix generalization of (4):
"
!#
" k
#
k
X
Y
tr exp
Ai
≤ tr
exp(Ai ) ,
i=1

i=1

which turns out to be false for k > 2. To see why, observe that the left hand side is always
nonnegative, whereas the right hand side can be the trace of a product of any three positive
semidefinite matrices, which can be negative (and this is not the case for two matrices). This led
to a fatal gap in their proof.
The main ingredient in our proof is a new multi-matrix generalization of (4), which is inspired
by the following statement that was recently proven in [SBT17] (see also [HKT16]).
3

Theorem 1.4 (Corollary 3.3 in [SBT17]). Let H1 , . . . , Hk ∈ Cd×d be Hermitian matrices. Then
 
 




Y


Z ∞
k
k
1
Y
X
Hj (1 + ib)
Hj (1 − ib) 
log tr 
exp
log tr exp 
Hj  ≤
exp
dµ(b)
2
2
−∞
j=1

j=1

j=k

where µ is some probability distribution on (−∞, ∞).
The above inequality successfully relates the matrix exponential of a sum to a product of
matrix exponentials, but is not adequate for proving an optimal Chernoff bound. The reason is
that all known arguments require a Taylor expansion, and Theorem 1.4 involves integration over
an unbounded region (this region can be truncated, but this introduces a loss which leads to a
suboptimal bound). To remedy this, we prove a new multi-matrix Golden-Thompson inequality,
which only involves integration over a bounded region instead of a line.
Theorem 1.5 (Bounded Multi-matrix Golden-Thompson inequality). Let H1 , . . . , Hk ∈ Cd×d be
Hermitian matrices. Then
 


 

 −iφ 
 iφ  Y
Z π
k
k
1
X
Y
4 2
e
e
log tr exp 
Hj
Hj  dµ(φ)
Hj  ≤
log tr 
exp
exp
π −π
2
2
j=1

2

j=1

j=k

where µ is some probability distribution on [− π2 , π2 ].
We present the proof in Section 3. Theorem 1.5 is likely to be of independent interest and could
have further applications, e.g. in quantum information theory. We draw attention to the following
notable features of the above two theorems:
 iφ 
 −iφ ∗
(a) Since exp(H(1 + ib)) = exp(H(1 − ib))∗ and exp e2 Hj = exp e 2 Hj
for Hermitian
H, the right hand always considers the trace of a matrix times its adjoint, which is always
positive semidefinite, ruling out the bad example described above.
(b) They are average case inequalities, where the averaging is done over specific distributions.
We remark that the first inequality is known to be false in the worst case (i.e., with b = 0
and with other small values of b; see [SBT17] for a discussion).
The main point is that Theorem 1.5 allows one to relate the exponential of a sum of matrices to
a (two-sided) product of bounded d × d matrices and their adjoints. In order to prove Theorem 1.2,
we rewrite this as a one-sided matrix product of d2 × d2 matrices acting on Cd×d , by encoding left
and right multiplication on this space via a tensor product. However, these matrices are no longer
Hermitian (or even normal), so it is difficult to analyze the moment generating function of their
product over the random walk using the perturbation-theoretic approach of [WX05]. We surmount
this difficulty by employing a variant of the more robust linear algebraic proof technique of Healy
[Hea08]. The proof of Theorem 1.2 is presented in Section 4.

1.2

Martingale Approximation of Expander Walks

While Theorem 1.2 provides a satisfactory generalization of the expander Chernoff bound to the case
when one is interested in the spectral norm of a matrix-valued function on V , one could ask what
4

happens for other matrix norms (such as Schatten norms), or even more generally, for functions
taking values in an arbitrary Banach space. Our second contribution is a generic reduction from
this problem, of proving concentration for random variables sampled using a Markov chain, to the
much more well-studied problem (see e.g. [CL06]) of concentration for sums of martingale random
variables.
Theorem 1.6. Suppose G = (V, E) is a regular graph whose transition matrix has second
qP eigenvalue
P
2
λ and f : V → RN is a vector-valued function satisfying v∈V f (v) = 0 with F :=
v∈V kf (v)k2 ,
where k · k2 denotes the Frobenius norm. If v1 , . . . , vk is a stationary random walk on G, then for
every  > 0, there is a martingale difference sequence Z1 , . . . , Zk with respect to the filtration
generated by initial segments of v1 , . . . , vk such that
k
k
1X
1X
f (vi ) = W +
Zi ,
k
k
i=1

i=1

where
1. W is a random vector satisfying kW k2 ≤ .
2. Each term Zi satisfies
kZi k∗ ≤

2 log(F/)
· max kf (v)k∗
v∈V
1−λ

for every norm k · k∗ .
Thus, the empirical sums of any bounded (in any norm) function on a graph are well-approximated
by a martingale whose increments are also bounded, with a loss in the bound depending on the `2
norm F of the function and the spectral gap of the graph. Since F will typically scale with the
number of vertices, the ratio above is typically comparable to the mixing time.
To see the theorem in action, consider the case when f (v) is matrix-valued in d × d Hermitian
matrices and k · k∗ is the operator norm. If kf (v)k ≤ 1 then we have the bound
X
F2 =
kf (v)k2F ≤ dn.
v∈V

Suppose we are interested in obtaining an estimate on the probability:
"
#
1X
P
f (v) >  .
k

(5)

v∈V

Applying Theorem 1.6 with parameter /2 and noting that kW k ≤ kW kF , we have that (5) is at
most
"
#
k
1X
P
Zi > /2 ,
k
i=1

where Zi is a martingale with bound
kZi k ≤

log(nd/)
.
1−λ
5

We now appeal to the existing martingale generalization of (2) (see e.g. [Tro12]) and find that this
probability is at most

 2

k (1 − λ)2
2d · exp −Ω
.
log2 (nd)
While this theorem is much weaker than the previous one in terms of parameters (depending
on the square of the mixing time rather than on the spectral gap), it shows qualitatively that
concentration for Markov chains is a generic phenomenon rather than something specific to matrices.
It also allows one to instantly import the wealth of results regarding concentration for martingales
in various Banach spaces (see e.g., [LT13]) to the random walk setting, albeit with suboptimal
parameters. The simple proof of Theorem 1.6 is presented in Section 5.

2

Preliminaries

√
For an n ∈ N+ , let [n] denote the set {1, 2, · · · , n}. Let i denote −1.
√ For z = a + ib, where
a, b ∈ R, we define the complex conjugate of z to be z = a − ib and |z| = a2 + b2 . Then |z|2 = zz.
z−z
We define real part Re(z) = a and imaginary part Im(z) = b. Then Re(z) = z+z
2 and Im(z) = 2i .
We will be working with D-regular undirected graphs G = (V, E). The number of vertices of the
graph, V will be denoted by n. A will denote the adjacency matrix of the graph and P = A/D will
denote its normalized adjacency matrix. A regular
graph G will be called a λ-expander (0 < λ < 1)
P
if kP xk ≤ λ · kxk for all vectors x ∈ Cn s.t. ni=1 xi = 0.
We will use ei ∈ Cd to denote the standard basis vector with 1 in ith position and 0 everywhere
else.

2.1

Linear Algebra

Matrices and Norms. For matrix A, we use A> to denote the transpose of A, we use A to
denote the entry-wise complex conjugate of A. For square matrix A ∈ Cn×n , we use A∗ to denote
>
the conjugate transpose of matrix A. It is obvious that A∗ = A = A> . We say a complex square
matrix A is Hermitian, if A = A∗ , unitary if AA∗ = A∗ A = I, and positive-semidefinite (psd) if
A = A∗ and x∗ Ax ≥ 0 for all x ∈ Cn . We use ,  to denote the semidefinite ordering, e.g. A  0
means that A is psd.
For p ∈ [1, ∞), define the Schatten p-norm of A as
1/p


kAkp = 

X

spn (A)

n≥1

for s1 (A) ≥ s2 (A) ≥ · · ·p
≥ sn (A) ≥ · · · ≥ 0 the singular values of A, i.e., the eigenvalues of the
Hermitian matrix |A| = (A∗ A). Then kAkpp = tr[|T |p ].
For matrix A ∈ Cn×n , we define kAk to be the spectral norm of A, i.e.,
kAk =

max

kxk2 =1,x∈Cn

x∗ Ax

Tensor Products. Given two vectors v ∈ Cd1 and w ∈ Cd2 , their tensor product v ⊗ w ∈ Cd1 d2 is
the vector whose (i, j)th entry is v(i)w(j) (for concreteness, assume the entries are in lexicographic
6

order). Given two matrices A1 ∈ Cd1 ×d1 and A2 ∈ Cd2 ×d2 , their tensor product A1 ⊗A2 ∈ Cd1 d2 ×d1 d2
is the matrix whose ((i, k), (j, l))th entry is A1 (i, j)A2 (k, l). It is easy to see that
(A ⊗ B)(v ⊗ w) = Av ⊗ Bw
and
(A ⊗ B)(C ⊗ D) = AB ⊗ CD.
For a matrix X ∈

Cd×d ,

2

vec(X) ∈ Cd will denote the vectorized version of the matrix X. That

is
vec(X) =

d
X

X(i, j)ei ⊗ ej

i,j=1

We have the following relationship between matrix multiplication and the tensor product:
vec(AXB) = (A ⊗ B > )vec(X).
Exponential and Logarithm. All logarithms will be taken with the base e, and exp(x) will denote
ex . The matrix exponential of a complex matrix A ∈ Cd×d is defined by the Taylor expansion:
exp(A) =

∞
X
Aj
j=0

j!

,

which converges for all matrices A. We will use the fact that
exp(A) ⊗ exp(B) = exp(A ⊗ I + I ⊗ B),
which may be checked by expanding both sides and comparing terms.
The matrix logarithm of a positive definite matrix A = U DU ∗ with D diagonal and positive is
defined by
log(A) := U log(D)U ∗ ,
where the logarithm of D is taken entrywise. For such matrices we have
log(exp(A)) = exp(log(A)) = A.
For positive definite A and complex z, we define Az := exp(z log(A)).
Polar Decomposition. The polar decomposition of a square complex matrix A is a matrix
decomposition of the form
A = UV
where U is a unitary matrix and V is a psd matrix. The polar decomposition separates matrix A
into a component that stretches the space along a set of orthogonal axes, represented by V , and a
rotation (with possible reflection) represented by U . The decomposition of the complex conjugate
of matrix A can written as
A = UV
The decomposition of the conjugate transpose of matrix A can be written as
A∗ = V ∗ U ∗ .
The following simple proposition will be useful in our proofs.
7

Proposition 2.1. Let A and B be Hermitian psd matrices. Then
tr[AB] ≤ kAk · tr[B]
Proof. Let B =

†
j=1 σj vj vj

Pn

tr[AB] =

n
X

be the eigenvalue decomposition of B. Then

σj tr

h

Avj vj†

j=1

2.2

i

=

n
X

σj vj† Avj

≤

j=1

n
X

σj · kAk = kAk · tr[B]

j=1

Complex analysis

A function f : U → C on a domain U ⊆ C is holomorphic if it has a complex derivative in a
neighborhood of every point z ∈ U . The existence of a complex derivative in a neighborhood is a
very strong condition, for it implies that any holomorphic function is actually infinitely differentiable
and equal to its own Taylor series (i.e., analytic) at every point in U . A biholomorphic function is
a bijective holomorphic function whose inverse is also holomorphic. It follows from the definition
that sums, products, and compositions of holomorphic functions are holomorphic. We will also talk
about matrix-valued holomorphic functions f : U → Cd×d , which just means that every entry is
holomorphic.
The main property that we will use is that the value of a holomorphic function at a point z ∈ U
can be related to values that it takes on the boundary of U , in the following way. A function
f : U → R ∪ {−∞} is called subharmonic if it is upper semicontinuous and
Z 2π
1
f (z) ≤
f (z + reiθ )dθ
2π 0
for all z ∈ U and r > 0 such that the closed disk D(z, r) is contained in U , and all of the above
integrals converge.
We will make frequent use of the following standard fact.
Proposition 2.2. If f is analytic on a domain U ⊂ C then log |f (z)| is subharmonic on U .
Our main tool will be the Poisson Integral Formula for subharmonic functions.
Lemma 2.3 (Poisson integral formula on unit disk [Gra08, Eq 1.3.35]). For any subharmonic
function U defined on the unit disk {z ∈ C : |z| ≤ 1}, we have that
Z π
1
1 − |z|2
U (z) ≤
U (eiϕ ) iϕ
dϕ,
∀ |z| < 1.
2π −π
|e − z|2

3

New Golden-Thompson inequality

We begin by giving an outline of the proof of Theorem 1.5. The proof of Theorem 1.4 in [SBT17]
relies on the multivariate Lie-Trotter product formula (e.g. see [Bha97]), which states that:



1
θ
k
k
X
Y
exp 
Lj  = lim 
exp(θLj ) .
j=1

θ→0+

8

j=1

Im

Im

Re

Figure 1: The function h(z) =

− 1+z
1−z

+

Re

r

1+z
1−z

2

+ 1 maps the unit disk {z ∈ C : |z| ≤ 1} to the

half disk {z ∈ C : |z| ≤ 1 and Re(z) ≥ 0}.
For Hermitian Lj , one can rewrite this as a limit of the Schatten 2−norm, since:
 



log tr exp 

k
X
j=1





Lj  = 2 log exp 

k
1X

2

j=1





Lj 

= lim 2 log 
θ→0+

2

k
Y

j=1


exp



1/θ

θ
Lj 
2
2

Thus, understanding the matrix exponential of a sum is the same as understanding the behavior of
a certain norm of the product as θ → 0. The idea of [SBT17] is to use complex interpolation, along
the lines of the Stein-Hirschman theorem in complex analysis: for every fixed real θ near zero, find
a complex function Fθ (z) that agrees with the right hand side at z = θ and is holomorphic on the
strip {0 ≤ <(z) ≤ 1}. Since the value of a holomorphic function at any point can be related to an
integral of its values on the boundary, this allows one to relate Fθ (θ) to its integrals on {<(z) = 0}
and {<(z) = 1}, which are easy to understand. Taking the limit in θ yields Theorem 1.4.
To avoid integration on the whole vertical line {1 + ib : b ∈ R}, we observe that the above strategy only relies on the fact that θ is enclosed by the two vertical lines {ib : b ∈ R} and {1 + ib : b ∈ R},
and we could have used any other region enclosing a neighborhood of real positive θ near zero, provided we can define the required holomorphic functions Fθ . We choose the half-circle (which is easy
to work with because the Riemann map to the unit disk is explicit) and use it to derive a variant
of the Riesz–Thorin theorem (Theorem 3.3), from which our new multi-matrix Golden-Thompson
inequality follows by mimicking the remainder of the proof of 1.4 given in [SBT17].

3.1

Complex estimate on the half disk

In general, we can upper bound the value of any subharmonic function on a simply connected
domain by mapping the domain to the unit disk via Riemann mapping theorem and applying the
Poisson integral formula. In this section, we will give such estimate on a unit half disk.

9

The following lemma follows from the biholomorphic map from unit disk onto the half disk.
defined in Figure 1.
Lemma 3.1. [Poisson Integral Formula on the Half-Disk] For any analytic function F on the half
disk {z ∈ C : |z| ≤ 1 and Re(z) ≥ 0}, we have that
Z π
1 − ρ2
1
dϕ
(6)
log |F (x)| ≤
log F ◦ h(eiϕ )
2π −π
1 − 2ρ cos(ϕ) + ρ2
for any 0 ≤ x ≤ 1 where
1+z
h(z) = −
+
1−z

s

1+z
1−z

2
+1

and

ρ=

x2 + 2x − 1
.
x2 − 2x − 1

Proof. Note that the function h(z) is a biholomorphic map from the unit disk {z ∈ C : |z| ≤ 1}
to the half disk {z ∈ C : |z| ≤ 1 and Re(z) ≥ 0}. (We provide a proof for completeness, see
Lemma A.1 2 )
Since F and h are holomorphic, log |F ◦ h(z)| is subharmonic. Therefore, we can apply the
Poisson integral formula for subharmonic functions (Lemma 2.3) and get
Z π
1 − |z|2
1
log F ◦ h(eiϕ ) iϕ
log |F ◦ h(z)| ≤
dϕ
2π −π
|e − z|2
Z π
1 − ρ2
1
log F ◦ h(eiϕ )
dϕ
=
2π −π
1 − 2ρ cos(θ − ϕ) + ρ2
for z = ρeiθ .
Setting x = h(z), we obtain that
z=

x2 + 2x − 1
.
x2 − 2x − 1

Therefore, we have that
θ = 0 and ρ =

x2 + 2x − 1
.
x2 − 2x − 1

This gives the desired result.
The following lemma allows us to conveniently study the behavior of certain analytic functions
near zero. The idea is that when |F (z)| is at most 1 on the imaginary axis, log |F (θ)| should be
close to 0 for small θ, and the value of log |F (θ)|/θ can be upper bounded by a suitable average of
the values on the boundary of the half disk.
2

The similar version is an exercise 4 in page 163 (Section VII) of [Con78], and also can be found here, https:
//math.stackexchange.com/questions/882147/find-a-conformal-map-from-semi-disk-onto-unit-disk

10

Lemma 3.2. Given any analytic function F on the half disk {z ∈ C : |z| ≤ 1 and Re(z) ≥ 0}.
Suppose that |F (iy)| ≤ 1 for all y ∈ [−1, 1]. Then, for any 0 ≤ θ ≤ 1/4, we have

log |F (θ)| ≤

4θ
+ O(θ2 )
π

Z

π/2

log F (eiφ ) dµθ (φ)

−π/2

where µθ is some probability distribution on [− π2 , π2 ] depending only on θ, and µθ → some probability
distribution as θ → 0+ .
Proof. Since log |F (iy)| ≤ 0 for all y ∈ [−1, 1] and since h(eiϕ ) is imaginary with modulus at most
1 whenever |ϕ| ≤ π/2, we can ignore these ϕ in the integral (6), namely,
Z π
1
1 − ρ2
log |F (x)| ≤
log F ◦ h(eiϕ )
dϕ
2π −π
1 − 2ρ cos(ϕ) + ρ2
Z
1 − ρ2
1
log F ◦ h(eiϕ )
dϕ.
(7)
≤
2π π/2≤|ϕ|≤π
1 − 2ρ cos(ϕ) + ρ2
To bound the right hand side, for π/2 ≤ |ϕ| ≤ π and 0 ≤ ρ ≤ 1, we can prove the following
statement using elementary calculations (see Lemma A.4),
1 − ρ2
1−ρ
=
± O(1 − ρ)2 .
2
1 − 2ρ cos(ϕ) + ρ
1 − cos(ϕ)
Note that ρ =

θ2 +2θ−1
θ2 −2θ−1

≥ 1 − 4θ for all 0 ≤ θ ≤ 1/4. Therefore, we have that 0 ≤ ρ ≤ 1 and
1 − ρ2
4θ
≤
+ O(θ2 )
1 − 2ρ cos(ϕ) + ρ2
1 − cos(ϕ)

Putting this inequality into (7), we have that


Z
1
4θ
2
log |F (x)| ≤
+ O(θ ) log |F ◦ h(eiϕ )|dϕ.
2π π/2≤|ϕ|≤π 1 − cos(ϕ)
We now observe that
Z
π/2≤|ϕ|≤π

1
dϕ =
1 − cos(ϕ)

Z

−π/2

−π

1
dϕ +
1 − cos(ϕ)

Z

π

π/2

1
dϕ = 2.
1 − cos(ϕ)

Note that h maps eiϕ for π/2 ≤ |ϕ| ≤ π to the boundary of the half disk ([−π/2, π/2]), and let µθ
be some probability distribution on [− π2 , π2 ] depending only on θ. Then we can have

log |F (θ)| ≤

 Z π/2
4θ
2
+ O(θ )
log F (eiφ ) dµθ (φ).
π
−π/2

Note that µθ → some probability distribution as θ → 0+ .

11

3.2

Bounded Multimatrix Golden-Thompson type inequality

Plugging our new complex estimate into the proof of Theorem 3.1 in [SBT17], we obtain the
following Riesz-Thorin-type inequality. We give a complete proof for completeness.
Theorem 3.3 (Riesz-Thorin-type inequality). Let S = {z ∈ C : |z| ≤ 1 and Re(z) ≥ 0} and let G
be a holomorphic map from S to square matrices. Let p0 ≥ p1 ∈ [1, ∞], for θ ∈ (0, 1), define pθ by
θ
1
1−θ
+ .
=
pθ
p0
p1
If z → kG(z)kpRe(z) is uniformly bounded on S and kG(it)kp0 ≤ 1, then for any 0 ≤ θ ≤ 1/4,

log kG(θ)kpθ ≤

 Z π/2
4θ
+ O(θ2 )
log kG(eiφ )kp1 dµθ (φ)
π
−π/2

where µθ is some probability distribution on [− π2 , π2 ] depending only on θ.
Proof. To apply Lemma 3.2, we want to define a holomorphic function F (z) such that
|F (it)| ≤ 1 , |F (z)| ≤ kG(z)kp1 and F (θ) = kG(θ)kpθ .
Now, we describe how to define such F (z). For x ∈ [0, 1], define qx as the Hölder conjugate of
−1
px such that p−1
x + qx = 1. Hence, using the definition of px in the statement, we have
1−x
x
1
=
+ .
qx
q0
q1
Now for our fixed θ ∈ (0, 1), let G(θ) = U V be the polar decomposition of G(θ), where V is positive
definite since G(θ) is always invertible, and U is unitary. Finally, we define X(z) and F (z) by
pθ ( 1−z
+ qz )
q

X(z)∗ = (V /c)

0

1

U ∗ , where c = kV kpθ = kG(θ)kpθ

F (z) = tr[X(z)∗ G(z)].
Note that F (z) is holomorphic. Due to the renormalization c, we can show kX(x + iy))kqqxx = 1
for all x ∈ [0, 1]:
hp
i
qx
kX(x + iy)kqqxx = tr
X ∗ (x + iy)X(x + iy)
by definition of k · kp
h
i
q p ( 1−x + x )
= tr (V /c) x θ q0 q1
by U ∗ U = I
= tr [(V /c)pθ ]

by

= 1.

1
1−x
x
=
+
qx
q0
q1
by c = kV kpθ

Therefore, F (z) is bounded on S as follows
|F (x + iy)| ≤ kX(x + iy)kqx · kG(x + iy)kpx ≤ kG(x + iy)kpx
Using this, it is obvious that
|F (it)| ≤ kG(it)kp0 ≤ 1, and |F (z)| ≤ kG(z)kpRe(z) ≤ kG(z)kp1 .
12

for all z ∈ S where we used that p0 ≥ pRe(z) ≥ p1 .
Finally, we verify that F (θ) = kG(θ)kpθ :
F (θ) = tr[X(θ)∗ G(θ)]
pθ ( 1−θ
+ qθ )
q

= tr[(V /c)

0

1

pθ ( 1−θ
+ qθ )
q0
1

= tr[(V /c)

U∗ · UV ]

by definition of X and G
by U ∗ U = I
θ
1
1−θ
+
by
=
qθ
q0
q1
by pθ /qθ = pθ (1 − 1/pθ ) = pθ − 1

V]

= tr[c−pθ /qθ V 1+pθ /qθ ]
= tr[c1−pθ V pθ ]

by (tr[V pθ ])1/pθ = c

= c1−pθ cpθ

by c = kG(θ)kpθ .

= kG(θ)kpθ
Hence, the statement follows from Lemma 3.2.

Now, we are ready to prove our variant of multimatrix Golden-Thompson inequality. It follows
from plugging in Theorem 3.3 into the proof of Theorem 3.5 in [SBT17]. We give a complete proof
for completeness.
Theorem 3.4 (Multimatrix Golden-Thompson inequality). For any k Hermitian matrices H1 , · · · , Hk ,
we have:
 
 



 iφ  Y
 −iφ 
Z π
k
k
1
Y
X
2
e
e
4
log tr 
log tr exp 
exp
Hj
exp
Hj  dµ(φ)
Hj  ≤
π −π
2
2
j=1

j=1

2

j=k

where µ is some probability distribution on [− π2 , π2 ].
Proof. Fix θ ∈ (0, 1/4), we define
Gθ (z) =

k
Y

exp

j=1

z
2


Hj .

Note that kGθ (iy)k∞ = 1 for all y ∈ R.
Fix θ ∈ (0, 1/4), we have
 




k
k
X
X
1
log tr exp 
Hj  = 2 log exp 
Hj 
2
j=1

j=1


= 2 log

lim 

θ→0+

k
Y

j=1

2


exp


 1/θ
θ
Hj 
2
2

2
= lim log kGθ (θ)k2/θ
+
θ→0 θ

 Z π/2
4
≤ lim 2
+ O(θ)
log kGθ (eiφ )k2 dµθ (φ)
π
θ→0+
−π/2

 Z π/2
 h
i
4
= lim
+ O(θ)
log tr Gθ (eiφ )Gθ (eiφ )∗ dµθ (φ),
θ→0+ π
−π/2
13

where the first step follows by definition of k · k2 , the second step Q
follows by taking limit θ → 0+
and Lie-Trotter product formula, the third step follows by Gθ (θ) = kj=1 exp( 2θ Hj ) and fourth step
follows by Theorem 3.3 with p0 = ∞ and p1 = 2.
When θ → 0+ , µθ (φ) converges to some probability distribution µ. This completes the proof.
Remark 3.5. We suspect the constant 4/π is tight and that any constant larger than one is unavoidable if we consider the maximum over a bounded domain inside the strip {z ∈ C : 0 ≤ Re(z) ≤ 1}.

4

Proof of Theorem 1.2

In this section we present the proof of Theorem 1.2. We restate it here (with explicit constants)
for convenience.
Theorem 4.1. Let G be a regular λ-expander on V and let f be a function f : V → Cd×d s.t.
1. For each v ∈ V , f (v) is Hermitian and kf (v)k ≤ 1.
P
2.
v∈V f (v) = 0.
If v1 , . . . , vk is a stationary random walk on G, and  ∈ (0, 1),




k
X

P λmax 
f (vj ) ≥ k ≤ d2−π/4 · exp −2 (1 − λ)k/80
j=1

"
P λmin

k
X

!
f (vj )

#

≤ −k ≤ d2−π/4 · exp −2 (1 − λ)k/80

i=1

Remark 4.2. Depsite the exponent of d is different from Theorem 1.2, we note that since the left
hand side (the probability) is at most 1, one can prove the same statement with any positive
exponent by changing the constant 80.
Proof. Due to symmetry, it suffices to prove just one of the statements. Let t > 0 be a parameter
to be chosen later. Then




 



k
k
X
X
P λmax 
f (vj ) ≥ k ≤ P tr exp t
f (vj ) ≥ exp(tk)
j=1

j=1

≤

h h
 P
ii
E tr exp t kj=1 f (vj )
exp(tk)

The second inequality follows from Markov’s inequality.

14

(8)

P
Now the question is how to bound Ev1 ,··· ,vk [tr[exp(t kj=1 f (vj ))]]. Using Theorem 3.4 and note
that µ(φ) is a probability distribution on [− π2 , π2 ], we have
 


k
X
log tr exp t
f (vj )
j=1

≤

4
π

≤

4
π




Y

 −iφ
1
e
log tr 
exp
tf (vj )
tf (vj )  dµ(φ)
exp
2
2
− π2
j=1
j=k


 iφ
Y

 −iφ
Z π
k
1
Y
2
e
e
tr 
exp
log
tf (vj )
tf (vj )  dµ(φ)
exp
π
2
2
−
π
2

Z

k
Y



eiφ

j=1

2

j=k

where the the second step follows by concavity of log function. This implies that




tr exp t

k
X




Z



f (vj )
≤

π
2

− π2

j=1


tr 

k
Y


exp


4
π
Y
 −iφ

1
e


tf (vj )
exp
tf (vj )
dµ(φ)
2
2

eiφ

j=1

(9)

j=k

Note that kxkp ≤ d1/p−1 kxk1 for p ∈ (0, 1), choosing p = π/4 we have
 4



π
k
k
X
X
π
tr exp  t
f (vj ) ≤ d4/π−1 tr exp t
f (vj ) .
4
 



j=1

(10)

j=1

Combining Eq. (9) and Eq. (10), we have





Y
 −iφ

 iφ
Z π
k
k
1
X
Y
2
π
e
e
tr exp  t
tr 
tf (vj )
exp
tf (vj )  dµ(φ)
f (vj ) ≤ d1−π/4
exp
π
4
2
2
−
j=1

2

j=1

j=k

(11)
The core of the proof is the following bound on the moment generating function-like expression
that appears above, thinking of iφ as γ + ib with γ 2 + b2 = 1:
Lemma
4.3. Let G be a regular λ-expander on V , let f be a function f : V → Cd×d and
P
v∈V f (v) = 0, let v1 , · · · , vk be a stationary random walk on G, for any t > 0, γ ≥ 0, b > 0,
2
t (γ 2 + b2 ) ≤ 1, and tγ ≤ 1−λ
4λ we have
 

Y





1
k
Y
tf
(v
)(γ
−
ib)
tf
(v
)(γ
+
ib)
8
j
j
2
2
2
 ≤ d · exp kt (γ + b )(1 +
E tr 
exp
exp
) .
2
2
1−λ
j=1

j=k

15

Assuming this lemma, we can easily complete the proof of the theorem as:
 


k
X
π
Ev1 ,··· ,vk tr exp  t
f (vj )
4
j=1




 iφ
Y

 −iφ
Z π
k
1
Y
2
e
e
tr 
≤ d1−π/4 Ev1 ,··· ,vk 
exp
tf (vj )
tf (vj )  dµ(φ)
exp
π
2
2
−2
j=1
j=k
 

Y

 iφ
 −iφ
Z π
k
1
Y
2
e
e
Ev1 ,··· ,vk tr 
tf (vj )
tf (vj )  dµ(φ)
exp
exp
= d1−π/4
π
2
2
−2
j=1
j=k


Z π
2
8
d exp kt2 |eiφ |2 (1 +
) dµ(φ)
≤ d1−π/4
1−λ
− π2

Z π
2
8
2−π/4
2
=d
exp kt (1 +
)
dµ(φ)
1−λ
− π2


8
2−π/4
2
=d
exp kt (1 +
) ,
1−λ

(12)

R
where the first step follows by the Equation (11), the second step follows by swapping E and ,
the third step follows by Lemma 4.3 , the fourth step follows by |eiφ | = 1, and the last step follows
Rπ
by −2 π dµ(φ) = 1.
2
Finally, putting it all together,






k
X
9
2−π/4
2
2
Pv1 ,··· ,vk λmax 
− kt
f (vj ) ≥ k ≤ d
· exp (4/π) kt
1−λ
j=1


1
9
(1 − λ)
= d2−π/4 · exp (4/π)2 k2 (1 − λ)2 2
−k

36 1 − λ
36

≤ d2−π/4 · exp −k2 (1 − λ)/72 .
where the first step follows by Eq. (12) the second step follows by choosing t = (1 − λ)/36.
We now give the proof of Lemma 4.3
Proof of Lemma 4.3. We start by writing the expected trace expression in terms of the transition
matrix of the random walk. This is an analogue of a step which is common to most of the expander
chernoff bound proofs in the scalar case. Let P be the normalized adjacency matrix of G and let
Pe = P ⊗ Id2 . Let E denote the nd2 × nd2 block diagonal matrix where the v th diagonal block is
the matrix




tf (v)(γ − ib)
tf (v)(γ + ib)
⊗ exp
.
(13)
Mv = exp
2
2

k
Then E Pe is an nd2 × nd2 block matrix whose (u, v)th (d2 × d2 ) block is given by the matrix




k−1
k−2
X
Y
Y
Pu,v1 · 
Pvj ,vj+1  · Pvk−1 ,v · Mu · 
Mv j 
(14)
v1 ,...,vk−1

j=1

j=1

16

2

Let z0 ∈ Cnd be the vector √1n ⊗ vec(Id ). Here 1 is the all 1’s vector and vec(Id ) is the vector form
of the identity matrix. Then, by applying


hvec(Id ), A1 ⊗ A2 vec(Id )i = tr A1 AT2
it follows that for a stationary random walk v1 , . . . , vk :

 
"*
+#
Y



1
k
k
Y
Y
tf
(v
)(γ
−
ib)
tf
(v
)(γ
+
ib)
j
j
 = E
exp
vec(Id ),
Mvi vec(Id )
E tr 
exp
2
2
j=1
i=1
j=k
 
k 
= z0 , E Pe z0

Hence we can focus our attention on



z0 , E Pe

k


z0 .
2

Let 1 be the all 1’s vector. For a vector z ∈ Cnd , let z k denote the component of z which lies
in the subspace spanned by the d2 vectors 1 ⊗ ei , 1 ≤ i ≤ d2 . Let z ⊥ denote the component in the

j
orthogonal space. Letting zj = E Pe z0 , we are interested in bounding
k

k

hz0 , zk i = hz0 , zk i ≤ kz0 k · kzk k =

√

k

d · kzk k

The following lemma is the analogue of the main lemma in Healy’s proof for the scalar valued
expander Chernoff bound [Hea08]. Roughly speaking, it tracks how much a vector can move in and
out of the subspace we are interested in as the operator E Pe is applied.
Lemma 4.4. Given four parameters λ ∈ [0, 1], γ ≥ 0, ` ≥ 0, and t > 0. Let G be a regular
2
2
λ-expander
on V . Suppose each vertex v is assigned a matrix Hv ∈ Cd ×d s.t. kHv k ≤ ` and
P
e
v Hv = 0. Let P be the normalized adjacency matrix of G and let P = P ⊗ Id2 . Let E denote the
2
2
nd × nd block diagonal matrix where the v-th diagonal block is the matrix exp(tHv ). Also suppose
2
that kEk = maxv∈V kexp(tHv )k ≤ exp(γt). Then for any z ∈ Cnd , we have:
1.
2.

k(E Pez k )k k ≤ α1 kz k k
k(E Pez k )⊥ k ≤ α2 kz k k

3. k(E Pez ⊥ )k k ≤ α3 kz ⊥ k
4. k(E Pez ⊥ )⊥ k ≤ α4 kz ⊥ k

where α1 = exp(t`) − t`
where α2 = exp(t`) − 1
where α3 = λ · (exp(t`) − 1)
where α4 = λ · exp(tγ)

Proof of Lemma 4.4. Part 1.
Note that (E Pez k )k = (Ez k )k . Let 1 ∈ Rn denote all ones vector, suppose z k = 1 ⊗ w for some
√
2
w ∈ Cd . Then kz k k = n · kwk and
!
1X
k k
(Ez ) = 1 ⊗
exp(Hv )w .
n
v∈V

17

We can upper bound k n1

P

v∈V

exp(tHv )k in the following way,
∞
1 X X tj Hvj
n
j!

1X
exp(tHv ) =
n

v∈V j=0

v∈V

∞
1 X X tj Hvj
I+
n
j!

=

v∈V j=2

1 X X tj
≤ 1+
kHv kj
n
j!
v∈V j≥2

= 1+

X (t`)j
j≥2

j!

= exp(t`) − t`,
P
where the first step follows by Taylor expansion, the second step follows by v∈V Hv = 0, the third
step follows by triangle inequality, the fourth step follows by |V | = n and kHv k ≤ `, and last step
follows by Taylor expansion.
Thus,
k(Ez k )k k =

√

n

√
1X
exp(tHv )w ≤ nkwk(exp(t`) − t`) = kz k k(exp(t`) − t`).
n
v∈V

Part 2. Note that (E Pez k )⊥ = (Ez k )⊥ = ((E − I)z k )⊥ . and (z k )⊥ = 0. We can upper bound
k((E − I)z k )⊥ k in the following way,
k((E − I)z k )⊥ k ≤ k(E − I)z k k
≤ kE − Ik · kz k k
= max k exp(tHv ) − Ik · kz k k
v∈V

= max
v∈V

∞ j
X
t
j=1

j!


Hvj · kz k k


∞ j j
X
t ` 

· kz k k
≤
j!
j=1

= (exp(t`) − 1) · kz k k,
where the second step follows by kAxk ≤ kAk · kxk, the third step follows by definition of E, the
fourth step follows by Taylor expansion, the fifth step follows by triangle inequality and kHv k ≤ `,
and the last step follows by Taylor expansion.
Part 3. Note that
(E Pez ⊥ )k = ((E − I)Pez ⊥ )k

18

This is because (Pez ⊥ )k = 0 since Pe preserves the property of being orthogonal to the space spanned
by the vectors 1 ⊗ ei (these are the top eigenvectors of Pe). Hence we can bound
((E − I)Pez ⊥ )k ≤ (E − I)Pez ⊥
≤ kE − Ik · Pez ⊥
≤ (exp(t`) − 1) · λ · z ⊥
Third inequality follows from the fact that kE − Ik ≤ exp(t`) − 1 and that G is a λ-expander.
Part 4. We can bound
k(E Pez ⊥ )⊥ k ≤ kE Pez ⊥ k ≤ exp(tγ) · λkz ⊥ k
where the second step follows by kEk ≤ exp(γt) and G is a λ-expander.
k

We now use the above Lemma 4.4 to analyze the evolution of zj and zj⊥ . Recall the definition
of Hv ,
Hv =

f (v)(γ + ib)
f (v)(γ − ib)
⊗ Id + Id ⊗
.
2
2

which means


tf (v)(γ − ib)
tf (v)(γ + ib)
⊗ Id + Id ⊗
2
2




tf (v)(γ + ib)
tf (v)(γ − ib)
= exp
⊗ exp
2
2
= Mv ,



exp(tHv ) = exp

where the the first step follows by definition of Hv , the second step follows by exp(A⊗Id +Id ⊗B) =
exp(A) ⊗ exp(B), and the last step
pfollows by Eq. (13).
p
We can upper bound kHv k ≤ γ 2 + b2 and then set ` = γ 2 + b2 . We can also upper bound
k exp(tHv )k

 
f (v)
f (v)
⊗ Id + Id ⊗
k exp(tHv )k = k exp(t · Re(Hv ))k = exp γt
≤ exp(γt).
2
2
P
P
Note that v∈V Hv = 0 since v∈V f (v) = 0.
Claim 4.5. kzi⊥ k ≤

α2
1−α4

k

maxj<i kzj k.

Proof.
kzi⊥ k = k(E Pezi−1 )⊥ k
k

⊥ ⊥
≤ k(E Pezi−1 )⊥ k + k(E Pezi−1
) k
k

⊥
≤ α2 kzi−1 k + α4 kzi−1
k
k

≤ (α2 + α2 α4 + α2 α4 + · · · ) · max kzj k
j<i

≤

α2
k
max kz k,
1 − α4 j<i j
19

where the first step follows by definition of zi , the second step follows by triangle inequality, the
third step follows by part 2 and 4 of Lemma 4.4.
k

Claim 4.6. kzi k ≤ (α1 +

k
α2 α3
1−α4 ) maxj<i kzj k.

Proof.
k

kzi k = k(E Pezi−1 )k k
k
⊥ k
≤ k(E Pezi−1 )k k + k(E Pezi−1
) k
k

⊥
≤ α1 kzi−1 k + α3 kzi−1
k
α
k
k
2
≤ α1 kzi−1 k + α3
max kz k
1 − α4 j<i−1 j
α2 α3
≤ (α1 +
),
1 − α4

where the first step follows by definition of zi , the second step follows by triangle inequality, the
third step follows by part 1 and 3 of Lemma 4.4, the fourth step follows by Claim 4.5.
Combining Claim 4.5 and Claim 4.6 gives
k

kzk k ≤ (α1 +

√
α2 α3 k
α2 α3 k k
) kz0 k = d · (α1 +
) ,
1 − α4
1 − α4

which implies that
D

E
α2 α3 k
) .
z0 , (E Pe)k z0 ≤ d · (α1 +
1 − α4

Now the question is how to bound (α1 +
following sense,

α2 α3 k
1−α4 ) .

We can upper bound α1 , α2 α3 and α4 in the

α1 = exp(t`) − t` ≤ 1 + t2 `2 = 1 + t2 (γ 2 + b2 ),
and
α2 α3 = λ(exp(t`) − 1)2 ≤ λ(2t`)2 = 4λt2 (γ 2 + b2 )
where the second step follows by t` < 1 (because exp(x) ≤ 1 + 2x, ∀x ∈ [0, 1]),
α4 = λ · exp(tγ) ≤ λ(1 + 2tγ) ≤

1 1
+ λ
2 2

where the second step follows by tγ < 1, and the third step follows by tγ ≤ (1 − λ)/4λ.
Thus,
!k
α2 · α3 k
4λt2 (γ 2 + b2 )
2 2
2
(α1 +
) ≤ 1 + t (γ + b ) +
1
1
1 − α4
2 − 2λ


8
2 2
2
≤ exp kt (γ + b )(1 +
) .
1−λ

20

Remark 4.7. As is the case with Healy’s proof [Hea08], our proof also works for the case when there
are different mean zero functions f1 , . . . , fk for the different steps of the walk and also when there
are k λ-expanders G1 , . . . , Gk and the j th step of the walk is taken according to Gj .
Remark 4.8. We suspect that with appropriate modifications, our proof should generalize to random
walks on irregular undirected graphs (or reversible Markov chains) as was done for Healy’s proof
in [CLLM12].
Remark 4.9. Although we have stated the theorem for Hermitian matrices, the same result can be
obtained for general matrices by a standard dilation trick, namely replacing every d × d matrix M
that appears with the 2d × 2d Hermitian matrix


0 M
,
M∗ 0
whose norm is always within a factor of two of M .

5

Proof of Theorem 1.6

Proof. Observe that for every i = 2, . . . , k we have
X
E[f (vi ) | vi−1 ] =
P (vi−1 , u)f (u) = P f (vi−1 ),
u∼vi−1

whence the random vectors

(1)

Yi

:= f (vi ) − P f (vi−1 )

satisfy
(1)

E[Yi

| v1 , . . . , vi−1 ] = 0

and thus form a martingale difference sequence with respect to the filtration generated by initial
(1)
segments of v1 , . . . , vk . Denoting Y1 := f (v1 ), we can write the sum of interest as a martingale
part plus a remainder, which is a sum of k − 1 (i.e., one fewer) random variables:
S=

k
X

(1)

Yi

+

i=1

k−1
X

P f (vi ).

i=1

Notice that P f is also a mean zero function on G, and by Jensen’s inequality we have
k(P f )(v)k∗ ≤ M := max kf (v)k∗
v∈V

for all v.

The key point is that the remainder terms P f (vi ) are smaller on average than the original terms
f (vi ) in squared Euclidean norm, because P is a contraction orthogonal to the constant vector; in
particular, by considering the action of P on each coordinate of f separately, we have:
X
X
kP f (v)k22 ≤ λ ·
kf (v)k22 .
(15)
v

v

Iterating this construction on the remainder a total of T ≤ k times, we obtain a sequence of
martingales 1 ≤ t ≤ T :
(t)

Y1

:= P t−1 f (v1 )

(t)

Yi

:= P t−1 f (vi ) − P t f (vi−1 ),
21

i = 1 . . . , k − (t − 1)

which are related to the original sum as:
S=

T k−t+1
X
X
t=1

(t)

Yi

+

i=1

k−T
X

P T f (vi ).

i=1

Interchanging the order of summation, we find that the random matrices
min{(k+1−i),T }

X

Zi :=

(t)

Yi

t=1

themselves form a martingale difference sequence, with each
X (t)
kYi k∗ ≤ T M.
kZi k∗ ≤
t

We bound the error W :=

1
k

Pk−T
i=1

(P T f )(vi ) crudely as:

k−T
k−T X
1X
k(P T f )(v)k2 ≤ λT /2 F ≤ exp(−(1 − λ)T /2)F,
kP T f (vi )k2 ≤
kW k2 ≤
k
k
i=1

v∈V

qP

2
where F :=
v∈V kf (v)k2 , by applying (15). Rearranging and setting T = 2 log(F/)/(1 − λ)
yields the advertised bound on kZi k∗ .

6

Acknowledgments

We thank Sébastien Bubeck, Yash Deshpande, Ravi Kannan, Zeph Landau, Jelani Nelson, Eric
Price, Aviad Rubinstein, Avi Wigderson, David P. Woodruff, David Xiao and David Zuckerman
for helpful conversations, as well Microsoft Research India and the Simons Institute for the Theory
of Computing, where much of this work was carried out.

References
[AW02]

Rudolf Ahlswede and Andreas Winter. Strong converse for identification via quantum
channels. IEEE Transactions on Information Theory, 48(3):569–579, 2002.

[Bha97]

Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media,
1997.

[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.

[CL06]

Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a
survey. Internet Mathematics, 3(1):79–127, 2006.

[CLLM12] Kai-min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. ChernoffHoeffding bounds for Markov chains: Generalized and simplified. arXiv preprint
arXiv:1201.0559, 2012.
22

[Con78]

John B. Conway. Functions of one Complex Variable, volume I of Graduate Texts in
Mathematics (Second Edition). Springer New York, Heidelberg, Berlin, 1978.

[Gil98]

David Gillman. A chernoff bound for random walks on expander graphs. SIAM Journal
on Computing, 27(4):1203–1220, 1998.

[Gol65]

Sidney Golden.
Lower bounds for the Helmholtz function.
137(4B):B1127, 1965.

[Gra08]

Loukas Grafakos. Classical Fourier Analysis, volume 249 of Graduate Texts in Mathematics. Springer New York, 2008.

[Hea08]

Alexander D Healy. Randomness-efficient sampling within NC1. Computational Complexity, 17(1):3–37, 2008.

[HKT16]

Fumio Hiai, Robert Koenig, and Marco Tomamichel. Generalized log-majorization and
multivariate trace inequalities. arXiv preprint arXiv:1609.01999, September 2016.

[Kah97]

Nabil Kahale. Large deviation bounds for Markov chains. Combinatorics, Probability
and Computing, 6(04):465–474, 1997.

[Lez98]

Pascal Lezaud. Chernoff-type bound for finite Markov chains. Annals of Applied Probability, pages 849–867, 1998.

[LP04]

C. A. Leon and F. Perron. Optimal Hoeffding bounds for discrete reversible Markov
chains. Annals of Applied Probability, 14(2), 2004.

[LPS88]

Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.

[LT13]

Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and
processes. Springer Science & Business Media, 2013.

[RR17]

Shravas Rao and Oded Regev. A sharp tail bound for the expander random sampler.
arXiv preprint arXiv:1703.10205, 2017.

[Rud99]

Mark Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis, 164(1):60–72, 1999.

Physical Review,

[RVW00] Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph
product, and new constant-degree expanders and extractors. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, pages 3–13. IEEE, 2000.
[SBT17]

David Sutter, Mario Berta, and Marco Tomamichel. Multivariate trace inequalities.
Communications in Mathematical Physics, 352(1):37–58, 2017. arXiv:1604.03023.

[Tho65]

Colin J Thompson. Inequality with applications in statistical mechanics. Journal of
Mathematical Physics, 6(11):1812–1813, 1965.

[Tro12]

Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of
computational mathematics, 12(4):389–434, 2012.
23

[Tro15]

Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and
Trends R in Machine Learning, 8(1-2):1–230, 2015.

[Wag08]

R. Wagner. Tail estimates for sums of variables sampled by a random walk. Combinatorics, Probability and Computing, 17(2), 2008.

[WX]

Avi Wigderson and David Xiao. Retraction of Wigderson-Xiao: A randomness-efficient
sampler for matrix valued functions, eccc tr05-107. 2006.

[WX05]

Avi Wigderson and David Xiao. A randomness-efficient sampler for matrix-valued functions and applications. In Foundations of Computer Science, 2005. FOCS 2005. 46th
Annual IEEE Symposium on, pages 397–406. IEEE, 2005.

[WX08]

Avi Wigderson and David Xiao. Derandomizing the AW matrix-valued Chernoff bound
using pessimistic estimators and applications. Theory of Computing, 4(3):53–76, 2008.

A

Elementary calculations

Lemma A.1. We define function h(z) : C → C as follows
s

1+z
1+z 2
h(z) = −
+
+1
1−z
1−z
Then function h(z) maps the unit disk {z ∈ C : |z| ≤ 1} to the half disk {z ∈ C : |z| ≤ 1 and Re(z) ≥
0}.
Proof. We first compute the inverse of function h(z), let f = h−1 . By definition of h(z), we can do
the following elementary calculations,
s

1+z
1+z 2
h(z) +
=
+1
1−z
1−z




1+z 2
1+z 2
=⇒
h(z) +
=
+1
1−z
1−z
1+z
=⇒ (h(z))2 + 2h(z)
=1
1−z
=⇒ (1 − z)(h(z))2 + 2h(z)(1 + z) = (1 − z)
=⇒ (h(z))2 + 2h(z) − 1 = z((h(z))2 − 2h(z) − 1),
Thus, we obtain that
f (z) =

z 2 + 2z − 1
z 2 − 2z − 1

To finish the proof, we need Claim A.2 and Claim A.3.
Claim A.2. For all z ∈ {z ∈ C : |z| ≤ 1 and Re(z) ≥ 0},
|f (z)| ≤ 1
24

Proof. Let z = reiφ , where r ∈ [0, 1] and φ ∈ [−π/2, π/2]. It is easy to observe that cos(φ) ∈ [0, 1]
We have
z 2 + 2z − 1
z 2 − 2z − 1
r2 ei2φ + 2reiφ − 1
= 2 i2φ
r e − 2reiφ − 1
|r2 ei2φ + 2reiφ − 1|
= 2 i2φ
|r e − 2reiφ − 1|

|f (z)| =

We can compute the numerator,
|r2 ei2φ + 2reiφ − 1|2 = |r2 cos 2φ + ir2 sin 2φ + 2r cos φ + 2ri sin φ − 1|2
= (r2 cos 2φ + 2r cos φ − 1)2 + (r2 sin 2φ + 2r sin φ)2
= r4 + 4r2 + 1 − 2r2 cos 2φ + 4r3 cos 2φ cos φ − 4r cos φ + 4r3 sin 2φ sin φ
= r4 + 4r2 + 1 − 2r2 cos 2φ + 4r3 cos φ − 4r cos φ.
We can compute the denominator,
|ei2φ − 2eiφ − 1|2 = |r2 cos 2φ + ir2 sin 2φ − 2r cos φ − 2ri sin φ − 1|2
= (r2 cos 2φ − 2r cos φ − 1)2 + (r2 sin 2φ − 2r sin φ)2
= r4 + 4r2 + 1 − 2r2 cos 2φ − 4r3 cos 2φ cos φ + 4r cos φ − 4r3 sin 2φ sin φ
= r4 + 4r2 + 1 − 2r2 cos 2φ − 4r3 cos φ + 4r cos φ.
Note that, in order to show |f (z)| ≤ 1, it is sufficient to prove
4r3 cos φ − 4r cos φ ≤ −4r3 cos φ + 4r cos φ
which is equivalent to
8r(1 − r2 ) cos φ ≥ 0.
It follows by definition of r and φ. Thus, we complete the proof.
Next, we can show that
Claim A.3. For all z is on the boundary of half disk,
|f (z)| = 1.
Proof. First, we want to show that ∀z ∈ [−i, i], |f (z)| = 1. Let b ∈ [0, 1], let z = ib, then we have
|f (z)| = |f (ib)|
−b2 + 2bi − 1
−b2 − 2bi − 1
= 1.

=

25

Second, we want to show that for all z on half circle, |f (z)| = 1. We replace z by eiφ , where
φ ∈ [−π/2, π/2]. Then we have
z 2 + 2z − 1
z 2 − 2z − 1
ei2φ + 2eiφ − 1
= i2φ
e − 2eiφ − 1
|ei2φ + 2eiφ − 1|
= i2φ
.
|e − 2eiφ − 1|

|f (z)| =

We can compute the numerator,
|ei2φ + 2eiφ − 1| = | cos 2φ + i sin 2φ + 2 cos φ + 2i sin φ − 1|
= (cos 2φ + 2 cos φ − 1)2 + (sin 2φ + 2 sin φ)2

1/2

= (6 − 2 cos 2φ + 4 cos 2φ cos φ − 4 cos φ + 4 sin 2φ sin φ)1/2
= (6 − 2 cos 2φ + 4 cos φ − 4 cos φ)1/2
= (6 − 2 cos 2φ)1/2 .
We can compute the denominator,
|ei2φ − 2eiφ − 1| = | cos 2φ + i sin 2φ − 2 cos φ − 2i sin φ − 1|
= (cos 2φ − 2 cos φ − 1)2 + (sin 2φ − 2 sin φ)2

1/2

= (6 − 2 cos 2φ − 4 cos 2φ cos φ + 4 cos φ − 4 sin 2φ sin φ)1/2
= (6 − 2 cos 2φ + 4 cos φ − 4 cos φ)1/2
= (6 − 2 cos 2φ)1/2 .
Thus, we have
|f (z)| = 1

Note the biholomorphic is basically follows from the formula of f and h, because they are
composition of holomorphic function.
Lemma A.4. For any ρ ∈ [0, 1] and cos ϕ ∈ [−1, 0], we have
1−ρ
1 − ρ2
1−ρ
− (1 − ρ)2 ≤
≤
+ 2(1 − ρ)2 .
2
1 − cos ϕ
1 − 2ρ cos ϕ + ρ
1 − cos ϕ
Proof. This directly follows by combining Claim A.5 and Claim A.6
Claim A.5. There exists some sufficiently large constant c ≥ 1 such that for any ρ ∈ [0, 1] and
cos ϕ ∈ [−1, 0], we have
1 − ρ2
1−ρ
≤
+ c(1 − ρ)2 .
2
1 − 2ρ cos ϕ + ρ
1 − cos ϕ
26

Proof. It is equivalent to
1
1+ρ
≤
+ c(1 + ρ)
1 − 2ρ cos ϕ + ρ2
1 − cos ϕ
(1 + ρ)(1 − cos ϕ) ≤ 1 − 2ρ cos ϕ + ρ2 + c(1 + ρ)(1 − cos ϕ)(1 − 2ρ cos ϕ + ρ2 )
ρ − cos ϕ ≤ − ρ cos ϕ + ρ2 + c(1 + ρ)(1 − cos ϕ)(1 − 2ρ cos ϕ + ρ2 )
which is equivalent to,
−ρ cos ϕ + ρ2 − ρ + cos ϕ + c(1 + ρ)(1 − cos ϕ)(1 − 2ρ cos φ + ρ2 ) ≥ 0
Since 1 − 2ρ cos ϕ + ρ2 ≥ 1, thus it suffices to show
(ρ − 1)(ρ − cos ϕ) + c(1 + ρ)(1 − cos ϕ) ≥ 0
Note that (ρ − 1)(ρ − cos ϕ) ≥ −2, by choosing c ≥ 2, we complete the proof.
Claim A.6. There exists some sufficiently large constant c ≥ 1 such that for any ρ ∈ [0, 1] and
cos ϕ ∈ [−1, 0], we have
1 − ρ2
1−ρ
≥
− c(1 − ρ)2 .
2
1 − 2ρ cos ϕ + ρ
1 − cos ϕ
Proof. It is equivalent to
1+ρ
1
≥
+ c(1 + ρ)
1 − 2ρ cos ϕ + ρ2
1 − cos ϕ
(1 + ρ)(1 − cos ϕ) ≥ 1 − 2ρ cos ϕ + ρ2 − c(1 + ρ)(1 − cos ϕ)(1 − 2ρ cos ϕ + ρ2 )
ρ − cos ϕ ≥ − ρ cos ϕ + ρ2 − c(1 + ρ)(1 − cos ϕ)(1 − 2ρ cos ϕ + ρ2 )
which is equivalent to,
−ρ cos ϕ + ρ2 − ρ + cos ϕ − c(1 + ρ)(1 − cos ϕ)(1 − 2ρ cos φ + ρ2 ) ≤ 0
which is equivalent to
(ρ − 1)(ρ − cos ϕ) ≤ c(1 + ρ)(1 − cos ϕ)(1 − 2ρ cos ϕ + ρ2 )
It suffices to choose c = 1

27

