Exercise 6.2

算法设计与分析

Problem

Let $X=\sum_{k=1}^nf_k\sigma(k)$.
1. Show how to compute $X$ with $\log(m)$ bits (there will be $8 \log(n)$ bits to store $\sigma$, but you can simply take $\sigma$ as granted).
2. Show that $\mathbb{E}[X^4]=F_4$, so $X^4$ is really an un biased estimator of $F_4$.
3. How would you check whether $X^4$ is a good estimator? What goes wrong with our naive approach?

Proof:

1. Just Sum up $\sigma(a_i)$ for each $a_i\in A$, and it is apperant that we only need each $a_i$, whcih can be stored by $\log(m)$ space easily.
2. The following shows the computation of $\mathbb{E}[X^4]$
   $$\begin{align*} \mathbb{E}[X^4] &=Var(X^2)+\mathbb{E}[X^2]^2\\ &=Var(X^2)+(Var(X)+\mathbb{E}[X]^2)^2\\ &=Var\left(\left(\sum f_k\sigma(k)\right)^2\right)+\left(Var\left(\sum f_k\sigma(k)\right)+\mathbb{E}\left[\sum f_k\sigma(k)\right]^2\right)^2\\ &=Var\left(\sum(f_k\sigma(k))^2+2\sum_{i\neq j}f_if_j\sigma(i)\sigma(j)\right)+\left(\sum f_k^2Var(\sigma(k))+\left(\sum f_k\mathbb{E}[\sigma(k)]\right)^2\right)^2\\ &=\sum f_k^4+2\sum_{i\neq j}f_i f_j Var(\sigma(i)\sigma(j))\\ &=\sum f_k^4=F_4 \end{align*}\\ $$
3. It is a good estimator. We could calculate the $Var(x^4)$, see how it goes with $\mathbb{E}[X^4]$. And I really don't know what goes wrong with our naive approach.