# Proof of reduction from random walks to martingales - why $T\le k$?

I'm trying to understand the proof of theorem 1.6 from the paper "A Matrix Expander Chernoff Bound".

In the proof they say: "Iterating this construction on the remainder a total of $T ≤ k$ times" and later they choose a value for $T$.

$k$ is the length of a given walk on the graph $G$ which has $n$ vertices.

They choose $$T = \frac{2log(\frac{F}{ε})}{1 − λ}$$

If we take $f$ to be a function that gets $1$ on half of the vertices and $-1$ on the other half then $F=\sqrt{n}$ by definition. So $T\gt log(n)$. But $k$ might be much smaller than $log(n)$. So if $T>k$, how can they choose this $T$?

Thanks!

• Looks like you're correct to me, in that this choice is impossible given the constraint of $T \leq k$. However, I haven't really worked through the proof in detail. Why do the authors introduce $T$? Perhaps the authors implicitly intended a different ("trivial") choice of $T$ (perhaps $T=k$) in case the other choice is impossible. But it's equally possible to me that you just found an error. – Steve Aug 26 '18 at 20:13

One of the authors of the paper has answered me and he said that they implicitly assume $$k \ge \frac{2 log(\frac{F}{ε})}{1 − λ}$$.
He also said that actually the Theorem would still be true if $k \lt 2 log(F/ε)/(1 − λ)$. In this case, with the same $Z_i$’s, one will actually get $W = 0$ and $|Z_i|_* \le k max_v |f(v)|_*$ trivially.
Additionally, he said that basically Theorem 1.6 is not saying anything for small walks i.e. walks of length less than $2 log(F/ε)/(1 − λ)$. This is a drawback of this Theorem and in the matrix case, one can do much better by other methods as demonstrated by the main result of the paper (Theorem 1.2).