A large-deviation inequality for vector-valued martingales

Thomas P. Hayes

February 20, 2003

Abstract

Let X = (X_{0}, …, X_{n}) be a discrete-time martingale taking values in any real Euclidean space such that X_{0} = 0 and for all n, ∥X_{n} − X_{n−1}∥ ≤ 1. We prove the large deviation bound

Pr [∥X_{n}∥ ≥ a] < 2e^{1−(a−1)^{2}/2n}.

This upper bound is within a constant factor, e^{2}, of the Azuma-Hoeffding Inequality for real-valued martingales. This improves an earlier result of O. Kallenberg and R. Sztencel (1992).

Our inequality holds even for “very-weak martingales,” namely, discrete stochastic processes X which satisfy, for every n,

E (X_{n} | X_{n−1}) = X_{n}  (1)

In particular, this includes the class of weak martingales.

More generally, we prove that, for every very-weak martingale X in ℝ^{d}, there exists a martingale Y in ℝ^{d} such that for all n, the distribution of (Y_{n−1}, Y_{n}) is the same as that of (X_{n−1}, X_{n}).

As an application, we answer questions posed by L. Babai about Fourier coefficients of random subsets of a finite abelian group.

1 Introduction

This paper is centered around extending the following well-known result to more general classes of random series.

Proposition 1.1 (Azuma-Hoeffding Inequality) Let X = (X_{0}, X_{1}, …, X_{n}) be a real-valued martingale such that X_{0} = 0 and for every i, |X_{i} −X_{i−1}| ≤ 1. Then, for every a > 0,

Pr [|X_{n}| ≥ a] < 2e^{−a^{2}/2n}.  (2)

Our first objective is to replace “real-valued martingale” with “vectorvalued martingale.” Throughout this paper, 𝔼 will denote any real Euclidean space (of finite or infinite dimension), and ∥·∥ will denote the Euclidean norm.

We will use the following definition in this paper.

Definition 1.2 Let X = (X_{i} : Ω → 𝔼) be a sequence of random vectors taking values in 𝔼, such that X_{0} = 0, and for every i ≥ 1, E (∥X_{i}∥) < ∞ and E (X_{i} | X_{0}, X_{1}, …, X_{i−1}) = X_{i−1}. Then we call X a (strong) martingale in 𝔼.

Our second objective is to relax the conditioning on the expectation in this definition from E (X_{i} | X_{0}, X_{1}, …, X_{i−1}) to E (X_{i} | X_{i−1}).

Definition 1.3 Let X = (X_{i} : Ω → 𝔼) be a sequence of random vectors taking values in 𝔼, such that X_{0} = 0, and for every i ≥ 1, E (∥X_{i}∥) < ∞ and E (X_{i} | X_{i−1}) = X_{i−1}. Then we call X a very-weak martingale in 𝔼.

Note that every martingale is automatically a very-weak martingale. The converse is false (see below). To explain the terminology, we recall the common definition of weak martingales, introduced by P. Nelson [15] (see also J. Berman [6]).

Definition 1.4 Let X = (X_{i} : Ω → 𝔼) be a sequence of random vectors taking values in 𝔼, such that X_{0} = 0, and for every j < i, E (∥X_{i}∥) < ∞ and E (X_{i} | X_{j}) = X_{j}. Then we call X a weak martingale in 𝔼.

Every strong martingale is a weak martingale, and every weak martingale is a very-weak martingale. Neither of the converses is true. In Section 4, we present a canonical example of a very-weak martingale which is not a weak martingale, and discuss some combinatorial differences between the classes.

It has been shown that the Azuma-Hoeffding inequality holds with realvalued very-weak martingales in place of martingales. A nice presentation may be found in Alon, Spencer, and Erdős [2, Appendix A]; the reader should note that what that text calls “martingales” are actually “very-weak martingales” in our terminology.

We prove more generally that any very-weak martingale may be replaced by a strong martingale which has the same distributions of values and of differences. Azuma-Hoeffding and other similar bounds thus automatically apply equally well to very-weak martingales and to martingales. This result applies to very-weak martingales taking values in any real Euclidean space.

Precise statements of all our results are in the following subsection.

1.1 Overview of Results

Our first tool is the discrete-time case of a theorem of Kallenberg and Sztencel [11, Theorem 3.1], stating that for many purposes, “local martingales” (cf. [12, Definition 1.5.15, p. 36]) in 𝔼 are equivalent to local martingales in ℝ^{2}.

Proposition 1.5 (Kallenberg, Sztencel) Let X be a martingale in 𝔼. Then there exists a martingale Y in ℝ^{2} such that for every i, ∥Y_{i}∥ has the same distribution as ∥X_{i}∥ and ∥Y_{i}−Y_{i−1}∥ has the same distribution as ∥X_{i}−X_{i−1}∥.

We give a simple direct proof of this result for discrete martingales and show that the result applies even to discrete very-weak martingales, in the following strong sense:

Proposition 1.6 Let X be a very-weak martingale in 𝔼. Then there exists a (strong) martingale Y in ℝ^{2} such that for every i ≥ 1, the triples (∥Y_{i−1}∥, ∥Y_{i}∥, ∥Y_{i} − Y_{i−1}∥) and (∥X_{i−1}∥, ∥X_{i}∥, ∥X_{i} − X_{i−1}∥) share the same distribution.

The proof is in Section 2.

Kallenberg and Sztencel were also able to prove the following generalization of the Azuma-Hoeffding Inequality. Again, we only state the version for discrete martingales with uniformly bounded differences. (See the remarks preceding their continuous version, [11, Theorem 5.3].)

Proposition 1.7 (Kallenberg, Sztencel) Let X be a martingale in 𝔼, such that for every i, ∥X_{i} − X_{i−1}∥ ≤ 1. Then

Pr [∥X_{n}∥ ≥ a] = O ((1 + \frac{a}{\sqrt{n}}) e^{−a^{2}/2n}) .  (3)

(The constant implicit in the big-Oh notation is absolute, perhaps approximately 2.)

By a more detailed analysis, in Section 3, we eliminate the dependence on a and n outside the exponent. Moreover, our inequality holds not only for martingales, but also for very-weak martingales.

Theorem 1.8 Let X be a very-weak martingale taking values in 𝔼 such that X_{0} = 0 and for every i, ∥X_{i} − X_{i−1}∥ ≤ 1. Then, for every a > 0,

