2010119-130Nancy, France 119

Vladimir Braverman

Kai-Min Chung

Zhenming Liu

Michael Mitzenmacher

Rafail Ostrovsky

# AMS Without $\bf{4}$-Wise Independence on Product Domains111This paper is a
merge from the work of [7, 9, 10]

V. Braverman  University of California Los Angeles. Supported in part by NSF
grants 0716835, 0716389, 0830803, 0916574 and Lockheed Martin Corporation.
<EMAIL_ADDRESS>http://www.cs.ucla.edu/~vova ,  K. Chung  Harvard School of
Engineering and Applied Sciences. Supported by US-Israel BSF grant 2006060 and
NSF grant CNS-0831289<EMAIL_ADDRESS>http://people.seas.harvard.edu/~kmchung/ ,  Z. Liu  Harvard School of
Engineering and Applied Sciences. Supported in part by NSF grant CNS-0721491.
The work was finished during an internship in Microsoft Research Asia.
<EMAIL_ADDRESS>http://people.seas.harvard.edu/~zliu/ ,  M. Mitzenmacher
Harvard School of Engineering and Applied Sciences. Supported in part by NSF
grant CNS-0721491 and research grants from Yahoo!, Google, and Cisco.
<EMAIL_ADDRESS>http://www.eecs.harvard.edu/~michaelm/ and  R.
Ostrovsky  University of California Los Angeles. Supported in part by IBM
Faculty Award, Lockheed-Martin Corporation Research Award, Xerox Innovation
Group Award, the Okawa Foundation Award, Intel, Teradata, NSF grants 0716835,
0716389, 0830803, 0916574 and U.C. MICRO grant<EMAIL_ADDRESS>http://www.cs.ucla.edu/~rafail

###### Abstract.

In their seminal work, Alon, Matias, and Szegedy introduced several sketching
techniques, including showing that $4$-wise independence is sufficient to
obtain good approximations of the second frequency moment. In this work, we
show that their sketching technique can be extended to product domains
$[n]^{k}$ by using the product of $4$-wise independent functions on $[n]$. Our
work extends that of Indyk and McGregor, who showed the result for $k=2$.
Their primary motivation was the problem of identifying correlations in data
streams. In their model, a stream of pairs $(i,j)\in[n]^{2}$ arrive, giving a
joint distribution $(X,Y)$, and they find approximation algorithms for how
close the joint distribution is to the product of the marginal distributions
under various metrics, which naturally corresponds to how close $X$ and $Y$
are to being independent. By using our technique, we obtain a new result for
the problem of approximating the $\ell_{2}$ distance between the joint
distribution and the product of the marginal distributions for $k$-ary
vectors, instead of just pairs, in a single pass. Our analysis gives a
randomized algorithm that is a $(1\pm\epsilon)$ approximation (with
probability $1-\delta$) that requires space logarithmic in $n$ and $m$ and
proportional to $3^{k}$.

###### Key words and phrases:

Data Streams, Randomized Algorithms, Streaming Algorithms, Independence,
Sketches

###### 1991 Mathematics Subject Classification:

F.2.1, G.3

##  1\. Introduction

In their seminal work, Alon, Matias and Szegedy [4] presented celebrated
sketching techniques and showed that $4$-wise independence is sufficient to
obtain good approximations of the second frequency moment. Indyk and McGregor
[12] make use of this technique in their work introduce the problem of
measuring independence in the streaming model. There they give efficient
algorithms for approximating pairwise independence for the $\ell_{1}$ and
$\ell_{2}$ norms. In their model, a stream of pairs $(i,j)\in[n]^{2}$ arrive,
giving a joint distribution $(X,Y)$, and the notion of approximating pairwise
independence corresponds to approximating the distance between the joint
distribution and the product of the marginal distributions for the pairs.
Indyk and McGregor state, as an explicit open question in their paper, the
problem of whether one can estimate $k$-wise independence on $k$-tuples for
any $k>2$. In particular, Indyk and McGregor show that, for the $\ell_{2}$
norm, they can make use of the product of $4$-wise independent functions on
$[n]$ in the sketching method of Alon, Matias, and Szegedy. We extend their
approach to show that on the product domain $[n]^{k}$, the sketching method of
Alon, Matias, and Szegedy works when using the product of $k$ copies of
$4$-wise independent functions on $[n]$. The cost is that the memory
requirements of our approach grow exponentially with $k$, proportionally to
$3^{k}$.

Measuring independence and $k$-wise independence is a fundamental problem with
many applications (see e.g., Lehmann [13]). Recently, this problem was also
addressed in other models by, among others, Alon, Andoni, Kaufman, Matulef,
Rubinfeld and Xie [1]; Batu, Fortnow, Fischer, Kumar, Rubinfeld and White [5];
Goldreich and Ron [11]; Batu, Kumar and Rubinfeld [6]; Alon, Goldreich and
Mansour [3]; and Rubinfeld and Servedio [15]. Traditional non-parametric
methods of testing independence over empirical data usually require space
complexity that is polynomial to either the support size or input size. The
scale of contemporary data sets often prohibits such space complexity. It is
therefore natural to ask whether we will be able to design algorithms to test
for independence in streaming model. Interestingly, this specific problem
appears not to have been introduced until the work of Indyk and McGregor.
While arguably results for the $\ell_{1}$ norm would be stronger than for the
$\ell_{2}$ norm in this setting, the problem for $\ell_{2}$ norms is
interesting in its own right. The problem for the $\ell_{1}$ norm has been
recently resolved by Braverman and Ostrovsky in [8]. They gave an
$(1\pm\epsilon,\delta)$-approximation algorithm that makes a single pass over
a data stream and uses polylogarithmic memory.

###  1.1. Our Results

In this paper we generalize the “sketching of sketches” result of Indyk and
McGregor. Our specific theoretical contributions can be summarized as follows:

_Main Theorem._

Let ${\vec{v}}\in\mathrm{R}^{(n^{k})}$ be a vector with entries
${\vec{v}}_{{\mathbf{p}}}\in R$ for ${\mathbf{p}}\in[n]^{k}$. Let
$h_{1},\dots,h_{k}:[n]\rightarrow\\{-1,1\\}$ be independent copies of 4-wise
independent hash functions; that is, $h_{i}(1),\dots,h_{i}(n)\in\\{-1,1\\}$
are $4$-wise independent hash functions for each $i\in[k]$, and
$h_{1}(\cdot),\dots,h_{k}(\cdot)$ are mutually independent. Define
$H({\mathbf{p}})=\prod_{i=1}^{k}h_{j}(p_{j})$, and the sketch
$Y=\sum_{p\in[n]^{k}}\vec{v}_{\mathbf{p}}H(p)$.

We prove that the sketch $Y$ can be used to give an efficient approximation
for $\|{\vec{v}}\|^{2}$; our result is stated formally in Theorem 4.2. Note
that $H$ is not $4$-wise independent.

As a corollary, the main application of our main theorem is to extend the
result of Indyk and McGregor [12] to detect the dependency of $k$ random
variables in streaming model.

######  Corollary 1.1.

For every $\epsilon>0$ and $\delta>0$, there exists a randomized algorithm
that computes, given a sequence $a_{1},\dots,a_{m}$ of $k$-tuples, in one pass
and using $O(3^{k}\epsilon^{-2}\log\frac{1}{\delta}(\log m+\log n))$ memory
bits, a number $Y$ so that the probability $Y$ deviates from the $\ell_{2}$
distance between product and joint distribution by more than a factor of
$(1+\epsilon)$ is at most $\delta$.

###  1.2. Techniques and a Historical Remark

This paper is merge from [7, 9, 10], where the same result was obtained with
different proofs. The proof of [10] generalizes the geometric approach of
Indyk and McGregor [12] with new geometric observations. The proofs of [7, 9]
are more combinatorial in nature. These papers offer new insights, but due to
the space limitation, we focus on the proof from [9] in this paper. Original
papers are available on line and are recommended to the interested reader.

##  2\. The Model

We provide the general underlying model. Here we mostly follow the notation of
[7, 12].

Let $S$ be a stream of size $m$ with elements $a_{1},\dots,a_{m}$, where
$a_{i}\equiv(a^{1}_{i},\dots,a^{k}_{i})\in[n]^{k}$. (When we have a sequence
of elements that are themselves vectors, we denote the sequence number by a
subscript and the vector entry by a superscript when both are needed.) The
stream $S$ defines an _empirical_ distribution over $[n]^{k}$ as follows: the
frequency $f(\omega)$ of an element $\omega\in[n]^{k}$ is defined as the
number of times it appears in $S$, and the empirical distribution is

