We have seen reservoir sampling and the related weighted sampling technique to obtain independent samples from a stream without the algorithm knowing the length of the stream. We now discuss a technique to sample from a stream $\sigma =a_1,a_2,\dots ,a_m$$\sigma =a_1,a_2,\dots ,a_m$sigma=a_(1),a_(2),dots,a_(m)\sigma=a_{1}, a_{2}, \ldots, a_{m} where the tokens $a_j$$a_j$a_(j)a_{j} are integers from $[n]$$[n]$[n][n] and we wish to estimate a function

where $f_i$$f_i$f_(i)f_{i} is the frequency of $i$$i$ii and $g$$g$gg is a real-valued function such that $g(0)=0$$g(0)=0$g(0)=0g(0)=0. A natural example is to estimate frequency moments $F_k=\sum _{i\in [n]}{f}_i^k$$F_k=\sum _{i\in [n]} f_i^k$F_(k)=sum_(i in[n])f_(i)^(k)F_{k}=\sum_{i \in[n]} f_{i}^{k}; here we have $g(x)=x^k$$g(x)=x^k$g(x)=x^(k)g(x)=x^{k}, a convex function for $k\ge 1$$k\ge 1$k >= 1k \geq 1. Another example is the empirical entropy of $\sigma$$\sigma$sigma\sigma defined as $\sum _{i\in [n]}{p}_i\log p_i$$\sum _{i\in [n]} p_i\log p_i$sum_(i in[n])p_(i)log p_(i)\sum_{i \in[n]} p_{i} \log p_{i} where $p_i=\frac{f_i}{m}$$p_i=\frac{f_i}{m}$p_(i)=(f_(i))/(m)p_{i}=\frac{f_{i}}{m} is the empirical probability of $i$$i$ii; here $g(x)=x\log x$$g(x)=x\log x$g(x)=x log xg(x)=x \log x.^[1]

AMS sampling from the famous paper [?] gives an unbiased estimator for $g(\sigma )$$g(\sigma )$g(sigma)g(\sigma). The estimator is based on a random variable $Y$$Y$YY defined as follows. Let $J$$J$JJ be a uniformly random sample from $[m]$$[m]$[m][m]. Let $R=|\{j|a_j=a_J,J\le j\le m\}|$$R=|\{j|a_j=a_J,J\le j\le m\}|$R=|{j|a_(j)=a_(J),J <= j <= m}|R=|\{j | a_{j}=a_{J}, J \leq j \leq m\}|. That is, $R$$R$RR is the count of the number of tokens after $J$$J$JJ that are for the same coordinate. Then, let $Y$$Y$YY the estimate defined as:

The lemma below shows that $Y$$Y$YY is an unbiased estimator of $g(\sigma )$$g(\sigma )$g(sigma)g(\sigma).

Proof: The probability that $a_J=i$$a_J=i$a_(J)=ia_{J}=i is exactly $f_i/m$$f_i/m$f_(i)//mf_{i} / m since $J$$J$JJ is a uniform sample. Moreover if $a_J=i$$a_J=i$a_(J)=ia_{J}=i then $R$$R$RR is distributed as a uniform random variable over $[f_i]$$[f_i]$[f_(i)][f_{i}].

One can estimate $Y$$Y$YY using small space in the streaming setting via the reservoir sampling idea for generating a uniform sample. The algorithm is given below; the count $R$$R$RR gets reset whenever a new sample is picked.

To obtain a $(ϵ,\delta )$$(ϵ,\delta )$(epsilon,delta)(\epsilon, \delta)-approximation via the estimator $Y$$Y$YY we need to estimate $\mathrm{Var}[Y]$$\mathrm{Var}[Y]$Var[Y]\operatorname{Var}[Y] and apply standard tools. We do this for frequency moments now.

We now apply the AMS sampling to estimate $F_k$$F_k$F_(k)F_{k} the $k$$k$kk'th frequency moment for $k\ge 1$$k\ge 1$k >= 1k \geq 1. We have already seen that $Y$$Y$YY is an exact statistication estimator for $F_k$$F_k$F_(k)F_{k} when we set $g(x)=x^k$$g(x)=x^k$g(x)=x^(k)g(x)=x^{k}. We now estimate the variance of $Y$$Y$YY in this setting.

Lemma 2 When $g(x)=x^k$$g(x)=x^k$g(x)=x^(k)g(x)=x^{k} and $k\ge 1$$k\ge 1$k >= 1k \geq 1,

We now use convexity of the function $x^k$$x^k$x^(k)x^{k} for $k\ge 1$$k\ge 1$k >= 1k \geq 1 to prove the second part. Note that $\underset{i}{max}{f}_i=F_{\mathrm{\infty }}$$\underset{i}{max} f_i=F_{\mathrm{\infty }}$max_(i)f_(i)=F_(oo)\max _{i} f_{i}=F_{\infty}.

Using the preceding inequality, and the inequality $(\sum _{i=1}^n{x}_i)/n\le ((\sum _{i=1}^n{x}_i^k)/n{)}^{\frac{1}{k}}$$(\sum _{i=1}^n x_i)/n\le ((\sum _{i=1}^n x_i^k)/n{)}^{\frac{1}{k}}$(sum_(i=1)^(n)x_(i))//n <= ((sum_(i=1)^(n)x_(i)^(k))//n)^((1)/(k))(\sum_{i=1}^{n} x_{i}) / n \leq((\sum_{i=1}^{n} x_{i}^{k}) / n)^{\frac{1}{k}} for all $k\ge 1$$k\ge 1$k >= 1k \geq 1 (due to the convexity of the function $g(x)=x^k)$$g(x)=x^k)$g(x)=x^(k))g(x)=x^{k}), we obtain that