Pr [∥X_{n}∥ ≥ a] < 2e^{1−(a−1)^{2}/2n} < 2e^{2}e^{−a^{2}/2n}.  (4)

Our next result shows that, for many purposes (such as Theorem 1.8), a given very-weak martingale may be replaced by an “equivalent” strong martingale.

Theorem 1.9 Let X be a very-weak martingale taking values in ℝ^{d}. Then there exists a (strong) martingale Y taking values in ℝ^{d} such that for each i ≥ 1, (Y_{i−1}, Y_{i}) has the same distribution as (X_{i−1}, X_{i}).

This theorem, combined with Proposition 1.6, allows us to automatically extend a certain class of results about strong martingales in ℝ^{2} to apply to very-weak martingales in an arbitrary Euclidean space. The proof is in Section 5.

The question which motivated our study of martingales in higher dimensions was to find upper bounds on Fourier coefficients of random subsets of finite abelian groups. We will assume some familiarity with basic terminology of finite abelian groups and characters; we recommend Babai’s lecture notes [5] for a concise introduction, but any abstract algebra textbook should do.

Definition 1.10 Let G be a finite abelian group. A homomorphism χ : G → ℂ^{×}, from G into the multiplicative group of complex units is called a character of G. The all-ones character χ_{0} : G → 1 often plays a special role, and is known as the principal character. Let f be a function on a finite abelian group G. For a given character χ, the Fourier coefficient of f corresponding to χ is the average \frac{1}{|G|} ∑_{x∈G} χ(x)f(x).

Note that when f_{S} is the characteristic function of a subset S ⊆ G, the Fourier coefficient corresponding to the principal character is the relative size of the subset, χ_{0}(f) = |S|/|G|. We are interested in proving upper bounds on the size of non-principal Fourier coefficients, motivating the following definition.

Definition 1.11 (see [5]) Let G be a finite abelian group, and let f : G → ℂ be any function. For every character χ : G → ℂ^{×}, we set

Φ_{χ}(f) := |∑_{x∈G} χ(x)f(x)| ,
and denote Φ(f) := max_{χ≠χ_{0}} Φ_{χ}(f)

where the maximum is taken over all characters χ : G → ℂ^{×} except the principal character χ_{0} ≡ 1. In the special case where f_{S} : G → {0, 1} is the characteristic function of a subset S ⊆ G, we write Φ(S) in place of Φ(f_{S}).

László Babai suggested using Chernoff bounds to show, when S is a random subset of G, that usually Φ(S) = O(\sqrt{n ln n}), i. e., “almost all subsets are nice.” We prove

Proposition 1.12 Let ϵ > 0. Let G be a finite abelian group of order n. For all but a O(n^{−ϵ}) fraction of subsets S ⊆ G,

Φ(S) < \sqrt{\frac{1 + ϵ}{2} n ln(n)}.

Babai also posed the same question when the size of the subset is fixed. This case is more interesting, because the Fourier coefficients can no longer be viewed as sums of n independent random variables. Nevertheless, using martingales, we can prove a similar upper bound on Φ(S):

Theorem 1.13 Let ϵ > 0. Let G be a finite abelian group of order n. Let k ≤ n, and let m = min{k, n − k}. For all but an O(n^{−ϵ}) fraction of subsets S ⊆ G such that |S| = k,

Φ(S) < 2\sqrt{2(1 + ϵ) m ln(n)}.

Remark 1.14 This result raises the following open question (as posed by L. Babai): construct an explicit family of sets of size m < n^{1−c}, for which Φ(S) is close to the probabilistic upper bound of Theorem 1.13. A challenge case is to construct S with |S| = n^{2/3} and Φ(S) < n^{1/2−ϵ}. Note that the estimate of Proposition 1.12 can be reached (even improved on) by explicit construction; namely, the set of quadratic residues in GF (n), for n a prime power, and more generally, cyclotomic sets S, always satisfy Φ(S) < \sqrt{n} (cf. [5, Section 6]).

Our proofs of Proposition 1.12 and Theorem 1.13, presented in Section 6, are a nice illustration of the convenience of having a two-dimensional version of the Azuma-Hoeffding inequality. We must in honesty point out that one can prove both results using only the (one-dimensional) Azuma-Hoeffding inequality, if we allow slightly worse constants; see Section 6 for details.

2 Reduction to Two Dimensions

In this section, we present a proof of Proposition 1.6. In light of Theorem 1.9, It will suffice for us to prove that, given a very-weak martingale X in 𝔼, there exists a very-weak martingale Y in ℝ^{2} having the desired properties. Then, by Theorem 1.9, which will be proved in Section 5, Y may be replaced by a strong martingale in ℝ^{2} also having the desired properties.

Our proof proceeds along roughly the same lines as Kallenberg and Sztencel’s proof of Proposition 1.5. However, the proof in [11, Section 3] is complicated by technical difficulties related to continuous time, which we do not encounter here. Kallenberg and Sztencel mention the existence of an elementary proof for discrete time [11, p. 223, first paragraph], but we could not find such a proof in the literature. Proof of Proposition 1.6, modulo Theorem 1.9: Given a very-weak martingale X in 𝔼, we define a very-weak martingale Y in ℝ^{2}, such that, for all i, ∥Y_{i} − Y_{i−1}∥ = ∥X_{i} − X_{i−1}∥ and ∥Y_{i}∥ = ∥X_{i}∥. In our construction, we will need a countable sequence of fair coin tosses, independent of X and each other. Without loss of generality, we assume that X is defined on a probability space containing such a sequence.

The Y_{i} are defined recursively, starting with Y_{0} = 0. Suppose i > 0 and Y_{i−1} has been defined, satisfying the desired conditions. We define Y_{i} so that the triangle (0, Y_{i−1}, Y_{i}) is congruent to (0, X_{i−1}, X_{i}). Since Y_{i−1} has been defined, the problem is to embed a given ordered triangle in the plane, with the first two corners specified. There are two choices for where to place the third corner, which are mirror images of each other over the line containing the first two corners. We use a fair coin flip to assign one of these two possibilities to Y_{i}.

Since we defined Y_{i} to make the triangles (0, Y_{i−1}, Y_{i}) and (0, X_{i−1}, X_{i}) congruent, it follows that