$\Pr[\omega]=\frac{f(\omega)}{m}\quad\mbox{for any $\omega\in[n]^{k}$.}$

Since $\omega=(\omega_{1},\dots,\omega_{k})$ is a vector of size $k$, we may
also view the streaming data as defining a joint distribution over the random
variables $X_{1},\dots,X_{k}$ corresponding to the values in each dimension.
(In the case of $k=2$, we write the random variables as $X$ and $Y$ rather
than $X_{1}$ and $X_{2}$.) There is a natural way of defining marginal
distribution for the random variable $X_{i}$: for $\omega_{i}\in[n]$, let
$f_{i}(\omega_{i})$ be the number of times $\omega_{i}$ appears in the $i$th
coordinate of an element of $S$, or

$f_{i}(\omega_{i})=\left|\\{a_{j}\in S:a^{i}_{j}=\omega_{i}\\}\right|.$

The empirical marginal distribution $\Pr_{i}[\cdot]$ for the $i$th coordinate
is defined as

$\mathrm{Pr}_{i}[\omega_{i}]=\frac{f_{i}(\omega_{i})}{m}\quad\mbox{for any
$\omega_{i}\in[n]$.}$

Next let $\vec{v}$ be the vector in ${\mathrm{R}}^{[n]^{k}}$ with
$\vec{v}_{\omega}=\Pr[\omega]-\prod_{1\leq i\leq k}\Pr_{i}[\omega_{i}]$ for
all $\omega\in[n]^{k}$. Our goal is to approximate the value

$\|\vec{v}\|\equiv\left(\sum_{\omega\in[n]^{k}}\left|\Pr[\omega]-\prod_{1\leq
i\leq k}\mathrm{Pr}_{i}[\omega_{i}]\right|^{2}\right)^{\frac{1}{2}}.$ (1)

This represent the $\ell_{2}$ norm between the tensor of the marginal
distributions and the joint distribution, which we would expect to be close to
zero in the case where the $X_{i}$ were truly independent.

Finally, our algorithms will assume the availability of 4-wise independent
hash functions. For more on 4-wise independence, including efficient
implementations, see [2, 16]. For the purposes of this paper, the following
simple definition will suffice.

######  Definition 2.1.

_(4-wise independence)_ A family of hash functions $\mathcal{H}$ with domain
$[n]$ and range $\\{-1,1\\}$ is _4-wise independent_ if for any distinct
values $i_{1},i_{2},i_{3},i_{4}\in[n]$ and any
$b_{1},b_{2},b_{3},b_{4}\in\\{-1,1\\}$, the following equality holds,

$\Pr_{h\leftarrow\mathcal{H}}\left[h(i_{1})=b_{1},h(i_{2})=b_{2},h(i_{3})=b_{3},h(i_{4})=b_{4}\right]=1/16.$

######  Remark 2.2.

In [12], the family of 4-wise independent hash functions $\mathcal{H}$ is
called 4-wise independent random vectors. For consistencies within our paper,
we will always view the object $\mathcal{H}$ as a hash function family.

##  3\. The Algorithm and its Analysis for $k=2$

We begin by reviewing the approximation algorithm and associated proof for the
$\ell_{2}$ norm given in [12]. Reviewing this result will allow us to provide
the necessary notation and frame the setting for our extension to general $k$.
Moreover, in our proof, we find that a constant in Lemma 3.1 from [12] that we
subsequently generalize appears incorrect. (Because of this, our proof is
slightly different and more detailed than the original.) Although the error is
minor in the context of their paper (it only affects the constant factor in
the order notation), it becomes more important when considering the proper
generalization to larger $k$, and hence it is useful to correct here.

In the case $k=2$, we assume that the sequence
$(a^{1}_{1},a^{2}_{1}),(a^{1}_{2},a^{2}_{2}),\dots,(a^{1}_{m},a^{2}_{m})$
arrives an item by an item. Each $(a^{1}_{i},a^{2}_{i})$ (for $1\leq i\leq m$)
is an element in $[n]^{2}$. The random variables $X$ and $Y$ over $[n]$ can be
expressed as follows:

$\left\\{\begin{array}[]{lllll}\Pr[i,j]&=&\Pr[X=i,Y=j]&=&|\\{\ell:(a^{1}_{\ell},a^{2}_{\ell})=(i,j)\\}|/m\\\
\Pr_{1}[i]&=&\Pr[X=i]&=&|\\{\ell:(a^{1}_{\ell},a^{2}_{\ell})=(i,\cdot)\\}|/m\\\
\Pr_{2}[j]&=&\Pr[Y=j]&=&|\\{\ell:(a^{1}_{\ell},a^{2}_{\ell})=(\cdot,j)\\}|/m.\end{array}\right.$

We simplify the notation and use $p_{i}\equiv\Pr[X=i]$, $q_{j}\equiv\Pr[Y=j]$,
$r_{i,j}=\Pr[X=i,Y=j]$. and $s_{i,j}=\Pr[X=i]\Pr[Y=j]$.

Indyk and McGregor’s algorithm proceeds in a similar fashion to the streaming
algorithm presented in [4]. Specifically let $s_{1}=72\epsilon^{-2}$ and
$s_{2}=2\log(1/\delta)$. The algorithm computes $s_{2}$ random variables
$Y_{1},Y_{2},\dots,Y_{s_{2}}$ and outputs their median. The output is the
algorithm’s estimate on the norm of $v$ defined in Equation 1. Each $Y_{i}$ is
the average of $s_{1}$ random variables $Y_{ij}$: $1\leq j\leq s_{1}$, where
$Y_{ij}$ are independent, identically distributed random variables. Each of
the variables $D=D_{ij}$ can be computed from the algorithmic routine shown in
Figure 1.

  * $\textnormal{2-D Approximation}\left((a^{1}_{1},a^{2}_{1}),\dots,(a^{1}_{m},a^{2}_{m})\right)$
1Independently generate 4-wise independent random functions $h_{1},h_{2}$ from
$[n]$ to $\\{-1,1\\}$. 2for $c\leftarrow 1$ to $m$ 3 doLet the $c$th item
$(a^{1}_{c},a^{2}_{c})=(i,j)$ 4 $t_{1}\leftarrow t_{1}+h_{1}(i)h_{2}(j)$,
$t_{2}\leftarrow t_{2}+h_{1}(i)$, $t_{3}\leftarrow t_{3}+h_{2}(j)$. 5Return
$Y=(t_{1}/m-t_{2}t_{3}/m^{2})^{2}$.

Figure 1.  The procedure for generating random variable $Y$ for $k=2$.

By the end of the process 2-D Approximation, we have
$t_{1}/m=\sum_{i,j\in[n]}h_{1}(i)h_{2}(j)r_{i,j}$,
$t_{2}/m=\sum_{i\in[n]}h_{1}(i)p_{i}$, and
$t_{3}/m=\sum_{i\in[n]}h_{2}(i)q_{i}$. Also, when a vector is in
${\mathrm{R}}^{(n^{2})}$, its indices can be represented by
$(i_{1},i_{2})\in[n]^{2}$. In what follows, we will use a bold letter to
represent the index of a high dimensional vector, e.g., $v_{\mathbf{i}}\equiv
v_{i_{1},i_{2}}$. The following Lemma shows that the expectation of $Y$ is
$\|v\|^{2}$ and the variance of $Y$ is at most $8(\mathrm{E}[Y])^{2}$ because
$\mathrm{E}[Y^{2}]\leq 9\mathrm{E}[Y]^{2}$.

######  Lemma 3.1.

([12]) Let $h_{1},h_{2}$ be two independent instances of 4-wise independent
hash functions from $[n]$ to $\\{-1,1\\}$. Let $v\in\mathrm{R}^{n^{2}}$ and
$H(\mathbf{i})(\equiv H\big{(}(i_{1},i_{2})\big{)}=h_{1}(i_{i})\cdot
h_{2}(i_{2})$. Let us define
$Y=\left(\sum_{\mathbf{i}\in[n]^{2}}H(\mathbf{i})v_{\mathbf{i}}\right)^{2}$.
Then $\mathrm{E}[Y]=\sum_{\mathbf{i}\in[n]^{2}}\vec{v}_{\mathbf{i}}^{2}$ and
$\mathrm{E}[Y^{2}]\leq 9(\mathrm{E}[Y])^{2}$, which implies
$\mathrm{Var}[Y]\leq 8E^{2}[Y]$.

######  Proof 3.2.

We have
$\mathrm{E}[Y]=\mathrm{E}[(\sum_{\mathbf{i}}H(\mathbf{i})\vec{v}_{\mathbf{i}})^{2}]=\sum_{\mathbf{i}}\vec{v}^{2}_{\mathbf{i}}\mathrm{E}[H^{2}(\mathbf{i})]+\sum_{\mathbf{i}\neq\mathbf{j}}\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\mathrm{E}[H(\mathbf{i})H(\mathbf{j})]$.
For all $\mathbf{i}\in[n]^{2}$, we know $h^{2}(\mathbf{i})=1$. On the other
hand, $H(\mathbf{i})H(\mathbf{j})\in\\{-1,1\\}$. The probability that
$H(\mathbf{i})H(\mathbf{j})=1$ is
$\Pr[H(\mathbf{i})H(\mathbf{j})=1]=\Pr[h_{1}(i_{1})h_{1}(j_{1})h_{2}(i_{2})h_{2}(j_{2})=1]=1/16+\binom{4}{2}1/16+1/16=1/2$.
The last equality holds is because
$h_{1}(i_{1})h_{1}(j_{1})h_{2}(i_{2})h_{2}(j_{2})=1$ is equivalent to saying
either all these variables are 1, or exactly two of these variables are -1, or
all these variables are -1. Therefore,
$\mathrm{E}[h(\mathbf{i})h(\mathbf{j})]=0$. Consequently,
$\mathrm{E}[Y]=\sum_{\mathrm{i}\in[n]^{2}}(\vec{v}_{\mathrm{i}})^{2}$.

Now we bound the variance. Recall that
$\mathrm{Var}[Y]=\mathrm{E}[Y^{2}]-\mathrm{E}[Y]^{2}$, we bound

$\mathrm{E}[Y^{2}]=\sum_{\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}\in[n]^{2}}\mathrm{E}[H(\mathbf{i})H(\mathbf{j})H(\mathbf{k})h(\mathbf{l})]\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}\leq\sum_{\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}\in[n]^{2}}\left|\mathrm{E}[H(\mathbf{i})H(\mathbf{j})H(\mathbf{k})H(\mathbf{l})]\right|\cdot|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|.$

