I'm trying to understand the proof of theorem 1.6 from the [paper "A Matrix Expander Chernoff Bound"](https://arxiv.org/pdf/1704.03864.pdf).


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!



Proof of reduction from random walks to martingales - why $T\le k$?
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).


