# X-Mark: Towards Lossless Watermarking Through Lexical Redundancy

Liang Chen1, Yatao Bian2, Yang Deng3, Shuaiyi Li1, Bingzhe Wu2,
Peilin Zhao2, Kam-fai Wong1
1The Chinese University of Hong Kong, 2Tencent AI Lab 3National University of
Singapore,
<EMAIL_ADDRESS>
###### Abstract

Text watermarking has emerged as an important technique for detecting machine-
generated text. However, existing methods can severely degrade text quality
due to arbitrary vocabulary partitioning, which disrupts the language model’s
expressiveness and impedes textual coherence. To mitigate this, we introduce
X-Mark, a novel approach that capitalizes on text redundancy within the
lexical space. Specifically, X-Mark incorporates a mutually exclusive rule for
synonyms during the language model decoding process, thereby integrating prior
knowledge into vocabulary partitioning and preserving the capabilities of
language generation. We present theoretical analyses and empirical evidence
demonstrating that X-Mark substantially enhances text generation fluency while
maintaining watermark detectability. Furthermore, we investigate
watermarking’s impact on the emergent abilities of large language models,
including zero-shot and few-shot knowledge recall, logical reasoning, and
instruction following. Our comprehensive experiments confirm that X-Mark
consistently outperforms existing methods in retaining these crucial
capabilities of LLMs.

##  1 Introduction

The advent of large language models Ouyang et al. (2022); OpenAI (2023a) with
human-level generative capabilities presents tremendous opportunities across
diverse domains. However, their ability to synthesize high-quality text also
raises widespread concerns about potential misuse, including the propagation
of misinformation Zellers et al. (2019) and the facilitation of academic
dishonesty Stokel-Walker (2022). This necessitates developing techniques to
reliably attribute generated text to AI systems.

Figure 1: An illustration of X-Mark’s advantage for harmless watermarking. The
left panel shows a vanilla LM with all words available during generation. The
middle panel exposes the flaw in vanilla watermarking, which may assign all
suitable tokens (e.g., ’ocean’ and ’sea’) to the red list, diminishing text
quality. The right panel underlines how X-Mark exploits lexical redundancy by
applying a mutual exclusion rule between such words, guaranteeing at least one
suitable word remains on the green list, thereby improving text quality.

Existing approaches fall into two main paradigms. The first attempts to
distinguish machine-generated text by hunting for inductive statistical or
linguistic patterns (Gehrmann et al., 2019; Mitchell et al., 2023; Zellers et
al., 2019; OpenAI, 2023b), employing methods that span from basic manual
feature engineering to the intricate training of complex classifiers. However,
as generative models continue improving, their outputs increasingly resemble
the pattern of human writing, rendering statistical detectors ineffective (Dou
et al., 2022; Sadasivan et al., 2023; Chakraborty et al., 2023). The second
paradigm promotes a more proactive approach, advocating for direct
intervention in the generative process to actively watermark model outputs
(Kirchenbauer et al., 2023; Christ et al., 2023; Zhao et al., 2023). This
strategy embeds identifiable fingerprints within machine-generated text,
enabling provenance verification. As large language models’ capabilities
continue to burgeon, this approach proves more effective in governing machine-
generated text. However, introducing watermarks during text generation can
significantly impact output quality, which has been a consistent challenge for
model developers and regulators - how to effectively watermark while
preserving text quality.

Drawing analogies from the world of images and audio, it becomes apparent that
the ease of watermarking these mediums lies in their inherent redundancy. The
surplus pixels in image data, or the additional signals in audio data, provide
ample room for the integration of watermarks with minimal impact on the
overall quality of the content. Inspired by this, we turn our attention to the
redundancy found in textual data, with the aim of introducing watermarks that
maintain the generated text’s quality.

Nevertheless, the discrete and succinct nature of natural language text
presents significant challenges in identifying redundancy within. As an
alternative, we propose exploring the redundancy within the lexical
space—effectively the vocabulary dictionary of the language model—during the
decoding process. This lexical space encompasses a broad array of tokens that
share similar semantic or syntactic functions. These interchangeable tokens
can be grouped into clusters, each capable of conveying a specific semantic or
syntactic unit. As such, tokens within a cluster are fully interchangeable,
thereby explicitly establishing a redundant relationship with the other
clusters. This inherent redundancy serves as the starting point for our
watermarking process.

After identifying these redundancies, we exploit them via our novel algorithm,
X-Mark (Watermark with Exclusive Rules). X-Mark operates during each step of
text generation by randomly assigning at least one cluster from each semantic
or syntactic unit to what we term the green list (tokens within which are
encouraged to be used), while all other clusters are incorporated into the red
list (tokens within which are discouraged from use). Through the application
of mutual exclusion rules between these redundant token clusters, X-Mark
effectively exploits the redundant relationships identified during the
exploration phase, repurposing them into valuable spaces for watermark
information. This method is in line with successful watermarking techniques
used traditionally in audio and visual mediums, with the primary goal being
the preservation of the quality of the watermarked text.

Our main contributions are as follows:

  * •

Inspired by the harmlessness of image and audio watermarks—a characteristic
that we believe stems primarily from the inherent redundancy in multimedia
data—we introduce a related concept in NLP: lexical redundancy, which emerges
during the text generation process. Building on this concept, we propose three
approaches to explore this redundancy structure in the lexical space.

  * •

Capitalizing on our redundancy hypothesis and the mined lexical redundancy, we
meticulously crafted the X-Mark algorithm. This algorithm incorporates mutual
exclusion rules into the lexical space during the watermarking procedure,
allowing for the embedding of identifiable marks while preserving text
quality. Our theoretical analyses, backed by empirical evidence, demonstrate
that X-Mark significantly enhances generation ability.

  * •

Moving beyond text fluency, our study investigates the impact of watermarking
on the emergent abilities of Large Language Models. We believe these
abilities, which are unique to LLMs, are also the skills of utmost interest to
users in real-world scenarios. To effectively evaluate these abilities, we
employ Cattell’s cognitive theory, differentiating between crystallized and
fluid abilities. We gauge crystallized abilities through an assessment of the
LLMs’ knowledge capabilities, while fluid abilities are evaluated via
reasoning and instruction-following tasks. Extensive experiments demonstrate
that our approach consistently preserves these emergent abilities of LLMs.

##  2 Related Work

Early works on AI-generated text detection develop post-hoc detection methods
to analyze machine-generated text by treating the problem as a binary
classification task (OpenAI, 2019; Jawahar et al., 2020; Mitchell et al.,
2023; Bakhtin et al., 2019; Fagni et al., 2020). For instance, OpenAI has
fine-tuned RoBERTa-based (Liu et al., 2019) GPT-2 detector models to
distinguish between human and GPT-2 generated texts (OpenAI, 2019), though
such models necessitate fine-tuning for each new language model for reliable
detection.

Other works emphasize zero-shot AI-generated text detection, eliminating the
need for additional training by assessing the expected log probability of
individual tokens or passages and applying thresholding to identify AI-
generated content (Mitchell et al., 2023). However, existing detectors are
also found to be fragile against adversarial attacks (Wolff, 2020) and biased
towards non-native English writers (Liang et al., 2023). Moreover, as LLMs
continue to advance, their generated outputs more closely resemble human-
written text, rendering these post-hoc detection methods progressively less
effective.

On the other side, watermarking, traditionally a copyright marking tool, has
evolved into a process involving developers, users, and regulatory entities.
Developers start by choosing an algorithm to subtly embed hidden modifications
into data, which can be altered during user transmission. Regulatory bodies
can later extract this information to trace and regulate AI-generated content
(Atallah et al., 2001; Wilson et al., 2014; Hacker et al., 2023). In the
context of natural languages, watermarking typically involves modifying
content or structure. For example, rule-based methods (Stefan et al., 2000) or
carefully designed neural encoders (Yang et al., 2022; Ueoka et al., 2021)
encrypt messages into text, which are then extracted using the corresponding
rules and neural decoder. The discrete nature of natural language, however,
presents a considerable challenge to this approach, as modifications can
unintentionally degrade text quality or alter its intended meaning.

In the landscape of LLM-generated texts, a pioneering watermarking technique
(Kirchenbauer et al., 2023) establishes unique patterns by dividing tokens
into "green" and "red" lists. A watermarked LLM predominantly selects tokens
from the "green" list, generating patterns that are often invisible to humans.
Nevertheless, while yielding promising detection results, these methods may
still degrade textual quality and be vulnerable to the paraphrase attack.
Current efforts Christ et al. (2023); Sadasivan et al. (2023); Fernandez et
al. (2023); Zhao et al. (2023) in this field aim to develop more robust
watermarking methods capable of defending various user attacks.

Complementary to these approaches, our work contributes by focusing on the
creation of more harmless watermarks, striving to minimize the impact on the
capabilities of LLMs and the user experience.

##  3 Method

In this section, we first recap preliminaries in the text watermark. Then we
delve into the exploration of redundancy in the lexical space and show how to
exploit this redundancy to design a more harmless watermark algorithm for
large language models. Finally, we use mathematical analysis to explain the
advantages of our method.

###  3.1 Preliminary

The watermarking process comprises two crucial procedures: watermark embedding
and watermark detection. The embedding process entails developers
incorporating a watermark into the natural language sequence $\boldsymbol{y}$,
which is generated by a LLM $\mathcal{M}$ for a given prompt $\boldsymbol{x}$.
On the other hand, the detection process, executed by regulators, involves
extracting and identifying the watermark from the sequence $\boldsymbol{y}$,
with the objective of monitoring the generation of model $\mathcal{M}$. These
procedures are thoroughly explained in Algorithms 1 and 2, respectively, and
will be discussed below.

Algorithm 1 Watermark Encoding

Input: prompt $x_{1}\cdots x_{m}$, green list size $\gamma\in(0,1)$, watermark
strength $\delta>0$.

for $t=0,1,\cdots,n-1$ do

  1. 1.

Get the logit $\boldsymbol{\ell}_{t}\in\mathbb{R}^{|\mathcal{V}|}$ from
$\mathcal{M}$.

  2. 2.

Use the hash of the previous token as the random seed to partition the
vocabulary of $\mathcal{M}$ into a “green list” $G_{t}$ of size $\gamma|V|,$
and a “red list” $R_{t}$ of size $(1-\gamma)|V|$.

  3. 3.

Add $\delta$ to each green list logit and then apply softmax to the modified
logits.

$\hat{\boldsymbol{\ell}}_{t}[i]:=\boldsymbol{\ell}_{t}[i]+\delta,i\in G$
$\hat{\boldsymbol{p}}_{t}=softmax(\hat{\boldsymbol{\ell}}_{t})$

  4. 4.

Sample a next token $y_{t+1}$ from $\hat{\boldsymbol{p}}_{t}$.

end for

Output: watermarked text $y_{1}\cdots y_{n}$.

The watermarking process, detailed in Algorithm 1, is guided by two
parameters: $\gamma$ and $\delta$. Each decoding step partitions the
vocabulary into two categories: a green list which encourages usage, and a red
list which discourages usage. The parameter $\gamma$ determines the size of
the green list, while $\delta$ specifies the degree of encouragement for the
green list, i.e., the increase in logits attributed to the green list tokens.
As $\delta$ rises, the watermark becomes more detectable in the subsequent
detection process, but it may also compromise the quality of the generation.
In real-world regulatory scenarios, where complete detectability is required,
a large $\delta$ value is generally preferred.