(∥Y_{i−1}∥, ∥Y_{i}∥, ∥Y_{i} − Y_{i−1}∥) = (∥X_{i−1}∥, ∥X_{i}∥, ∥X_{i} − X_{i−1}∥) .

All that remains is to show that Y is a very-weak martingale.

To see this, we write Y_{i} = α_{Y,i}Y_{i−1} +P_{Y,i}, where α_{Y,i}Y_{i−1} is the component of Y_{i} in the direction of Y_{i−1} and P_{Y,i} is perpendicular to Y_{i−1}. Similarly, break X_{i} up as X_{i} = α_{X,i}X_{i−1} + P_{X,i}. Since X is a very-weak martingale, we know that

X_{i−1} = E (X_{i} | X_{i−1})
= E (α_{X,i} | X_{i−1})X_{i−1} + E (P_{X,i} | X_{i−1}).

Since P_{X,i} is perpendicular to X_{i−1}, it follows that E (P_{X,i} | X_{i−1}) = 0, so E (α_{X,i} | X_{i−1}) = 1.

Since the triangles (0, Y_{i−1}, Y_{i}) and (0, X_{i−1}, X_{i}) are congruent, we have α_{Y,i} = α_{X,i}. Since α_{X,i} does not depend on the coin flips,

E (α_{Y,i} | Y_{i−1}) = E (α_{X,i} | Y_{i−1}) = E (α_{X,i} | X_{i−1}) = 1.

Recall that when choosing Y_{i} given Y_{i−1}, the two possibilities are mirror images over the line containing 0 and Y_{i−1}. This is equivalent to saying that the two possibilities for P_{Y_{i}} sum to the zero vector. Since we used a fair coin flip to make our selection, it follows that

E (P_{Y,i} | Y_{i−1}) = 0.

Putting these facts together, we have

E (Y_{i} | Y_{i−1}) = E (α_{Y,i} | Y_{i−1})Y_{i−1} + E (P_{Y,i} | Y_{i−1})
= Y_{i−1}.

Thus Y is a very-weak martingale, as claimed.

2.1 Dimension 2 is necessary

Having seen that martingales in any dimension may be reduced to martingales in the plane, as far as large deviations are concerned, it is worth seeing that we cannot immediately reduce all the way to a martingale in ℝ.

Definition 2.1 Let PS be a martingale in ℝ^{2} in which each step is of unit length, and is perpendicular to the previous total. (We may take PS_{1} = ±1, to be determined by fair coin toss, and determine the k’th step by tossing a coin to decide between the two possible vectors perpendicular to PS_{k−1}.) We will call PS the perpendicular-steps martingale.

For this martingale, the square of the distance from the origin increases by one at each step, so the deviation is always \sqrt{n} after n steps. In contrast, any unit-step martingale in ℝ has positive probability of remaining in [−1, 1] for n steps.

3 A Bound on Large Deviations

In this section, we prove Theorem 1.8 for the case when X is a strong martingale. The proof for very-weak martingales will follow by Theorem 1.9 (Section 5).

Before presenting the proof, we describe the general approach and some obstacles. The usual strategy for the proof of the Azuma-Hoeffding Inequality, Proposition 1.1, presented in [2, pp. 83–85, 233–240], is to bound

E (e^{λ|X_{n}|}), using the equalities e^{λ|X_{n}|} = max{e^{±λX_{n}}} and e^{λX_{n}} = ∏_{i=1}^{n} e^{λ(X_{i}−X_{i−1})}.

Obviously the first equality does not generalize to higher dimensions. Nevertheless, we are able to follow a similar strategy, bounding e^{λ∥X_{n}∥} using the

equality e^{λ∥X_{n}∥} = ∏_{i=1}^{n} e^{λ(∥X_{i}∥−∥X_{i−1}∥)}.

It turns out that the terms in this product have small conditional expectations when ∥X_{i}∥ is sufficiently large. When ∥X_{i}∥ is small, however, problems arise. We would encounter similar difficulties in the proof for martingales on the real line, if we tried to bound ∏_{i=1}^{n} e^{λ(|X_{i}|−|X_{i−1}|)} directly.

The problematic behavior when ∥X_{i}∥ is small is caused by the possibility of substantial “free progress” away from the origin. On the real line, as long as |X_{i−1}| > 1, the conditional expectation of |X_{i}|−|X_{i−1}| is zero, conditioned on the history. In higher dimensions, ∥X_{i}∥−∥X_{i−1}∥ may never have conditional expectation zero, as shown by the perpendicular steps martingale (Section 2.1). However, this expectation tends to zero as ∥X_{i}∥ becomes large.

To handle this problem, we define a new random series X′, which has a “similar shape” to X, but never comes close to the origin, and which consequently never makes much free progress. On the other hand, no matter how much free progress X makes, it cannot “catch up:” ∥X_{i}∥ < ∥X′_{i}∥ with probability 1. Figure 1 illustrates the situation when X is a perpendicular steps martingale.

Figure 1: At left: the given martingale, X. At right: the induced random walk X′, starting at (λ, 0). X′ behaves like a martingale, except when this would cause ∥X′_{n}∥ < λ. Note that while X has moved \sqrt{5} units from the origin, ∥X′_{5}∥ is still very close to ∥X′_{0}∥ = λ.

We will not present an explicit description of X′, as it is not needed in the proof. However, we will study its norm, Y, which we do define. The interested reader should be able to construct a suitable definition of X′ from the definition of Y and from Figure 1. We now proceed to the proof. Proof of Theorem 1.8, assuming X is a strong martingale: Let X be a given (strong) martingale in 𝔼, such that for every i, ∥X_{i} − X_{i−1}∥ ≤ 1.

We recursively define four real-valued series, A, D, Z, and Y, which will be useful for our analysis.

As in the proof of Proposition 1.5, we define

X_{i} = α_{X,i}X_{i−1} + P_{i},

where α_{X,i} is a real number, and P_{i} is the component of X_{i} orthogonal to X_{i−1}. Define the series A = (A_{i}) by A_{i} := (α_{X,i} − 1)∥X_{i−1}∥. We observe that

1 ≥ ∥X_{i} − X_{i−1}∥^{2} = A_{i}^{2} + ∥P_{i}∥^{2}.

The three random walks D, Z, Y are defined simultaneously by induction, as follows:

Y_{0} = 1 + λ^{−1} Z_{0} = 0
D_{i} = s̃gn(Z_{i−1}) (\sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1} − Y_{i−1})
Z_{i} = Z_{i−1} + D_{i}
Y_{i} = Y_{0} + |Z_{i}|.

With foreknowledge of the proof, we define λ := (a − 1)/n. The function s̃gn : ℝ → {−1, +1} is defined by

s̃gn(x) = \{ \begin{matrix}1 & if x ≥ 0 \\ −1 & if x < 0 \end{matrix}

Claim 3.1 For 1 ≤ i ≤ n,

|Z_{i}| = |\sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1} − Y_{0}| .

Proof: By the definitions of Z_{i}, D_{i}, and Y_{i}, respectively,

s̃gn(Z_{i−1})Z_{i} = s̃gn(Z_{i−1})Z_{i−1} + s̃gn(Z_{i−1})D_{i}
= |Z_{i−1}| + \sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1} − Y_{i−1}
= \sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1} − Y_{0}.

The claim follows by taking absolute values.

Claim 3.2 For all i, Y_{i} > ∥X_{i}∥.

Proof: (Induction on i.) Y_{0} = 1+λ^{−1} > 0 = ∥X_{0}∥. Suppose the claim holds for i − 1. By Claim 3.1, we have

Y_{i} = Y_{0} + |Z_{i}| = Y_{0} + |\sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1} − Y_{0}|
≥ \sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1}.

This can be rewritten as

Y_{i}^{2} ≥ (Y_{i−1} + A_{i})^{2} + 1 − A_{i}^{2}.

By the definition of A_{i}, it is easy to see that

∥X_{i}∥^{2} = (∥X_{i−1}∥^{2} + A_{i})^{2} + ∥P_{i}∥^{2}.

Subtracting, we have

Y_{i}^{2} − ∥X_{i}∥^{2} ≥ (Y_{i−1} + A_{i})^{2} − (∥X_{i−1}∥ + A_{i})^{2} + (1 − A_{i}^{2} − ∥P_{i}∥^{2})
= (Y_{i−1} − ∥X_{i−1}∥)(Y_{i−1} + ∥X_{i−1}∥ + 2A_{i}) + (1 − A_{i}^{2} − ∥P_{i}∥^{2})
> 0.

The last inequality above follows because

1. Y_{i−1} > ∥X_{i−1}∥ by induction.

2. Y_{i−1} ≥ Y_{0} = 1 + λ^{−1} ≥ 2 ≥ 2|A_{i}| from the definitions.

3. 1 ≥ A_{i}^{2} + ∥P_{i}∥^{2} as already observed.

Claim 3.3 Fix Z_{i−1}. Then the random variable f(A_{i}) := e^{λD_{i}} satisfies

f(A_{i}) ≤ cosh λ + A_{i} s̃gn(Z_{i−1}) sinh λ.

Proof: By definition, when A_{i} = ±1, D_{i} = s̃gn(Z_{i−1})A_{i}. Hence f(−1) = e^{−λ s̃gn(Z_{i−1})A_{i}} and f(1) = e^{λ s̃gn(Z_{i−1})A_{i}}. The secant line joining (−1, f(−1)) to (1, f(1)) has equation

y = cosh λ + A_{i} s̃gn(Z_{i−1}) sinh λ.

Thus, to prove the claim, it suffices to show that \frac{d^{2}f}{dA_{i}^{2}} > 0 on the interval (−1, 1).

Differentiating and simplifying, we have

\frac{d^{2}f}{dA_{i}^{2}} = ((λ\frac{dD_{i}}{dA_{i}} )^{2} + λ\frac{d^{2}D_{i}}{dA_{i}^{2}} ) f

= (λ\sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1} − s̃gn(Z_{i−1})) \frac{λY_{i−1}^{2}f(A_{i})}{(Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1)^{3/2}}

Since \sqrt{Y_{i−1}^{2} + 2Y_{i−1}A_{i} + 1} ≥ Y_{i−1} − 1 ≥ Y_{0} − 1 ≥ |λ|^{−1} > 1, we see that \frac{d^{2}f}{dA_{i}^{2}} > 0 as desired.

Claim 3.4 E (e^{λD_{n}} | Z_{n−1}) ≤ cosh λ.

Proof: By Fubini’s Theorem,

E (e^{λD_{n}} | Z_{n−1}) = E (E (e^{λD_{n}} | X_{0}, …, X_{n−1}) | Z_{n−1}).  (5)

By Claim 3.3, we have

E (e^{λD_{n}} | X_{0}, …, X_{n−1}) ≤ cosh λ + s̃gn(Z_{n−1}) sinh(λ)E (A_{n} | X_{0}, …, X_{n−1}) = cosh λ.

Because X_{0}, …, X_{n−1} determine Z_{n−1}, this upper bound applies to E (e^{λD_{n}} | X_{0}, …, X_{n−1}, Z_{n−1}) as well. Applying this bound to equation (5) proves the Claim.

By Fubini’s Theorem and Claim 3.4, we deduce

E (e^{λZ_{n}}) = E (e^{λZ_{n−1}}e^{λD_{n}})
= E (e^{λZ_{n−1}}E (e^{λD_{n}} | Z_{n−1}))
≤ E (e^{λZ_{n−1}}) cosh λ

By induction, it follows that

E (e^{λZ_{n}}) ≤ (cosh λ)^{n}.  (6)

Now, by Claim 3.2 and the definition of Y_{n}, we have:

e^{λ∥X_{n}∥} < e^{λY_{n}} = e^{λ(Y_{0}+|Z_{n}|)} ≤ e^{λY_{0}}(e^{λZ_{n}} + e^{−λZ_{n}}).  (7)

Combining (6) and (7), we find

E (e^{λ∥X_{n}∥}) < e^{λY_{0}}2(cosh λ)^{n}.  (8)

Applying Markov’s Inequality and equation (8), we have

Pr [∥X_{n}∥ ≥ a] = Pr [e^{λ∥X_{n}∥} ≥ e^{λa}]
≤ E (e^{λ∥X_{n}∥−λa})
≤ e^{λY_{0}−λa}2 (cosh λ)^{n} .

