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

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\usepackage{tikz}
\usepackage{algorithm}% http://ctan.org/pkg/algorithm
\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx
\usepackage{caption}
\usepackage{amsmath}
\usetikzlibrary{positioning, decorations.text}
\usepackage{wrapfig}
\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{13}{March 20, 2019}{Ronitt Rubinfeld}{Michal Shlapentokh-Rothman}

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

\section{Outline}
Today, we will continue our discussion about testing the uniformity of a distribution in sub-linear time. We will focus on the analysis of the algorithm that we went over in the previous lecture.
\begin{itemize}
	\item Setup and Review from Last Lecture
	\item Analysis
\end{itemize}
\section{Setup and Review from Last Lecture}
Our overall goal is to be able to pass a distribution, $D$, if it is uniform with probability greater than $\frac{2}{3}$ and reject a distribution $D$ with probability greater than $\frac{2}{3}$, if the $dist(D,Uniform)>\epsilon$. There are two definitions that we consider for distance functions, $L_1$ and $L_2$. 
\begin{definition}
The $L_1(p,q)$ or the $L_1$ distance between distributions $p$ and $q$ is
\[ 
L_1(p,q)=||{p-q}_1||_{1}=\sum_{x \in D}|p(x)-q(x)|
\]
\end{definition}
\begin{definition}
The $L_2(p,q)$ or the $L_2$ distance between distributions $p$ and $q$ as 
\[
L_2(p,q)=||p-q||_{2}=\sqrt{\sum_{x \in D}{(p(x)-q(x))^2}}
\]
\end{definition}
It is important to note the relationship between these two definitions:
\[
||p-q||_{2} \leq ||p-q||_{1} \leq \sqrt{n}||p-q||_{2}
\]
where $n$ is the number of points in $p$ and $q$.\\~\\ 
We can also identify an important fact about the \textit{squared} $L_2$ distance when determining the distance between a distribution $p$ and the uniform distribution $U$
\[
||p-u||^2_2=\sum_{x \in D} p^2(x) - \frac{1}{n}
\]
where we will define $||p||^2_2$ as the collision probability. Please see Lecture $12$ notes for a more detailed explanation of this fact. 
\\~\\ 
The last part we will review from last lecture is the algorithm we will use for determining the distance between a distribution and the uniform distribution.
\begin{algorithm}[H]
\caption{Uniformity Testing}
\begin{algorithmic}
\State{Take $s$ Samples}
\State{$\hat{c} \leftarrow \textrm{estimate of } ||p||_2^2 \textrm{ from sample}$}
\If{$\hat{c}<\frac{1}{n}+\delta$}
	\State Pass
\Else
	\State Fail
\EndIf
\end{algorithmic}
\end{algorithm}

\section{Analysis}
The rest of the lecture will cover three questions we can ask about the algorithm (described at the end of the last section):
\begin{itemize}
\item  How well should we estimate $||p||_2^2$?
\item What should $\delta$ be for the last statement? 
\item How many samples should we take?
\end{itemize}
\subsection{Estimating Collision Probability}
We will start with a naive idea for estimating $||p||_2^2$ or the collision probablility. 
\begin{algorithm}[H]
\caption{Naive $||p||_2^2$}
\begin{algorithmic}
\State{Take $s$ samples from $p$}
\For{each pair $k$}
	\If{$X_k=X_{k+1}$}
		\State{$\sigma_{k}=1$ where $\sigma_{k}$ is an indicator variable}

	\Else
		\State{$\sigma_k=0$}
	\EndIf
\EndFor
\State{Output $\hat{c} \leftarrow {\frac{\sum^k_{k=1}\sigma_k}{k}}$}