The watermark detection process, described in Algorithm 2, computes the total
number of tokens in the suspect sequence $\boldsymbol{y}$ that belong to the
green list. This process begins with the null hypothesis $H_{0}$: The text
sequence is generated without adherence to the green list rule. A
$z$-statistic is then computed using Eq.1. If the $z$-score surpasses a pre-
specified threshold, the null hypothesis is rejected, and the watermark is
identified.

Algorithm 2 Watermark Detection

Input: text $\boldsymbol{y}$, detection threshold $\tau$.

1\. Use the previous token to find the “green list” $G_{t}$ at the step t as
in Algo. 1.

2\. Calculate the number of green tokens in $\boldsymbol{y}$ as
$|\boldsymbol{y}|_{G}=\sum_{t=1}^{n}\mathbbm{1}(y_{t}\in G)$.

3\. Compute the $z$-statistic:
$z_{\boldsymbol{y}}=\left(|\boldsymbol{y}|_{G}-\gamma
n\right)/\sqrt{n\gamma(1-\gamma)}.\vspace*{-2.8mm}$ (1)

4\. if $z_{\boldsymbol{y}}>\tau$ then return 1 (watermarked).

5\. else return 0 (unwatermarked).

Output: 0 or 1

###  3.2 Explore the Redundancy in Lexical Space

#### Concept of Lexical Redundancy

Inspired by the success of image watermarking, we hypothesize that identifying
redundancy within data can enable watermarking that doesn’t compromise text
quality. This hypothesis prompts us to explore opportunities within textual
data. However, detecting redundancy in natural language text is challenging
due to its discrete nature.

To address this challenge, we introduce a related concept in NLP: lexical
redundancy. This phenomenon typically arises during text generation when the
most appropriate word is selected from a large, pre-constructed vocabulary.
Often, this vast vocabulary includes numerous words with similar semantic and
syntactic functions — a feature that makes these words interchangeable,
thereby resulting in the inherent redundancy in the lexical space.

Our interest in exploring lexical redundancy is grounded in the understanding
that interchangeable synonyms, even when used in varied contexts, can deliver
similar or identical semantic or syntactic functions. This insight assists in
preserving the quality of text generation through an optimized watermark
embedding method. For instance, if a suitable word is allocated to the red
list, while its synonym is placed in the green list, then the language model
can still express the intended semantics or accomplish the necessary syntactic
functions. This understanding forms the primary motivation for investigating
lexical redundancy.

#### Constructing Redundant Lexical Clusters

To this end, we now focus on the construction of lexical redundancy. This
process involves automatically grouping tokens—each with similar semantic or
syntactic functions—from the language model’s vocabulary into clusters. Each
cluster, made up of interchangeable tokens, is designed to express a specific
semantic or syntactic unit.

To obtain high-quality redundant lexical clusters, we propose the following
two different methods: the dictionary-based method, and the prompting-based
method:

  * •

Dictionary-Based Method: Utilize external dictionaries, such as WordNet Miller
(1992) and Youdao Dictionary, to discover synonyms within the vocabulary.
These synonyms often can be substituted for each other, although there are
inevitably some cases where they cannot be interchanged due to polysemy. This
method is beneficial for exploiting established synonym relationships but is
limited to complete words due to its dependency on external resources.

  * •

Prompting-based Method: We prompt large language models, such as LLaMA2
Touvron et al. (2023), to infer synonyms for a given token by utilizing in-
context learning techniques Brown et al. (2020a), with the demonstrations
being annotated manually by us. After the inference process, we map the
acquired synonyms into the vocabulary to filter out synonyms not present in
it.

Cluster | Word1 | Word2 | Word3 | …
---|---|---|---|---
1 | car | motor | vehicle | …
2 | in | inside | within | …
… | … | … | … | …
n | token1 | token2 | token3 | …
Table 1: Example of the redundant lexical clusters. Each row represents a
cluster, composed of a set of semantically or syntactically similar words.

For a more intuitive understanding, refer to Table 1, where each row
represents a cluster composed of different interchangeable tokens. Note that a
token may appear in different clusters due to phenomena such as polysemy and
multiple-word classes. We manually assess the quality of these lexical
clusters in our experiments LABEL:cluster_quality.

#### Handling Subword Tokenization

Although a predominant method for model vocabulary construction and neural
text processing, subword tokenization presents significant challenges when it
comes to redundant lexical cluster mining. This approach, which adopts a
hybrid methodology of word tokenization and character tokenization, is key for
balancing vocabulary size and learning meaningful representations in the
transformer architecture. Three widely used subword tokenizers exist,
including Byte-Pair Encoding (BPE) Sennrich et al. (2016), WordPiece Schuster
and Nakajima (2012), and SentencePiece Kudo and Richardson (2018). Despite
their individual differences, all these tokenizers follow a common principle:
they preserve frequently used words as whole units while rare words are broken
down into meaningful subwords.

Leveraging this principle, in this study, we address the challenges posed by
subwords by prioritizing frequently used, intact words. This is achieved by
first identifying these words in the vocabulary and maintaining their
wholeness during the preprocessing stage. Subwords that do not form complete
words are then disregarded, which minimizes noise and reduces unnecessary
complexity in our models. This approach enables our algorithm to focus on
these common words, thereby circumventing difficulties posed by subwords and
enhancing the overall quality of our lexical cluster mining.

#### Incorporating Grammatical Factors

In the process of mining interchangeable words in English, the consideration
extends beyond semantic similarity to include grammatical factors such as
tense, voice, and number. These elements significantly influence the
interchangeability among words. For instance, while ’car’ and ’vehicles’ are
very semantically similar, a direct substitution could often cause grammatical
errors due to their difference in number agreement.

In response to this challenge, we meticulously devise a set of explicit rules
to eliminate words with inconsistent grammatical features - namely tense,
voice, number, and capitalization - during the process of mining for
interchangeable words. This strategy assures the creation of high-quality
redundant clusters, providing a solid foundation for future use.

###  3.3 X-Mark: Exploit the Lexical Redundancy

Having constructed redundant clusters within the lexical space, we now turn to
exploit these for a harmless watermark algorithm.

To facilitate the description of our algorithm, we provide some definitions: A
subset $S\subseteq\mathcal{V}$ is defined within the vocabulary $\mathcal{V}$
of a language model $\mathcal{M}$. This subset specifically comprises complete
tokens that share synonyms within the vocabulary. We then denote a collection
of redundant lexical clusters we mined as $C=\\{C_{i}\mid i=1..n\\}$ such that
$\bigcup_{i=1}^{n}C_{i}=S$. Each cluster, $C_{i}$, is represented as a token
collection $C_{i}=\\{s_{ij}\mid j=1..m_{i},s_{ij}\in S\\}$ for $i=1..n$, and
any pair of tokens $s_{ij},s_{ik}\in C_{i}$ are interchangeable. We propose to
implement our understanding of harmless watermarks by introducing a mutual
exclusion rule building on the identified lexical clusters: interchangeable
tokens are mutually exclusive during partitioning. In other words, if a
fraction of tokens $\mathcal{A}$, representing a certain semantic or syntactic
function, is assigned to the red list, then their remaining synonyms
$\mathcal{B}$ should be placed on the green list, and vice versa.

We then detail the X-Mark encoding process, outlined in Algorithm 3, which
employs a two-step partitioning process to form a green and red list. The
first partition occurs within the redundant lexical clusters $C$ that we have
identified within $S$, while the second takes place among the remaining part
in the vocabulary denoted as $\mathcal{V}\setminus\mathcal{S}$. We use $gamma$
to determine the number of tokens from the mined clusters that are allocated
to the green list $G_{t}^{\prime}$ in the first partition. The remaining
tokens, based on the principle of mutual exclusivity, are assigned to the red
team $R_{t}^{\prime}$. The second partition continues to allocate words to the
green list $G_{t}$ from the remaining vocabulary until the combined size of
the green teams from both steps reaches the predefined limit, $\gamma$. The
rest of the process follows the steps outlined in Algorithm 1.

Algorithm 3 X-Mark Encoding

Input: prompt $x_{1}\cdots x_{m}$, green list size $\gamma\in(0,1)$, watermark
strength $\delta>0$.

for $t=0,1,\cdots,n-1$ do

  1. 1.

Get the logit $\boldsymbol{\ell}_{t}\in\mathbb{R}^{|\mathcal{V}|}$ from
$\mathcal{M}$.

  2. 2.

Compute a random seed from the previous token. Then, for each redundant
lexical cluster $C_{i}$ with the subset $\mathcal{S}$, partition it into a
green list $G_{t}^{\prime}$ of size $|C_{i}|\gamma$ and a red list
$R_{t}^{\prime}$ of size $|C_{i}|-|G_{t}|$.

  3. 3.

Compute a distinct seed from the previous token. Then, partition the remaining
part of the vocabulary $\mathcal{V}\setminus\mathcal{S}$ into a green list
$G_{t}$ of size $\gamma|V|-|G_{t}^{\prime}|$ and a red list $R_{t}$ of size
$(1-\gamma)|V|-|R_{t}^{\prime}|$.

  4. 4.

Merge the green and red lists from the previous two steps: $G_{t}=G_{t}\cup
G_{t}^{\prime}$ and $R_{t}=R_{t}\cup R_{t}^{\prime}$.

  5. 5.

Add $\delta$ to each green list logit and then apply softmax to the modified
logits.

$\hat{\boldsymbol{\ell}}_{t}[i]:=\boldsymbol{\ell}_{t}[i]+\delta,i\in G$
$\hat{\boldsymbol{p}}_{t}=softmax(\hat{\boldsymbol{\ell}}_{t})$

  6. 6.

Sample a next token $y_{t+1}$ from $\hat{\boldsymbol{p}}_{t}$.

end for

Output: watermarked text $y_{1}\cdots y_{n}$.

The X-Mark detection algorithm is similar to Algorithm 2, except that the
calculation of the green list in each step is replaced with the two-step
calculation from Algorithm 1.

###  3.4 Theoretical Analysis

We now present a mathematical analysis demonstrating why X-Mark consistently
yields superior text generation fluency compared to the vanilla watermarking
method.

###### Assumption 3.1

We consider practical scenarios that require complete detectability, and thus
a large value of $\delta$. In such a strong watermarking scenario, tokens from
the green list are more probable to be used than those from the red list.

Based on these assumptions, we propose a theorem suggesting that the X-Mark
method yields a lower expected PPL than the vanilla watermark method.

###### Theorem 3.2

Consider a tested language model (LM) $\mathcal{M}$, where
$\boldsymbol{p}_{t}\in\mathbb{R}^{|\mathcal{V}|}$ represents the predicted
distributions of $\mathcal{M}$ at decoding time $t$. Let $w_{i}$ denote the
token with the $i^{th}$ highest probability in $\boldsymbol{p}_{t}$. The
higher the rank of a token (i.e., the smaller $i$ is), the more suitable it is
to be selected. Under the conditions of Assumption 3.1, the X-Mark
watermarking method is more likely to select a suitable token compared to the
vanilla watermarking method.

  * Proof

let ’X’ and ’V’ denote the X-Mark and vanilla watermarking methods,
respectively. We articulate this proof by considering two possible cases for
$i=1,2$:

    1. 1.

Case where $w_{1}$ is in the green list ($G_{t}$):

If $w_{1}\in G_{t}$, then both watermarking methods are lossless because they
can select the most suitable token $w_{1}$.

    2. 2.

Case where $w_{1}$ is in the red list ($R_{t}$):

We consider $w_{2}$, which may or may not be a synonym of $w_{1}$:

      1. (a)

Sub-case 1: $w_{2}$ is not a synonym of $w_{1}$.

If $w_{1}\notin G_{t}$ and $\centernot\exists C_{i}\in\mathcal{C}$ s.t.
$w_{1},w_{2}\in C_{i}$, then according to Algo. 3 we have:

$\displaystyle P_{X}(w_{2}\in G_{t})$ $\displaystyle=P_{V}(w_{2}\in G_{t}).$

In this case, the two methods are the same.

      2. (b)

Sub-case 2: $w_{2}$ is a synonym of $w_{1}$.

If $w_{1}\notin G_{t}$ and $\exists C_{i}\in\mathcal{C}$ s.t. $w_{1},w_{2}\in
C_{i}$, then according to Algo. 3 we have:

$\displaystyle P_{X}(w_{2}\in G_{t})$ $\displaystyle>P_{V}(w_{2}\in G_{t}).$

In this case, X-Mark is more likely to select the suitable token.

Combining these cases, the theorem is proven. It should be noted that while
this proof explicitly considers the cases for $i=1,2$, the logic extends to
any arbitrary value of $i$.

##  4 Impact on Emergent Abilities

Watermarks not only impact the fluency of text generation but also hold the
potential to influence LLMs on a broader scale, such as emergent abilities.
These unique abilities intrinsic to LLMs garner significant interest from
users and stimulate curiosity within the research community. However, they are
often overlooked by researchers in the field of watermarking algorithms.

Although a consensus definition is lacking, emergent abilities are typically
characterized in many studies Brown et al. (2020b); Wei et al. (2022); Yu et
al. (2023) as a model’s capacity to perform specific tasks through zero-shot
or few-shot in-context learning. In light of this, we propose to test and
compare the performance of X-Mark and Vanilla watermark algorithms on
different tasks using both zero-shot and few-shot approaches.

To comprehensively test the impact of watermarking on these abilities, we
attempt to categorize it into different scenarios for a more exhaustive
examination. Specifically, we draw upon Cattell’s cognitive theory Cattell
(1963), which bifurcates intelligence into crystallized and fluid
intelligence. Crystallized intelligence corresponds to the model’s utilization
of learned knowledge and experience, while fluid intelligence involves logical
thinking and solving problems. Correspondingly, we propose to examine
crystallized intelligence through an assessment of the model’s knowledge
capabilities, and fluid intelligence through its ability to reason and solve
mathematical problems.

#### Knowledge Capability.

To evaluate the model’s mastery of world knowledge, we employ TruthfulQA Lin
et al. (2022), a benchmark designed to test if LLMs can generate truthful and
informative answers. This benchmark offers both a multiple-choice and a
generation setting, of which we opt for the latter.

#### Reasoning Capability.

We utilize the GSM8K dataset to examine the model’s chain-of-thought reasoning
abilities. This dataset, comprising 8K arithmetic and mathematical problems,
provides a platform to assess the model’s reasoning performance. In alignment
with the methodology from the CoT HubFu et al. (2023), our evaluations include
few-shot scenarios where the model provides demonstrations to stimulate
reasoning and generate coherent chains of thought.

##  5 Experiment

###  5.1 Experimental Setups

#### Evaluation Metrics

To evaluate detection performance, following previous work, we use the Area
Under the Receiver Operating Characteristic curve (AUROC), a well-established
metric for binary classifiers. For mathematical reasoning tasks, we employ an
accuracy metric to assess the correctness of the model’s solutions. In our
evaluation of the TruthfulQA dataset, following the methodology of Lin et al.
(2022), we apply the GPT-Truth and GPT-Info scores, assessing the model’s
capacity to generate both truthful and informative responses. Given the
potential trade-off between these two qualities, we often use their product
(truth.*info.) as an overall performance metric to balance truthfulness and
informativeness effectively.

Model | GSM8K | TruthfulQA
---|---|---
Acc. | AUROC | True. | Info. | True.*Info. | AUROC
Llama2-7b | 11.22 | - | 99.51 | 95.84 | 95.37 | -
+ Watermark | 5.61 | 0.8886 | 56.30 | 74.66 | 42.03 | 0.7425
+ X-Markdictionary | 9.17 | 0.8995 | 58.75 | 91.43 | 53.72 | 0.7438
+ X-Markprompting | 5.84 | 0.9128 | 46.88 | 95.35 | 44.70 | 0.7540
vicuna-7b | 17.51 | - | 99.61 | 97.84 | 97.45 | -
+ Watermark | 13.87 | 0.7870 | 72.83 | 79.80 | 58.12 | 0.6908
+ X-Markdictionary | 14.78 | 0.8044 | 68.91 | 96.45 | 66.46 | 0.7278
+ X-Markprompting | 16.22 | 0.7843 | 67.07 | 93.76 | 62.88 | 0.6656
Table 2: Performance of Llama2-7B on GSM8K and TruthfulQA: Comparison of the
original model with versions incorporating Vanilla and X-Mark watermarks,
under gamma=0.3 and delta=3.0. Under watermark, results that are underlined
and in bold represent the highest and second highest performances across
various metrics, respectively.

###  5.2 Main Results

#### Detrimental Impact of Vanilla Watermark on Emergent Abilities

Experimental results emphasize that the Vanilla Watermark, despite maintaining
acceptable detection performance, significantly impedes the emergent abilities
of LLMs. Specifically, LLAMA2-7B experienced a 50% reduction in accuracy on
the GSM8K dataset, and a marked 55.9% decrease in the overall performance
(measured by truth*info) on the TruthfulQA dataset. These findings suggest
that the Vanilla Watermark detrimentally impacts both the crystallized and
fluid intelligence of LLMs, underscoring its negative effect on these emergent
abilities.

#### Superiority of X-Mark over Vanilla Watermark in Preserving Emergent
Abilities

Across all experimental settings, models utilizing the X-Mark watermarking
technique consistently outperformed those applying the traditional Vanilla
Watermark. Specifically, the optimal performance of our algorithm improved the
degradation in the LLAMA2-7B model’s performance from a 50.0% reduction to an
18.3% reduction on the GSM8K dataset, and from a 55.9% decrease to a 43.7%
decrease in overall performance on the TruthfulQA dataset. These results
highlight the effectiveness of the X-Mark in preserving the emergent abilities
of LLMs.

#### Comparable Detection Performance of X-Mark and Vanilla Watermark

Our empirical evaluations also revealed that the detection performance of the
X-Mark algorithm was on par with that of the Vanilla Watermark. This was
evidenced by the AUROC scores. The different implementations of X-Mark
(dictionary and prompting techniques) showed consistent results. This
indicates that X-Mark’s enhancements for LLMs do not compromise its core
watermarking functionality.

#### Distinct Advantages of X-Mark Variations

The empirical results indicate distinct advantages associated with different
X-Mark variations. The ’dictionary’ variation yielded superior performance in
terms of accuracy and informativeness, while the ’prompting’ variation
achieved the highest AUROC score. This underscores the flexibility of the
X-Mark approach, suggesting its potential for customization according to
specific applications or requirements.

#### Impact of Alignment on Model Robustness Against Watermarks

The robustness of aligned models against the impact of watermarks is
significantly better than their non-aligned counterparts. This is evident when
comparing the aligned VICUNA-7B model with the non-aligned LLAMA2-7b model. As
demonstrated in the table2, even with the incorporation of Vanilla watermarks,
the performance of the VICUNA-7B model on the GSM8k and TruthfulQA did not
significantly degrade with the introduction of watermarks, indicating its
resilience to potential watermark damage. This demonstrates the effectiveness
of model alignment in mitigating the impact of watermarks, thereby enhancing
the robustness of models.

##  6 Discussion

###  6.1 Impact of Hyperparameter

Figure 2: Performance comparison between X-Mark and Vanilla Watermark on
TruthfulQA and GSM8K at different Delta values.

The performance of X-Mark and Vanilla Watermark is influenced by the
hyperparameter, Delta, which controls the strength of the watermark. As Delta
increases, watermark detection becomes easier but at the cost of severer
impact on the LLMs.

Our experiments across different Delta values on TruthfulQA and GSM8K datasets
show that X-Mark consistently outperforms Vanilla Watermark in terms of
accuracy and AUROC, indicating a stronger robustness to changes in watermark
strength. X-Mark also matches Vanilla Watermark’s detection performance across
all Delta values, suggesting that increased watermark strength does not
compromise its detection efficacy.

###  6.2 Time Complexity Analysis

The conventional algorithm necessitates a partition of the vocabulary per
decoding operation, which results in a time complexity of $O(|V|)$. Our method
incorporates two partitioning stages: initially targeting the redundant
cluster, followed by the remaining vocabulary. During the first stage, we pad
the cluster into a 2D matrix and conduct parallel sampling. The subsequent
stage aligns with the procedures of the Vanilla algorithm. Consequently, the
time complexity of our method remains at $O(|V|)$.

##  7 Conclusion

This study crucially explores the impact of watermarking on the emergent
abilities of LLMs—an aspect often neglected in the field. Our findings
highlight the considerable adverse effects of traditional watermarking methods
on LLMs’ emergent abilities, including knowledge recall, logical reasoning,
and instruction following.

In response, we introduced X-Mark—a novel, lossless watermarking approach that
leverages lexical redundancy. Theoretical analysis and empirical evidence from
our research indicate that X-Mark not only preserves but also enhances the
emergent abilities of LLMs.

Our comprehensive experimental results confirm that X-Mark consistently
surpasses existing methods in preserving these key abilities, marking a
significant leap in balancing watermarking with the cognitive capabilities of
LLMs. We anticipate that future investigations will continue refining these
techniques, aiming for an optimal balance between watermark detectability and
the preservation of LLMs’ emergent abilities.