Also
$\left|\mathrm{E}[H(\mathbf{i})H(\mathbf{j})H(\mathbf{k})H(\mathbf{l})]\right|\in\\{0,1\\}$.
The quantity
$\mathrm{E}[H(\mathbf{i})H(\mathbf{j})H(\mathbf{k})H(\mathbf{l})]\neq 0$ if
and only if the following relation holds,

$\forall
s\in[2]:\left((i_{s}=j_{s})\wedge(k_{s}=l_{s})\right)\vee\left((i_{s}=k_{s})\wedge(j_{s}=l_{s})\right)\vee\left((i_{s}=l_{s})\wedge(k_{s}=j_{s})\right).$
(2)

Denote the set of 4-tuples $(\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l})$
that satisfy the above relation by $\mathcal{D}$. We may also view each
4-tuple as an ordered set that consists of 4 points in $[n]^{2}$. Consider the
unique smallest axes-parallel rectangle in $[n]^{2}$ that contains a given
4-tuple in $\mathcal{D}$ (i.e. contains the four ordered points). Note this
could either be a (degenerate) line segment or a (non-degenerate) rectangle,
as we discuss below. Let $M:\mathcal{D}\rightarrow\\{A,B,C,D\\}$ be the
function that maps an element $\sigma\in\mathcal{D}$ to the smallest rectangle
$ABCD$ defined by $\sigma$. Since a rectangle can be uniquely determined by
its diagonals, we may write
$M:\mathcal{D}\rightarrow(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$, where
$\chi_{1}\leq\chi_{2}\in[n]$, $\varphi_{1}\leq\varphi_{2}\in[n]$ and the
corresponding rectangle is understood to be the one with diagonal
$\\{(\chi_{1},\varphi_{1}),(\chi_{2},\varphi_{2})\\}$. Also, the inverse
function $M^{-1}(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$ represents the
pre-images of $(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$ in $\mathcal{D}$.
$(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$ is degenerate if either
$\chi_{1}=\chi_{2}$ or $\varphi_{1}=\varphi_{2}$, in which case the rectangle
(and its diagonals) correspond to the segment itself, or $\chi_{1}=\chi_{2}$
and $\varphi_{1}=\varphi_{2}$, and the rectangle is just a single point.

######  Example 3.3.

Let $\mathbf{i}=(1,2)$, $\mathbf{j}=(3,2)$, $\mathbf{k}=(1,5)$, and
$\mathbf{l}=(3,5)$. The tuple is in $\mathcal{D}$ and its corresponding
bounding rectangle is a non-degenerate rectangle. The function
$M(\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l})=(1,3,2,5)$.

######  Example 3.4.

Let $\mathbf{i}=\mathbf{j}=(1,4)$ and $\mathbf{k}=\mathbf{l}=(3,7)$. The tuple
is also in $\mathcal{D}$ and minimal bounding rectangle formed by these points
is an interval $\\{(1,4),(3,7)\\}$. The function
$M(\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l})=(1,3,4,7)$.

To start we consider the non-degenerate cases. Fix any
$(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$ with $\chi_{1}<\chi_{2}$ and
$\phi_{1}<\phi_{2}$. There are in total $\binom{4}{2}^{2}=36$ tuples
$(\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l})$ in $\mathcal{D}$ with
$M(\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l})=(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$.
Twenty-four of these tuples correspond to the setting where none of
$\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}$ are equal, as there are twenty-
four permutations of the assignment of the labels
$\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}$ to the four points. (This
corresponds to the first example). In this case the four points form a
rectangle, and we have
$|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|\leq\frac{1}{2}((\vec{v}_{\chi_{1},\varphi_{1}}\vec{v}_{\chi_{2},\varphi_{2}})^{2}+(\vec{v}_{\chi_{1},\varphi_{2}}\vec{v}_{\chi_{2},\varphi_{1}})^{2})$.
Intuitively, in these cases, we assign the “weight” of the tuple to the
diagonals.

The remaining twelve tuples in
$M^{-1}(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$ correspond to intervals.
(This corresponds to the second example.) In this case two of
$\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}$ correspond to one endpoint of
the interval, and the other two labels correspond to the other endpoint. Hence
we have either
$|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|=(\vec{v}_{\chi_{1},\varphi_{1}}\vec{v}_{\chi_{2},\varphi_{2}})^{2}$
or
$|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|=(\vec{v}_{\chi_{1},\varphi_{2}}\vec{v}_{\chi_{2},\varphi_{1}})^{2}$,
and there are six tuples for each case.

Therefore for any $\chi_{1}<\chi_{2}\in[n]$ and
$\varphi_{1}<\varphi_{2}\in[n]$ we have:

$\sum_{\scriptsize{}\begin{subarray}{c}(\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l})\in\\\
M^{-1}(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})\end{subarray}}|v_{\mathbf{i}}v_{\mathbf{j}}v_{\mathbf{k}}v_{\mathbf{l}}|\leq
18((v_{\chi_{1},\varphi_{1}}v_{\chi_{2},\varphi_{2}})^{2}+(v_{\chi_{1},\varphi_{2}},v_{\chi_{2},\varphi_{1}})^{2}).$

The analysis is similar for the degenerate cases, where the constant 18 in the
bound above is now quite loose. When exactly one of $\chi_{1}=\chi_{2}$ or
$\varphi_{1}=\varphi_{2}$ holds, the size of
$M^{-1}(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})$ is $\binom{4}{2}=6$, and
the resulting intervals correspond to vertical or horizontal lines. When both
$\chi_{1}=\chi_{2}$ and $\varphi_{1}=\varphi_{2}$, then
$|M^{-1}(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})|=1$. In sum, we have
Following the same analysis as for the non-degenerate cases, we find

