Lecture 8. Diameter, Doubling, and Applications
A first bound on diameter [#b00bdbe9]
lazy random walk matrix $M := A/2d + I/2$．$\mu_2 = 1 - \lambda$ を $M$ の second-largest eigenvalue．直径 $\delta$ は，
$$
\delta \leq \frac{\ln n}{\lambda}
$$
証明：ランダムウォークで来る確率，つまり M^k が全要素 0 より大きくなっていれば良い．というのを計算する．
Improving the bound on diameter [#p78eaced]
M^k だけじゃなくて，M を多項式 p(x) につっこんだとき non-zero だったらよい．これにチェビシェフ多項式を使うといいらしい．（数値計算の授業で出てきた気がする……）
突っ込んで計算すると，
$$
\delta \leq (1 + 1/\sqrt{2\lambda})\ln(2n)
$$
Doubling Distance [#qb9441c8]
この部分の記述なんか変な気がする（変数の文字衝突してない？）
Application: tail inequalities [#ib04703f]
Johnson graph というのに入れてみるとこれがでてくるっぽい
