hw04 ans

Problem 1

(a) H(X) 和 H(Y)

$H(X)=-0.6{\log }_{2}0.6-0.4{\log }_{2}0.4\approx 0.971\text{ bits}$

$H(Y)=-0.7{\log }_{2}0.7-0.3{\log }_{2}0.3\approx 0.881\text{ bits}$

(b) H(X,Y) 的范围

下界： $H(X,Y)\ge \max (H(X),H(Y))=0.971$ bits

取等条件：X 是 Y 的函数（或反之）。由于 Pr[X=1]=0.6, Pr[Y=1]=0.7，X 不能是 Y 的函数，但可以令 Y=1 尽量蕴含 X=1。最紧的coupling为：

$\mathrm{Pr}[X=1,Y=1]=0.6,\mathrm{Pr}[X=0,Y=1]=0.1,\mathrm{Pr}[X=0,Y=0]=0.3$

此时 X 是 (X,Y) 的函数，$H(X,Y)=H(Y)=0.881$

实际上下界为 $\max (H(X),H(Y))=H(X)=0.971$ bits，通过令 $X\to Y$ 的确定函数实现（令 Pr[X=1,Y=1]=0.6, Pr[X=0,Y=0]=0.3, Pr[X=0,Y=1]=0.1），此时 H(X,Y)=H(Y)=0.881。

上界： X, Y 独立时取最大值

$H(X,Y)\le H(X)+H(Y)=0.971+0.881=1.852\text{ bits}$

结论： $0.881\le H(X,Y)\le 1.852\text{ bits}$

• 最小值：X 是 Y 的函数（令 Pr[X=1,Y=1]=0.6, Pr[X=0,Y=1]=0.1, Pr[X=0,Y=0]=0.3）
• 最大值：X 与 Y 独立

(c) X, Y 独立时

$H(X,Y)=H(X)+H(Y)=0.971+0.881=1.852\text{ bits}$

$H(X|Y)=H(X,Y)-H(Y)=1.852-0.881=0.971\text{ bits}=H(X)$

---

Problem 2

证明 $A(n)=K\log n$

$A(1)=0$。令 $m=n=1$：$A(1)=A(1)+A(1)\Rightarrow A(1)=0$。

对有理数 $r=p/q$，由完全可加性： $A(n^p)=pA(n),A(n^q)=qA(n)$

对任意正整数 $m,n$ 和正整数 $r,s$，若 $n^r\le m^s$，由单调性 $A(n^r)\le A(m^s)$，即 $rA(n)\le sA(m)$。

固定 $m=2$，令 $K=A(2)/\log 2$。对任意 $n\ge 2$ 及任意有理数 $p/q$ 满足 $p/q\le \log n/\log 2$： $n^q\ge 2^p\Rightarrow qA(n)\ge pA(2)\Rightarrow \frac{A(n)}{\log n}\ge \frac{A(2)}{\log 2}=K$

类似可得另一侧，故 $A(n)=K\log n$。

---

Problem 3

证明多项式系数公式

$\left(\genfrac{}{}{0ex}{}{N}{p_{1}N,\dots ,p_{n}N}\right)=\frac{N!}{{\prod }_{i=1}^n(p_{i}N)!}$

利用 Stirling 近似： ${\log }_2(m!)=m{\log }_{2}m-m{\log }_{2}e+O(\log m)$

${\log }_2\left(\genfrac{}{}{0ex}{}{N}{\dots }\right)={\log }_2(N!)-{\sum }_{i=1}^n{\log }_2((p_{i}N)!)$

$=N{\log }_{2}N-{\sum }_{i=1}^n{p}_{i}N{\log }_2(p_{i}N)+O(\log N)$

$=N{\log }_{2}N-N{\sum }_{i=1}^n{p}_i({\log }_{2}N+{\log }_2{p}_i)+O(\log N)$

$=N{\log }_{2}N-N{\log }_{2}N\underset{=1}{\underbrace{\sum p_i}}-N\sum p_i{\log }_2{p}_i+O(\log N)$

$=-N{\sum }_{i=1}^n{p}_i{\log }_2{p}_i+O(\log N)$

$=N\cdot H(p_1,\dots ,p_n)+o_{p_1,\dots ,p_n}(N)$

因此：

$\left(\genfrac{}{}{0ex}{}{N}{p_{1}N,\dots ,p_{n}N}\right)=2^{N(H(p_1,\dots ,p_n)+o_{p_1,\dots ,p_n}(1))}$

其中余项 $o_{p_1,\dots ,p_n}(1)\to 0$（$N\to \infty$）。

| method | keep_ratio | layer | e2e_ms | ttft_ms | tps | mem_GB | vis_before | vis_after |

|--------|-----------|-------|--------|---------|------|--------|------------|-----------|

| fastv | 1.00 | 3 | 3329.5 | 5.2 | 18.0 | 4.283 | 64 | 64 |

| fastv | 0.75 | 3 | 3336.6 | 4.9 | 17.7 | 4.283 | 64 | 48 |

| fastv | 0.50 | 3 | 3046.9 | 4.6 | 17.7 | 4.283 | 64 | 32 |

| fastv | 0.25 | 3 | 1746.6 | 4.6 | 17.8 | 4.283 | 64 | 16 |

| fastv | 0.10 | 3 | 1777.8 | 4.7 | 17.5 | 4.283 | 64 | 6 |