\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

% \usepackage{mathrsfs}
\usepackage[mathscr]{euscript}
\usepackage{amsmath}
\usepackage{scalerel,amssymb}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}


\def\P(#1){\Phelper#1|\relax\Pchoice(#1)}
\def\Phelper#1|#2\relax{\ifx\relax#2\relax\def\Pchoice{\Pone}\else\def\Pchoice{\Ptwo}\fi}
\def\Pone(#1){\Pr\left( #1 \right)}
\def\Ptwo(#1|#2){\Pr\left( #1 \,\middle|\, #2 \right)}
\def\Pr{\mathbf{Pr}}
\def\Pois{\textnormal{Pois}}
\def\PoisBf{\mathbf{Pois}}
\def\Exp{\mathbb{E}}

\usepackage{amsmath}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{14: Poissonization and Closeness Testing}{October 20, 2020}{Ronitt Rubinfeld}{Pachara Sawettamalya}

%%%% body goes in here %%%%

\section{Overview}
Today we will show how to test closeness of two \textit{unknown} distributions in a sublinear number of samples. The Plug-in Estimator that we saw in previous lectures posits two major concerns: the dependency and the $L_2$-norm. We will introduce a few procedures that can help us resolve these issues.

\section{Setting}

\subsection{Probability Distribution}
For a probability distribution $p$ on a discrete domain $\mathcal{D}$, for any $i \in \mathcal{D}$, we refer to $\Pr_{x\in \mathcal{D}}(x=i)$ as $p_i$ or $p(i)$ depending on the context.

\subsection{Distances and Norm}

Suppose we have two distributions $p$ and $q$ on the same discrete domain $\mathcal{D}$, we define two distances functions as follows.

\begin{itemize}
    \item $L_1$-distance : $||p-q||_1 = \sum_{i \in \mathcal{D}}{|p_i-q_i|}$
    \item $L_2$-distance : $||p-q||_2 = \sqrt{\sum_{i \in \mathcal{D}}{(p_i-q_i)^2}}$
\end{itemize}

In addition, we denote an $L_2-$norm of a distribution $p$ as $\sqrt{\sum_{i \in \mathcal{D}}{p_i^2}}$.

\subsection{Closeness Testing}
Given two \textit{unknown} distributions $p$ and $q$ on the same size-$n$ domain $\mathcal{D}$. This means we cannot make any prior assumption of $p$ or $q$. The only operation allowed is to sample from either distributions. We want to determine a tester with the following behaviors.

\begin{itemize}
    \item If $p = q$, then output PASS
    \item If $||p-q||_1 \leq \varepsilon$, then output FAIL with probability at least $\frac{3}{4}$
\end{itemize}

The rest of this note is dedicated to showing the tester with $O(n^{\frac{2}{3}}\varepsilon^{-\frac{4}{3}})$ samples. It is also worth recalling the \textit{typical strategy}, such as the one used in the Plug-in Estimator, is as follows. We take a multiset $S$ of $m$ samples and count $x_i = \textnormal{the number of } i \textnormal{'s occurrences in S}$. We note here that there are two major concerns about this approach: the dependency of $x_i$'s and the magnitude of $p$'s $L_2-$norm.

\section{Resolving Dependency via Poissonization}
The first concern that arises is the dependency of $x_i$'s. This is because we only limit the total number of samples to $m$. For example, $x_i > \frac{m}{2}$ infers $x_j < \frac{m}{2}$ for the rest of the domain. To resolve this problem, we introduce the Poisson Distribution.

\begin{definition}
A random variable $X$ is said to have a Poisson Distribution $\PoisBf(\lambda)$ if for any non-negative integer $k$, $\Pr(x=k) = \frac{e^{-\lambda}\lambda^k}{k!}$. In addition, we have $\Exp[X] = \Var[X] = \lambda$.
\end{definition}

We now propose two algorithms for sampling $x_i$'s. In Algorithm 1, we first fix $\hat{m}$ drawn from a Poisson distribution and do $\hat{m}$ sampling, while in Algorithm 2, we individually sample the number of occurrences of $x_i$ based on a Poisson distribution.

\begin{algorithm}[H]
\caption{: Single-Poissonization$(p,\mathcal{D})$}
\begin{algorithmic}[1]


\State{$\hat{m} \leftarrow \Pois(m)$}
\State{$S_1 \leftarrow \hat{m}$ samples from distribution $p$}
\For{$i \in [n]$}
    \State{$x_i^{(1)} \leftarrow$ occurrences of $i$ in $S_1$}
\EndFor
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{: Individual-Poissonization$(p,\mathcal{D})$}
\begin{algorithmic}[1]
\State{$S_2 \leftarrow \phi$}
\For{$i \in [n]$}
    \State{Sample $x_i^{(2)} \in \Pois(mp_i)$} and add $x_i^{(2)}$ copies of $i$ to $S_2$
\EndFor
\State{Randomly permute $S_2$}
\end{algorithmic}
\end{algorithm}


\begin{claim}
The distributions of $x_i$'s in Algorithm 1 and Algorithm 2 are equivalent.
\end{claim}

\begin{proof}
Let's consider 
\begin{equation*}
\begin{split}
\Pr(x_i^{(1)} = c) & = \sum_{k\geq c}{\Pr(\hat{m}=k)\cdot\binom{k}{c} p_i^k(1-p_i)^{k-c}} \\
& = \sum_{k \geq c}{ \frac{e^{-m}m^k}{k!}}\cdot\frac{k!}{c!(k-c)!}\cdot p_i^c(1-p_i)^{k-c} \\
& = \frac{e^{-m}\cdot (mp_i)^c}{c!}\cdot \sum_{k \geq c}\frac{m^{k-c}(1-p_i)^{k-c}}{(k-c)!} \\
& = \frac{e^{-m}\cdot (mp_i)^c}{c!}\cdot e^{m(1-p_i)} = \frac{e^{-mp_i}\cdot (mp_i)^c}{c!} = \Pr(x_i^{(2)} = c)
\end{split}
\end{equation*}
In addition, we can check that the joint distributions are equivalent in a similar analysis. 
\end{proof}

A key observation is that the sampling of $x_i^{(2)}$'s from Algorithm 2 is independent. Since the distribution from both algorithms are equivalent, it must also be independent in Algorithm 1.


\section{Resolving $L_2$-norm via Reduction}

It is also known that the magnitude of distribution's $L_2-$norm affects the sample complexity. In particular, distributions with large $L_2-$norm requires more samples to check. For this reason, we can now state our goal. We need a way to transform the initial distributions $(p,q)$ to $(p',q')$ such that
\begin{itemize}
    \item If $p = q$, then $p' = q'$
    \item If $||p-q||_1 \geq \varepsilon$, then $||p'-q'||_1 \geq \varepsilon$
    \item $||p'||_2$ is small.
\end{itemize}

It is crucial to note that this reduction does not require $||q'||_2$ to be small though it would be ideal. We will discuss in the next section that the small $||q'||_2$ is unnecessary as we can circumvent it. 

We propose a procedure to transform $(p,q)$ into $(p',q')$ as follows.

\begin{algorithm}[H]
\caption{: Transform$(p,q)$}
\begin{algorithmic}[1]
\State{$\mathcal{D}' \leftarrow \phi$  }
\State{$\hat{m} \leftarrow \Pois(m)$}
\State{$S \leftarrow \hat{m}$ samples drawn from $p$ over domain $[n]$}
\For{$i\in [n]$}
\State{$b_i \leftarrow$ occurrences of $i$ in $S$}
\State{add $b_i+1$ elements $(i,1), (i,2),...(i,b_i+1)$} to $\mathcal{D}'$
\EndFor
\State{$p' \leftarrow$ a distribution on $\mathcal{D'}$ where $p'(i,j) = \frac{p_i}{b_i+1}$}
\State{$q' \leftarrow$ a distribution on $\mathcal{D'}$ where $q'(i,j) = \frac{q_i}{b_i+1}$}
\State{Output $(p',q')$}
\end{algorithmic}
\end{algorithm}

Since $p_i$'s and $q_i$'s are unknown, we cannot directly construct $p'$ and $q'$ based on the probability distributions given in Line 7-8; however, there is an easy fix. For $p'$, we can sample $i$ from the distribution $p$ and sample $j$ uniformly from $\{1,2,...,b_i+1\}$, and likewise for $q'$.


Furthermore, notice that  $\hat{m} = O(m)$ with high probability. This means that with high probability, Algorithm 3 only uses $O(m)$ samples. Plus, we have $|\mathcal{D}'| = \sum_{i\in[n]}{b_i+1} = n + \sum_{i\in[n]}{b_i} = n+ |S| = n+\hat{m}$. 

We will now show that the output $(p',q')$ has the desired behaviors. The first behavior is trivially true -- if $p=q$ then the probability distribution of $p'$ and $q'$ will be identical which is equivalent to $p'=q'$.

\begin{claim} $||p-q||_1 = ||p'-q'||_1$ \end{claim}
This is true as we can see that
$$||p'-q'||_1 =  \sum_{i\in[n]}\sum_{j\in[b_i+1]}{|p'(i,j)-q'(i,j)} = \sum_{i\in[n]}\sum_{j\in[b_i+1]}\frac{|p_i-q_i|}{b_i+1} = \sum_{i\in[n]}{|p_i-q_i|} = ||p-q||_1 $$

\begin{claim} $\Exp\left[ ||p'||_2^2 \right] \leq \frac{1}{m}$ \end{claim}

\begin{proof} First of all, recall that as we discussed in Section 3, the distribution of $b_i$ is indeed $\Pois(\lambda_i)$ when $\lambda_i=mp_i$. This implies
\begin{equation*}
\begin{split}
\Exp\left[\frac{1}{b_i+1}\right] & = \sum_{k \geq 0}{\frac{1}{k+1}\cdot\frac{e^{-\lambda_i}\lambda_i^k}{k!}} = \frac{1}{\lambda_i} \cdot \sum_{k \geq 1}{\frac{e^{-\lambda_i}\lambda_i^{k+1}}{(k+1)!}} \leq \frac{1}{\lambda_i} = \frac{1}{mp_i} 
\end{split}
\end{equation*}
Therefore we will have
\begin{equation*}
\begin{split}
\Exp\left[ ||p'||_2^2 \right] &= \Exp\left[\sum_{i\in[n]}\sum_{j\in[b_i+1]}{p'(i,j)^2}\right] = \Exp\left[\sum_{i\in[n]}\sum_{j\in[b_i+1]}{\left(\frac{p_i}{b_i+1}\right)^2}\right] = \Exp\left[\sum_{i\in[n]}{\frac{p_i^2}{b_i+1}}\right] \\
& = \sum_{i \in [n]}p_i^2\cdot \Exp\left[\frac{1}{b_i+1}\right] \leq \sum_{i \in [n]}\left(p_i^2\cdot\frac{1}{mp_i}\right) = \frac{1}{m} \cdot \sum_{i \in [n]}{p_i} = \frac{1}{m}
\end{split}
\end{equation*}
This completes the proof. \end{proof}

\section{Circumventing Large $||q'||_2$}

\begin{theorem}
Given distributions $p,q$ on a discrete domain of size $n$ and $b \geq \max\left (||p||_2,||q||_2\right)$. Then we can distinguish the case of $p=q$ from $||p-q||_1\geq \varepsilon$ in $O\left(\frac{bn}{\varepsilon^2}\right)$ samples.
\end{theorem}

We will not prove this theorem, but we rather give a sketch proof to a useful corollary.

\begin{corollary}
Given distributions $p,q$ on a discrete domain of size $n$ and $b \geq \min\left (||p||_2,||q||_2\right)$. Then we can distinguish the case of $p=q$ from $||p-q||_1\geq \varepsilon$ in $O\left(\frac{bn}{\varepsilon^2}+\sqrt{n}\right)$ samples.
\end{corollary}

\begin{proof-sketch}  The following procedure gives the desired tester.
\begin{enumerate}
    \item Estimate $||p||_2$ and $||q||_2$ within a multiplicative factor of $C$ when $C>1$ is a constant. This can be done within $O(\sqrt{n})$ samples.
    \item If the estimated $||p||_2$ and $||q||_2$ are more than a multiplicative factor of $C$ away, output FAIL. We can do this because if it is the case, we can guarantee that $||p||_2 \ne ||q||_2$ which implies $p \ne q$.
    \item Run the tester from Theorem 5 with $b' = Cb$, and gives the same output. We only need to verify that $b' = Cb \geq C \cdot \min\left (||p||_2,||q||_2\right) \geq \max\left (||p||_2,||q||_2\right)$ where the last inequality follows from the fact that $||p||_2$ and $||q||_2$ are at most a multiplicative factor of $C$ away. This only uses $O\left(\frac{bn}{\varepsilon^2}\right)$ samples according to Theorem 5.
\end{enumerate}
This completes the proof.
\end{proof-sketch}

The key takeaway from Corollary 6 is that we only need $||p'||_2$ to be small but not necessary for $||q'||_2$. This because we can set $b=||p'||_2$ regardless of $q'$.

\section{The Closeness Tester}

Now we can give a tester for closeness between two distributions as follows.
\begin{algorithm}[H]
\caption{: Closeness-Tester$(p,q)$}
\begin{algorithmic}[1]
\State{$k \leftarrow n^{\frac{2}{3}}\varepsilon^{-\frac{4}{3}}$  }
\State{$(p',q') \leftarrow (p,q)$ transformed by Algorithm 3 with $m=k$ }
\State{Run the tester from Corollary 6 on $(p',q')$ and give the same output}
\end{algorithmic}
\end{algorithm}

To begin with, we notice that Algorithm 4 can distinguish $p'=q'$ and $||p'-q'||_1\geq \varepsilon$ due to Corollary 6. Plus, in section 4 we have shown that $(p,q)$ and $(p',q')$ are equivalent in closeness testing. Therefore Algorithm 4 successfully distinguishes $p=q$ and $||p-q||_1\geq \varepsilon$.

Last but not least, let's analyze the number of samples needed.

\begin{claim}
With high probability, Algorithm 4 uses $O(n^{\frac{2}{3}}\varepsilon^{-\frac{4}{3}})$ samples
\end{claim}
\begin{proof}
We have established that with high probability, transforming $(p,q)$ into $(p',q')$ uses at most $O(k) = O(n^{\frac{2}{3}}\varepsilon^{-\frac{4}{3}})$ samples.

In addition, Claim 4 gives $\Exp(||p'||_2^2)\leq \frac{1}{k}$ which implies $||p'||_2=O\left(\frac{1}{\sqrt{k}}\right)$ with high probability. This also means we can set $b = O\left(\frac{1}{\sqrt{k}}\right)$ in Corollary 6, and the tester will use $O(\frac{n}{\varepsilon^2\sqrt{k}}+\sqrt{n}) = O(n^{\frac{2}{3}}\varepsilon^{-\frac{4}{3}})$ samples.

In total, Algorithm 4 uses $O(n^{\frac{2}{3}}\varepsilon^{-\frac{4}{3}})$ samples.
\end{proof}










\end{document}