\end{algorithmic}
\end{algorithm}
This algorithm gives us $\Theta(k)$ samples of collision probability from $k$ samples of $p$. We would like a better query complexity than this. 
\\~\\
A better idea is to `recycle' pairs and use \textbf{all} pairs in a sample. This way we can get $\Theta(k^2)$ samples of collision probability from $k$ samples.
\begin{algorithm}[H]
\caption{Recycle $||p||_2^2$}
\begin{algorithmic}
\State{Take $s$ samples from $p$}
\For{each $1\leq i \leq j \leq s$}
	\If{$X_i=X_j$}
		\State{$\sigma_{ij}=1$}
	\Else
		\State{$\sigma_{ij}=0$}
	\EndIf
\EndFor
\State{Output $\hat{C} \leftarrow {\frac{\sum_{i<j}\sigma_{ij}}{{S \choose 2}}}$}
\end{algorithmic}
\end{algorithm}
Note that $\sigma_{ij}$s are not independent so we cannot use Chernoff to bound our error. Also, note that the expectation of \textbf{both} algorithms is correct and equals to the collision probability.
\\~\\
The goal of the rest of our analysis is to show that with enough samples the expectation of our estimate is close enough to the collision probability. Formally, we want to show
\[
E[\hat{c}]=\frac{1}{{s \choose 2}}{s \choose 2}E[\sigma_{ij}]=||p||_2^2
\]
\subsection{Picking $\delta$}
Since we are approximating the collision probability, we need to determine how good of an estimate we need to satisfy the algorithm we described in the first section. 
\\~\\
Let $\Delta=\frac{\epsilon^2}{2}$. Then we have:
\[
|\hat{c}-||p||_2^2|<\Delta=\frac{\epsilon^2}{2}
\]
When $\Delta=\frac{\epsilon^2}{2}$, the algorithm will produce the correct behavior (with enough samples taken):
\begin{itemize}
	\item If $p=U_{[n]}$ then $\hat{c} \leq ||U_{[n]}||^2 + \Delta=\frac{1}{n} + \frac{\epsilon^2}{2}$, so the test will pass.
	\item If $||p-U_{[n]}||_2 > \epsilon$ then $||p-U_{[n]}||_2^2>\epsilon^2$. We will also show that if this happens then $||p||_2^2=||p-U_{[n]}||_2^2+\frac{1}{n} > \epsilon^2+\frac{1}{n}$ and $\hat{c} > ||p||_2^2-\Delta \geq \epsilon^2 +\frac{1}{n} -\Delta = \epsilon^2+\frac{1}{n}-\frac{\epsilon^2}{2}=\frac{\epsilon^2}{2}+\frac{1}{n}$, so the test will fail.
\end{itemize}
Now we have answered two of our three questions. To estimate the collision probability, we will use the `Recycle' algorithm and $\delta$ should equal $\frac{\epsilon^2}{2}$. The next section will show that the number of samples we need to take can be done in sub-linear queries.
\subsection{Determining the Number of Samples}
The samples we are drawing are not independent, we will be using Chebyshev's inequality to bound our error:
\[
Pr[|\hat{c}-||p||_2^2|>p] \leq \frac{Var[\hat{c}]}{p^2}
\]
From the previous section, we can say the following
\[
Var[\hat{c}]=Var[\frac{1}{{s \choose 2}}\sum_{i<j}\sigma_{ij}]=\frac{1}{{s \choose 2}^2}Var[\sum_{i<j}\sigma_{ij}]
\]
Noting that $Var[aX]=a^2Var[x]$, we will bound $Var[\sum_{i<j}\sigma_{ij}]$.
\begin{lemma}
$Var[\sum_{i<j}\sigma_{ij}] \leq 4 {\left({s \choose 2}||p||_2^2\right)}^{\frac{3}{2}}$
\end{lemma}
\begin{proof}
We will start with a definition:
\begin{definition}
$\overline{\sigma_{ij}}=\sigma_{ij}-E[\sigma_{ij}]=0$
\end{definition}
The reason why we need this definition is because we will use it as a trick to rewrite $E[\sum \sigma_{ij}]^2$:
\[
Var[\sum \overline{\sigma_{ij}}]=E[(\sum \overline{\sigma_{ij}}-E[\sum \overline{\sigma_{ij}}])^2]=E[(\sum \sigma_{ij}-E[\sum \sigma_{ij}])^2]=Var[\sum \sigma_{ij}]
\]
So $E[\overline{\sigma_{ij}}]=0$. We will also use several other facts:
\begin{itemize}
	\item $E[\overline{\sigma_{ij}}\,\overline{\sigma_{kl}}] \leq E[\sigma_{ij}\sigma_{kl}]$
	\item ${\left(\sum{p(x)^3}\right)}^{\frac{1}{3}} \leq {\left(\sum{p(x)^2}\right)}^{\frac{1}{2}}$
	\item $s^2 \leq 3{s \choose 2}$
	\item ${s \choose 3} \leq 
	\frac{s^3}{6}$