$\sum_{\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}\in\mathcal{D}}|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|=\sum_{\scriptsize{}\begin{subarray}{c}\chi_{1}\leq\chi_{2}\\\
\varphi_{1}\leq\varphi_{2}\end{subarray}}\sum_{\scriptsize{}\begin{subarray}{c}(\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l})\in\\\
M^{-1}(\chi_{1},\chi_{2},\varphi_{1},\varphi_{2})\end{subarray}}|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|\\\
$ $\leq\sum_{\scriptsize{}\begin{subarray}{c}\chi_{1}<\chi_{2}\\\
\varphi_{1}<\varphi_{2}\end{subarray}}18((\vec{v}_{\chi_{1},\varphi_{1}}\vec{v}_{\chi_{2},\varphi_{2}})^{2}+(\vec{v}_{\chi_{1},\varphi_{2}}\vec{v}_{\chi_{2},\varphi_{1}})^{2})+\sum_{\scriptsize{}\begin{subarray}{c}\chi_{1}=\chi_{2}\\\
\varphi_{1}<\varphi_{2}\end{subarray}}6((\vec{v}_{\chi_{1},\varphi_{1}}\vec{v}_{\chi_{2},\varphi_{2}})^{2}+(\vec{v}_{\chi_{1},\varphi_{2}}\vec{v}_{\chi_{2},\varphi_{1}})^{2})$
$+\sum_{\scriptsize{}\begin{subarray}{c}\chi_{1}<\chi_{2}\\\
\varphi_{1}=\varphi_{2}\end{subarray}}6((\vec{v}_{\chi_{1},\varphi_{1}}\vec{v}_{\chi_{2},\varphi_{2}})^{2}+(\vec{v}_{\chi_{1},\varphi_{2}}\vec{v}_{\chi_{2},\varphi_{1}})^{2})+\sum_{\scriptsize{}\begin{subarray}{c}\chi_{1}=\chi_{2}\\\
\varphi_{1}=\varphi_{2}\end{subarray}}(\vec{v}_{\chi_{1},\varphi_{1}}\vec{v}_{\chi_{2},\varphi_{2}})^{2}\\\
$ $\leq 9\sum_{\scriptsize{}\begin{subarray}{c}\mathbf{i}\in[n]^{2}\\\
\mathbf{j}\in[n]^{2}\end{subarray}}(\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}})^{2}=9\mathrm{E}^{2}[Y].$

Finally, we have
$\sum_{\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}\in[n]^{2}}\left|\mathrm{E}[H(\mathbf{i})H(\mathbf{j})H(\mathbf{k})H(\mathbf{l})]\right|\cdot|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|\leq\sum_{\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}\in\mathcal{D}}|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|\leq
9\mathrm{E}^{2}[Y]$ and $\mathrm{Var}[Y]\leq 8\mathrm{E}[Y]^{2}$.

We emphasize the geometric interpretation of the above proof as follows. The
goal is to bound the variance by a constant times
$\mathrm{E}^{2}[Y]=\sum_{\scriptsize{}\begin{subarray}{c}\mathbf{i},\mathbf{j}\in[n]^{2}\end{subarray}}(\vec{v}_{\mathbf{i}}v_{\mathbf{j}})^{2}$,
where the index set is the set of all possible lines in plane $[n]^{2}$ (each
line appears twice). We first show that
$\mathrm{Var}[Y]\leq\sum_{\mathbf{i},\mathbf{j},\mathbf{k},\mathbf{l}\in\mathcal{D}}|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|$,
where the 4-tuple index set corresponds to a set of rectangles in a natural
way. The main idea of [12] is to use inequalities of the form
$|\vec{v}_{\mathbf{i}}\vec{v}_{\mathbf{j}}\vec{v}_{\mathbf{k}}\vec{v}_{\mathbf{l}}|\leq\frac{1}{2}((\vec{v}_{\chi_{1},\varphi_{1}}\vec{v}_{\chi_{2},\varphi_{2}})^{2}+(\vec{v}_{\chi_{1},\varphi_{2}}\vec{v}_{\chi_{2},\varphi_{1}})^{2})$
to assign the “weight” of each $4$-tuple to the diagonals of the corresponding
rectangle. The above analysis shows that $18$ copies of all lines are
sufficient to accommodate all 4-tuples. While similar inequalities could also
assign the weight of a $4$-tuple to the vertical or horizontal edges of the
corresponding rectangle, using vertical or horizontal edges is problematic.
The reason is that there are $\Omega(n^{4})$ $4$-tuples but only $O(n^{3})$
vertical or horizontal edges, so some lines would receive $\Omega(n)$ weight,
requiring $\Omega(n)$ copies. This problem is already noted in [7].

Our bound here is $\mathrm{E}[Y^{2}]\leq 9\mathrm{E}^{2}[Y]$, while in [12]
the bound obtained is $\mathrm{E}[Y^{2}]\leq 3\mathrm{E}^{2}[Y]$. There
appears to have been an error in the derivation in [12]; some intuition comes
from the following example. We note that $|\mathcal{D}|$ is at least
$\binom{4}{2}^{2}\cdot\binom{n}{2}^{2}=9n^{4}-9n^{2}$. (This counts the number
of non-degenerate $4$-tuples.) Now if we set $v_{i}=1$ for all $1\leq i\leq
n^{2}$, we have
$\mathrm{E}[Y^{2}]\geq|\mathcal{D}|=9n^{4}-9n^{2}\sim\mathrm{9}\mathrm{E}^{2}(D)$,
which suggests $\mathrm{Var}[D]>3\mathrm{E}^{2}[D]$. Again, we emphasize this
discrepancy is of little importance to [12]; the point there is that the
variance is bounded by a constant factor times the square of the expectation.
It is here, where we are generalizing to $k\geq 3$, that the exact constant
factor is of some importance.

Given the bounds on the expectation and variance for the $D_{i,j}$, standard
techniques yield a bound on the performance of our algorithm.

######  Theorem 3.5.

For every $\epsilon>0$ and $\delta>0$, there exists a randomized algorithm
that computes, given a sequence
$(a^{1}_{1},a^{2}_{1}),\dots,(a^{1}_{m},a^{2}_{m})$, in one pass and using
$O(\epsilon^{-2}\log\frac{1}{\delta}(\log m+\log n))$ memory bits, a number
$\mathrm{Med}$ so that the probability $\mathrm{Med}$ deviates from
$\|v\|^{2}$ by more than $\epsilon$ is at most $\delta$.

######  Proof 3.6.

Recall the algorithm described in the beginning of Section 3: let
$s_{1}=72\epsilon^{-2}$ and $s_{2}=2\log\delta$. We first computes $s_{2}$
random variables $Y_{1},Y_{2},\dots,Y_{s_{2}}$ and outputs their median
$\mathrm{Med}$, where each $Y_{i}$ is the average of $s_{1}$ random variables
$Y_{ij}$: $1\leq j\leq s_{1}$ and $Y_{ij}$ are independent, identically
distributed random variables computed by Figure 1. By Chebyshev’s inequality,
we know that for any fixed $i$,

$\Pr\big{(}\big{|}Y_{i}-\|\vec{v}\|\big{|}\big{)}\geq\epsilon\|\vec{v}\|]\leq\frac{\mathrm{Var}(Y_{i})}{\epsilon^{2}\|\vec{v}\|^{2}}=\frac{(1/s_{1})\mathrm{Var}[Y]}{\epsilon^{2}\|\vec{v}\|^{2}}=\frac{(9\epsilon^{2}/72)\|\vec{v}\|^{2}}{\epsilon^{2}\|\vec{v}\|^{2}}=\frac{1}{8}.$

Finally, by standard Chernoff bound arguments (see for example Chapter 4 of
[14]), the probability that more than $s_{2}/2$ of the variables $Y_{i}$
deviate by more than $\epsilon\|\vec{v}\|$ from $\|\vec{v}\|$ is at most
$\delta$. In case this does not happen, the median $\mathrm{Med}$ supplies a
good estimate to the required quantity $\|\vec{v}\|$ as needed.

##  4\. The General Case $k\geq 3$