Thus we have $\mathbf{E}[Y]=F_k$$\mathbf{E}[Y]=F_k$E[Y]=F_(k)\mathbf{E}[Y]=F_{k} and $\mathbf{V}\mathbf{a}\mathbf{r}[Y]\le k{n}^{1-1/k}{F}_k^2$$\mathbf{V}\mathbf{a}\mathbf{r}[Y]\le k{n}^{1-1/k}{F}_k^2$Var[Y] <= kn^(1-1//k)F_(k)^(2)\mathbf{Var}[Y] \leq k n^{1-1 / k} F_{k}^{2}. We now apply the trick of reducing the variance and then the median trick to obtain a high-probability bound. If we take $h$$h$hh independent estimators for $Y$$Y$YY and take their average the variance goes down by a factor of $h$$h$hh. We let $h=$$h=$h=h= $\frac{c}{{ϵ}^2}k{n}^{1-1/k}$$\frac{c}{{ϵ}^2}k{n}^{1-1/k}$(c)/(epsilon^(2))kn^(1-1//k)\frac{c}{\epsilon^{2}} k n^{1-1 / k} for some fixed constant $c$$c$cc. Let $Y^{\mathrm{\prime }}$$Y^{\mathrm{\prime }}$Y^(')Y^{\prime} be the resulting averaged estimator. We have $\mathbf{E}[Y^{\mathrm{\prime }}]=$$\mathbf{E}[Y^{\mathrm{\prime }}]=$E[Y^(')]=\mathbf{E}[Y^{\prime}]= $F_k$$F_k$F_(k)F_{k} and $\mathbf{V}\mathbf{a}\mathbf{r}[Y^{\mathrm{\prime }}]\le \mathbf{V}\mathbf{a}\mathbf{r}[Y]/h\le \frac{{ϵ}^2}{c}{F}_k^2$$\mathbf{V}\mathbf{a}\mathbf{r}[Y^{\mathrm{\prime }}]\le \mathbf{V}\mathbf{a}\mathbf{r}[Y]/h\le \frac{{ϵ}^2}{c}{F}_k^2$Var[Y^(')] <= Var[Y]//h <= (epsilon^(2))/(c)F_(k)^(2)\mathbf{Var}[Y^{\prime}] \leq \mathbf{Var}[Y] / h \leq \frac{\epsilon^{2}}{c} F_{k}^{2}. Now, using Chebyshev, we have

We can choose $c=3$$c=3$c=3c=3 to obtain a $(ϵ,1/3)$$(ϵ,1/3)$(epsilon,1//3)(\epsilon, 1 / 3)-approximation. By using the median trick with $\mathrm{\Theta }(\log \frac{1}{\delta })$$\mathrm{\Theta }(\log \frac{1}{\delta })$Theta(log (1)/(delta))\Theta(\log \frac{1}{\delta}) independent estimators we can obtain a $(ϵ,\delta )$$(ϵ,\delta )$(epsilon,delta)(\epsilon, \delta)-approximation. The overall number of estimators we run independently is $O(\log \frac{1}{\delta }\cdot \frac{1}{{ϵ}^2}\cdot n^{1-1/k})$$O(\log \frac{1}{\delta }\cdot \frac{1}{{ϵ}^2}\cdot n^{1-1/k})$O(log (1)/(delta)*(1)/(epsilon^(2))*n^(1-1//k))O(\log \frac{1}{\delta} \cdot \frac{1}{\epsilon^{2}} \cdot n^{1-1 / k}). Each estimator requires $O(\log n+\log m)$$O(\log n+\log m)$O(log n+log m)O(\log n+\log m) space since we keep track of one index from $[m]$$[m]$[m][m], one count from $[m]$$[m]$[m][m], and one item from $[n]$$[n]$[n][n]. Thus the space usage to obtain a $(ϵ,\delta )$$(ϵ,\delta )$(epsilon,delta)(\epsilon, \delta)-approximation is $O(\log \frac{1}{\delta }\cdot \frac{1}{{ϵ}^2}\cdot n^{1-1/k}\cdot (\log m+\log n))$$O(\log \frac{1}{\delta }\cdot \frac{1}{{ϵ}^2}\cdot n^{1-1/k}\cdot (\log m+\log n))$O(log (1)/(delta)*(1)/(epsilon^(2))*n^(1-1//k)*(log m+log n))O(\log \frac{1}{\delta} \cdot \frac{1}{\epsilon^{2}} \cdot n^{1-1 / k} \cdot(\log m+\log n)). The time to process each stream element is also the same.

The space complexity of $\tilde{O}(n^{1-1/k})$$\tilde{O}(n^{1-1/k})$tilde(O)(n^(1-1//k))\tilde{O}(n^{1-1 / k}) is not optimal for estimating $F_k$$F_k$F_(k)F_{k}. One can achieve $\tilde{O}(n^{1-2/k})$$\tilde{O}(n^{1-2/k})$tilde(O)(n^(1-2//k))\tilde{O}(n^{1-2 / k}) which is optimal for $k>2$$k>2$k > 2k>2 and one can in fact achieve poly-logarithmic space for $1\le k\le 2$$1\le k\le 2$1 <= k <= 21 \leq k \leq 2. We will see these results later in the course.

Bibliographic Notes: See Chapter 1 of the draft book by McGregor and Muthukrishnan; see the application of AMS sampling for estimating the entropy. See Chapter 5 of Amit Chakrabarti for the special case of frequency moments explained in detail. In particular he states a clean lemma that bundles the variance reduction technique and the median trick.