## References

  * Atallah et al. (2001) Mikhail J Atallah, Victor Raskin, Michael Crogan, Christian Hempelmann, Florian Kerschbaum, Dina Mohamed, and Sanket Naik. 2001.  Natural language watermarking: Design, analysis, and a proof-of-concept implementation.  In _Information Hiding: 4th International Workshop, IH 2001 Pittsburgh, PA, USA, April 25–27, 2001 Proceedings 4_ , pages 185–200. Springer.
  * Bakhtin et al. (2019) Anton Bakhtin, Sam Gross, Myle Ott, Yuntian Deng, Marc’Aurelio Ranzato, and Arthur Szlam. 2019.  Real or fake? learning to discriminate machine from human generated text.  _arXiv preprint arXiv:1906.03351_.
  * Brown et al. (2020a) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020a.  Language models are few-shot learners.
  * Brown et al. (2020b) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020b.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165.
  * Cattell (1963) Raymond B. Cattell. 1963.  Theory of fluid and crystallized intelligence: A critical experiment.  _Journal of Educational Psychology_ , 54(1):1–22.  ShortDOI: 10/fs6ptd KerkoCite.ItemAlsoKnownAs: 10.1037/h0046743 10/fs6ptd 1963-07991-001 2339240:TGQK3VJY 2405685:C8ZBFK3U.
  * Chakraborty et al. (2023) Souradip Chakraborty, Amrit Singh Bedi, Sicheng Zhu, Bang An, Dinesh Manocha, and Furong Huang. 2023.  On the possibilities of ai-generated text detection.
  * Christ et al. (2023) Miranda Christ, Sam Gunn, and Or Zamir. 2023.  Undetectable watermarks for language models.  _arXiv preprint arXiv:2306.09194_.
  * Dou et al. (2022) Yao Dou, Maxwell Forbes, Rik Koncel-Kedziorski, Noah A. Smith, and Yejin Choi. 2022\.  Is gpt-3 text indistinguishable from human text? scarecrow: A framework for scrutinizing machine text.
  * Fagni et al. (2020) T Fagni, F Falchi, M Gambini, A Martella, and M Tesconi. 2020.  Tweepfake: About detecting deepfake tweets. arxiv.  _arXiv preprint arXiv:2008.00036_.
  * Fernandez et al. (2023) Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. 2023.  Three bricks to consolidate watermarks for large language models.
  * Fu et al. (2023) Yao Fu, Litu Ou, Mingyu Chen, Yuhao Wan, Hao Peng, and Tushar Khot. 2023.  Chain-of-thought hub: A continuous effort to measure large language models’ reasoning performance.  _CoRR_ , abs/2305.17306.
  * Gehrmann et al. (2019) Sebastian Gehrmann, Hendrik Strobelt, and Alexander M. Rush. 2019.  Gltr: Statistical detection and visualization of generated text.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Hacker et al. (2023) Philipp Hacker, Andreas Engel, and Marco Mauer. 2023.  Regulating chatgpt and other large generative ai models.
  * Jawahar et al. (2020) Ganesh Jawahar, Muhammad Abdul-Mageed, and Laks V. S. Lakshmanan. 2020.  Automatic detection of machine generated text: A critical survey.  In _International Conference on Computational Linguistics_.
  * Kirchenbauer et al. (2023) John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. 2023.  A watermark for large language models.  _International Conference on Machine Learning_.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.
  * Liang et al. (2023) Weixin Liang, Mert Yuksekgonul, Yining Mao, Eric Wu, and James Y. Zou. 2023.  Gpt detectors are biased against non-native english writers.  _ArXiv_ , abs/2304.02819.
  * Lin et al. (2022) Stephanie Lin, Jacob Hilton, and Owain Evans. 2022.  Truthfulqa: Measuring how models mimic human falsehoods.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Miller (1992) George A. Miller. 1992.  WordNet: A lexical database for English.  In _Speech and Natural Language: Proceedings of a Workshop Held at Harriman, New York, February 23-26, 1992_.
  * Mitchell et al. (2023) Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D. Manning, and Chelsea Finn. 2023.  Detectgpt: Zero-shot machine-generated text detection using probability curvature.  _ArXiv_ , abs/2301.11305.
  * OpenAI (2019) OpenAI. 2019.  Gpt-2: 1.5b release.
  * OpenAI (2023a) OpenAI. 2023a.  Gpt-4 technical report.  _ArXiv_ , abs/2303.08774.
  * OpenAI (2023b) OpenAI. 2023b.  New ai classifier for indicating ai-written text.  _OpenAI blog_.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. 2022\.  Training language models to follow instructions with human feedback.  _ArXiv_ , abs/2203.02155.
  * Sadasivan et al. (2023) Vinu Sankar Sadasivan, Aounon Kumar, S. Balasubramanian, Wenxiao Wang, and Soheil Feizi. 2023.  Can ai-generated text be reliably detected?  _ArXiv_ , abs/2303.11156.
  * Schuster and Nakajima (2012) Mike Schuster and Kaisuke Nakajima. 2012.  Japanese and korean voice search.  _2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 5149–5152.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.
  * Stefan et al. (2000) Katzenbeisser Stefan, AP Fabien, et al. 2000.  Information hiding techniques for steganography and digital watermarking.
  * Stokel-Walker (2022) Chris Stokel-Walker. 2022.  Ai bot chatgpt writes smart essays - should professors worry?  _Nature_.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023.  Llama 2: Open foundation and fine-tuned chat models.
  * Ueoka et al. (2021) Honai Ueoka, Yugo Murawaki, and Sadao Kurohashi. 2021.  Frustratingly easy edit-based linguistic steganography with a masked language model.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5486–5492, Online. Association for Computational Linguistics.
  * Wei et al. (2022) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. 2022\.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_.
  * Wilson et al. (2014) Alex Wilson, Phil Blunsom, and Andrew D Ker. 2014.  Linguistic steganography on twitter: hierarchical language modeling with manual interaction.  In _Media Watermarking, Security, and Forensics 2014_ , volume 9028, pages 9–25.
  * Wolff (2020) Max Wolff. 2020.  Attacking neural text detectors.  _ArXiv_ , abs/2002.11768.
  * Yang et al. (2022) Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. 2022.  Tracing text provenance via context-aware lexical substitution.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 11613–11621.
  * Yu et al. (2023) Wenhao Yu, Dan Iter, Shuohang Wang, Yichong Xu, Mingxuan Ju, Soumya Sanyal, Chenguang Zhu, Michael Zeng, and Meng Jiang. 2023.  Generate rather than retrieve: Large language models are strong context generators.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. 2019.  Defending against neural fake news.  _Advances in neural information processing systems_ , 32.
  * Zhao et al. (2023) Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. 2023.  Provable robust watermarking for ai-generated text.


Identifying Correlation in Stream of Samples

Gu Zhenhao111School of Computing, National University of Singapore. Email:
<EMAIL_ADDRESS>Zhang Hao

###### Abstract

Identifying independence between two random variables or correlated given
their samples has been a fundamental problem in Statistics. However, how to do
so in a space-efficient way if the number of states is large is not quite
well-studied.

We propose a new, simple counter matrix algorithm, which utilize hash
functions and a compressed counter matrix to give an unbiased estimate of the
$\ell_{2}$ independence metric. With
$\mathcal{O}(\epsilon^{-4}\log\delta^{-1})$ (very loose bound) space, we can
guarantee $1\pm\epsilon$ multiplicative error with probability at least
$1-\delta$. We also provide a comparison of our algorithm with the state-of-
the-art sketching of sketches algorithm and show that our algorithm is
effective, and actually faster and at least 2 times more space-efficient.

##  1 Introduction

In this paper, we try to check whether two (or more) random variables are
independent based on their samples in a data stream. More specifically, given
a stream of pairs $(i,j)$, where $i,j\in[n]^{2}$, and $(i,j)$ follows a joint
distribution $(X,Y)$, we want to check if $X$ and $Y$ are independent, i.e.
$\Pr[X=i,Y=j]=\Pr[X=i]\Pr[Y=j]$ for all $i,j\in[n]^{2}$.

This is a fundamental problem with a lot of applications in network
monitoring, sensor networks, economic/stock market analysis, and communication
applications, etc.

For simplicity, we define matrix $r$ and $s$ where $r_{ij}=\Pr[X=i,Y=j]$ and
$s_{ij}=\Pr[X=i]\Pr[Y=j]$. Now, to measure how close $X$ and $Y$ are to
independence, we have three metrics[3]:

  1. 1.

$\ell_{1}$ difference: The sum of absolute difference of the joint
distribution and the product distribution, similar to the $\ell_{1}$-norm of
vectors,

$|\Delta|=|r-s|=\sum_{i,j}|r_{ij}-s_{ij}|$

  2. 2.

$\ell_{2}$ difference: The sum of squared difference of the joint distribution
and the product distribution, taken square root, similar to the
$\ell_{2}$-norm of vectors,

$\lVert\Delta\rVert=\lVert r-s\rVert=\sqrt{\sum_{i,j}(r_{ij}-s_{ij})^{2}}$

  3. 3.

Mutual information: defined by $I(X;Y)=H(X)-H(X\mid Y)$, where
$H(X)=-\sum_{i=1}^{n}\Pr[X=1]\log\Pr[X=i]$ is the entropy of distribution $X$
and

$H(X\mid Y)=\sum_{i,j}\Pr[X=i,Y=j]\log\frac{\Pr[Y=j]}{\Pr[X=i,Y=j]}$

is the conditional entropy.

All metrics should be zero if $X$ and $Y$ are independent, and further away
from 0 if $X$ and $Y$ are further away from independence (higher correlation).
Our goal then reduces to give an estimation of the value of these metrics, and
check if it is small enough to conclude independence between $X$ and $Y$.

Our work in this paper involves the following:

  1. 1.

Implement the state-of-the-art sketching of sketches algorithm proposed by
Indyk and McGregor [3].

  2. 2.

Propose a novel counter matrix algorithm that store the frequency of each pair
$(i,j)$ in a compressed counter matrix and calculate an unbiased estimate for
the $\ell_{2}$ difference, and

  3. 3.

implement the counter matrix algorithm, and compare the result with the
sketching of sketches algorithm.

To avoid confusion, we summarize the notation used in the report as follows:

Notation | Meaning
---|---
$X,Y$ | Two random variables whose correlation we are trying to identify
$n$ | Range of $X$ and $Y$ should be $[1,n]$.
$p_{i}$ | Probability of $X$ taking value $i$, $\Pr[X=i]$
$q_{j}$ | Probability of $Y$ taking value $j$, $\Pr[Y=j]$
$s_{i,j}$ | Probability of $(i,j)$ appearing in the stream, $\Pr[X=i,Y=j]$
$r_{i,j}$ | Product of marginal probabilities, $\Pr[X=i]\Pr[Y=j]$
$\Delta_{i,j}$ | Difference between joint probability and product probability, $s_{i,j}-r_{i,j}$
$A$ | Size of counter matrix
$B$ | Number of counter matrices to run
$\hat{p},\hat{q},\hat{s},\hat{\Delta}$ | Estimator of $p,q,s,\Delta$ calculated by the full $n\times n$ counter matrix
$\tilde{p},\tilde{q},\tilde{s},\tilde{\Delta}$ | Estimator of $\hat{p},\hat{q},\hat{s},\hat{\Delta}$ calculated by the truncated $A\times A$ counter matrix
$n_{i,j}$ | The number of time each pair $(i,j)$ appears in the stream
$C_{i,j}$ | The value in the counter matrix on the $i^{\text{th}}$ row and $j^{\text{th}}$ column
$\sum C_{i,\cdot},\sum C_{\cdot,j}$ | The sum of values in the $i^{\text{th}}$ row, $j^{\text{th}}$ column in $C$, respectively
$N$ | Length of the stream
Table 1: Notations

##  2 Related Work

Indyk and McGregor were the first to try to identify the correlation between
sample in data stream using sketching algorithms [3]. They propose an estimate
for the above matrices,

###  2.1 $\ell_{2}$ Difference

The paper mainly utilizes the result that the weighted sum of 4-wise
independent vectors $x,y\in\\{-1,1\\}^{n}$ and any $n\times 2$ matrix $v$
could be used to estimate the norm of $v$ [1]. More specifically,

######  Lemma 1 (Unbiased estimator).

Consider $x,y\in\\{-1,1\\}^{n}$ where each vector is 4-wise independent. Let
$v\in\mathds{R}^{n^{2}}$. Define
$\Upsilon=(\sum_{i,j\in[n]}x_{i}y_{j}v_{i,j})^{2}$. Then
$\operatorname{E}[\Upsilon]=\sum_{i,j\in[n]}v_{i,j}^{2}=\lVert v\rVert^{2}$
and $\operatorname{Var}[\Upsilon]\leq 3(\operatorname{E}[\Upsilon])^{2}$.

Using this lemma, we can randomly generate vectors of $x,y\in\\{-1,1\\}^{n}$,
and let $v$ in the lemma be $r-s$, and calculate $\Upsilon$ base on the data
in the stream. $\Upsilon$ is then an unbiased estimator for the $\ell_{2}$
difference, and the variance is also bounded, meaning that we can use
Chebychev’s inequality to limit the error.

1 $x,y\leftarrow$ random vector of length $n$ containing $1$ or $-1$;

2 $t_{1},t_{2},t_{3}\leftarrow 0$;

3 for  _each pair $(i,j)$ in stream_ do

4 $t_{1}\leftarrow t_{1}+x_{i}y_{j}$; // sums to $\sum_{i,j}x_{i}y_{j}(N\cdot
s_{i,j})$

5 $t_{2}\leftarrow t_{2}+x_{i}$; // sums to $\sum_{i}x_{i}(N\cdot p_{i})$