Now let us move to the general case where $k\geq 3$. Recall that ${\vec{v}}$
is a vector in $\mathrm{R}^{n^{k}}$ that maintains certain statistics of a
data stream, and we are interested in estimating its $\ell_{2}$ norm
$\|{\vec{v}}\|$. There is a natural generalization for Indyk and McGregor’s
method for $k=2$ to construct an estimator for $\|{\vec{v}}\|$: let
$h_{1},\dots,h_{k}:[n]\rightarrow\\{-1,1\\}$ be independent copies of 4-wise
independent hash functions (namely, $h_{i}(1),\dots,h_{i}(n)\in\\{-1,1\\}$ are
$4$-wise independent hash functions for each $i\in[k]$, and
$h_{1}(\cdot),\dots,h_{k}(\cdot)$ are mutually independent.). Let
$H({\mathbf{p}})=\prod_{i=1}^{k}h_{j}(p_{j})$. The estimator $Y$ is defined as
$Y\equiv\left(\sum_{{\mathbf{p}}\in[n]^{k}}\vec{v}_{{\mathbf{p}}}H({\mathbf{p}})\right)^{2}$.

Our goal is to show that $\mathrm{E}[Y]=\|\vec{v}\|^{2}$ and $\mathrm{Var}[Y]$
is reasonably small so that a streaming algorithm maintaining multiple
independent instances of estimator $Y$ will be able to output an approximately
correct estimation of $\|{\vec{v}}\|$ with high probability. Notice that when
$\|{\vec{v}}\|$ represents the $\ell_{2}$ distance between the joint
distribution and the tensors of the marginal distributions, the estimator can
be computed efficiently in a streaming model similarly to as in Figure 1. We
stress that our result is applicable to a broader class of $\ell_{2}$-norm
estimation problems, as long as the vector ${\vec{v}}$ to be estimated has a
corresponding efficiently computable estimator $Y$ in an appropriate streaming
model. Formally, we shall prove the following main lemma in the next
subsection.

######  Lemma 4.1.

Let ${\vec{v}}$ be a vector in $\mathrm{R}^{n^{k}}$, and
$h_{1},\dots,h_{k}:[n]\rightarrow\\{-1,1\\}$ be independent copies of 4-wise
independent hash functions. Define
$H({\mathbf{p}})=\prod_{i=1}^{k}h_{j}(p_{j})$, and
$Y\equiv\left(\sum_{{\mathbf{p}}\in[n]^{k}}\vec{v}_{{\mathbf{p}}}H({\mathbf{p}})\right)^{2}$.
We have ${\mathrm{E}}[Y]=||{\vec{v}}||$ and ${\mathrm{Var}}[Y]\leq
3^{k}{\mathrm{E}}[Y]^{2}$.

We remark that the bound on the variance in the above lemma is tight. One can
verify that when the vector ${\vec{v}}$ is a uniform vector (i.e., all entries
of ${\vec{v}}$ are the same), the variance of $Y$ is $\Omega(3^{k}E[Y]^{2})$.
With the above lemma, the following main theorem mentioned in the introduction
immediately follows by a standard argument presented in the proof of Theorem
3.5 in the previous section.

######  Theorem 4.2.

Let $\vec{v}$ be a vector in $\mathrm{R}^{[n]^{k}}$ that maintains an
arbitrary statistics in a data stream of size $m$, in which every item is from
$[n]^{k}$. Let $\epsilon,\delta\in(0,1)$ be real numbers. If there exists an
algorithm that maintains an instance of $Y$ using
$O(\mu(n,m,k,\epsilon,\delta))$ memory bits, then there exists an algorithm
$\Lambda$ such that:

  1. (1)

With probability $\geq 1-\delta$ the algorithm $\Lambda$ outputs a value
between $[(1-\epsilon)\|{\vec{v}}\|^{2},(1+\epsilon)\|{\vec{v}}|^{2}]$ and

  2. (2)

the space complexity of $\Lambda$ is
$O(3^{k}{1\over\epsilon^{2}}\log{1\over\delta}\mu(n,m,k,\epsilon,\delta))$.

As discussed above, an immediate corollary is the existence of a one-pass
space efficient streaming algorithm to detect the dependency of $k$ random
variables in $\ell_{2}$-norm:

######  Corollary 4.3.

For every $\epsilon>0$ and $\delta>0$, there exists a randomized algorithm
that computes, given a sequence $a_{1},\dots,a_{m}$ of $k$-tuples, in one pass
and using $O(3^{k}\epsilon^{-2}\log\frac{1}{\delta}(\log m+\log n))$ memory
bits, a number $Y$ so that the probability $Y$ deviates from the square of the
$\ell_{2}$ distance between product and joint distribution by more than a
factor of $(1+\epsilon)$ is at most $\delta$.

###  4.1. Analysis of the Sketch $Y$

This section is devoted to prove Lemma 4.1, where the main challenge is to
bound the variance of $Y$. The geometric approach of Indyk and McGregor [12]
presented in Section 3 for the case of $k=2$ can be extended to analyze the
general case. However, we remark that the generalization requires new ideas.
In particular, instead of performing “local analysis” that maps each rectangle
to its diagonals, a more complex “global analysis” is needed in higher
dimensions to achieve the desired bounds. The alternative proof we present
here utilizes similar ideas, but relies on a more combinatorial rather than
geometric approach.

For the expectation of $Y$, we have

$\displaystyle\mathrm{E}[Y]$ $\displaystyle=$
$\displaystyle\mathrm{E}\left[\sum_{{\mathbf{p}},{\mathbf{q}}\in[n]^{k}}{\vec{v}}_{{\mathbf{p}}}\cdot{\vec{v}}_{{\mathbf{q}}}\cdot
H({\mathbf{p}})\cdot H({\mathbf{q}})\right]$ $\displaystyle=$
$\displaystyle\sum_{{\mathbf{p}}\in[n]^{k}}\vec{v}_{{\mathbf{p}}}^{2}\cdot\mathrm{E}\left[H({\mathbf{p}})^{2}\right]+\sum_{{\mathbf{p}}\neq{\mathbf{q}}\in[n]^{k}}{\vec{v}}_{{\mathbf{p}}}\cdot{\vec{v}}_{{\mathbf{q}}}\cdot\mathrm{E}\left[H({\mathbf{p}})H({\mathbf{q}})\right]$
$\displaystyle=$
$\displaystyle\sum_{{\mathbf{p}}\in[n]^{k}}\vec{v}_{{\mathbf{p}}}^{2}=||{\vec{v}}||^{2},$

where the last equality follows by $H({\mathbf{p}})^{2}=1$, and
$\mathrm{E}\left[H({\mathbf{p}})H({\mathbf{q}})\right]=0$ for
${\mathbf{p}}\neq{\mathbf{q}}$.

Now, let us start to prove ${\mathrm{Var}}[Y]\leq 3^{k}\mathrm{E}[Y]^{2}$. By
definition, ${\mathrm{Var}}[Y]=\mathrm{E}[(Y-{\mathrm{E}}[Y])^{2}]$, so we
need to understand the following random variable:

$Err\equiv
Y-{\mathrm{E}}[Y]=\sum_{{\mathbf{p}}\neq{\mathbf{q}}\in[n]^{k}}H({\mathbf{p}})H({\mathbf{q}}){\vec{v}}_{{\mathbf{p}}}{\vec{v}}_{{\mathbf{q}}}.$
(3)

The random variable $Err$ is a sum of terms indexed by pairs
$({\mathbf{p}},{\mathbf{q}})\in[n]^{k}\times[n]^{k}$ with
${\mathbf{p}}\neq{\mathbf{q}}$. At a very high level, our analysis consists of
two steps. In the first step, we group the terms in $Err$ properly and
simplify the summation in each group. In the second step, we expand the square
of the sum in ${\mathrm{Var}}[Y]=\mathrm{E}[Err^{2}]$ according to the groups
and apply Cauchy-Schwartz inequality three times to bound the variance.

We shall now gradually introduce the necessary notation for grouping the terms
in $Err$ and simplifying the summation. We remind the reader that vectors over
the reals (e.g., ${\vec{v}}\in R^{n^{k}}$) are denoted by
${\vec{v}},\vec{w},\vec{r}$, and vectors over $[n]$ are denoted by
${\mathbf{p}},{\mathbf{q}},{\mathbf{a}},{\mathbf{b}},{\mathbf{c}},{\mathbf{d}}$
and referred as _index vectors_. We use $S\subseteq[k]$ to denote a subset of
$[k]$, and let ${\bar{S}}=[k]\backslash S$. We use
$\mathrm{Ham}({\mathbf{p}},{\mathbf{q}})$ to denote the _Hamming distance_ of
index vectors ${\mathbf{p}},{\mathbf{q}}\in[n]^{k}$, i.e., the number of
coordinates where ${\mathbf{p}}$ and ${\mathbf{q}}$ are different.