We will use the inequality cosh λ ≤ e^{λ^{2}/2} (which can easily be seen by examining the power series for each side), and the definition Y_{0} = 1 + λ^{−1}, to simplify the right hand side. Choosing λ = (a−1)/n minimizes the resulting expression. Thus we have

Pr [∥X_{n}∥ ≥ a] ≤ 2e^{λ+1−λa+λ^{2}n/2} = 2e^{1−(a−1)^{2}/2n}.

Remark 3.5 Unlike the proof of the 1-dimensional Azuma-Hoeffding inequality in [2], this proof technique apparently does not apply directly to very-weak martingales; instead we must appeal to Theorem 1.9. A careful look at the proof of Claim 3.4 shows the obstacle: we cannot replace the conditioning on X_{0}, …, X_{n−1} here with conditioning only on X_{n−1}, because the real number Z_{n−1} depends essentially on the entire history of X_{n−1}, not just the current value X_{n−1}. We would be interested in a proof of Theorem 1.8 which applies directly to the very-weak martingale case.

4 An Example of a very-weak martingale

One reason why very-weak martingales may be of interest is that they can be realized over much smaller sample spaces than strong martingales. Indeed, if a martingale X has all steps of positive length with probability one, then the random variable (X_{1}, …, X_{n}) induces a subalgebra with at least 2^{n} atoms, by an easy induction. However, there are very-weak martingales X for which all steps have positive length, but (X_{1}, …, X_{n}) has only O(n^{2}) atoms. In this section, we give a very simple construction of such a very-weak martingale.

Small sample spaces have been useful in a variety of contexts, notably derandomization of algorithms using only pairwise or k-wise independent random variables [1, 3, 13, 14]. Although it is unclear how any advantage could be made of a weak martingale defined on a small sample space, we would not rule it out as a possibility.

The very-weak martingale we construct has a superficial similarity to the following familiar “coin flips” martingale, in that, if any two adjacent times are selected, and both processes observed at only those times, the processes are statistically indistinguishable.

Definition 4.1 Let ξ_{1}, ξ_{2}, …, be the ±1-valued indicator variables for a sequence of fully independent coin flips. For every n ≥ 0, let CF_{n} := ∑_{i=1}^{n} ξ_{i}. Then the sequence CF = (CF_{0}, CF_{1}, …) is the “coin flips” martingale.

Construction 4.2 For each real number α in [0, 1], for every n ≥ 0, define

f_{n}(α) = −n + 2 min \{k | ∑_{i=0}^{k} \binom{n}{i}2^{−n} ≥ α\}

The “fake coin flip” process, FCF = (FCF_{0}, FCF_{1}, …) is defined by selecting α uniformly at random from [0, 1], and for every n ≥ 0, setting FCF_{n} = f_{n}(α).

Proposition 4.3 FCF is a very-weak martingale which is not a weak martingale. Moreover, for every i ≥ 1, (FCF_{n−1}, FCF_{n}) has the same distribution as (CF_{n−1}, CF_{n}).

Proof: Using the standard recurrence

\binom{n}{j} = \binom{n − 1}{j} + \binom{n − 1}{j − 1},

we can see that, given that FCF_{n−1} = x, there is a 1/2 chance that FCF_{n} = x + 1 and a 1/2 chance that FCF_{n} = x − 1. This proves that FCF is a very-weak martingale, and also, by induction, that the distribution of (FCF_{n−1}, FCF_{n}) is the same as (CF_{n−1}, CF_{n}).

To see that FCF is not a weak martingale, observe that if FCF_{2}(α) = 2, then α ≥ 3/4, so, for instance, FCF_{6}(α) ≥ 4 with probability 1. More generally, for any integers 0 < x ≤ j, where j ≡ x (mod 2),

E (FCF_{n} | FCF_{j} = x) = Θ(\sqrt{n}).

Next, we describe a combinatorial difference between the class of veryweak martingales and that of strong martingales.

Proposition 4.4 For every n, |FCF_{n} − FCF_{n−1}| = 1, and the random variable (FCF_{1}, …, FCF_{n}) has O(n^{2}) atoms. Let X be a martingale satisfying |X_{n} − X_{n−1}| = 1. Then (X_{1}, …, X_{n}) has at least 2^{n} atoms.

Proof: The atoms of (FCF_{1}, …, FCF_{n}) are the intervals between consecutive values of the form

∑_{j=0}^{k} \binom{i}{j}2^{−i},

where 0 ≤ i ≤ n. Since there are \binom{n+2}{2} terms of this form, counting multiplicity, there are at most this many atoms.

Suppose X is a martingale satisfying |X_{n} − X_{n−1}| > 0 for every n. Then every atom of (X_{1}, …, X_{n−1}) is a disjoint union of at least two atoms of (X_{1}, …, X_{n}) (since the average of X_{n} − X_{n−1} over these atoms must be zero). By induction, it follows that (X_{1}, …, X_{n}) has at least 2^{n} atoms.

5 Turning very-weak martingales into strong

We now present the proof of Theorem 1.9, which for any very-weak martingale in ℝ^{d}, shows the existence of a strong martingale for which the terms X_{n} and the steps X_{n} −X_{n−1} have the same distribution as the original series.

We present the proof in two parts: first the proof for very-weak martingales whose range is a finite set and which run for only finitely many steps, second the proof for arbitrary very-weak martingales in ℝ^{d}. Most readers will probably be satisfied with the finite case, which has a simple proof. Proof of Theorem 1.9 (case of finite range and finitely many steps): Let X be a very-weak martingale taking values in a real vector space V. Furthermore suppose each X_{n} takes values in a finite set F ⊂ V. Let P be the probability measure on which X is defined.

We construct Y and its underlying probability measure Q recursively, starting with Y_{0} = 0.

Assume that Y_{n−1} = (Y_{0}, …, Y_{n−1}) has already been defined, with underlying probability measure Q_{n−1}. To define the distribution of Y_{n} = (Y_{0}, …, Y_{n}), we need to specify how the atoms of Q_{n−1} should be refined.

Let (y_{0}, …, y_{n}) ∈ (ℝ^{d})^{n} be any sequence of vectors in ℝ^{d}. We define

Q_{n} [Y_{n} = (y_{0}, …, y_{n}) | Y_{n−1} = (y_{0}, …, y_{n−1})] = P [X_{n} = y_{n} | X_{n−1} = y_{n−1}].

