计算机与人工智能应用数学笔记

$$ \boxed{\eq{ &\P\left[\bigcap_iA_i\right]=\prod_i\P\left[A_i\Big|\bigcap_{j{<}i}A_j\right]\\ &\P[A]=\sum_i\P[A|B_i]\P[B_i] }} $$ 如果后件概率为 $0$，那么条件概率为 $0$！！！

Nonnegative $X$, $\boxed{\P[X>a\E(X)]<1/a}$, or $\boxed{\P[X>a]<\E(X)/a}$.

Allow negative! $X\mapsto(X-\E(x))^2$, $\P[(X-\E(X))^2>a\V(X)]<1/a$ $\Longrightarrow$ $\boxed{\P[|X-\E(X)|>\sqrt a\sigma(X)]<1/a}$, or $\boxed{\P[|X-\E(X)|>a\sigma(X)]<1/a^2}$, or $\boxed{\P[|X-\E(X)|>a]<\V(X)/a^2}$. Not always better than Markov. 几何解释：考虑用直线（Markov）或二次函数曲线（Chebyshev）去 bound X，保证各处都大于等于（在 $x=a$/$x=\mu$ 处等）。Chebyshev 保证在 $\mu$ 附近比较逼进，离 $\mu$ 远的地方可能比 Markov 差。