######  Definition 4.4.

_(Projection and inverse projection)_ Let ${\mathbf{c}}\in[n]^{k}$ be an index
vector and $S\subseteq[k]$ a subset. We define the _projection of
${\mathbf{c}}$ to $S$_, denoted by $\Phi_{S}({\mathbf{c}})\in[n]^{|S|}$, to be
the vector ${\mathbf{c}}$ restricted to the coordinates in $S$. Also, let
${\mathbf{a}}\in[n]^{|S|}$ and ${\mathbf{b}}\in[n]^{k-|S|}$ be index vectors.
We define the _inverse projection of ${\mathbf{a}}$ and ${\mathbf{b}}$ with
respect to $S$_, denoted by
$\Phi^{-1}_{S}({\mathbf{a}},{\mathbf{b}})\in[n]^{k}$, as the index vector
${\mathbf{c}}\in[n]^{k}$ such that $\Phi_{S}({\mathbf{c}})={\mathbf{a}}$ and
$\Phi_{{\bar{S}}}({\mathbf{c}})={\mathbf{b}}$.

We next define _pair groups_ and use the definition to group the terms in
$Err$.

######  Definition 4.5.

_(Pair Group)_ Let $S\subseteq[k]$ be a subset of size $|S|=t$. Let
${\mathbf{c}},{\mathbf{d}}\in[n]^{t}$ be a pair of index vectors with
$\mathrm{Ham}({\mathbf{c}},{\mathbf{d}})=t$ (i.e., all coordinates of
${\mathbf{c}}$ and ${\mathbf{d}}$ are distinct.). The _pair group_
$\sigma_{S}({\mathbf{c}},{\mathbf{d}})$ is the set of pairs
$({\mathbf{p}},{\mathbf{q}})\in[n]^{k}\times[n]^{k}$ such that (i) on
coordinate $S$, $\Phi_{S}({\mathbf{p}})={\mathbf{c}}$ and
$\Phi_{S}({\mathbf{q}})={\mathbf{d}}$, and (ii) on coordinate ${\bar{S}}$,
${\mathbf{p}}$ and ${\mathbf{q}}$ are the same, i.e.,
$\Phi_{{\bar{S}}}({\mathbf{p}})=\Phi_{{\bar{S}}}({\mathbf{q}})$. Namely,

$\sigma_{S}({\mathbf{c}},{\mathbf{d}})=\left\\{({\mathbf{p}},{\mathbf{q}})\in[n]^{k}\times[n]^{k}:\Big{(}{\mathbf{c}}=\Phi_{S}({\mathbf{p}})\Big{)}\wedge\Big{(}{\mathbf{d}}=\Phi_{S}({\mathbf{q}})\Big{)}\wedge\Big{(}\Phi_{{\bar{S}}}({\mathbf{p}})=\Phi_{{\bar{S}}}({\mathbf{q}})\Big{)}\right\\}.$
(4)

To give some intuition for the above definitions, we note that for every
${\mathbf{a}}\in[n]^{|{\bar{S}}|}$, there is a unique pair
$({\mathbf{p}},{\mathbf{q}})\in\sigma_{S}({\mathbf{c}},{\mathbf{d}})$ with
${\mathbf{a}}=\Phi_{{\bar{S}}}({\mathbf{p}})=\Phi_{{\bar{S}}}({\mathbf{q}})$,
and so $|\sigma_{S}({\mathbf{c}},{\mathbf{d}})|=n^{|{\bar{S}}|}$. On the other
hand, for every pair $({\mathbf{p}},{\mathbf{q}})\in[n]^{k}\times[n]^{k}$ with
${\mathbf{p}}\neq{\mathbf{q}}$, there is a unique non-emtpy $S\subseteq[k]$
such that ${\mathbf{p}}$ and ${\mathbf{q}}$ are distinct on exactly
coordinates in $S$. Therefore, $({\mathbf{p}},{\mathbf{q}})$ belongs to
exactly one pair group $\sigma_{S}({\mathbf{c}},{\mathbf{d}})$. It follows
that we can partition the summation in $Err$ according to the pair groups:

$Err=\sum_{\begin{subarray}{c}S\subseteq[k]\\\ S\neq\emptyset\end{subarray}}\
\ \ \ \ \sum_{\begin{subarray}{c}{\mathbf{c}},{\mathbf{d}}\in[n]^{|S|},\\\
\mathrm{Ham}({\mathbf{c}},{\mathbf{d}})=|S|\end{subarray}}\ \ \ \ \
\sum_{\begin{subarray}{c}({\mathbf{p}},{\mathbf{q}})\in\\\
\sigma_{S}({\mathbf{c}},{\mathbf{d}})\end{subarray}}H({\mathbf{p}})H({\mathbf{q}}){\vec{v}}_{{\mathbf{p}}}{\vec{v}}_{{\mathbf{q}}}.$
(5)

We next observe that for any pair
$({\mathbf{p}},{\mathbf{q}})\in\sigma_{S}({\mathbf{c}},{\mathbf{d}})$, since
${\mathbf{p}}$ and ${\mathbf{q}}$ agree on coordinates in ${\bar{S}}$, the
value of the product $H({\mathbf{p}})H({\mathbf{q}})$ depends only on $S$,
${\mathbf{c}}$ and ${\mathbf{d}}$. More precisely,

$H({\mathbf{p}})H({\mathbf{q}})=\prod_{i\in[k]}h_{i}(p_{i})h_{i}(q_{i})=\left(\prod_{i\in
S}h_{i}(p_{i})h_{i}(q_{i})\right)\cdot\left(\prod_{i\in{\bar{S}}}h_{i}(p_{i})^{2}\right)=\prod_{i\in
S}h_{i}(p_{i})h_{i}(q_{i}),$

which depends only on $S$, ${\mathbf{c}}$ and ${\mathbf{d}}$ since
$\Phi_{S}({\mathbf{p}})={\mathbf{c}}$ and
$\Phi_{S}({\mathbf{q}})={\mathbf{d}}$. This motivates the definition of
_projected hashing_.

######  Definition 4.6.

_(Projected hashing)_ Let $S=\\{s_{1},s_{2},\dots,s_{t}\\}$ be a subset of
$[k]$, where $s_{1}<s_{2}<\dots<s_{j}$. Let ${\mathbf{c}}\in[n]^{t}$. We
define the _projected hashing_ $H_{S}({\mathbf{c}})=\prod_{i\leq
t}h_{s_{i}}(c_{i})$.

We can now translate the random variable $Err$ as follows:

$Err=\sum_{\begin{subarray}{c}S\subseteq[k]\\\ S\neq\emptyset\end{subarray}}\
\ \ \ \ \sum_{\begin{subarray}{c}{\mathbf{c}},{\mathbf{d}}\in[n]^{|S|},\\\
\mathrm{Ham}({\mathbf{c}},{\mathbf{d}})=|S|\end{subarray}}\left(H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})\sum_{\begin{subarray}{c}({\mathbf{p}},{\mathbf{q}})\in\\\
\sigma_{S}({\mathbf{c}},{\mathbf{d}})\end{subarray}}{\vec{v}}_{{\mathbf{p}}}{\vec{v}}_{{\mathbf{q}}}\right).$
(6)

Fix a pair group $\sigma_{S}({\mathbf{c}},{\mathbf{d}})$, we next consider the
sum
$\sum_{\begin{subarray}{c}({\mathbf{p}},{\mathbf{q}})\in\sigma_{S}({\mathbf{c}},{\mathbf{d}})\end{subarray}}{\vec{v}}_{{\mathbf{p}}}{\vec{v}}_{{\mathbf{q}}}$.
Recall that for every ${\mathbf{a}}\in[n]^{|{\bar{S}}|}$, there is a unique
pair $({\mathbf{p}},{\mathbf{q}})\in\sigma_{S}({\mathbf{c}},{\mathbf{d}})$
with
${\mathbf{a}}=\Phi_{{\bar{S}}}({\mathbf{p}})=\Phi_{{\bar{S}}}({\mathbf{q}})$.
The sum can be viewed as the inner product of two vectors of dimension
$n^{|{\bar{S}}|}$ with entries indexed by ${\mathbf{a}}\in[n]^{|{\bar{S}}|}$.
To formalize this observation, we introduce the definition of _hyper-
projection_ as follows.

######  Definition 4.7.

