Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling


I’m trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are allowed).

  1. What am I missing? According to my (buggy) analysis of the reported estimator’s variance, the variance equal to 0 (see below).
  2. How should I analyze the use in an $ \ell_0$ -sampler? (Currently, my analysis ignore it)

Algorithm:

  1. Init: Define $ k := O(\frac {n^3} {\epsilon^2 t})$ . Pick $ k$ random subsets $ S_1, \ldots, S_k \subset V$ each of size 3 (with repetitions).
  2. Update: For each random subset of size 3, denoted $ S_i$ , maintain a counter $ x_{S_i}$ , which represent the number of internal edges in $ S_i$ , i.e. a number in $ \{0, 1, 2, 3\}$ .
  3. Output: Use an $ \ell_o$ -sampler over the vector $ x = (x_{S_1}, \ldots, x_{S_k})$ to pick an index $ j \in [k]$ (i.e. $ j$ is chosen uniformly at random from $ \{i \in [k] : x_{S_i} > 0\}$ ). Compute $ z := \mathbb{1}[x_{S_j} = 3], N = \|x\|_0$ . Report $ \tilde{T} = N \cdot z$ .

Analysis, where $ T$ is the number of triangles: $ $ \begin{split} E[\tilde T] &= E[N \cdot z] \ &= N \cdot E[z] \ &= \|x\|_0 \cdot \Pr \left[ \mathbb{1} \left[ x_{S_j} = 3 \right] \right] \ &= \|x\|_0 \cdot \frac T {\|x\|_0} \ &= T \end{split} $ $

Which seems to be ok. But for the variance: $ $ \begin{split} Var[\tilde T] &= Var[N \cdot z] \ &= N^2 \cdot Var[z] \ \end{split} $ $ Then $ $ \begin{split} Var[z] &= Var \left[ \mathbb{1} \left[ x_{S_j} = 3 \right] \right] \ &= E \left[ \left( \mathbb{1} \left[ x_{S_j} = 3 \right] \right)^2 \right] – \left( E \left[ \mathbb{1} \left[ x_{S_j} = 3 \right] \right] \right)^2 \ &= E \left[ \mathbb{1} \left[ x_{S_j} = 3 \right], \mathbb{1} \left[ x_{S_i} = 3 \right] \right] – \left( \frac {T} {\|x\|_0} \right)^2 \ &= \Pr \left[ \mathbb{1} \left[ x_{S_j} = 3 \right], \mathbb{1} \left[ x_{S_i} = 3 \right] \right] – \left( \frac {T} {\|x\|_0} \right)^2 \ &= \left( \Pr \left[ \mathbb{1} \left[ x_{S_j} = 3 \right] \right] \right)^2 – \left( \frac {T} {\|x\|_0} \right)^2 \ &= \left( \frac {T} {\|x\|_0} \right)^2 – \left( \frac {T} {\|x\|_0} \right)^2 \ &= 0 \end{split} $ $