$$ \boxed{\text{Condition}:X=\sum_{i=1}^nX_i,\text{independent }X_i\in\set{0,1}} $$ Consider $g(x)=\e^{tx}/\e^{ta}$，then $\P[X\ge a]\le\E[g(X)]=\E(\e^{tX})/\e^{ta}$. Now consider $X=\sum X_i$, where $X_i\in\set{0,1}$ and $\set{X_i}$ are independent. $\mu=\E(X)=\sum\P[X_i=1]$. Let $\P[X_i=1]=b_i$. $$ \eq{ \E(\e^{tX})=\E(\e^{t\sum X_i})=\E(\prod\e^{tX_i})=\prod\E(\e^{tX_i})=\prod(1-b_i+\e^{t}b_i)\le\prod\e^{(\e^t-1)b_i}=\e^{(\e^t-1)\sum b_i}=\e^{(\e^t-1)\mu} } $$ Now, $a=(1+\delta)\mu$, $\min\e^{(\e^t-1)\mu-t(1+\delta)\mu}$, take derivative, $t=\ln(1+\delta)$, we get $$ \min=\left(\frac{\e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu $$

$$ \left(\frac{\e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu\longrightarrow \e^{-\frac{\delta^2}{2+\delta}\mu}:\text{take log then use }\ln(1+x)\ge \frac{2x}{2+x} $$

Remark. For $\P[X\ge a]=\E(\e^{tX})/\e^{ta}$, we can simple use Markov: $\P[X\ge a]=\P[tX\ge ta]=\P[\e^{tX}\ge\e^{ta}]=\cdots$.

For $\P[X\le a]$, $a=(1-\delta)\eps$, the best $t$ will be negative. $$ \left(\frac{\e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu\longrightarrow \e^{-\frac{\delta^2}2\mu}:(1-x)\ln(1-x)\ge-x+\frac{x^2}2\text{ for }x\in(0,1) $$

Overall: $$ \boxed{ \left\{\eq{&\P[X\ge(1+\delta)\mu]\le\left(\frac{\e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu\le\e^{-\frac{\delta^2}{2+\delta}\mu}&(\delta\ge 0)\\ &\P[X\le(1-\delta)\mu]\le\left(\frac{\e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu\le\e^{-\frac{\delta^2}2\mu}&(0\le\delta<1)}\right\}\longrightarrow\P[|X-\mu|\ge\delta\mu]\le2\e^{-\frac{\delta^2}3\mu} } $$

$$ \boxed{\P[X\ge c]\le 2^{-c}\text{ if } c\ge 7\mu} $$

$$ \boxed{\P[|\overline{X}-\E(\overline{X})|\ge\eps]\le2\e^{-\frac{\eps^2}{2+\eps}n}} $$

$Z=\sum Z_i$, $Z_i\in[a,b]$ independent $$ \boxed{\P[\overline{Z}-\E(\overline{Z})\ge t],\P[\overline{Z}-\E(\overline{Z})\le-t]\le\e^{-\frac{2nt^2}{(b-a)^2}}} $$ Prove by considering $\E[\e^{tZ}]$, from convexity of $\e^x$, we have $$ \E[\e^{tZ}]\le\e^{\frac{t^2(b-a^2)}8} $$ For the original $\P[\overline{Z}-\E(\overline{Z})\ge t]$, first convert to $\e^{t\cdot}$ form, then use Hoeffding lemma, then minimize it by derivative.

$$ \boxed{\frac{2^{nH(q)}}{n+1}\le\binom{n}{nq}\le 2^{nH(q)}} $$ where $nq\in[0,n]\cap\Z$, $H(q)=-q\log_2q-(1-q)\log_2(1-q)$. Can be proven by $1=(q+1-q)^n=\sum\binom niq^i(1-q)^{n-i}$, 后一个只取 $\binom{n}{nq}$ 一项，前一个证明 $\binom{n}{nq}q^{nq}(1-q)^{n(1-q)}$ 是最大的，别的都放成它。 $$ 2^{H(q)}=\frac1{q^q(1-q)^{1-q}} $$

$$ 1-(1-\eps)^d\le 1-\e^{-\eps d} $$

$$ 1-\text{ratio}=\frac{V\text{ above }\frac{c}{\sqrt{d-1}}}{V_d/2} $$

$$ \begin{align*} V\text{ above }\frac{c}{\sqrt{d-1}}&=\int_{c/\sqrt{d-1}}^1\sqrt{1-r^2}^{d-1}V_{d-1}\d r\\ &\le V_{d-1}\int_{c/\sqrt{d-1}}^1\e^{-\frac{d-1}2r^2}\d r\\ &\le V_{d-1}\int_{c/\sqrt{d-1}}^{+\infty}\e^{-\frac{d-1}2r^2}\d r\\ &\le V_{d-1}\int_{c/\sqrt{d-1}}^{+\infty}\e^{-\frac{d-1}2r^2}\cdot\frac{r}{c/\sqrt{d-1}}\d r\\ &=\frac{V_{d-1}\sqrt{d-1}}{2c}\int_{c/\sqrt{d-1}}^{+\infty}\e^{-\frac{d-1}2r^2}\d(r^2)\\ &=\frac{V_{d-1}\sqrt{d-1}}{2c}\cdot\frac{2}{d-1}\e^{-\frac{d-1}2\cdot\frac{c^2}{d-1}}\\ &=\frac{V_{d-1}}{c\sqrt{d-1}}\e^{-c^2/2} \end{align*} $$

(Main idea: 凑 $V_{d-1}$ and $\e^{-x^2}\to x\e^{-x^2}$) $$ \begin{align*} \frac{V_d}2&=\int_0^1\sqrt{1-r^2}^{d-1}V_{d-1}\d r\\ &=V_{d-1}\int_0^1(1-r^2)^{(d-1)/2}\d r\\ &\ge V_{d-1}\int_0^{1/\sqrt{d-1}}\left(1-\frac{d-1}2r^2\right)\d r&\left(\text{need }\frac{d-1}2\ge 1\text{ !!!}\right)\\ &\ge V_{d-1}\frac{1}{\sqrt{d-1}}\left(1-\frac{d-1}2\left(\frac1{\sqrt{d-1}}\right)^2\right)\\ &=\frac{V_{d-1}}{2\sqrt{d-1}} \end{align*} $$ (Main idea: 取一个圆柱)

So, $$ 1-\text{ratio}\le\boxed{\frac c2\e^{c^2/2}}\qquad\color{red}\text{when }d\ge 3,c\ge 1 $$

With $\P=1-\Omicron(n^{-1})$:

• all $|\b x_i|\ge 1-\frac{2\ln n}d$. Directly union bound.
• all pairs $|\b x_i\cdot\b x_j|\le\frac{\sqrt{6\ln n}}{\sqrt{d-1}}$. 把 $\b x_i$ 视作 equator 的法向量，$\b x_j$ 大概率在 equator 的圆盘附近，再 union bound.

• Hoeffding. i.i.d. $X_i\sim\mathcal{U}(-a,+a)$, $$ \boxed{\P\left[\left\lvert S_n - \E(S_n)\right\rvert\geq t \right] \leq2\exp\left( -\frac{t^2}{2na^2} \right)} $$

• sub-Gaussian. i.i.d. $X_i$ s.t. $\forall \lambda$, $\E\left[\e^{\lambda(X_i-\E(X_i))}\right]\le\e^{\lambda^2\sigma^2/2}$, $$ \boxed{\P\left[\left\lvert S_n - \E(S_n)\right\rvert\geq t \right] \leq 2\exp\left( -\frac{t^2}{2n\sigma^2} \right)} $$

• sub-Exponential. i.i.d. $X_i$ s.t. $\forall|\lambda|<\alpha^{-1}$, $\E\left[\e^{\lambda(X_i-\E(X_i))}\right]\le\e^{\lambda^2\nu^2/2}$, $$ \boxed{\P\left[\left\lvert S_n - \E(S_n)\right\rvert\geq t \right] \leq 2\exp\left(-\min\Set{\frac{t^2}{2n\nu^2},\frac{t}{2\alpha}}\right)} $$

sub-Gaussian is $(\sigma,0)$ sub-exp.

$$ \boxed{\underset{x\sim\mathcal{N}(\b 0,I)}\P\left[\left\lvert|\b x|-\sqrt d\right\rvert\le\beta\right]\ge 1-3\e^{-c\beta^2}\text{ for any }\beta\le\sqrt{d}\text{ and some constant }c} $$ First, $$ \P\left[\left\lvert|\b x|-\sqrt{d}\right\rvert\ge\beta\right]=\P\left[\left\lvert|\b x|^2-d\right\rvert\ge\beta\left(|\b x|+\sqrt{d}\right)\right]\le\P\left[\left\lvert|\b x|^2-d\right\rvert\ge\beta\sqrt{d}\right] $$ 证 1. use sub-exp tail bound.

1. 易证 $\E(|\b x|^2)=d$. 这玩意叫卡方分布（$k$ 个标准正态的平方和记作 $\chi_k^2$）。

2. 证明 $\chi_1^2$ 是 sub-exp with $(\nu,\alpha)=(2,4)$:

   1. MGF $\E[\e^{\lambda (Z-1)}]=\frac{\e^{-\lambda}}{\sqrt{1 - 2\lambda}}$.
   2. 取 $\ln$，为 $-\lambda-\frac12\ln(1-2\lambda)=-\lambda-\frac12\left(-2\lambda-2\lambda^2-\frac83(\theta\lambda)^3\right)=\lambda^2+\frac43\theta^3\lambda^3\le\lambda^2+\frac13\theta^3\lambda^2\le 2\lambda^2$.

3. $$ \P\left[\left\lvert|\b x|^2-d\right\rvert\ge\beta\sqrt{d}\right]\le 2\exp\left(-\min\Set{\frac{(\beta\sqrt d)^2}{8d},\frac{\beta\sqrt d}{8}}\right)=2\e^{-\beta^2/8} $$

证 2. Master tail bound theorem: i.i.d. $X_i$ s.t. $\E=0$ and $\V\le\sigma^2$. $0\le a\le \sqrt2n\sigma^2$, $|\E(X_i^s)|\le \sigma^2s!$ for $s=3\sim\lfloor a^2/4n\sigma^2\rfloor$, $$ \boxed{\P[|S_n|\ge a]\le 3\exp\left(-\frac{a^2}{12n\sigma^2}\right)} $$ We have $\left\lvert|\b x^2|-d\right\rvert=\left\lvert\sum_{i=1}^d(\b x_i^2-1)\right\rvert$, let $X_i=\frac{\b x_i^2-1}2$. $$ \begin{align*} |\E(X_i^s)|&\le\E(|X_i|^s)\\ &\le 2^{-s}\E(1+\b x_i^{2s})\\ &=2^{-s}(1+(2s-1)!!)\\ &\le s! \end{align*} $$ So, we can let $\sigma=2$, $a=\beta\sqrt d/2$, $|\E(X_i^s)|\le \sigma^2s!$ is easily satisfied, thus $$ \P\left[\left||\b x|^2-d\right|\ge\beta\sqrt d\right]=\P\left[\left|\sum_{i=1}^dX_i\right|\ge a\right]\le 3\e^{-\frac{\beta^2}{96}} $$ 证 3. Chernoff bound: $$ \P[X\ge a]\le\inf_{t\ge0}\frac{\E(\e^{tX})}{\e^{ta}} $$ Here $\E(\e^{tX})=M_X(t)$ is the MGF of $X$. Consider $Y=|\b x|^2$. $$ \begin{align*} M_Y(t)&=\E\left(\e^{tY}\right)\\ &=\E\left(\e^{t\sum_{i=1}^d\b x_i^2}\right)\\ &=\E\left(\prod_{i=1}^d\e^{t\b x_i^2}\right)\\ &=\left(\E\left(\e^{t\b x_1^2}\right)\right)^d\\ &=\left(\int_{-\infty}^{+\infty}\frac{1}{\sqrt{2\pi}}\e^{-x^2/2}\e^{tx^2}\d x\right)^d\\ &=\left(\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{+\infty}\e^{-(1/2-t)x^2}\d x\right)^d\\ &=\left(\frac{1}{\sqrt{2\pi}}\sqrt{\frac{\pi}{1/2-t}}\right)^d\\ &=\left(1-2t\right)^{-d/2} \end{align*} $$

$$ \begin{align*} \P\left[|\b x|^2\ge d(1+\eps)^2\right]&\le\frac{(1-2t)^{-d/2}}{\e^{td(1+\eps)^2}}\\ &=\exp\left(-\frac d2\ln(1-2t)-d(1+\eps)^2t\right)\\ &=\exp\left(d\ln(1+\eps)-d\eps\left(1+\frac\eps2\right)\right)&\left(t=\frac12\left(1-\frac1{(1+\eps)^2}\right)\right)\\ &\le\exp\left(d\eps-d\eps\left(1+\frac\eps2\right)\right)\\ &=\e^{-d\eps^2/2} \end{align*} $$

Take $Z=-Y$, we can similarly prove $\P\left[|\b x|^2\le d(1-\eps)^2\right]\le\e^{-d\eps^2/2}$. $$ \P\left[\left\lvert|\b x|-\sqrt d\right\rvert\ge\beta\right]=\P\left[|\b x|^2\ge d\left(1+\frac{\beta}{\sqrt d}\right)^2\right]+\P\left[|\b x|^2\le d\left(1-\frac{\beta}{\sqrt d}\right)^2\right]\le2\e^{-\beta^2/2}\quad(\eps=\beta/\sqrt d) $$

$$ \begin{align*} M_X(t)&=\E\left[\e^{t X}\right]\\\ &=\frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^{+\infty}\e^{t(x+\mu)}\e^{-x^2/2\sigma^2}\d x\\\ &=\frac{\e^{\mu t+\sigma^2t^2/2}}{\sqrt{2\pi}\sigma}\int_{-\infty}^{+\infty}\e^{-(x/\sigma+\sigma t)^2/2}\d x\\\ &=\e^{\mu t+\sigma^2t^2/2} \end{align*} $$

$$ \begin{align*} &\P[X-\mu\ge t]\le\inf_\lambda\frac{\E\left[\e^{\lambda X}\right]}{\e^{\lambda(t+\mu)}}=\e^{-t^2/2\sigma^2}\\\ &\boxed{\P[|X-\mu|\ge t]\le 2\e^{-t^2/2\sigma^2}} \end{align*} $$

For $\b v\in\R^d$, i.i.d. $\b u_i\sim\Nd(\b 0,I_d)$, $f(\b v):\b v\mapsto\mat{\b u_1\cdot\b v&\cdots&\b u_k\cdot\b v}$. $$ \boxed{\P\left[\left\lvert|f(\b v)|-\sqrt k|\b v|\right\rvert\ge\eps\sqrt k|\b v|\right]\le 3\e^{-ck\eps^2}\text{ for some constant }c\text{ and any }\eps\in(0,1)} $$ Proof. i.i.d. $\b u_i\cdot\b{\hat v}\sim\Nd(0,1)$, then use GAT with $\beta=\sqrt k\eps$. 注意这里关键的一点是，i.i.d. 的随机变量的相同线性组合也是 i.i.d. 的。

$c$ and $\eps$ as above. For any $n$ points in $\R^d$, let $k\ge\frac{3}{c\eps^2}\ln n$, $f:\R^d\to\R^k$ as above. $$ \boxed{\P\left[\forall i,j,(1-\eps)\sqrt k|\b v_i-\b v_j|\le |f(\b v_i)-f(\b v_j)|\le (1+\eps)\sqrt k|\b v_i-\b v_j|\right]\ge 1-\frac{3}{2n}} $$

Proof. $f(\b v_i)-f(\b v_j)=f(\b v_i-\b v_j)$, then use RPT above. $3\e^{-ck\eps^2}\le 3n^{-3}$ then union bound, times $\binom n2$.

Under the same setting, plus $|\b v_i|\le 1$, we have with high Pr: $$ \boxed{\forall i,j,\left\lvert\frac{\ip{f(\b v_i),f(\b v_j)}}k-\ip{\b v_i,\b v_j}\right\rvert\le 2\eps+\frac{\eps^2}4} $$ Proof. Consider $$ \ip{f(\b v_i),f(\b v_j)}=\frac14\left(|f(\b v_i)+f(\b v_j)|^2-|f(\b v_i)-f(\b v_j)|^2\right) $$ Other versions: https://kexue.fm/archives/8679/comment-page-1

$$ \boxed{\sum\sigma_i^2=\sum|A\b v_i|^2=\sum\sum(\b a_i\cdot\b v_j)^2=\sum|\b a_i|^2=\sum\sum a_{i,j}^2=\|A\|_F^2} $$

定义 left singular vectors $\b u_k=\sigma_k^{-1}A\b v_k$, we have: $\boxed{\b u_i\perp\b u_j}$.

Proof. 反证，找到最小的 $\b u_i\not\perp\b u_j$（$i<j$），不妨设 $\b u_i\cdot\b u_j=\delta>0$。 $$ A\frac{\b v_i+\eps\b v_j}{|\b v_i+\eps\b v_j|}=\frac{\sigma_i\b u_i+\eps\sigma_j\b u_j}{\sqrt{1+\eps^2}}\Longrightarrow \b u_i\left(A\frac{\b v_i+\eps\b v_j}{|\b v_i+\eps\b v_j|}\right)=\frac{\sigma_i+\eps\sigma_j\delta}{\sqrt{1+\eps^2}}=\sigma_i+\sigma_j\delta\eps+\omicron(\eps^2) $$ 这与 $\b v_i$ 定义（$\max.|A\b v_i|$）矛盾。

$$ \boxed{A_{n\times m}=\sum\sigma_i\b u_i\b v_i^\top=\mat{\b u_1&\cdots&\b u_r}\mat{\sigma_1&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&\sigma_r}\mat{\b v_1^\top\\\vdots\\\b v_r^\top}=U_{n\times r}\Sigma_{r\times r}V^\top_{r\times m}} $$ Proof. $$ \sum\sigma_i\b u_i\b v_i^\top=\sum A\b v_i\b v_i^\top=A\mat{\b v_1&\cdots&\b v_n}\mat{\b v_1^\top\\\vdots\\\b v_n^\top} $$ and by definition, $$ \mat{\b v_1^\top\\\vdots\\\b v_n^\top}\mat{\b v_1&\cdots&\b v_n}=I\Longrightarrow \mat{\b v_1&\cdots&\b v_n}\mat{\b v_1^\top\\\vdots\\\b v_n^\top}=I $$ or we can prove by $\forall\b x(A\b x=B\b x)\Longrightarrow A=B$.

Let $A_k=\sum_{i\le k}\sigma_i\b u_i\b v_i^\top$.

Note. 当 $A$ 是实对称矩阵时，$\set{\sigma_i}=\set{\lvert\lambda_i\rvert}$，如果 $\lambda_i$ 是负的，则 $U$ 和 $V$ 的对应列符号相反。$A$ 有重复特征值时 $U$ 和 $V$ 不唯一。求 SVD 的手工方法是 $A^\top A=V\Sigma^2 V^\top$，对它做正交对角化。对称正定矩阵的特征值分解保证 $U=V$，但半正定不保证 $U=V$。

The rows of $A_k$ are the projections of the rows of $A$ onto the subspace $V_k$ spanned by the first $k$ singular vectors of $A$.

Proof. $$ \sum_{i\le k}A\b v_i\b v_i^\top=\sum_{i\le k}\sigma_i\b u_i\b v_i^\top=A_k $$

$$ \boxed{\|A-A_k\|_F=\min_{\r(B)\le k}\|A-B\|_F,\|A-A_k\|_2=\min_{\r(B)\le k}\|A-B\|_2} $$ Proof. $\min$ 差的 Frobenius 范数可以理解成 $A$ 的各行到 $\operatorname{R}(B)$ 的距离，于是从 best-fit space 的角度即可说明。 对于 $2$ 范数，找单位向量 $\b z\in\operatorname{N}(B)\cap\span{\b v_1,\cdots,\b v_{k+1}}$，设 $\b z=\sum c_i\b v_i$， $$ \|A-B\|_2\ge|(A-B)\b z|=|A\b z|=\left\lvert\sum Ac_i\b v_i\right\rvert=\left\lvert\sum c_i\sigma_i\b u_i\right\rvert=\sqrt{\sum c_i^2\sigma_i^2}\ge\sigma_{k+1}\sqrt{\sum c_i}=\sigma_{k+1}|\b z|=\sigma_{k+1} $$

Unit vector $\b x$ satisfies $|\b x^\top\b v_1|\ge\delta$. Let $V$ be the subspace spanned by 特征值 $>(1-\eps)\sigma_1$ 的 $\b v$ 们. For $$ \boxed{k=\frac{-\ln(\eps\delta)}{2\eps}} $$ the result $\b w=\left(A^\top A\right)^k\b x$ satisfies that $$ \boxed{\left\lvert\b{\hat w}_{V^\perp}\right\rvert\le\eps} $$ Proof. 单位化后垂直分量的长度，就是 $\b w$ 垂直分量部分占总模长的比例： $$ \left\lvert\b w\right\rvert=\left\lvert\sum\sigma_i^{2k}c_i\b v_i\right\rvert\ge\sigma_1^{2k}c_1=\sigma_1^{2k}\delta $$

$$ \left\lvert\b w_\perp\right\rvert=\left\lvert\sum_{\sigma_i\le(1-\eps)\sigma_1}\sigma_i^{2k}c_i\b v_i\right\rvert\le(1-\eps)^{2k}\sigma_1^{2k}\sqrt{\sum_{\sigma_i\le(1-\eps)\sigma_1}c_i^2}\le(1-\eps)^{2k}\sigma_1^{2k} $$

$$ \text{ratio}\le\frac{(1-\eps)^{2k}}\delta\le\frac{\e^{-2k\eps}}\delta=\eps $$

1. $1\text{-D}$ case: $$ \P[X_{2n}=0]=4^{-n}\binom{2n}n=\frac{1}{\sqrt{\pi n}}\left(1+\Omicron(n^{-1})\right)\Longrightarrow\E[N_0]=\sum_{n}\P[X_{2n}=0]\sim\sum_nn^{-1/2}=\infty $$ so $f_0=1$.

2. $2\text{-D}$ case (考虑组合恒等式或转 $45^\circ$): $$ \P[X_{2n}=(0,0)]=16^{-n}\binom{2n}{n}^2=\frac{1}{\pi n}\left(1+\Omicron(n^{-1})\right)\Longrightarrow\E[N_{(0,0)}]=\infty $$ so $f_{(0,0)}=1$.

3. For any $(x,y)$, it is also reached almost surely, because $\P[(0,0)\to(x,y)]\ne 0\Longrightarrow\E[N_{(0,0),(x,y)}]=\infty\Longrightarrow f_{(0,0),(x,y)}=1$.

4. $\ge 3\text{-D}$ case: approximately $\E[N_{(0,0,0)}]\sim\sum_nn^{-3/2}<\infty$, so we expect that it is not recurrent. Accurately, consider $$ \P[X_{2n}=\b 0]=[x_1^0\cdots x_k^0]\left(\frac{x_1+x_1^{-1}+\cdots+x_k+x_k^{-1}}{2k}\right)^{2n} $$ to get something like $[x^0]P(x)$, we can consider $\frac{1}{2\pi}\int_0^{2\pi}P(\e^{\i\theta})\d\theta$. So $$ \P[X_{2n}=\b 0]=\frac{1}{(2\pi)^k}\int_{[0,2\pi]^k}\left(\frac{\sum_{i=1}^k\cos x_k}{k}\right)^{2n}\d x $$ Notice that $2n+1$ does not contribute to the result, so we can also have $$ \E[N_{\b 0}]=\frac{k}{(2\pi)^k}\int_{[0,2\pi]}\left(k-\sum_{i=1}^k\cos x_k\right)^{-1} $$ For $k=3$, it's called Watson integral, and the result is $\approx 1.516$, leading to $f_{(0,0,0)}\approx 0.34$.

$$\r(\mat{P-I&\b 1})=m.$$ Proof. We need to how that $\operatorname{Nul}\mat{P-I&\b 1}=\span{\mat{1&\cdots&1&0}^\top}$. If there\'s another vector $\mat{\b x&\alpha}^\top$, then $$ \forall i,\b x_i=\sum_{j}P_{i,j}\b x_j+\alpha $$ and $\sum\b x_i=0$ (so that $\mat{\b x&\alpha}\perp\mat{1&\cdots&1&0}$), thus $\b x_i$ are not all the same. By irreducibility, 存在一个 $\b x_i\ge$ 它所有出边且有 $>$ 的, so $\alpha>0$; also 存在一个 $\b x_i\le$ 它所有出边且有 $<$ 的, so $\alpha<0$. Contradiction.

$\exists$ unique distribution $\b\pi$ s.t. $\b\pi P=\b\pi$. $\b\pi=\lim_{t\to\infty}\b a(t)$, here $\b a(t)=$ average of $\b p(0)\sim\b p(t-1)$. Proof. Let $\b b(t)=\b a(t)P-\b a(t)$. On one hand, $$ \b b(t)=\frac1t\left(\sum_{i=0}^{t-1}\b a(i)P-\sum_{i=0}^{t-1}\b a(i)\right)=\frac1t\left(\sum_{i=1}^{t}\b a(i)-\sum_{i=0}^{t-1}\b a(i)\right)=\frac1t(\b a(t)-\b a(0))\Longrightarrow|\b b(t)|\le\frac{2}{t} $$ On the other hand, let $B=\mat{P-I&\b 1}$, and $\b x_1$ denote $\b x$ removing the first column, taking limit on both side, $$ \b a(t)B_1=\mat{(\b a(t)P-\b a(t))_1&1}=\mat{\b b(t)_1&1}\Longrightarrow\lim_{t\to\infty}\b a(t)B_1=\mat{0&\cdots&0&1}\Longrightarrow\lim_{t\to\infty}\b a(t)=B_1^{-1}\mat{0&\cdots&0&1} $$ Uniqueness is from $\r(P-I)=m-1$.

For SCC, if $\b\pi$ satisfies $\b\pi_xp_{x,y}=\b\pi_yp_{y,x}$ for every edge and $\sum_i\b\pi_i=0$, then $\b\pi$ is the stationary distribution.
注意这里加强了条件，所以这样的向量不总是存在。如果稳态分布满足该条件，则称它为 reversible. $P$ 对称一定是 reversible 的。

$$ \|\b p-\b q\|_1=2\sum(p_i-q_i)^+=2\sum(q_i-p_i)^+ $$

Intuition: 找到图的一个割，使得两部分之间以低概率互通。Conductance: $$ \boxed{\Phi(S)=\frac{\sum_{x\in S,y\notin S}\pi_xp_{x,y}}{\min\left(\pi(S),\pi(\overline S)\right)},\Phi=\min_{\varnothing\subset S\subset V}\Phi(S)} $$ $$ \boxed{\Theta\left(\frac{1}{\Phi}\right)\le\tau(\eps)\le\Theta\left(\frac{-\ln\min\pi}{\Phi^2\eps^3}\right)} $$ Proof. WLOG assume $\pi(S)\le1/2$, then we can write $\Phi(S)$ as $$ \Phi(S)=\sum_{x\in S}\frac{\pi_x}{\pi(S)}\sum_{y\notin S}p_{x,y} $$ For the lower bound, consider starting in $S$, and each time with $\P=\sum_{x\in S,y\notin S}p_{x,y}\quad(*)$ we get to $\overline{S}$ so by union bound, $\P[\text{from }S\text{ to }\overline{S}\text{ in }t]\le t\cdot(*)$, and under the condition that $X_0\in S$ (we can do this since $\b p(0)$ is arbitrary), $\P[\text{stays in }S\text{ in }t\text{ steps}\mid X_0\in S]=\Phi(S)$. thus $\|\b a(t)-\b\pi\|_1\ge1-t\Phi(S)-\pi(S)\ge1/2-t\Phi(S)$. For $\eps=1/4$, $t$ need to be $\ge 1/4\Phi(S)$.

For the upper bound:

1. Let $\tau=-C(\ln\min\pi)/\Phi^2\eps^3$. Denote $a_i=\b a(t)_i$, $v_i=a_i/\pi_i$ (multiplicative error) and sort $v_i$s in decreasing order.

2. Now $\|\b a(t)-\b\pi\|_1=2\sum_{i\le i_0}(v_i-1)\pi_i=2\sum_{i>i_0}(1-v_i)\pi_i$, where $i_0$ is the split point between $\pi_i>1$ and $<1$.

3. $>i_0$ 的再大也大不过 $2\sum_{i>i_0}\pi_i$，如果它 $\le\eps/2$ 就完事了。

4. 否则将 $\le i_0$ 的部分划分连续段 $G_1\sim G_?$。令 $\gamma=\sum\pi$（前缀和），$G_1=[1]$，每次从上次的末尾加一（记为 $k$）往后找到最后一个 $$ \sum_{j=k+1}^l\pi_j\le\frac{\eps\Phi\gamma_{k}}4 $$ 的 $l$，$G_{\text{next}}=[k\sim l]$。

   1. 已知 $\gamma_{l+1}-\gamma_{k}>\eps\Phi\gamma_{k}/4\Longrightarrow \gamma_{l+1}>(1+\eps\Phi/4)\gamma_{k}$，至少每次跳跃都乘了这个倍数，所以至多跳 $\log_{1+\eps\Phi/4}\pi_1\le-4\ln\pi_1/\eps\Phi$ 次。

   2. 现在我们只需 bound 每次的贡献即可。此处先得修改一下求和的顺序。令 $u_i$ 为 $G_i$ 开头的 $v$。 $$ \sum_{i\le i_0}(v_i-1)\pi_i\le\sum_i(u_i-1)\sum_{j\in G_i}\pi_j=\sum_i\pi(G_1\sim G_i)\cdot(u_i-u_{i+1}) $$ 其中 $u_{r+1}=1$。我们将证明求和中的每一项都 $\le 8/\eps\Phi\tau$。

   3. 对于 $G_r=[k\sim l]$：

      1. By the proof of fundamental theorem of Markov chain, $$ \begin{align*} \frac2\tau&\ge\left\lVert\b a-\b aP\right\rVert_1\\ &\ge\sum_{i=1}^k(\b a-\b aP)_i\\ &=\sum_{i\le k}\sum_{j>k}(p_{i,j}a_i-p_{j,i}a_j)&(\text{imagine as flow})\\ &=\sum_{i\le k}\sum_{j>k}(p_{i,j}\pi_iv_i-p_{j,i}\pi_jv_j)\\ &=\sum_{i\le k}\sum_{j>k}p_{j,i}\pi_j(v_i-v_j)\\ &\ge\sum_{i\le k}\sum_{j>l}p_{j,i}\pi_j(v_i-v_j)\\ &\ge(v_k-v_{l+1})\sum_{i\le k}\sum_{j>l}p_{j,i}\pi_j\\ &=(u_r-u_{r+1})\sum_{i\le k}\sum_{j>l}p_{j,i}\pi_j \end{align*} $$

      2. Dealing with the stupid $\sum\sum$: $$ \begin{align*} \sum_{i\le k}\sum_{j>l}p_{j,i}\pi_j&=\sum_{i\le k}\sum_{j>k}p_{j,i}\pi_j-\sum_{i\le k}\sum_{k<j\le l}p_{j,i}\pi_j\\ &\ge\sum_{i\le k}\sum_{j>k}p_{j,i}\pi_j-\sum_{j=k+1}^l\pi_j\\ &\ge\Phi\cdot\min(\pi(1\sim k),\pi(k+1\sim n))-\frac{\eps\Phi\gamma_k}4\\ &\ge\Phi\cdot\min(\gamma_k,\pi(i_0+1\sim n))-\frac{\eps\Phi\gamma_k}4\\ &\ge\Phi\cdot\gamma_k\cdot\pi(i_0+1\sim n)-\frac{\eps\Phi\gamma_k}4\\ &\ge\frac{\eps\Phi\gamma_k}4&\left(\text{by }\sum_{i\ge i_0}\pi_i>\frac\eps4\right) \end{align*} $$

      3. Dividing: $$ u_r-u_{r+1}\le\frac{8}{\eps\Phi\gamma_k\tau} $$

         $$ \sum_i\pi(G_1\sim G_i)\cdot(u_i-u_{i+1})\le-\frac{4\ln\pi_1}{\eps\Phi}\cdot\frac{8}{\eps\Phi\gamma_k\tau}\le\frac{32\eps}{C} $$

5. Yippee!

6. BTW this proof is as stupid as shit.

For irreducible, aperiodic, reversible Markov chain, let $\lambda_2$ be the second largest eigenvalue norm of the transition matrix, for mixing time of $\b p(t)$: $$ \boxed{\left(\frac{1}{1-\lambda_2}-1\right)\ln\frac1\eps\le\tau(\eps)\le\frac{1}{1-\lambda_2}\ln\frac{1}{\eps\pi_{\min}}} $$ Remark. 如果 $P$ 是对称的，直接设出谱分解，然后 $1$ 范数和 $2$ 范数之间来回放缩即可，证明较简单（期末考了！）。

Proof. WLOG assume $\lambda_2=$ actual $\lambda_2$. Let $D=\diag(\pi)$. Although $P$ is not symmetric, $A=D^{1/2}PD^{-1/2}$ is symmetric by reversibility. So we have spectral decomposition $$ A=\sum\lambda_i\b v_i\b v_i^\top\Longrightarrow P^t=D^{-1/2}\sum\lambda_i^t\b v_i\b v_i^\top D^{1/2} $$ For some (row vector) $\b p_0$, $$ \b p_0P^t-\b\pi=\b p_0D^{-1/2}\sum\lambda_i^t\b v_i\b v_i^\top D^{1/2}-\b 1^\top D $$ For $i=1$, $\lambda_1=1$, $\b v_1=D^{1/2}\b 1$, so $$ \b p_0D^{-1/2}\b v_1\b v_1^\top D^{1/2}=\b p_0\b 1\b 1^\top D=\b 1^\top D $$ so $$ \b p_0P^t-\b\pi=\b p_0D^{-1/2}\sum_{i\ge 2}\lambda_i^t\b v_i\b v_i^\top D^{1/2} $$ 我们可以把 $|\b p_0P^t-\b\pi|_1$ 想象成一个高维凸多面体上离一个点的距离，最远的一定是顶点，因此只考虑 $\b p_0=\b e_x^\top$。 $$ \begin{align*} \left\lvert\left(\b e_x^\top D^{-1/2}\sum_{i\ge 2}\lambda_i^t\b v_i\b v_i^\top D^{1/2}\right)_y\right\rvert&=\left|\b e_x^\top D^{-1/2}\sum_{i\ge 2}\lambda_i^t\b v_i\b v_i^\top D^{1/2}\b e_y\right|\\ &\le\sqrt{\frac{\pi_y}{\pi_x}}\sum_{i\ge 2}|\lambda_i|^t|v_{i,x}||v_{i,y}|\\ &\le\sqrt{\frac{\pi_y}{\pi_x}}\lambda_2^t\sum_{i\ge 2}|v_{i,x}||v_{i,y}|\\ &\le\sqrt{\frac{\pi_y}{\pi_x}}\lambda_2^t\sqrt{\left(\sum_{i\ge 2}v_{i,x}^2\right)\left(\sum_{i\ge 2}v_{i,y}^2\right)}\\ &\le\sqrt{\frac{\pi_y}{\pi_x}}\lambda_2^t \end{align*} $$ 这里最后一个不等式是因为 $\set{\b v_i}$ 是一组单位正交基。现在 $$ \|\b p_0P^t-\b\pi\|_1\le\frac{\lambda_2^t}{\sqrt{\pi_x}}\sum\sqrt{\pi_y}\le\frac{\lambda_2^t}{\sqrt{\pi_x}}\sqrt{n} $$ 因此 $$ \max\lVert\b p_0P^t-\b\pi\rVert_1\le\lambda_2^t\cdot\sqrt n\cdot\max\frac{1}{\sqrt{\pi_x}}\le\frac{\lambda_2^t}{\pi_{\min}} $$ 所以可以要求 $t\ge\log_{\lambda_2}(\eps\pi_{\min})=\ln(\eps\pi_{\min})/\ln\lambda_2$，这里 $$ \ln\lambda_2=\ln(1-(1-\lambda_2))\le-\frac{1}{1-\lambda_2} $$

下界（不要问我为什么突然开始右乘，我也不知道）：考虑 $P$ 的 $\lambda_2$ 对应的右特征向量 $\b v_2$（用于硬凑 $\|\b p_0P^t-\b\pi\|_1$ 形式） $$ \lambda_2^t|(\b v_2)_x|=|(P^t\b v_2)_x|=\left|\sum_yP_{x,y}^t(\b v_2)_y\right|=\left|\sum_y(P_{x,y}^t-\pi_y)(\b v_2)_y\right|\le\|\b v_2\|_1\sum_y|P_{x,y}^t-\pi_y| $$ 其中 $\b\pi\cdot\b v_2=0$ 是因为 $P\b v_2=\lambda_2\b v_2$，而 $\b\pi^\top\lambda_2\b v_2=\b\pi^\top P\b v_2=\b\pi^\top\b v_2$。现在注意到 $$ \lVert\b e_xP^t-\b\pi\rVert_1=\sum_y|P_{x,y}^t-\pi_y| $$ 取 $x=\operatorname{argmax}|(\b v_2)_x|$，得到 $$ \eps\ge\lambda_2^{\tau(\eps)}\Longrightarrow\tau(\eps)\ge\log_{\lambda_2}\eps=\frac{\ln(1/\eps)}{\ln(1/\lambda_2)}\ge\frac{\ln(1/\eps)}{1/\lambda_2-1}=\left(\frac{1}{1-\lambda_2}-1\right)\ln\frac1\eps $$

$$ \frac{\Phi^2}2\le1-\lambda_2\le2\Phi $$

$$ \left(1-\frac{1}{2\Phi}\right)\ln\frac{1}{\eps}\le\tau(\eps)\le\frac{2}{\Phi^2}\ln{\frac{1}{\pi_{\min}\eps}} $$