_(Hyper-projection)_ Let ${\vec{v}}\in R^{n^{k}}$, $S\subseteq[k]$, and
$\mathbf{{\mathbf{c}}}\in[n]^{|S|}$. The _hyper-projection_
$\Upsilon_{S,{\mathbf{c}}}({\vec{v}})$ of ${\vec{v}}$ (with respect to $S$ and
${\mathbf{c}}$) is a vector $\vec{w}=\Upsilon_{S,{\mathbf{c}}}({\vec{v}})$ in
$\mathrm{R}^{[n]^{k-|S|}}$ such that
$\vec{w}_{{\mathbf{d}}}={\vec{v}}_{\Phi^{-1}_{S}({\mathbf{c}},{\mathbf{d}})}$
for all ${\mathbf{d}}\in[n]^{k-|S|}$.

Using the above definition, we continue to rewrite the $Err$ as

$Err=\sum_{\begin{subarray}{c}S\subseteq[k]\\\ S\neq\emptyset\end{subarray}}\
\ \ \ \ \sum_{\begin{subarray}{c}{\mathbf{c}},{\mathbf{d}}\in[n]^{|S|},\\\
\mathrm{Ham}({\mathbf{c}},{\mathbf{d}})=|S|\end{subarray}}H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})\cdot\langle\Upsilon_{S,{\mathbf{c}}}({\vec{v}}),\Upsilon_{S,{\mathbf{d}}}({\vec{v}})\rangle.$
(7)

Finally, we consider the product $H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})$
again and introduce the following definition to further simplify the $Err$.

######  Definition 4.8.

_(Similarity and dominance)_ Let $t$ be a positive integer.

  * •

Two pairs of index vectors
$({\mathbf{c}},{\mathbf{d}})\in[n]^{t}\times[n]^{t}$ and
$({\mathbf{a}},{\mathbf{b}})\in[n]^{t}\times[n]^{t}$ are _similar_ if for all
$i\in[t]$, the two sets $\\{c_{i},d_{i}\\}$ and $\\{a_{i},b_{i}\\}$ are equal.
We denote this as
$({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})$.

  * •

Let ${\mathbf{c}}$ and ${\mathbf{d}}\in[n]^{t}$ be two index vectors. We say
${\mathbf{c}}$ _is dominated by_ ${\mathbf{d}}$ if $c_{i}<d_{i}$ for all
$i\in[t]$. We denote this as ${\mathbf{c}}\prec{\mathbf{d}}$. Note that
${\mathbf{c}}\prec{\mathbf{d}}\Rightarrow\mathrm{Ham}({\mathbf{c}},{\mathbf{d}})=t$.

Now, note that if
$({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})$, then
$H_{S}({\mathbf{a}})H_{S}({\mathbf{b}})=H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})$
since the value of the product $H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})$
depends on the values $\\{c_{i},d_{i}\\}$ only as a set. It is also not hard
to see that $\sim$ is an equivalence relation, and for every equivalent class
$[({\mathbf{a}},{\mathbf{b}})]$, there is a unique
$({\mathbf{c}},{\mathbf{d}})\in[({\mathbf{a}},{\mathbf{b}})]$ with
${\mathbf{c}}\prec{\mathbf{d}}$. Therefore, we can further rewrite the $Err$
as

$Err=\sum_{\begin{subarray}{c}S\subseteq[k]\\\ S\neq\emptyset\end{subarray}}\
\sum_{{\mathbf{c}}\prec{\mathbf{d}}\in[n]^{|S|}}H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})\cdot\left(\sum_{({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})}\langle\Upsilon_{S,{\mathbf{a}}}({\vec{v}}),\Upsilon_{S,{\mathbf{b}}}({\vec{v}})\rangle\right).$
(8)

We are ready to bound the term $\mathrm{E}[Err^{2}]$ by expanding the square
of the sum according to Equation (8). We first show in Lemma 4.9 below that
all the cross terms in the following expansion vanish.

${\mathrm{Var}}[Y]=\sum_{\begin{subarray}{c}S,S^{\prime}\subseteq[k]\\\
S,S^{\prime}\neq\emptyset\end{subarray}}\
\sum_{\begin{subarray}{c}{\mathbf{c}}\prec{\mathbf{d}}\in[n]^{|S|}\\\
{\mathbf{c}}^{\prime}\prec{\mathbf{d}}^{\prime}\in[n]^{|S|^{\prime}}\end{subarray}}{\mathrm{E}}[H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})H_{S^{\prime}}({\mathbf{c}}^{\prime})H_{S^{\prime}}({\mathbf{d}}^{\prime})]\cdot$
$\left[\left(\sum_{({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})}\langle\Upsilon_{S,{\mathbf{a}}}({\vec{v}}),\Upsilon_{S,{\mathbf{b}}}({\vec{v}})\rangle\right)\left(\sum_{({\mathbf{a}}^{\prime},{\mathbf{b}}^{\prime})\sim({\mathbf{c}}^{\prime},{\mathbf{d}}^{\prime})}\langle\Upsilon_{S^{\prime},{\mathbf{a}}^{\prime}}({\vec{v}}),\Upsilon_{S^{\prime},{\mathbf{b}}^{\prime}}({\vec{v}})\rangle\right)\right].$
(9)

######  Lemma 4.9.

Let $S$ and $S^{\prime}$ be subsets of $[k]$, and
${\mathbf{c}}\prec{\mathbf{d}}\in[n]^{|S|}$ and
${\mathbf{c}}^{\prime}\prec{\mathbf{d}}^{\prime}\in[n]^{|S^{\prime}|}$ index
vectors. We have
$E[H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})H_{S^{\prime}}({\mathbf{c}}^{\prime})H_{S^{\prime}}({\mathbf{d}}^{\prime})]\in\\{0,1\\}$.
Furthermore, we have

${\mathrm{E}}[H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})H_{S^{\prime}}({\mathbf{c}}^{\prime})H_{S^{\prime}}({\mathbf{d}}^{\prime})]=1$
iff
$(S=S^{\prime})\wedge({\mathbf{c}}={\mathbf{c}}^{\prime})\wedge({\mathbf{d}}={\mathbf{d}}^{\prime})$.

######  Proof 4.10.

Recall that $h_{1},\dots,h_{k}$ are independent copies of $4$-wise independent
uniform random variables over $\\{-1,1\\}$. Namely, for every $i\in[k]$,
$h_{i}(1),\dots,h_{i}(n)$ are $4$-wise independent, and
$h_{1}(\cdot),\dots,h_{k}(\cdot)$ are mutually independent. Observe that for
every $i\in[k]$, there are at most $4$ terms out of $h_{i}(1),\dots,h_{i}(n)$
appearing in the product
$H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})H_{S^{\prime}}({\mathbf{c}}^{\prime})H_{S^{\prime}}({\mathbf{d}}^{\prime})$.
It follows that all distinct terms appearing in
$H_{S}({\mathbf{c}})H_{S}({\mathbf{d}})H_{S^{\prime}}({\mathbf{c}}^{\prime})H_{S^{\prime}}({\mathbf{d}}^{\prime})$
are mutually independent uniform random variable over $\\{-1,1\\}$. Therefore,
the expectation is either 0, if there is some $h_{i}(j)$ that appears an odd
number of times, or 1, if all $h_{i}(j)$ appear an even number of times. By
inspection, the latter case happens if and only if
$(S=S^{\prime})\wedge({\mathbf{c}}={\mathbf{c}}^{\prime})\wedge({\mathbf{d}}={\mathbf{d}}^{\prime})$.

By the above lemma, Equation (4.1) is simplified to

${\mathrm{Var}}[Y]=\sum_{\begin{subarray}{c}S\subseteq[k]\\\
S\neq\emptyset\end{subarray}}\
\sum_{{\mathbf{c}}\prec{\mathbf{d}}\in[n]^{|S|}}\left(\sum_{({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})}\langle\Upsilon_{S,{\mathbf{a}}}({\vec{v}}),\Upsilon_{S,{\mathbf{b}}}({\vec{v}})\rangle\right)^{2}.$
(10)

We next apply the Cauchy-Schwartz inequality three times to bound the above
formula. Consider a subset $S\subseteq[k]$ and a pair
${\mathbf{c}}\prec{\mathbf{d}}\in[n]^{|S|}$. Note that there are precisely
$2^{|S|}$ pairs $({\mathbf{a}},{\mathbf{b}})$ such that
$({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})$. Thus, by the
Cauchy-Schwartz inequality:

