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

Question

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!

Answer 1

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