6 $t_{3}\leftarrow t_{3}+y_{j}$; // sums to $\sum_{j}y_{j}(N\cdot q_{j})$

7

8$t\leftarrow t_{1}/N-t_{2}t_{3}/N^{2}$; //
$=\sum_{i,j}x_{i}y_{j}(s_{i,j}-p_{i}q_{j})=\sum_{i,j}x_{i}y_{j}(s_{i,j}-r_{i,j})$

9 $\Upsilon\leftarrow t^{2}$;

return $\Upsilon$;

Algorithm 1 Approximating $\lVert s-r\rVert^{2}$

The algorithm is very neat, as we only need to compute three numbers for each
run. However, when it comes to implementation, the drawback of the algorithm
appears.

  1. 1.

It is actually memory-inefficient since for each run, we need to generate
random 4-wise independent vectors $x,y$ and store them until we read the whole
stream. Therefore storing those vectors will actually cost
$\mathcal{O}(\epsilon^{-2}n\log\delta^{-1})$ space.

  2. 2.

We can solve the above problem by choosing a large $p$ and using a polynomial
of degree 3,

$h(x)=((h_{3}x^{3}+h_{2}x^{2}+h_{1}x+h_{0})\mod p\mod 2)\times 2-1$

where the coefficients $h_{0},h_{1},h_{2},h_{3}<p$ are randomly chosen, to map
$x$ to either $-1$ or $1$, creating a 4-wise independent vector [4].

T However, calculating this hash function is computationally expensive, making
the algorithm slow. And although we get rid of the $n$ factor in space
complexity, the constant factor is at least 8, so again a lot of space is
used.

We were able to verify the correctness of the algorithm, as shown in our
results section.

###  2.2 $\ell_{1}$ Difference

The algorithm of estimating $\ell_{1}$ difference will take a linear space
since we will need to generate and store

  * •

A vector $x$ of length $n$ where each element follows a Cauchy distribution,
and

  * •

a vector $y$ of length $n$ where each element follows a $T$-truncated-Cauchy
distribution [2]

######  Definition 1 (T-truncated Cauchy).

Let $T\geq 0$, $X\sim\text{Cauchy}$,

$Y=\left\\{\begin{array}[]{ll}-T&\text{if }X\leq-T\\\ X&\text{if }-T<X<T\\\
T&\text{if }X\geq T\end{array}\right.$

We say $Y\sim T$-truncated-Cauchy.

######  Lemma 2 (Property of T-truncated Cauchy).

Let $T=100n$, and $y\in\mathds{R}^{n}\sim T$-Truncated-Cauchy,

$\Pr\left[1/100\leq\frac{\sum_{j}|y\cdot v^{j}|}{\sum_{j}|v^{j}|}\leq 20\ln
n\right]\leq 9/10$

######  Lemma 3 (Property of $T$-truncated Cauchy [2]).

For any $T>0$, and $y\in\mathds{R}^{n}\sim T$-Truncated-Cauchy

$\operatorname{E}\left[\sum_{j}{y_{j}}^{T}\right]\leq
k\left[\frac{\ln{T^{2}+1}}{\pi}+b\right]$

for each $\mathcal{O}(\log\delta^{-1})$ runs of experiment. This time, we
cannot use a hash function anymore, so the $n$ factor would be inevitable for
a single-pass algorithm, making it very memory-inefficient. The pseudo-code
for the algorithm is as follows:

1 for  _$k$ in $1...\log(1/\delta)$ in parallel_ do

2 ${t_{1}}^{1}...{t_{1}}^{s},{t_{2}}^{1},...{t_{2}}^{s},t_{3}\leftarrow 0$;

3 $T\leftarrow 100n$;

4 $x_{1}...x_{s}\leftarrow$ For each $x_{i}^{j}\sim$ Cauchy and independent

5 $y_{i}\leftarrow y_{i}\sim T$-Truncated-Cauchy and independent

6 for  _each stream element (i,j)_ do

7 ${t_{1}}^{r}\leftarrow{t_{1}}^{r}+{x_{i}}^{r}\cdot y_{j}$; // sums to
$N\sum_{i,j\in[n]}{x_{i}}^{r}y_{j}{r_{i}}_{j}$

8 ${t_{2}}^{r}\leftarrow{t_{2}}^{r}+{x_{i}}^{r}$; // sums to
$N\sum_{i\in[n]}{x_{i}}^{r}p_{i}$

9 ${t_{3}}\leftarrow t_{3}+y_{j}$; // sums to $N\sum_{i\in[n]}y_{j}q_{j}$

10

11 $\Upsilon_{k}=\texttt{median}(|{t_{1}}^{1}/N-{t_{2}}^{1}\cdot
t_{3}/N^{2}|,....,|{t_{1}}^{n}/N-{t_{2}}^{n}\cdot t_{3}/N^{2}|)$;

return $texttt{median}(\Upsilon_{1},....\Upsilon_{\log{1/\delta}})$;

Algorithm 2 Approximating $|s-r|$

The paper proved that the algorithm is theoretically correct using definition
1, lemma 2, lemma 3, Markov’s inequality and Chernoff Bound. This algorithm is
extremely space efficient as it only takes $\mathcal{O}(\log 1/\delta)$ space,
however the error produced by the algorithm is high ($\mathcal{O}(\log n)$
multiplicative error) and it’s dependent on $n$. Also, this algorithm assumed
random oracle and infinite precision.

We tried to verify this algorithm with a few experiments, however the result
is way too far from the theoretical correctness. We suspect the issue is
caused by many "ideal" assumptions made in the proof and analysis, therefore
the algorithm performs poorly in real life. In addition, even the expected
error from its $(\mathcal{O}(\log n),\delta)$-approximation is very large, we
do not see any value of further evaluating the algorithm.

##  3 Preliminaries

Given two discrete random variables $X$ and $Y$, we say that they are
independent if and only if for all $i,j$,

$\underbrace{\Pr[X=i,Y=j]}_{=s_{i,j}}=\underbrace{\Pr[X=i]}_{=p_{i}}\underbrace{\Pr[Y=j]}_{=q_{j}}$

or $s_{i,j}=p_{i}q_{j}$. This means that ideally,
$\Delta_{i,j}=s_{i,j}-p_{i}q_{j}=0$ for all $i,j$ and the $\ell_{1}$
difference $|\Delta|=0$, $\ell_{2}$ difference $\lVert\Delta\rVert=0$. If we
have enough space, we can store an $n\times n$ counter matrix,

| 1 | 2 | $\dots$ | $j$ | $\dots$ | $n-1$ | $n$ | $\sum$
---|---|---|---|---|---|---|---|---
1 |  |  |  |  |  |  |  |
2 |  |  |  |  |  |  |  |
$\vdots$ |  |  |  |  |  |  |  |
$i$ |  |  |  | $n_{i,j}$ |  |  |  | $\sum n_{i,\cdot}$
$\vdots$ |  |  |  |  |  |  |  |
$n-1$ |  |  |  |  |  |  |  |
$n$ |  |  |  |  |  |  |  |
$\sum$ |  |  |  | $\sum n_{\cdot,j}$ |  |  |  | $N$
Table 2: $n\times n$ counter matrix

where each counter $n_{i,j}$ stores the number of times the pair $(i,j)$
appears in the stream. We can estimate the joint probability
$\hat{s}_{i,j}=n_{i,j}/N$. The sum of each row and each column are calculated
to estimate the marginal probabilities,

$\hat{p}_{i}=\frac{\sum{n_{i,\cdot}}}{N},\qquad\hat{q}_{j}=\frac{\sum{n_{\cdot,j}}}{N}$

Ideally, if $X$ and $Y$ are independent, we should have

$\hat{\Delta}_{i,j}:=\hat{s}_{i,j}-\hat{p}_{i}\hat{q}_{j}=0$

for all $i,j$. The $\ell_{1}$ difference can be estimated by

$\widehat{|s-r|}=|\hat{\Delta}|=\sum_{i,j}|\hat{s}_{i,j}-\hat{p}_{i}\hat{q}_{j}|$
(1)

and the $\ell_{2}$ difference can be estimated by

$\widehat{\lVert
s-r\rVert}=\lVert\hat{\Delta}\rVert=\sqrt{\sum_{i,j}(\hat{s}_{i,j}-\hat{p}_{i}\hat{q}_{j})^{2}}$
(2)

We can also calculate the $\chi^{2}$ statistics for independence test,

$X_{(n-1)^{2}}^{2}=\sum_{i,j}\frac{(\hat{s}_{i,j}-\hat{p}_{i}\hat{q}_{j})^{2}}{\hat{p}_{i}\hat{q}_{j}}$
(3)

follows a chi-squared distribution with degree of freedom $(n-1)^{2}$. This
statistics can be compared with the critical value $\chi_{0.05,(n-1)^{2}}^{2}$
to see if we can reject a null hypothesis: $X$ and $Y$ are independent with
$p<0.05$ [5].

##  4 Counter Matrix Algorithm

The counter matrix above is nice, but it will cost $\mathcal{O}(n^{2})$ space,
which is bad. The space complexity would be even worse if we want to identify
correlation between multiple random variables. Our idea is to use an $A\times
A$ $(A\ll n)$ matrix to store the information in $n\times n$ counter matrix by
randomly summing rows and columns together.

More specifically, we will choose two random hash functions
$h_{1},h_{2}:[n]\rightarrow[A]$, $x\mapsto i$ where $1\leq i\leq A$. Upon
seeing a pair $(x,y)$ in the stream, we increment the counter
$C_{h_{1}(x),h_{2}(y)}$.

| 1 | 2 | $\dots$ | $j$ | $\dots$ | $A-1$ | $A$ | $\sum$ |
---|---|---|---|---|---|---|---|---|---
1 |  |  |  |  |  |  |  |  |
2 |  |  |  |  |  |  |  |  |
$\vdots$ |  |  |  |  |  |  |  |  |
$i$ |  |  |  | $C_{i,j}$ |  |  |  | $\sum C_{i,\cdot}$ |
$\vdots$ |  |  |  |  |  |  |  |  |
$A-1$ |  |  |  |  |  |  |  |  |
$A$ |  |  |  |  |  |  |  |  |
$\sum$ |  |  |  | $\sum C_{\cdot,j}$ |  |  |  | $N$ |
Table 3: $A\times A$ Counter Matrix

After reading the stream we can calculate the estimators for joint and
marginal probabilities,

$\tilde{s}_{i,j}=\frac{C_{i,j}}{N},\qquad\tilde{p}_{i}=\frac{\sum
C_{i,\cdot}}{N},\qquad\tilde{q}_{j}=\frac{\sum C_{\cdot,j}}{N}$

and use them to estimate the $\ell_{2}$ difference using a similar fashion as
equation 2.

Input : $A$, the size of counter matrix

Output : Estimation for $\lVert s-r\rVert^{2}$

1 $C\leftarrow\mathbf{0}_{A\times A}$; // An $A\times A$ matrix of zeros

2 $h_{1},h_{2}\leftarrow$ random hash functions that maps $[n]\rightarrow[A]$;

3 for  _each pair $(i,j)$ in stream_ do

4 $C_{h_{1}(i),h_{2}(j)}\leftarrow C_{h_{1}(i),h_{2}(j)}+1$; // increment the
counter

5

6$\Upsilon\leftarrow\frac{1}{(1-1/A)^{2}}\sum_{x,y\in[A]}\left(\frac{C_{x,y}}{N}-\frac{\sum
C_{x,\cdot}\sum C_{\cdot,y}}{N^{2}}\right)^{2}$;

return $\Upsilon$;

Algorithm 3 Approximating $\lVert s-r\rVert^{2}$ (Counter Matrix Algorithm)

Similar to the FM++ algorithm, we run the counter matrix algorithm $B$ times
and take the median of all $\Upsilon$ as our final result.

###  4.1 Analysis

We can prove that our resulting algorithm

  * •

is correct if $X$ and $Y$ are actually independent (theorem 4),

  * •

can give an unbiased estimate for $\ell_{2}$ difference (lemma 7), and

  * •

has bounded variance (lemma 8).

We want to prove the correctness of our method. First we show that the
estimator is correct when $X$ and $Y$ are actually independent.

######  Theorem 4 (Independent Case).

If $X$ and $Y$ are indeed independent, with sufficiently large $N$, we will
have the estimated $\ell_{1}$ and $\ell_{2}$ difference be 0, i.e.
$|\tilde{\Delta}|=\lVert\tilde{\Delta}\rVert=0$, where
$\tilde{\Delta}_{i,j}=\tilde{s}_{i,j}-\tilde{p}_{i}\tilde{q}_{j}$.

###### Proof.

Let us denote $h_{1}^{-1}(i):=\\{x:h_{1}(x)=i\\}$ the set of all $x$ that maps
to $i$, and similarly $h_{2}^{-1}(j):=\\{y:h_{2}(y)=j\\}$. Let
$h^{-1}(i,j):=h_{1}^{-1}(i)\times h_{2}^{-1}(j)$ be all the pairs $(x,y)$ that
maps to $(i,j)$. Then for each $(i,j)\in[A]^{2}$, we will have the value of
the counter be

$C_{i,j}=\sum_{(x,y)\in h^{-1}(i,j)}n_{x,y}$

and the sum of the corresponding row and column be,

$\sum C_{i,\cdot}=\sum_{x\in h_{1}^{-1}(i)}n_{x,\cdot},\qquad\sum
C_{\cdot,j}=\sum_{y\in h_{2}^{-1}(y)}n_{\cdot,y}$

Therefore we will have $\tilde{p}_{i}\tilde{q}_{j}=\sum_{(x,y)\in
h^{-1}(i,j)}n_{x,\cdot}n_{\cdot,y}/N^{2}$. Now, for sufficiently large $N$, we
will have $n_{x,y}\rightarrow Ns_{x,y},\sum n_{x,\cdot}\rightarrow Np_{x}$ and
$\sum n_{\cdot,y}\rightarrow Nq_{y}$. Therefore,

$\tilde{\Delta}_{i,j}=\tilde{s}_{i,j}-\tilde{p}_{i}\tilde{q}_{j}=\sum_{(x,y)\in
h^{-1}(i,j)}\frac{n_{x,y}}{N}-\frac{n_{x,\cdot}n_{\cdot,y}}{N^{2}}\rightarrow\sum_{(x,y)\in
h^{-1}(i,j)}\underbrace{s_{x,y}-p_{x}q_{y}}_{=0}=0$

for all $i,j$. Therefore the $\ell_{1}$ and $\ell_{2}$ norm will be 0. ∎

If $X$ and $Y$ are correlated, however, things will get complicated. For
$\ell_{2}$ difference case, let us consider the $\ell_{2}$ difference squared,
i.e.

$\lVert\hat{\Delta}\rVert^{2}=\sum_{i,j\in[n]}(\hat{\Delta}_{i,j})^{2}=\sum_{i,j\in[n]}(\hat{s}_{i,j}-\hat{p}_{i}\hat{q}_{j})^{2}$

In the $A\times A$ counter matrix case, some of the
$\hat{s}_{i,j}-\hat{p}_{i}\hat{q}_{j}$ will be added together then squared,

$\displaystyle\lVert\tilde{\Delta}\rVert^{2}$ $\displaystyle=$
$\displaystyle\sum_{i,j\in[A]}(\tilde{s}_{i,j}-\tilde{p}_{i}\tilde{q}_{j})^{2}=\sum_{i,j\in[A]}\left(\sum_{(x,y)\in
h^{-1}(i,j)}\hat{s}_{x,y}-\hat{p}_{x}\hat{q}_{j}\right)^{2}=\sum_{i,j\in[A]}\left(\sum_{(x,y)\in
h^{-1}(i,j)}\hat{\Delta}_{x,y}\right)^{2}$ $\displaystyle=$
$\displaystyle\underbrace{\sum_{i,j\in[n]}(\hat{\Delta}_{i,j})^{2}}_{=\lVert\hat{\Delta}\rVert^{2}}+\underbrace{\sum_{\begin{subarray}{c}h(i,j)=h(k,l)\\\
(i,j)\neq(k,l)\end{subarray}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}}_{=:X}=\lVert\hat{\Delta}\rVert^{2}+X$

And we can see that the $\ell_{2}$ estimate given by our $A\times A$ matrix
can be expressed by $\lVert\hat{\Delta}\rVert^{2}$ plus a term $X$, where $X$
is just the sum of product of $\hat{\Delta}$ of all the colliding pairs in our
hash function. We thus want to study the distribution of $X$.

Before going into this, we want to show a property of $\hat{\Delta}$.

######  Lemma 5 (Property of $\hat{\Delta}$).

The sum of each row or each column of $\hat{\Delta}$ must be 0.

###### Proof.

For row $i$, for example, the sum of all elements on row $i$ would be

$\displaystyle\sum\hat{\Delta}_{i,\cdot}$ $\displaystyle=$
$\displaystyle\sum_{y\in[A]}\sum_{x\in[A]}(\hat{s}_{x,y}-\hat{p}_{x}\hat{q}_{y})=\sum_{x\in[A]}\underbrace{\sum_{y\in[A]}\hat{s}_{x,y}}_{=\hat{p}_{x}}-\sum_{x\in[A]}\hat{p}_{x}\underbrace{\sum_{y\in[A]}\hat{q}_{y}}_{=1}$
$\displaystyle=$
$\displaystyle\sum_{x\in[A]}\hat{p}_{x}-\sum_{x\in[A]}\hat{p}_{x}=0$

The column case can be proved by a similar fashion. ∎

The following result immediately follows from the above lemma.

######  Corollary 6.

All elements in $\hat{\Delta}$ sums to 0.

Now, let us investigate the expectation of $X$. The probability of the term
$\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}$ appear in $X$ is equal to the
probability of $(k,l)$ having the same hash values as $(i,j)$ (collide).

