第八周作业
1.$n$个数$a_n$串行写入一个固定的内存单元，只有比内存中数大才写入，内存初始为$0$
(a). 设$a$是一个随机的$1$到$n$的排列，求$f$中不同值数量的期望
先不考虑排列开头元素和$0$的比较。对于任意一个$1$到$n$的排列$P_i=\{p_1, p_2,\cdots,p_n\},i\in\{1,2,\cdots,n!\}$，会发生$w_i$次写入，总有一个颠倒的排列$P_{n!-i}=\{p_{n},p_{n-1},\cdots,p_1\}$与之对应，发生$w_{n!-i}=n-w_i$次写入。因此，这部分的期望写入次数为$\dfrac{1}{n!}\sum\limits_{i=1}^{n!}{w_i}=\dfrac{1}{n!}\sum\limits_{i=1}^{\frac{n!}{2}}{w_i+w_{n!-i}}=\dfrac{n}{2}$
加上开头一定写入的一次，所以期望为$\frac{n}{2}+1$次。
(b). 假设$a$中每个数互相独立且服从$[1,n]$的离散均匀分布（序列中可能出现重复的数），求$f$中不同值数量的期望。只需给出期望的确界，即求出$E=\Theta(g(n))$。
先不考虑排列开头元素和$0$的比较。由于随机分布，所以$P(a_i>a_{i-1})=\frac{1}{n}\sum\limits_{x=1}^{n}\frac{n-x}{n}=\frac{n^2-(1+2+\cdots+n)}{n^2}=\frac{n-1}{2n}$。加上开头必定写入的一次，那么$n$次的期望就是$1+n\cdot P(a_i>a_{i-1})=\frac{n+1}{2}$
2. 假设有$n$种不同的颜色，每种颜色分别有$1$个桶和$1$个球。现在让一个人蒙上眼睛后随机的将球放入桶里，并假定每个桶里只能放$1$个球。问最后桶和球的颜色匹配的数量的期望值是多少？
即错排问题。
设当$n$个球全放错时，方案为$D_n$。此时第$n$个球$a$有$n-1$个位置可以放，假设放在位置$b$上。那么要么球$b$放在$a$位置上，剩下$n-2$个球错排，贡献$D_{n-2}$种方案，要么放在$ab$以外的位置，相当于除$a$外的$n-1$个球进行错排，贡献$D_{n-1}$种方案。由此可得，$D_n=(n-1)(D_{n-1}+D_{n-2}), D_1=0,D_2=1,D_3=2$
那么刚好有$k$个球放在正确位置上的方案数就是
期望就是
3. Oblivious Routing on the Hypercube
算法
- 每个点$i$将数据包传输到一个随机点$R_i$
- $5d$轮后，将数据包从当前所在的点传输到$\pi_i$
Theorem 1：随机算法在$10d$轮内传输完成的概率$P_r\geq1-\frac2n$
Claim 2：假如$i\rightarrow R_i$和$j\rightarrow R_j$的路径存在公共路径，那么这样的公共路径最多只有一段。
- Claim 3：记$i\rightarrow R_i$的路径为$P_i$，和$P_i$存在公共路径的$P_j$的集合为$S_i$。则到达的时间最迟为$|P_i|+|S_i|$。
- 如果$S_i=\varnothing$，显然只要$|P_i|$的时间
- 我们希望将每次等待的时间分摊到最多一个$P_j\in S_i$，那么$i\rightarrow R_i$最多等待$|S_i|$的时间
- 根据以下方式定义$lag$：对于$P_i$中的第$k$条边$e_k$，在$t$时刻，位于$e_k$起点$w_{e_k}$的包$j$拥有$lag=t-k$。需要注意的是$lag$的定义都是基于$P_i$的，而不是基于$P_j$的。
- 当$t$时刻，包$i$在第个$k$点被包$j$阻塞时，向包$j$发送一个$t-k$的
token，那么包$i$发送的每个token的值都是唯一的（每次被阻塞，token的值+1） - 当$t$时刻，包$j$在第$k$个点被包$x$阻塞时，如果包有
token，则将这个token传给包$x$ - 包$x$在此之前一定没有
token，且同一时刻$t$，包$x$最多从一个包$j$处接受token - 每次包$i$交给包$j$一个新的
token时，包$j$一定没有token - 因此每个包做多接受1个
token，一共最多阻塞$|S_i|$次 - 总时间 $=$ 移动的时间 $+$ 阻塞的时间 $\leq |P_i|+|S_i|$
- Claim 4：$\text{Pr}\left[|S_i| \geq 4d\right]\leq e^{-2d}$