In other words, if X_{n−1} has positive probability of equaling y_{n−1}, we set

Q_{n} [Y_{n} = (y_{0}, …, y_{n})] = \frac{P [X_{n−1} = y_{n−1}, X_{n} = y_{n}]Q_{n−1} [Y_{n−1} = (y_{0}, …, y_{n−1})]}{P [X_{n−1} = y_{n−1}]},

and if not, all probabilities in the above equation are zero.

Intuitively, at the n’th step, Y “forgets” how it arrived at y_{n−1}, then chooses a random continuation according to X. The series Y thus defined obviously satisfies the desired criteria.

In the general case, we “construct” Y by specifying its finite joint distribution functions. We employ standard techniques to demonstrate the existence of a random series with the specified distributions. The basic idea of the construction remains the same: Y is obtained by modifying X to “forget the history” at each step.

We now present the proof for the general case. Proof of Theorem 1.9 (general case): We define Y implicitly by specifying its distribution on finite-dimensional rectangles. The existence of a countable series Y with the given distributions follows from the Kolmogorov extension theorem [7, Corollary 2.19].

Let P be the probability measure on which X is defined. Denote by Q the new probability measure being constructed, on which Y will be defined. Note that Construction 4.2 shows that Q cannot generally be taken to be P.

Let Y_{0} = 0. For all n, and all intervals A ⊆ (ℝ^{d})^{n−1}, B ⊆ ℝ^{d}, define

Q_{n} [Y_{n} ∈ A × B] = E_{x} (Q_{n−1} [Y_{n−1} ∈ A | Y_{n−1} = x]P [X_{n} ∈ B | X_{n−1} = x]). (9)

Here x is an independent random variable sampled from the same distribution as X_{n−1} (and as Y_{n−1}: the distributions are the same by inductive hypothesis). Let us briefly explain the meaning of terms on the right-hand side of (9).

Let μ be the law of X_{n−1}, i. e. the probability measure on ℝ^{d} defined by

μ [S] = P [X_{n−1} ∈ S],

for all Borel sets S ⊆ ℝ^{d}. By inductive hypothesis, μ is also the law of Y_{n−1}.

The conditional probabilities on the right-hand side of (9) are defined in terms of Radon-Nikodym derivatives (cf. [16]), in a manner we will now set forth. For each interval A ⊆ (ℝ^{d})^{n−2}, let Q_{A} be the probability measure on ℝ^{d} defined by

Q_{A}(S) = Q_{n−1} [Y_{n−1} ∈ A × S].

Then Q_{A} is absolutely continuous with respect to μ, and the Radon-Nikodym derivative dQ_{A}/dμ is a μ-measurable function f such that, for every interval S ⊆ ℝ^{d},

Q_{A}(S) = ∫_{x∈S} f(x)dμ(x).

We define

Q_{n−1} [Y_{n−1} ∈ A × S | Y_{n−1} = x] = f(x)ψ_{S}(x),

where ψ_{S} : S → {0, 1} is the characteristic function of S. With this notation, the definition of the R-N derivative f may be rewritten as

Q_{n−1} [Y_{n−1} ∈ A × S] = E_{x} (Q_{n−1} [Y_{n−1} ∈ A × S | Y_{n−1} = x]),

where x is selected according to μ.

Similarly, if P_{B} is the probability measure on ℝ defined by

P_{B}(S) = P [X_{n−1} ∈ S, X_{n} ∈ B],

then we denote the Radon-Nikodym derivative dP_{B}/dμ by P [X_{n} ∈ B | X_{n−1} = x].

Since the conditional probabilities on the right-hand side of (9) are now seen to be random variables in the range [0, 1], the right-hand side is welldefined, and is in [0, 1]. It is easy to check that this definition is finitely additive, and hence extends to a probability measure. Furthermore, it is easy to check that the sequence of distributions defined by (9) meet the regularity criteria of the Kolmogorov extension theorem [7, Corollary 2.19], and so define a countable random series.

To verify that (Y_{n−1}, Y_{n}) has the same distribution as (X_{n−1}, X_{n}), we just chase definitions:

Q [Y_{n−1} ∈ A, Y_{n} ∈ B] = Q [Y_{n} ∈ (ℝ^{d})^{n−2} × A × B]
= E (Q [Y_{n−1} ∈ (ℝ^{d})^{n−2} × A | Y_{n−1} = x]P [X_{n} ∈ B | X_{n−1} = x])
= E (ψ_{A}(x) P [X_{n} ∈ B | X_{n−1} = x])
= E (P [X_{n−1} ∈ A, X_{n} ∈ B | X_{n−1} = x])
= P [X_{n−1} ∈ A, X_{n} ∈ B].

The martingale condition E (Y_{n} | Y_{0}, …, Y_{n−1}) = Y_{n−1} may be rewritten in the form

E (ϕ(Y_{n}) Y_{n}) = E (ϕ(Y_{n}) Y_{n−1}),  (10)

for every measurable function ϕ : (ℝ^{d})^{n} → ℝ. By standard arguments, it suffices to prove this statement in the special case when ϕ = ψ_{S} is the characteristic function of an interval S ⊆ (ℝ^{d})^{n}.

Decompose S = A × B, where A ⊆ (ℝ^{d})^{n−1} and B ⊆ ℝ^{d} are intervals.

To verify (10) we expand the left side using (9) (the defining recurrence for Y). Writing everything explicitly in terms of Radon-Nikodym derivatives yields a rather messy intermediate expression, which may in turn be rewritten in a nice form, using Fubini’s Theorem and the Dominated Convergence Theorem . The result is:

E (ψ_{A×B}(Y_{n}) Y_{n}) = E_{x} (Q [Y_{n−1} ∈ A | Y_{n−1} = x] E (ψ_{B}(X_{n}) X_{n} | X_{n−1} = x)) where x is sampled according to the distribution μ introduced earlier. The right side of (10) may be expanded in the same way to obtain

E (ψ_{A×B}(Y_{n}) Y_{n−1}) = E_{x} (Q [Y_{n−1} ∈ A | Y_{n−1} = x] E (ψ_{B}(X_{n}) X_{n−1} | X_{n−1} = x)).

Since X is a very-weak martingale, we have E (ψ_{B}(X_{n}) X_{n} | X_{n−1} = x) = E (ψ_{B}(X_{n}) X_{n−1} | X_{n−1} = x) a.e. μ. Substituting, we obtain

