第十一周作业
1.
a.
令$Z=\langle x,y \rangle = \sum\limits_{i=1}^{d}{x_i y_i}$，则$E\left[ Z \right] = E\left[ \sum\limits_{i=1}^{d}{x_i y_i} \right] = \sum\limits_{i=1}^{d}{E\left[x_i y_i\right]}$
由于$x, y$独立且均匀取值，所以$E\left[ Z \right]=0$
根据霍夫丁不等式，有$\text{Pr}\left[ Z-E\left[Z\right] \geq \varepsilon d \right] = \text{Pr}\left[ \langle x,y \rangle \geq \varepsilon d \right] \leq 2\exp\left(-\dfrac{2 \varepsilon^2 d^2}{4d}\right) = 2\exp\left(-\dfrac{\varepsilon^2 d}{2}\right)<2\exp\left(-\dfrac{\varepsilon^2 d}{6}\right)$
得证
b.
由a得：$\text{Pr}\left[ \langle x,y \rangle \geq \varepsilon \right] \leq 2\exp{\left( -\varepsilon^2d/6 \right)}$。
那么$\binom{N}{2}$对的内积都小于$\varepsilon$的概率为
当$c\leq\frac1{12}-\frac{\ln2}{2\varepsilon^2d}$时即可，且$\frac1{12}-\frac{\ln2}{2\varepsilon^2d}$关于$d>0$单调递增且有大于$0$的时候，此时$d_0$取比零点大的值就行。
2.
要证明$S^TS$大概率是近似单位阵，需要它的对角线元素近似为$1$且非对角线元素近似为$0$。
对角线元素$\left(S^TS\right)_{ii}=\sum\limits_{k=1}^{K}{S_{ki}^2}$，由于$S_{ki}$从$\left\{ -\frac{1}{\sqrt{K}}, \frac{1}{\sqrt{K}} \right\}$中均匀抽取，所以$S_{ki}^2=\frac{1}{K}$，即$\left(S^TS\right)_{ii}=1$。
非对角线元素$(S^T S)_{ij} = \sum\limits_{k=1}^{K}{S_{ki} S_{kj}}$，同样，每个$S_{ki}$和$S_{kj}$的取值都是$-\frac{1}{\sqrt{K}}$或$\frac{1}{\sqrt{K}}$、概率都是$\frac 12$
因此，$E\left[ S_{ki} S_{kj} \right]=\left( \frac{1}{\sqrt{K}} \cdot \frac{1}{\sqrt{K}} + \frac{1}{\sqrt{K}} \cdot -\frac{1}{\sqrt{K}} + -\frac{1}{\sqrt{K}} \cdot \frac{1}{\sqrt{K}} + -\frac{1}{\sqrt{K}} \cdot -\frac{1}{\sqrt{K}} \right) \cdot \frac{1}{4} = 0$
且根据霍夫丁不等式，$(S^T S)_{ij}$的值不在$\varepsilon \sqrt{K}$范围内的概率
当$K$足够大时，$K^2\geq \frac{2\log{\left(2/\delta\right)}}{\varepsilon^2}$时，概率$\leq \delta$，大概率为近似单位阵。
3.
a.
定义$Y_t=2^{X_t}-1$，则$N=Y_n$，$2^{-X_t}=\frac{1}{Y_t+1}$
$E[Y_{t+1}|Y_t]=E[2^{X_{t+1}}-1|2^{X_t}-1=Y_t]$，由于$X_{t+1}$以$2^{-X_t}$概率增加$1$，所以
$E[Y_{t+1}|Y_t]=(2^{X_{t}+1}-1)\cdot2^{-X_t} + (2^{X_{t}}-1)\cdot(1-2^{-X_t})$
其中，$(2^{X_{t}+1}-1)\cdot2^{-X_t}=\frac{2Y_t+1}{Y_t+1}=2-\frac{1}{Y_t+1}$，$(2^{X_{t}}-1)\cdot(1-2^{-X_t})=Y_t (1-\frac{1}{Y_t+1})=Y_t-\frac{Y_t}{Y_t+1}$
所以，$E[Y_{t+1}|Y_t]=1+Y_t$
由于$Y_0=0$，所以$E[N]=E[Y_n]=n$
同理，$E[Y_{t+1}^2|Y_t]=Y_t^2+4Y_t+1$，即$E[Y_{t+1}^2]=E[Y_t^2]+4E[Y_t]+1=E[Y_t^2]+4t+1$
计算得$E[n]=E[Y_n]=E[Y_0^2]+4\sum\limits_{t=0}^{n-1}{t}+n=2n^2-n$
因此$D[N]=E[N^2]-\left(E\left[N\right]\right)^2=n^2-n$ ？
b.
$E[\hat{N}]=n$，$D[\hat{N}]=\frac1{k^2}\sum\limits_{i=1}^{k}{D[N_i]}=\frac{n(n-1)}{2k}$
需要计算$\text{Pr}\left[ \left|\hat{N}-E[\hat{N}] \right| > \varepsilon n\right]$，根据切比雪夫不等式，$\text{Pr}\left[ \left| \hat{N}-E[\hat{N}] \right| > \varepsilon n \right] \leq \frac{D[\hat{N}]}{\varepsilon^2 n^2}=\frac{n-1}{2k\varepsilon^2 n}$
当$n$较大时，$\dfrac{n}{n-1}\rightarrow 1$，因此$\text{Pr}\left[ \left| \hat{N}-E[\hat{N}] \right| > \varepsilon n \right] \leq \frac{1}{2\varepsilon^2 k}$
得证
