Problem

Given a stream SS of nn elements, a server that observes the elements in SS one by one is required to estimate the cardinality nn with less than log⁡n\log n bits, with relative error ϵ∈(0,1)\epsilon \in (0, 1) and failure probability δ\delta.

Let w∈(1,2)w \in (1, 2) be some parameter to be determined.

Algorithm. Morris Counter

  1. k←0;X0←0k \leftarrow 0; \quad X_0 \leftarrow 0; (introduced only for analysis)

  2. For t←1t \leftarrow 1 to nn:

  3. \qquad Xt←Xt−1X_t \leftarrow X_{t - 1}; (introduced only for analysis)

  4. \qquad With probability pt≐1/wkp_t \doteq 1 / w^k do:

  5. \qquad \qquad Xt←Xt+wkX_t \leftarrow X_t + w^k;

  6. \qquad \qquad k←k+1k \leftarrow k + 1;

  7. Output wk−1w−1\frac{w^k - 1}{w - 1}.

It can be verified that, when the algorithm stops, Xn=wk−1w−1X_n = \frac{w^k - 1}{w - 1}.

Theorem. ∀0≤t≤n\forall 0 \le t \le n, E[Xt]=t\mathbb{E} [ X_t ] = t.

Proof: Clearly, E[X0]=0\mathbb{E} [ X_0 ] = 0. For t≥1t \ge 1,

E[Xt∣Xt−1]=pt⋅(Xt−1+1pt)+(1−pt)⋅Xt−1=Xt−1+1. \mathbb{E} [ X_t \mid X_{t - 1} ] = p_t \cdot \left( X_{t - 1} + \frac{1}{p_t} \right) + ( 1 - p_t ) \cdot X_{t - 1} = X_{t - 1} + 1.

Hence, by induction on tt, we have

E[Xt]=E[E[Xt∣Xt−1]]=E[Xt−1]+1=t. \mathbb{E} [ X_t ] = \mathbb{E} [ \mathbb{E} [ X_t \mid X_{t - 1} ] ] = \mathbb{E} [ X_{t - 1} ] + 1 = t.

□\square

Theorem. ∀t∈[n]\forall t \in [n], Var[Xt]=(w−1)⋅t22\mathbb{Var } [ X_t ] = (w - 1) \cdot \frac{ t^2 }{ 2 }.

Proof: For t≥1t \ge 1, it holds that Xt−1=1/pt−1w−1X_{t - 1} = \frac{ 1 / p_t - 1}{w - 1}. Therefore,

1/pt=(w−1)⋅Xt−1+1 1 / p_t = (w - 1) \cdot X_{t - 1} + 1

and

E[Xt2∣Xt−1]=pt⋅(Xt−1+1/pt)2+(1−pt)⋅(Xt−1)2=1/pt+2⋅Xt−1+(Xt−1)2=(w+1)⋅Xt−1+1+(Xt−1)2 \begin{aligned} \mathbb{E} [ X_t^2 | X_{t - 1} ] &= p_t \cdot \left( X_{t - 1} + 1 / p_t \right)^2 + ( 1 - p_t ) \cdot (X_{t - 1})^2 \\ &= 1 / p_t + 2 \cdot X_{t - 1} + (X_{t - 1})^2 \\ &= (w + 1) \cdot X_{t - 1} + 1 + (X_{t - 1})^2 \end{aligned}

Therefore, since X0=0X_0 = 0,

E[Xt2]=E[E[Xt2∣Xt−1]]=(w+1)⋅E[Xt−1]+1+E[Xt−12]=E[Xt−12]+(w+1)⋅(t−1)+1...=E[X02]+(w+1)⋅∑i=0t−1i+t=(w+1)⋅t(t−1)2+t≤(w−1)⋅t22+t2, \begin{aligned} \mathbb{E} [ X_t^2 ] &= \mathbb{E} [ \mathbb{E} [ X_t^2 | X_{t - 1} ] ] \\ &= (w + 1) \cdot \mathbb{E} [ X_{t - 1} ] + 1 + \mathbb{E} [ X_{t - 1} ^2] \\ &= \mathbb{E} [ X_{t - 1}^2 ] + (w + 1) \cdot (t - 1) + 1 \\ &... \\ &= \mathbb{E} [ X_0^2 ] + (w + 1) \cdot \sum_{i = 0}^{t - 1} i + t \\ &= (w + 1) \cdot \frac{ t (t - 1) }{ 2 } + t \\ &\le (w - 1) \cdot \frac{ t^2 }{ 2 } + t^2, \end{aligned}

and

Var[Xt]=E[Xt2]−(E[Xt])2≤(w−1)⋅t22. \mathbb{Var } [ X_t ] = \mathbb{E} [ X_t^2 ] - (\mathbb{E} [ X_t ])^2 \le (w - 1) \cdot \frac{ t^2 }{ 2 } .

Corollary. By Chebyshev's inequality,

Pr⁡[∣Xt−t∣≥ϵ⋅t]≤(w−1)⋅t22ϵ2⋅t2=w−12ϵ2. \Pr[ | X_t - t | \ge \epsilon \cdot t ] \le (w - 1) \cdot \frac{ t^2 }{ 2 \epsilon^2 \cdot t^2} = \frac{w - 1}{ 2 \epsilon^2 }.

Corollary. If we set w=1+2ϵ2δw = 1 + 2 \epsilon^2 \delta, then the failure probability is at most δ\delta.

Reference.

[1] G. Cormode and K. Yi, Small Summaries for Big Data, 1st ed. Cambridge University Press, 2020.