E (ψ_{A×B}(Y_{n}) Y_{n}) = E (ψ_{A×B}(Y_{n}) Y_{n−1}),

which shows that Y is a martingale.

6 Random Subsets have all small Fourier Coefficients

6.1 Sets of Any Size

Our first application of Theorem 1.8 is to prove Proposition 1.12, which says that almost all subsets of a finite abelian group G are “nice” (have all small Fourier coefficients). The exact result follows as an easy corollary of the following lemma.

Lemma 6.1 Let G be a finite abelian group of order n, and let χ : G → ℂ^{×} be a non-principal character. Select a subset S ⊆ G uniformly at random. Then

Pr [Φ_{χ}(S) ≥ a\sqrt{n}] < 2e^{2}e^{−2a^{2}}.

Proof: Let G = {g_{1}, …, g_{n}}. For 0 ≤ i ≤ n, let η_{i} be the {0, 1}-valued indicator function for the event g_{i} ∈ S. Define X_{i} := 2E (∑_{x∈S} χ(x) | η_{1}, …, η_{i}). Then (X_{0}, …, X_{n}) is a martingale taking values in ℂ. (Martingales defined in this manner are known as “Doob martingales.”) Note that X_{0} = 0 and that |X_{n}| = 2Φ_{χ}(S). Moreover, it is easily verified that X_{i} = ∑_{j=1}^{i} χ(g_{j})(2η_{i} − 1), which shows that |X_{i} − X_{i−1}| = 1 for every i.

Hence Theorem 1.8 implies

Pr [Φ_{χ}(S) ≥ a\sqrt{n}] = Pr [|X_{n}| ≥ 2a\sqrt{n}] < 2e^{2}e^{−(2a)^{2}/2}.

Here is a slightly improved version of the same lemma, whose proof uses only the (weighted) real-number version of Hoeffding’s inequality, Proposition 7.3). The proof is somewhat more involved.

Lemma 6.2 Let G be a finite abelian group of order n, and let χ : G → ℂ^{×} be a non-principal character. Select a subset S ⊆ G uniformly at random. Then

Pr [Φ_{χ}(S) ≥ a\sqrt{n}] < 4e^{−2a^{2}}.

Proof: Let G = {g_{1}, …, g_{n}}. For 0 ≤ i ≤ n, let η_{i} be the {0, 1}-valued indicator function for the event g_{i} ∈ S. Define X_{i} := 2E (∑_{x∈S} χ(x) | η_{1}, …, η_{i}). Then (X_{0}, …, X_{n}) is a (Doob) martingale taking values in ℂ. Note that X_{0} = 0 and that |X_{n}| = 2Φ_{χ}(S). Moreover, it is easily verified that X_{i} = ∑_{j=1}^{i} χ(g_{j})(2η_{i} − 1), which shows that |X_{i} − X_{i−1}| = 1 for every i.

The sequences (Re(X_{0}), …, Re(X_{n})) and (Im(X_{0}), …, Im(X_{n})) are realvalued martingales which satisfy Re(X_{n})^{2} + Im(X_{n})^{2} = |X_{n}|^{2}. Moreover, |Re(X_{i})−Re(X_{i−1})| = |Re(χ(g_{j}))| =: c_{i}, and similarly |Im(X_{i})−Im(X_{i−1})| = |Im(χ(g_{j}))| =: d_{i}.

Now, since c_{i}^{2} + d_{i}^{2} = 1 for every i, it follows that ∑_{i=1}^{n} c_{i}^{2} + ∑_{i=1}^{n} d_{i}^{2} = n. Hence

Pr [Φ_{χ}(S) ≥ a\sqrt{n}] = Pr [|X_{n}| ≥ 2a\sqrt{n}]
≤ Pr [|Re(X_{n})| ≥ 2a\sqrt{∑_{i=1}^{n} c_{i}^{2}}] + Pr [|Im(X_{n})| ≥ 2a\sqrt{∑_{i=1}^{n} d_{i}^{2}}]
< 2e^{−(2a)^{2}/2} + 2e^{−(2a)^{2}/2},

the last inequality following from Proposition 7.3 applied to Re(X_{n}) and to Im(X_{n}).

We note that a simpler version of this proof which uses only the nonweighted version of Azuma-Hoeffding, achieves a worse constant in the exponent of the upper bound.

6.2 Sets of Fixed Size

The proof of Proposition 1.12 did not really take full advantage of the power of Theorem 1.8, since the random variables being summed were independent, which is much more than just being a martingale. The case where the set size is fixed, requires us to analyze a much more history-dependent process. Theorem 1.13 follows easily from the following Lemma.

Lemma 6.3 Let G be a finite abelian group of order n, and let χ : G → ℂ^{×} be a non-principal character of G. Let k ≤ n, and let m = min{k, n − k}. Select a subset S ⊂ G uniformly at random subject to the constraint |S| = k. Then

Pr [Φ_{χ}(S) ≥ a\sqrt{m}] < 2e^{2}e^{−a^{2}/8}.

Proof: Without loss of generality, assume m = k ≤ n/2 (if not, replace S by G \ S; this reverses the signs of the non-principal characters, but leaves the magnitudes unchanged). Let us think of S as being chosen as follows: first, pick a random ordering (g_{1}, g_{2}, …, g_{n}) of the elements of G, then let S = {g_{1}, …, g_{k}}. We next define a (Doob) martingale Y = (Y_{0}, …, Y_{k}), where Y_{i} is defined in terms of the random variables g_{1}, …, g_{i}, as follows.

Y_{i} := \frac{1}{2} E (∑_{j=1}^{k} χ(g_{j}) | g_{1}, …, g_{i})

Since for any g, h ∈ G, |χ(g)−χ(h)| ≤ 2, it follows easily that |Y_{i} −Y_{i−1}| ≤ 1. Hence Theorem 1.8 tells us, for every a > 0,

Pr [Φ_{χ}(S) ≥ a\sqrt{k}] = Pr [Y_{k} ≥ a\sqrt{k}/2]
≤ 2e^{2}e^{−a^{2}/8}.

Since we are assuming m = k, this completes the proof.