$\displaystyle\left(\sum_{\begin{subarray}{c}({\mathbf{a}},{\mathbf{b}})\in[n]^{|S|}\\\
({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})\end{subarray}}\langle\Upsilon_{S,{\mathbf{a}}}({\vec{v}}),\Upsilon_{S,{\mathbf{b}}}(\vec{v})\rangle\right)^{2}$
$\displaystyle\leq$ $\displaystyle
2^{|S|}\sum_{\begin{subarray}{c}({\mathbf{a}},{\mathbf{b}})\in[n]^{|S|}\\\
({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})\end{subarray}}(\langle\Upsilon_{S,{\mathbf{a}}},\Upsilon_{S,{\mathbf{b}}}\rangle)^{2}$
$\displaystyle\leq$ $\displaystyle
2^{|S|}\sum_{\begin{subarray}{c}({\mathbf{a}},{\mathbf{b}})\in[n]^{|S|}\\\
({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})\end{subarray}}\langle\Upsilon_{S,{\mathbf{a}}}({\vec{v}}),\Upsilon_{S,{\mathbf{a}}}({\vec{v}})\rangle\cdot\langle\Upsilon_{S,{\mathbf{b}}},\Upsilon_{S,{\mathbf{b}}}({\vec{v}})\rangle.$

Notice that in the second inequality, we applied Cauchy-Schwartz in a
component-wise manner. Next, for a subset $S\subseteq[k]$, we can apply the
Cauchy-Schwartz inequality a third time (from the third line to the fourth
line) as follows:

$\displaystyle\sum_{{\mathbf{c}}\prec{\mathbf{d}}\in[n]^{|S|}}\ \ \ \ \
\left(\sum_{\begin{subarray}{c}({\mathbf{a}},{\mathbf{b}})\in[n]^{|S|}\\\
({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})\end{subarray}}\langle\Upsilon_{S,{\mathbf{a}}}(\vec{v}),\Upsilon_{S,{\mathbf{b}}}(\vec{v})\rangle\right)^{2}$
$\displaystyle\leq$ $\displaystyle
2^{|S|}\sum_{{\mathbf{c}}\prec{\mathbf{d}}\in[n]^{|S|}}\ \ \
\sum_{\begin{subarray}{c}({\mathbf{a}},{\mathbf{b}})\in[n]^{|S|}\\\
({\mathbf{a}},{\mathbf{b}})\sim({\mathbf{c}},{\mathbf{d}})\end{subarray}}\langle\Upsilon_{S,{\mathbf{a}}}(\vec{v}),\Upsilon_{S,{\mathbf{a}}}(\vec{v})\rangle\cdot\langle\Upsilon_{S,{\mathbf{b}}}(\vec{v}),\Upsilon_{S,{\mathbf{b}}}(\vec{v})\rangle$
$\displaystyle=$ $\displaystyle
2^{|S|}\sum_{\begin{subarray}{c}{\mathbf{c}},{\mathbf{d}}\in[n]^{|S|}\\\
\mathrm{Ham}({\mathbf{c}},{\mathbf{d}})=|S|\end{subarray}}\langle\Upsilon_{S,{\mathbf{c}}}(\vec{v}),\Upsilon_{S,{\mathbf{c}}}(\vec{v})\rangle\cdot\langle\Upsilon_{S,{\mathbf{d}}}(\vec{v}),\Upsilon_{S,{\mathbf{d}}}(\vec{v})\rangle$
$\displaystyle\leq$ $\displaystyle
2^{|S|}\sum_{{\mathbf{c}},{\mathbf{d}}\in[n]^{|S|}}\langle\Upsilon_{S,{\mathbf{c}}}(\vec{v}),\Upsilon_{S,{\mathbf{c}}}(\vec{v})\rangle\cdot\langle\Upsilon_{S,{\mathbf{d}}}(\vec{v}),\Upsilon_{S,{\mathbf{d}}}(\vec{v})\rangle$
$\displaystyle=$ $\displaystyle
2^{|S|}\left(\sum_{{\mathbf{c}}\in[n]^{|S|}}\langle\Upsilon_{S,{\mathbf{c}}}(\vec{v}),\Upsilon_{S,{\mathbf{c}}}(\vec{v})\rangle\right)^{2}.$

Finally, we note that by definition, we have
$\sum_{{\mathbf{c}}\in[n]^{|S|}}\langle\Upsilon_{S,{\mathbf{c}}}(\vec{v}),\Upsilon_{S,{\mathbf{c}}}(\vec{v})\rangle=||{\vec{v}}||^{2}$,
which equals to $\mathrm{E}[Y]$. It follows that the variance in Equation (10)
can be bounded by

${\mathrm{Var}}[Y]\leq\sum_{S\subseteq[k],S\neq\emptyset}2^{|S|}\cdot\mathrm{E}[Y]^{2}=\mathrm{E}[Y]^{2}\sum_{i=1}^{k}{k\choose
i}2^{i}=(3^{k}-1)\mathrm{E}[Y]^{2},$

which finishes the proof of Lemma 4.1.

##  5\. Conclusion

There remain several open questions left in this space. Lower bounds,
particularly bounds that depend non-trivially on the dimension $k$, would be
useful. There may still be room for better algorithms for testing $k$-wise
independence in this manner using the $\ell_{2}$ norm. A natural
generalization would be to find a particularly efficient algorithm for testing
$k$-out-of-$s$-wise independence (other than handling each set of $k$ variable
separately). More generally, a question given in [12], to identify random
variables whose correlation exceeds some threshold according to some measure,
remains widely open.

## References

  * [1] Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie.  Testing k-wise and almost k-wise independence.  In STOC ’07: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pages 496–505, New York, NY, USA, 2007. ACM.
  * [2] Noga Alon, László Babai, and Alon Itai.  A fast and simple randomized parallel algorithm for the maximal independent set problem.  J. Algorithms, 7(4):567–583, 1986.
  * [3] Noga Alon, Oded Goldreich, and Yishay Mansour.  Almost k-wise independence versus k-wise independence.  Inf. Process. Lett., 88(3):107–110, 2003.
  * [4] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  J. Comput. Syst. Sci., 58(1):137–147, 1999.
  * [5] T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld, and P. White.  Testing random variables for independence and identity.  In FOCS ’01: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, page 442, Washington, DC, USA, 2001. IEEE Computer Society.
  * [6] Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld.  Sublinear algorithms for testing monotone and unimodal distributions.  In STOC ’04: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, pages 381–390, New York, NY, USA, 2004. ACM.
  * [7] Vladimir Braverman and Rafail Ostrovsky.  Measuring $k$-wise independence of streaming data.  CoRR, abs/0806.4790v1, 2008.
  * [8] Vladimir Braverman and Rafail Ostrovsky.  Measuring independence of datasets.  CoRR, abs/0903.0034, 2009.
  * [9] Vladimir Braverman and Rafail Ostrovsky.  AMS without $\bf{4}$-wise independence on product domains.  CoRR, abs/0806.4790v3, 2009.
  * [10] Kai-Min Chung, Zhenming Liu, and Michael Mitzenmacher.  Testing $k$-wise independence over streaming data.  Unpublished manuscript, available at http://www.eecs.harvard.edu/~michaelm/postscripts/sketchexttemp.pdf, 2009\.
  * [11] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  Technical report, Electronic Colloquium on Computational Complexity, 2000\.
  * [12] Piotr Indyk and Andrew McGregor.  Declaring independence via the sketching of sketches.  In SODA ’08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 737–745, Philadelphia, PA, USA, 2008\. Society for Industrial and Applied Mathematics.
  * [13] E. L. Lehmann and Springer.  Testing Statistical Hypotheses (Springer Texts in Statistics).  Springer, January 1997.
  * [14] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomized Algorithms and Probabilistic Analysis.  Cambridge University Press, New York, NY, USA, 2005.
  * [15] Ronitt Rubinfeld and Rocco A. Servedio.  Testing monotone high-dimensional distributions.  In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 147–156, New York, NY, USA, 2005. ACM.
  * [16] Mikkel Thorup and Yin Zhang.  Tabulation based 4-universal hashing with applications to second moment estimation.  In SODA ’04: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 615–624, Philadelphia, PA, USA, 2004\. Society for Industrial and Applied Mathematics.