In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf .

I don't state the full lemma as it appears at the above link. I only mention that I don't understand how to prove the first inequality $$ \left\Vert \pi M^t-u \right\Vert \leq \lambda(G)^t \left\Vert \pi -u \right\Vert $$ According to the monograph it follows from definition of $\lambda(G)$ and induction, but I don't know how to prove the induction step.

If someone is familiar with this monograph, I'll appreciate any lead.

  • 1
    $\begingroup$ Applying the definition of $\lambda(G)$ to $\pi M^i$ in place of $\pi$ yields $\lambda(G)\|\pi M^i-u\|\ge\|\pi M^{i+1}-u\|$. This is your induction hypothesis. $\endgroup$ – Emil Jeřábek Oct 25 '18 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.