$\Pr[h(k,l)=h(i,j)]=\left\\{\begin{array}[]{ll}1/A^{2}&\text{if }i\neq k,j\neq
l\\\ 1/A&\text{ if}i=k\text{ or }j=l\end{array}\right.$

since if $i=k$ or $j=l$, we only need to ensure the other dimension to have
the same hash values, while if $i\neq k,j\neq l$, we need both pairs to have
the same hash values.

| 1 | 2 | $\dots$ | $j$ | $\dots$ | $n-1$ | $n$
---|---|---|---|---|---|---|---
1 |  |  |
2 |  |  |
$\vdots$ | $\frac{1}{A^{2}}$ | $\frac{1}{A}$ | $\frac{1}{A^{2}}$
$i$ | $\frac{1}{A}$ |  | $\frac{1}{A}$
$\vdots$ |  |  |
$n-1$ |  |  |
$n$ | $\frac{1}{A^{2}}$ | $\frac{1}{A}$ | $\frac{1}{A^{2}}$
Table 4: Illustration of probability that a pair collides with (has the same
hash values as) $(i,j)$.

Using lemma 5 and corollary 6, the expectation of the sum of all terms
containing $\hat{\Delta}_{i,j}$ in $X$ is then

$\displaystyle\hat{\Delta}_{i,j}\left[\frac{1}{A^{2}}\underbrace{\sum_{(i,j)\neq(k,l)}\hat{\Delta}_{k,l}}_{=-\hat{\Delta}_{i,j}}+\left(\frac{1}{A}-\frac{1}{A^{2}}\right)\underbrace{\sum_{i\neq
k}\hat{\Delta}_{k,j}}_{=-\hat{\Delta}_{i,j}}+\left(\frac{1}{A}-\frac{1}{A^{2}}\right)\underbrace{\sum_{j\neq
l}\hat{\Delta}_{i,l}}_{=-\hat{\Delta}_{i,j}}\right]$ $\displaystyle=$
$\displaystyle-\left(\frac{2}{A}-\frac{1}{A^{2}}\right)\hat{\Delta}_{i,j}^{2}$

Therefore, the expectation of $X$ is then

$\operatorname{E}[X]=-\left(\frac{2}{A}-\frac{1}{A^{2}}\right)\sum_{i,j\in[n]}\hat{\Delta}_{i,j}^{2}=-\left(\frac{2}{A}-\frac{1}{A^{2}}\right)\lVert\hat{\Delta}\rVert^{2}$

Meaning that

$\operatorname{E}[\lVert\tilde{\Delta}\rVert^{2}]=\left(1-\frac{2}{A}+\frac{1}{A^{2}}\right)\lVert\hat{\Delta}\rVert^{2}=\left(1-\frac{1}{A}\right)^{2}\lVert\hat{\Delta}\rVert^{2}$

This gives rise to our theorem,

######  Lemma 7 (Unbiased Estimator).

$\lVert\tilde{\Delta}\rVert^{2}/(1-1/A)^{2}$ is going to be an unbiased
estimator for $\lVert\hat{\Delta}\rVert^{2}$.

This is a neat result, as it is not dependent on $n$ or $N$. This lemma
indicates that we can, again, create multiple $A\times A$ counter matrices,
divide the resulting squared $\ell_{2}$ difference with $(1-1/A)^{2}$, and
take the mean to get an unbiased estimation.

Remark. We should have $A>1$ for this algorithm to be meaningful. If we set
$A=1$, the expectation $\operatorname{E}[\lVert\tilde{\Delta}\rVert^{2}]=0$.
In fact, if we only use 1 number, then $s_{1,1}=p_{1}=q_{1}=1$, so the
resulting norm will always be zero.

We can also prove that the variance is also bounded,

######  Lemma 8 (Bounded Variance).

The variance of estimator
$\operatorname{Var}[\lVert\tilde{\Delta}\rVert^{2}]\leq
8\lVert\hat{\Delta}\rVert^{4}/A$.

The proof is pretty long, so we put it in the appendix. This result shows that
we can utilize Chebyshev’s inequality to limit the error rate.

######  Theorem 9 (Counter Matrix Algorithm).

There exists a one-pass, $\mathcal{O}(\epsilon^{-4}\log\delta^{-1})$-space
algorithm to calculate an estimator $\Upsilon$ such that
$\Upsilon\in(1\pm\epsilon)\lVert\hat{\Delta}\rVert^{2}$ with probability at
least $1-\delta$.

###### Proof.

We can take $A=32/\epsilon^{2}$ such that by Chebyshev’s Inequality, we have
can have $\Upsilon\in(1\pm\epsilon)\lVert\hat{\Delta}\rVert^{2}$ with
probability at least $1/4$, and we can take $B=32\log(2/\delta)$ to ensure
that the median is a correct answer with probability at least $1-\delta$. In
total we need $A^{2}B=\mathcal{O}(\epsilon^{-4}\log\delta^{-1})$ space. ∎

This is, however, a pretty loose upper bound. We can see our experiment that
the variance
$\operatorname{Var}[\Upsilon]=\mathcal{O}(\lVert\hat{\Delta}\rVert^{4}/A^{2})$
when $A$ is large. Therefore, in reality we can achieve
$\mathcal{O}(\epsilon^{-2}\log\delta^{-1})$-space, which is similar to the
sketching of sketches algorithm.

###  4.2 Implementation

For now, we have completed the implementation of this algorithm estimating the
$\ell_{2}$ difference. We choose the hash functions to be

$h_{1}(x)=(ax+b)\mod p\mod A,\qquad h_{2}(x)=(cx+d)\mod p\mod A$

where $p$ is a random prime that is significantly larger than $A$ and
$a,b,c,d<p$ are randomly chosen. We only need to compute two hash functions
and store the 4 parameters for each counter matrix. Comparing this with at
least 8 parameters for each run of the sketching of sketches algorithm, our
algorithm is quite fast and at least 2 times more memory-saving.

##  5 Results

The code and benchmark for our paper is given here:
github.com/GZHoffie/CS5234-mini-project.

###  5.1 Data Set Generation

We need to generate two types of distribution for sample stream:

  1. 1.

$X$ and $Y$ are independent: We first generate 2 marginal probability arrays
$p_{x}$ and $q_{y}$ of size $n$ with each array sums to 1. Then we generated
each element pairs using the probability arrays obtained.

  2. 2.

$X$ and $Y$ are correlated: Generate the probability matrix $s_{i,j}$ for each
$i,j\in[n]$ and normalize it such that all values sums up to 1. Then we
generated each element pairs using the probability matrix obtained.

We use two types of distributions:

  1. 1.

Random distribution: where $s_{i,j}$ or $p_{i}$ and $q_{j}$ are randomly
generated.

  2. 2.

Zipfian distribution: where $s_{i,j}$ or $p_{i}$ and $q_{j}$ follows Zipf’s
Law [6], where the second largest probability is $1/2$ of the largest
probability, and the third largest is $1/3$, so on and so forth.

We also use a $n\times n$ counter matrix to calculate the values for the exact
estimate of the $\ell_{2}$ difference, $\lVert\hat{\Delta}\rVert$, and store
them to calculate the multiplicative error.

In the following experiments, we used 4 generated data sets with $N=1000000$
and $n=10000$, produced by our data generation scripts mentioned in 5.1. Each
data set is generated with a different combination distribution type and
whether the two stream are independent or not.

  1. 1.

Random distribution, dependent. $\lVert\hat{\Delta}\rVert\approx 0.0010$.

  2. 2.

Random distribution, independent. $\lVert\hat{\Delta}\rVert\approx 0.00099$
(similar to the dependent case since real $\lVert\Delta\rVert\approx
5.77\times 10^{-5}$ is very small).

  3. 3.

Zipfian distribution, dependent. $\lVert\hat{\Delta}\rVert\approx 0.065$.

  4. 4.

Zipfian distribution, independent. $\lVert\hat{\Delta}\rVert\approx 0.00097$.

###  5.2 Metrics

We can compare the estimated result with the exact solution. In particular, we
used the multiplicative error,

$\epsilon=\left|1-\frac{\Upsilon-\lVert r-s\rVert}{\lVert r-s\rVert}\right|$

to check how far our estimator $\Upsilon$ is from the actual $\ell_{2}$
difference.

###  5.3 Experiments

We designed 2 experiments to evaluate our counter matrix algorithm.

  1. 1.

Given fixed space, determine the trade-off of parameters $A$ and $B$ used in
the algorithm

  2. 2.

Given fixed space, evaluate the multiplicative error by counter matrix
algorithm and algorithm 1

####  5.3.1 Effects of Parameters $A$ and $B$

In this experiment, for each data set we ran a set of sub-experiments. By
doing a grid search of changing $A$ and $B$ values, we can find out how the
multiplicative error change. We have selected 5 $A$ values and 5 $B$ values on
purpose such that if we arrange those values in a table where the cells in the
same diagonal direction from top-right to bottom-left (indicated using the
same color in the table) will use the same amount of space, $A^{2}B$.

Since storing the exact probability table for the stream takes
$\mathcal{O}(n^{2})$ space, the counter matrix algorithm will only make sense
if $A^{2}B=o(n^{2})$. Also, for each $A$ and $B$, type of distribution and
dependence, we repeat the experiment 5 times. The results below shows the
average multiplicative error for the 5 runs.

| A=2 | A=4 | A=8 | A=16 | A=32
---|---|---|---|---|---
B=1 | 0.450537 | 0.192048 | 0.053852 | 0.023916 | 0.015661
B=4 | 0.414036 | 0.141648 | 0.053533 | 0.025423 | 0.007171
B=16 | 0.239866 | 0.063814 | 0.026485 | 0.009675 | 0.004532
B=64 | 0.297715 | 0.052855 | 0.021604 | 0.006910 | 0.005641
B=256 | 0.288948 | 0.057999 | 0.018541 | 0.008588 | 0.001205
Table 5: Multiplicative error with Random Distribution, Dependent Stream | A=2 | A=4 | A=8 | A=16 | A=32
---|---|---|---|---|---
B=1 | 0.401140 | 0.292316 | 0.100423 | 0.051171 | 0.017768
B=4 | 0.224761 | 0.118114 | 0.019799 | 0.012302 | 0.011697
B=16 | 0.286748 | 0.052774 | 0.008510 | 0.012821 | 0.008939
B=64 | 0.328810 | 0.025917 | 0.022485 | 0.007506 | 0.002322
B=256 | 0.295032 | 0.011417 | 0.021785 | 0.003699 | 0.002610
Table 6: Multiplicative error with Random Distribution, Independent Stream | A=2 | A=4 | A=8 | A=16 | A=32
---|---|---|---|---|---
B=1 | 0.561978 | 0.116835 | 0.053566 | 0.026087 | 0.005170
B=4 | 0.241000 | 0.055140 | 0.040690 | 0.014915 | 0.005655
B=16 | 0.203792 | 0.037948 | 0.012536 | 0.007444 | 0.003694
B=64 | 0.230859 | 0.037576 | 0.005997 | 0.002579 | 0.001762
B=256 | 0.203329 | 0.028557 | 0.009255 | 0.001563 | 0.002044
Table 7: Multiplicative error with Zipfian Distribution, Dependent Stream | A=2 | A=4 | A=8 | A=16 | A=32
---|---|---|---|---|---
B=1 | 0.567727 | 0.117505 | 0.082284 | 0.038022 | 0.014242
B=4 | 0.465189 | 0.039366 | 0.031472 | 0.023964 | 0.014675
B=16 | 0.352457 | 0.068149 | 0.017812 | 0.016407 | 0.011978
B=64 | 0.311025 | 0.040865 | 0.025680 | 0.018174 | 0.011105
B=256 | 0.285863 | 0.029304 | 0.013811 | 0.013607 | 0.010472
Table 8: Multiplicative error with Zipfian Distribution, Independent Stream

We can summarize the following findings from this experiment from data in 4
tables:

  1. 1.

The counter matrix algorithm is effective, and achieve a small multiplicative
error when $A\geq 32$.

  2. 2.

Regardless of distribution type, and whether the streams are independent or
not, the multiplicative error will be lower as $A$ or $B$ increases.

  3. 3.

Given a fixed space where $A^{2}B$ are same (indicated by cells with same
color in the tables above), increasing $A$ generally results in lower
multiplicative error.

####  5.3.2 Comparison with Sketching of Sketches Algorithm

In this experiment, we try to compare counter matrix algorithm with the
sketching of sketches algorithm given the same amount of space. More
specifically, we choose multiple values for $A$, and run algorithm 3 with
parameter $A$, and $A^{2}$ copies of algorithm 1 so that both algorithms use
roughly $A^{2}$ space, and compare the multiplicative error. For each $A$, we
run 10 experiments and take the average error.

(a) Random Distribution, Dependent Stream

(b) Random Distribution, Inependent Stream

(c) Zipfian Distribution, Dependent Stream

(d) Zipfian Distribution, Inependent Stream

Figure 1: Comparison of log multiplicative error of two algorithms

We can see that

  1. 1.

In both cases, increasing $A$ will generally lead to smaller multiplicative
error, which is as expected.

  2. 2.

Even for small $A$ ($2\leq A\leq 20$), the multiplicative error of the counter
matrix algorithm is similar or smaller than the sketching of sketches
algorrithm.

Considering the fact that the sketching of sketches algorithm actually uses an
additional $(8A)^{2}$ space to store the hash parameters (or vectors taking
$(nA)^{2}$ space in the original implementation in the paper), and our counter
matrix algorithm only need to store $4$ hash parameters for each run, we can
see that our algorithm is actually uses 16x less space, and can get a
relatively good result at the same time.

##  6 Conclusion

In this mini-project, we analyzed and implemented 2 algorithms proposed in the
paper by Indyk and McGregor [3]:

  1. 1.

For $\ell_{2}$ difference: A 1-pass,
$\mathcal{O}(\epsilon^{-2}\log\delta^{-1})$-space estimation that achieve
$(1+\epsilon,\delta)$-approximation.

  2. 2.

For $\ell_{1}$ difference: A 1-pass, $\mathcal{O}(\log\delta^{-1})$-space
estimation that achieve $(\mathcal{O}(\log n),\delta)$-approximation.

The implementation of the algorithm to estimate $\ell_{2}$ difference we
achieved satisfactory results, however the algorithm to estimate $\ell_{2}$
difference produced error way beyond the estimated error stated in the paper.
As an extension to estimate $\ell_{2}$ difference, we proposed a different
counter matrix algorithm that aimed to achieve lower multiplicative error that
the one proposed in the paper by Indyk and McGregor [3]. From our analysis and
experiments above, we have showed that the counter matrix algorithm is able to
achieve better approximation and produce lower or similar multiplicative error
than the algorithm proposed in the paper given same (or even less) amount of
space.

## Appendix

Here we try to calculate $\operatorname{Var}[\lVert\tilde{\Delta}\rVert^{2}]$.
Since we have $\lVert\tilde{\Delta}\rVert^{2}=\lVert\hat{\Delta}\rVert^{2}+X$,
and we consider $\lVert\hat{\Delta}\rVert^{2}$ as a constant, then
$\operatorname{Var}[\lVert\tilde{\Delta}\rVert^{2}]=\operatorname{Var}[X]=\operatorname{E}[X^{2}]-\operatorname{E}[X]^{2}$.
We have

$X=\sum_{\begin{subarray}{c}h(i,j)=h(k,l)\\\
(i,j)\neq(k,l)\end{subarray}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}=\sum_{i,j,k,l\in[n]}\delta_{i,j,k,l}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}$

