### Recap: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

We are given an expander graph G.

We are interested in functions f:V->[-1, 1] and aim to calculate the

expectation E[f]. For this analysis we are given that E[f] = 0, but we can also consider estimating E[g] for functions g where

E[g] != 0. To do so let f = g - E[g], so that E[f] = 0.

We consider taking a sample W=(Y

_{1}, ..., Y

_{k}) of vertices of V. We consider three bounds:

**Chernoff**

e

^{( -γ^2 k/2.4) }

**Walk on G (strong bound)**

e

^{ -γ^2 ε k/60 }

**Walk on G (weak bound)**

((2/ε log 8/(γ ε)) e

^{ -(γ^2 k ε^3)/(12(2 log 8/(γ ε))) }

In the first case, W is a random, independent sample, resulting in a trivial Chernoff bound.

In the second and third cases, W is a random walk on G.

Chernoff bound and the weak bound for the random walk.

The proof for the Chernoff bound uses Markov's inequality and other simple algebraic

manipulations to arrive at a point where the independence of the Y

_{ i }

can be used.

When W is a walk, we cannot use the independence of the Y

_{ i }, since the

Y

_{ i }are not independent. Instead we apply linear algebra to show

that a summation is bounded by a dot product, and then bound the dot product by

an algebraic expression. We minimize over an arbitrary constant t to get the desired bound.

We then boost this result by dividing the walk W into samples and applying the union bound.

Lastly, we consider another paper, A Simple Chernoff Bound for Random Walks on a Weighted Graph, by David Gillman. In this paper a walk is taken on a

weighted graph, and the objective is to estimate the weight of the vertices in A, where

A is a subset of V, by sampling

(the weight of a vertex is equal to the sum of the weights of its edges).

In the setting of the previous paper, it is as though f is being taken as a 0-1 function, 0 for the vertices not in A and 1 for the vertices in A.

The main result of the paper quantifies the rate convergence of estimates of the weight of A to the actual weight of A as the length of the sample walk increases.

Then we explore three approximation algorithms, the Standard Procedure, Aldous's Procedure, and

Aldous's Procedure with Statistical Technique. The Standard Procedure takes multiple walks, sampling the last vertex of each walk.

Aldous's Procedure takes a walk and samples every verex after a certain count.

Aldous's Procedure with statistical techniques runs Aldous's Procedure multiple times to get

more accurate results.

The paper shows that Aldous's Procedure with Statistical Technique always beats the Standard Procedure, as does Aldous's Procedure given certain conditions.