\end{itemize}
Now, we can say
\[
Var[\sum_{i<j}\sigma_{ij}]=E[{\left(\sum_{i<j}\sigma_{ij}-E[\sum_{i<j}\sigma_{ij}]\right)}^2]=E[(\sum_{i<j} \overline{\sigma_{ij}})^2] =
\]
\begin{align}
E[\sum_{i<j}(\overline{\sigma_{ij}}^2) \\
+\sum_{i<j,k<l}\overline{\sigma_{ij}} \, \overline{\sigma_{kl}} \\
+\sum_{i<j,k<l}\overline{\sigma_{ij}} \, \overline{\sigma_{il}}\\
+\sum_{i<j,k<j}\overline{\sigma_{ij}} \, \overline{\sigma_{kj}}\\
+\sum_{i<j,j<l}\overline{\sigma_{ij}} \, \overline{\sigma_{jl}}\\
+\sum_{i<j,k<i}\overline{\sigma_{ij}} \, \overline{\sigma_{ki}}]
\end{align}
We will go through each part of the equation and simplify it using the facts we stated earlier.
\begin{enumerate}
	\item $E[\sum_{i<j}\overline{\sigma_{ij}^2}]\leq E[\sum \sigma_{ij}^2]={s \choose 2}||p||_2^2$. Note that we can make this statement because $E[\sigma_{ij}]=E[\sigma_{ij}^2]$ since $\sigma_{ij}$ is an indicator variable.
	\item We can use our trick to simplify the second term where $i,j,k,l$ are all distinct. 
	\[
	E[\sum_{i<j,k<l} \overline{\sigma_{ij}}\,\overline{\sigma_{kl}}] \leq \sum E[\overline{\sigma_{ij}}] E[\overline{\sigma_{kl}}]=0
	\]
	\item $E[\sum \overline{\sigma_{ij}} \, \overline{\sigma_{il}}] \leq E[\sum_{i,j,l \text{ distinct}} \sigma_{ij}\sigma_{il}]= \sum_{i,j,l \text{ distinct}} Pr[x_i=x_j=x_l]$. The probability that the three indicator variables are equal to each other is the same as the probability of a three way collision, which we can simplify using the facts: ${s \choose 3}\sum_{x} p(x)^3 \leq \frac{s^3}{6}(\sum_{x}p(x)^2)^{\frac{3}{2}} \leq \frac{\sqrt{3}}{2}{s \choose 2}^{\frac{3}{2}}(||p||_2^2)^{\frac{3}{2}}$
	\item Same as $3$
	\item Same as $3$
	\item Same as $3$
\end{enumerate}
We can put all of this together to say the following
\[
Var[\sum_{i<j} \sigma_{ij}]=Var[\sum_{i<j} \overline{\sigma_{ij}}] \leq {s \choose 2}||p||_2^2 +0 + 4(\frac{\sqrt{3}}{2})({s \choose 2}||p||_2^2)^{\frac{3}{2}} \leq 4[{s \choose 2}||p||_2^2]^{\frac{3}{2}}
\]
\end{proof}
We can now plug the lemma into Chebyshev with $p=\frac{\epsilon^2}{2}$:
\[
Pr[|\hat{c}-||p||_2^2| > \frac{\epsilon^2}{2}] \leq \frac{Var[\hat{c}]}{\epsilon^4}4 \leq \frac{4[{s \choose 2}||p||_2^2]^{\frac{3}{2}}}{{s \choose 2}^2 \epsilon^4}4 \leq \frac{32}{\epsilon^4}\frac{1}{s}||p||_2^3
\]
Thus, to get the approximating we would like, we can set the number of samples, $s$ to be $\geq \omega{\frac{1}{\epsilon^4}}$.
\subsection{Adjustment for $L_1$}
For the analysis above, we were assuming that the number of samples needed for the $L_2$ distance was sufficient. However, we need to modify that value to satisfy the $L_1$ distance as well. If a distribution is uniform, then we can say the following
\[
||p-U||_1=0 \Leftrightarrow ||p-U||_2^2 =0 \Leftrightarrow ||p||_2^2=\frac{1}{n}
\]
If a distribution is $\epsilon$-far from uniform, then
\[
||p-U||_1 >\epsilon \Rightarrow ||p-U||_2 > \frac{\epsilon}{\sqrt{n}} \Rightarrow ||p-U||_2^2 > \frac{\epsilon^2}{n} \Rightarrow ||p||_2^2 >\frac{1}{n}+\frac{\epsilon^2}{n}
\]
This implies that we can have an addistive estimate with error $\leq \frac{\epsilon^2}{2n}$ or multiplicative error $\leq(1\pm \frac{\epsilon^2}{3})$ which would occur if additive error is $\leq \frac{\epsilon^2}{3n}||p||_2^2$.
Now, we need to figure out how to choose the right number of samples such that our additive error is less than or equal to $\frac{\epsilon^2}{3n}||p||_2^2$. We can state the following where $k$ is a constant:
\[
Pr[|\hat{c}-||p||_2^2|] \geq \delta ||p||_2^2] \leq \frac{k||p||_2^3}{s\delta^2(||p||_2^2)^2} \leq \frac{k}{s \delta^2||p||_2} \leq \frac{k\sqrt{n}}{s\delta^2}
\]
The statement is true because $||p||_2^2 >\frac{1}{n}$ so $||p||_2 >\frac{1}{\sqrt{n}}$ meaning $\frac{1}{||p||_2}<
\sqrt{n}$. Because of the statements above, if we pick the number of samples $s$ to be $>> \frac{\sqrt{n}}{\epsilon^4}$ then we have a small probability of error which is approximately $\frac{k\sqrt{n}}{s\epsilon^4}$.
\end{document}