where $\delta_{i,j,k,l}=1$ if $h(i,j)=h(k,l)$ and $(i,j)\neq(k,l)$, and 0
otherwise. We have calculated that

$\operatorname{E}[\delta_{i,j,k,l}]=\left\\{\begin{array}[]{ll}1/A^{2}&\text{if
}i\neq k,j\neq l\\\ 1/A&\text{if }i=k\text{ or }j=l\end{array}\right.$

Now let us consider imagine that there is another hash function $h^{\prime}$
that is independent of $h$, and a random variable $X^{\prime}$, where

$X^{\prime}=\sum_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}\in[n]}\delta^{\prime}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\hat{\Delta}_{i^{\prime},j^{\prime}}\hat{\Delta}_{k^{\prime},l^{\prime}}$

where $\delta^{\prime}_{i,j,k,l}=1$ if $h^{\prime}(i,j)=h^{\prime}(k,l)$ and
$(i,j)\neq(k,l)$, and 0 otherwise. Then $X$ is independent of $X^{\prime}$ and

$\operatorname{E}[X]^{2}=\operatorname{E}[XX^{\prime}]=\operatorname{E}\left[\sum_{i,j,k,l\in[n]}\sum_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}\in[n]}\delta_{i,j,k,l}\delta^{\prime}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\hat{\Delta}_{i^{\prime},j^{\prime}}\hat{\Delta}_{k^{\prime},l^{\prime}}\right]$