It is possible to improve the bound in Theorem 1.13 to one of the form O(e^{−a^{2}/2(1+3m/n)}), by using the weighted version of Theorem 1.8 presented in the Notes as Theorem 7.4. This yields a corresponding improvement in the constant for Theorem 1.13. As in Section 6.1, it is also possible to deduce these results using only the (one-dimensional) Azuma-Hoeffding inequality, as long as one is not concerned with the constants.

7 Notes and Questions

Hoeffding’s original paper [10] actually proved the following stronger version of the Azuma-Hoeffding inequality.

Theorem 7.1 Let X = (X_{0}, X_{1}, …, X_{n}) be a real-valued martingale such that X_{0} = 0 and for every i, |X_{i} − X_{i−1}| ≤ 1. Then, for every a ∈ [0, n],

Pr [X_{n} ≥ a] ≤ 2^{n(H(\frac{a+n}{2n})−1)} ≤ e^{−a^{2}/2n},  (11)

where H(x) = −x log_{2}(x) − (1 − x) log_{2}(1 − x) is the binary entropy function.

The first inequality is within a factor O(\sqrt{n}) of equality for all values of a, and holds with equality for a = 0 and a = n. Our proof of Theorem 1.8 can easily be strengthened to the following:

Theorem 7.2 Let X = (X_{0}, X_{1}, …, X_{n}) be a very-weak martingale taking values in 𝔼 such that X_{0} = 0 and for every i, |X_{i} − X_{i−1}| ≤ 1. Then, for every a ∈ [0, n],

Pr [X_{n} ≥ a] ≤ e2^{n(H(\frac{a+n−1}{2n})−1)}  (12)

where H(x) = −x log_{2}(x) − (1 − x) log_{2}(1 − x) is the binary entropy function.

The proof is essentially the same as that of Theorem 1.8 up to the last paragraph, at which point, instead of approximating cosh(λ) by exp(λ^{2}/2), we set λ := archtanh((a − 1)/n) and carefully simplify the resulting bound, along lines similar to those of Hoeffding’s original proof [10]. It is not hard to show that the upper bound of Theorem 7.2 is within a factor O(n) of best possible for all values of a. Hoeffding also proved the following weighted version of the weaker inequality:

Proposition 7.3 Let X = (X_{0}, X_{1}, …, X_{n}) be a real-valued martingale such that for every i, |X_{i} − X_{i−1}| ≤ c_{i}. Then, for every a ≥ 0,

Pr [|X_{n}| ≥ a] ≤ 2 exp (\frac{−a^{2}}{2 ∑_{i} c_{i}^{2}} ) .  (13)

Proposition 7.3 was rediscovered by Azuma [4] a few years later.

Our proof technique naturally generalizes to the following weighted version of Theorem 1.8:

Theorem 7.4 Let X be a 𝔼-valued very-weak martingale such that for every i, ∥X_{i} − X_{i−1}∥ ≤ c_{i}. Then for every a > 0,

Pr [∥X_{n}∥ ≥ a] < 2 exp (\frac{−(a − Y_{0})^{2}}{2 ∑_{i=1}^{n} c_{i}^{2}} ) ,  (14)

where Y_{0} := max{1 + max c_{i}, 2 max c_{i}}.

This differs from the upper bound in Proposition 7.3 by a factor at most e^{O(c_{max}/c_{avg})}, where c_{max} = max c_{i}, and c_{avg} = ∑ c_{i}/n. Although this is only a constant factor when c_{max}/c_{avg} is bounded, in the general case this bound is considerably worse than that of Kallenberg and Sztencel, cited here as Proposition 1.7. It seems likely that Theorem 1.9 holds in more general contexts, such as very-weak martingales in ℓ_{2}, or even in Banach spaces (using the Bochner integral to define expectation). Although we are not sure whether we can guarantee the existence of a process which has the desired distributions in these contexts, we know of no obstacle to doing so, except the abstruseness of the subject. Regarding our upper bound for deviations of martingales in Euclidean space, it seems likely that the upper bound from the original Azuma-Hoeffding Inequality holds, without the additional factor of e^{1+(2a−1)/2n}.

8 Acknowledgements

I am indebted to László Babai not only for inspiring our investigations by his questions about Fourier coefficients, but also for much encouragement and assistance with the preparation of this paper. I am also grateful to Todd Rowland and Varsha Dani, among others, for helpful conversations.

I would like to thank the referee for pointing out several oversights and offering helpful suggestions.

References

[1] N. Alon, L. Babai, A. Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms 7 (1986) 567–583.

[2] Alon, Spencer, Erdős. The Probabilistic Method. John Wiley & Sons, Inc. New York.

[3] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy. Proof verification and the hardness of approximation problems. JACM 45 (1998) 501–555.

[4] K. Azuma. Weighted Sums of Certain Dependent Random Variables. Tôhoku Math. Journ. 19 (1967) 357–367.

[5] L. Babai. Fourier Transforms and Equations over Finite Abelian Groups, An introduction to the method of trigonometric sums. University of Chicago Department of Computer Science “Lecture Notes” version 1.2, December 1989. Technical report TR-2001-01. http://www.cs.uchicago.edu/research/publications/techreports/TR-2001-01

[6] J. Berman. An example of a weak martingale. Annals of Probability 4 (1976), 107–108.

[7] L. Breiman. Probability. Addison-Wesley Publishing Co., 1968.

[8] S.D. Chatterji. Vector-valued martingales and their applications. Probability in Banach Spaces, Proceedings of the First International Conference on Probability in Banach Spaces. Springer Verlag, 1976.

[9] H. Chernoff. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics 23 (1952) 493–509.

[10] W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58 (1963) 13–30.

[11] O. Kallenberg, R. Sztencel. Some dimension-free features of vectorvalued martingales. Probab. Th. Rel. Fields 88 (1991) 215–247.

[12] I. Karatzas, S.E. Shreve. Brownian motion and stochastic calculus. Springer-Verlag, 1988.

[13] M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15 (1986) 1036–1053.

[14] M. Luby, A. Wigderson. Pairwise independence and derandomization, a survey. ICSI TR-95-035. http://citeseer.nj.nec.com/luby95pairwise.html

[15] P. Nelson. A class of orthogonal series related to martingales. Annals of Mathematical Statistics 41 (1970) 1684–1694.

[16] D. Williams. Probability with Martingales. Cambridge University Press, 1991.