On the other hand,

$\operatorname{E}[X^{2}]=\operatorname{E}\left[\sum_{i,j,k,l\in[n]}\sum_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}\in[n]}\delta_{i,j,k,l}\delta_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\hat{\Delta}_{i^{\prime},j^{\prime}}\hat{\Delta}_{k^{\prime},l^{\prime}}\right]$

So we just need to find those
$(i,j,k,l,i^{\prime},j^{\prime},k^{\prime},l^{\prime})$ where
$\delta_{i,j,k,l}\delta_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}\neq\delta_{i,j,k,l}\delta^{\prime}_{i^{\prime},j^{\prime},k^{\prime},l^{\prime}}$
to calculate the variance. There are several cases we need to discuss.

  1. 1.

If $(i,j)$ and $(k,l)$ are on the same row, i.e. $i=k$, and we have
$\delta_{i,j,k,l}=1$. It implies that $h_{2}(j)=h_{2}(l)$, and therefore if
$j^{\prime}=j$ and $l^{\prime}=l$ or $j^{\prime}=l$ and $l^{\prime}=j$, the
probability of $h(i^{\prime},j^{\prime})=h(k^{\prime},l^{\prime})$ would be
increased.

For example, if we know $h(i,j)=h(i,l)$, then the probability of
$h(1,j)=h(1,l)$ will be 1 (which originally was $1/A$), and the probability of
$h(1,j)=h(2,l)$ will be $1/A$ (which originally was $1/A^{2}$).

We can then calculate the expected total difference in the variance for each
pair of $(i,j)$ and $(i,l)$,

$\displaystyle\frac{1}{A}\hat{\Delta}_{i,j}\hat{\Delta}_{i,l}\left[\left(1-\frac{1}{A}\right)\sum_{i^{\prime}=1}^{n}(\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{i^{\prime},l}+\hat{\Delta}_{i^{\prime},l}\hat{\Delta}_{i^{\prime},j})+\left(\frac{1}{A}-\frac{1}{A^{2}}\right)\sum_{i^{\prime}\neq
k^{\prime}}(\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{k^{\prime},l}+\hat{\Delta}_{i^{\prime},l}\hat{\Delta}_{k^{\prime},j})\right]$
$\displaystyle=$
$\displaystyle\frac{2}{A}\hat{\Delta}_{i,j}\hat{\Delta}_{i,l}\left[\left(1-\frac{1}{A}\right)\sum_{i^{\prime}=1}^{n}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{i^{\prime},l}+\left(\frac{1}{A}-\frac{1}{A^{2}}\right)\sum_{i^{\prime}\neq
k^{\prime}}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{k^{\prime},l}\right]$
$\displaystyle=$
$\displaystyle\frac{2}{A}\hat{\Delta}_{i,j}\hat{\Delta}_{i,l}\left[\left(1-\frac{1}{A}\right)^{2}\sum_{i^{\prime}=1}^{n}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{i^{\prime},l}+\left(\frac{1}{A}-\frac{1}{A^{2}}\right)\underbrace{\sum_{i^{\prime},k^{\prime}\in[n]}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{k^{\prime},l}}_{=0}\right]$
$\displaystyle=$
$\displaystyle\frac{2}{A}\hat{\Delta}_{i,j}\hat{\Delta}_{i,l}\left[\left(1-\frac{1}{A}\right)^{2}\sum_{i^{\prime}=1}^{n}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{i^{\prime},l}\right]$

Summing these all up across all pairs of $(i,j),(i,l)$, we will get

$\frac{2}{A}\left(1-\frac{1}{A}\right)^{2}\underbrace{\sum_{\begin{subarray}{c}(i,j),(k,l),(i^{\prime},j^{\prime}),(k^{\prime},l^{\prime})\\\
\text{form a
rectangle}\end{subarray}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\hat{\Delta}_{i^{\prime},j^{\prime}}\hat{\Delta}_{k^{\prime},l^{\prime}}}_{=:\mathcal{R}}$

where in $\mathcal{R}$, each rectangle of same position and shape is counted 4
times.

  2. 2.

If $(i,j)$ and $(k,l)$ are on the same column, i.e. $j=l$, and we have
$\delta_{i,j,k,l}=1$. This case is totally the same as the previous case,
which add another $2\mathcal{R}(1-1/A)^{2}/A$ to our variance.

  3. 3.

If $(i,j)$ and $(k,l)$ are on different column and different row, i.e. $i\neq
k$ and $j\neq l$, and $\delta_{i,j,k,l}=1$, then

     * •

If $\\{(i^{\prime},j^{\prime}),(k^{\prime},l^{\prime})\\}=\\{(i,j),(k,l)\\}$,
then the probability of $h(i^{\prime},j^{\prime})=h(k^{\prime},l^{\prime})$
increased from $1/A^{2}$ to 1. This means that for each pair of $(i,j)$ and
$(k,l)$, the following is added to the variance,

$\frac{1}{A^{2}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\left[2\left(1-\frac{1}{A^{2}}\right)\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\right]=\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)\hat{\Delta}^{2}_{i,j}\hat{\Delta}^{2}_{k,l}$

Summing them up across all pairs gives us

$\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)\sum_{\begin{subarray}{c}i\neq
k\\\ j\neq
l\end{subarray}}\hat{\Delta}^{2}_{i,j}\hat{\Delta}^{2}_{k,l}\leq\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)\lVert\hat{\Delta}\rVert^{2}\sum_{i,j\in[n]}\hat{\Delta}^{2}_{i,j}\leq\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)\lVert\hat{\Delta}\rVert^{4}$

     * •

If $\\{(i^{\prime},j^{\prime}),(k^{\prime},l^{\prime})\\}=\\{(i,l),(k,j)\\}$,
then the probability of $h(i^{\prime},j^{\prime})=h(k^{\prime},l^{\prime})$
also increased from $1/A^{2}$ to 1. Therefore we also add the following,

$\frac{1}{A^{2}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\left[2\left(1-\frac{1}{A^{2}}\right)\hat{\Delta}_{i,l}\hat{\Delta}_{k,j}\right]$

summing across all pairs gives us

$\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)\mathcal{R}$

     * •

If $\\{j^{\prime},l^{\prime}\\}=\\{j,l\\}$, then if $i^{\prime}=k^{\prime}$
the probability of matching is increased from $1/A$ to 1, otherwise the
probability increased from $1/A^{2}$ to $1/A$. This is similar to our first
case, adding the following term to our variance,

$\displaystyle\frac{1}{A^{2}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\left[2\left(1-\frac{1}{A}\right)\sum_{i^{\prime}=1}^{n}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{i^{\prime},l}+2\left(\frac{1}{A}-\frac{1}{A^{2}}\right)\sum_{i^{\prime}\neq
k^{\prime}}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{k^{\prime},l}\right]$
$\displaystyle=$
$\displaystyle\frac{2}{A^{2}}\hat{\Delta}_{i,j}\hat{\Delta}_{k,l}\left[\left(1-\frac{1}{A}\right)^{2}\sum_{i^{\prime}=1}^{n}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{i^{\prime},l}\right]$

We can see that the points $(i,j),(k,l),(i^{\prime},j),(i^{\prime},l)$ form a
right trapezoid. Summing all those trapezoids up, for each specific
$i,j,l,i^{\prime}$,

$\frac{2}{A^{2}}\left(1-\frac{1}{A}\right)^{2}\hat{\Delta}_{i,j}\hat{\Delta}_{i^{\prime},j}\hat{\Delta}_{i^{\prime},l}\underbrace{\sum_{k\neq
i}\hat{\Delta}_{k,l}}_{=-\hat{\Delta}_{i,l}}$

Summing all of them up gives us

$-\frac{4}{A^{2}}\left(1-\frac{1}{A}\right)^{2}\mathcal{R}$

     * •

If $\\{i^{\prime},k^{\prime}\\}=\\{i,k\\}$, then it’s also similar to the
previous case, adding $-4\mathcal{R}(1-1/A)^{2}/A^{2}$ to the variance.

It is quite hard to compute a value for $\mathcal{R}$, but we can compute an
upper bound, for a rectangle $(i,j),(k,j),(k,l),(i,l)$,

$\hat{\Delta}_{i,j}\hat{\Delta}_{k,j}\hat{\Delta}_{k,l}\hat{\Delta}_{i,l}\leq\frac{\hat{\Delta}_{i,j}^{2}\hat{\Delta}_{k,l}^{2}+\hat{\Delta}_{k,j}^{2}\hat{\Delta}_{i,l}^{2}}{2}$

Therefore, an upper bound for the sum of all terms containing
$\hat{\Delta}_{i,j}^{2}$ is going to sum up to
$2\hat{\Delta}_{i,j}^{2}\sum_{k,l\in[n]}\hat{\Delta}_{k,l}^{2}\leq
2\hat{\Delta}_{i,j}^{2}\lVert\hat{\Delta}\rVert^{2}$, which, summing over all
$i,j$ gives $2\lVert\hat{\Delta}\rVert^{4}$.

This completes the all parts for the variance and we can calculate that

$\displaystyle\operatorname{Var}[X]$ $\displaystyle\leq$
$\displaystyle\left[\frac{4}{A}\left(1-\frac{1}{A}\right)^{2}+\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)-\frac{8}{A^{2}}\left(1-\frac{1}{A}\right)^{2}\right]\mathcal{R}+\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)\lVert\hat{\Delta}\rVert^{4}$
$\displaystyle\leq$ $\displaystyle
2\left[\frac{4}{A}\left(1-\frac{1}{A}\right)^{2}+\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)-\frac{8}{A^{2}}\left(1-\frac{1}{A}\right)^{2}\right]\lVert\hat{\Delta}\rVert^{4}+\frac{2}{A^{2}}\left(1-\frac{1}{A^{2}}\right)\lVert\hat{\Delta}\rVert^{4}$
$\displaystyle=$
$\displaystyle\left(\frac{8}{A}-\frac{26}{A^{2}}+\frac{40}{A^{3}}-\frac{22}{A^{4}}\right)\lVert\hat{\Delta}\rVert^{4}$
$\displaystyle\leq$
$\displaystyle\frac{8}{A}\lVert\hat{\Delta}\rVert^{4}\qquad(\text{when }A\geq
2)$

In particular, when $A=1$, we can see that $\operatorname{Var}[X]=0$, which is
as expected since the output $\ell_{2}$ difference will always be 0.
Therefore, we can conclude that

$\operatorname{Var}[\lVert\tilde{\Delta}\rVert^{2}]=\operatorname{Var}[\lVert\hat{\Delta}\rVert^{2}+X]=\operatorname{Var}[X]\leq\frac{8}{A}\lVert\hat{\Delta}\rVert^{4}$

## References

  * [1] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  Journal of Computer and System Sciences, 58(1):137–147, 1999.
  * [2] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  Journal of the ACM (JACM), 53(3):307–323, 2006.
  * [3] Piotr Indyk and Andrew McGregor.  Declaring independence via the sketching of sketches.  pages 737–745, 01 2008.
  * [4] Mark N. Wegman and J.Lawrence Carter.  New hash functions and their use in authentication and set equality.  Journal of Computer and System Sciences, 22(3):265–279, 1981.
  * [5] Minhaz Fahim Zibran.  Chi-squared test of independence.  Department of Computer Science, University of Calgary, Alberta, Canada, pages 1–7, 2007.
  * [6] George Kingsley Zipf.  Human behavior and the principle of least effort: An introduction to human ecology.  Ravenio Books, 2016.