\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage[makeroom]{cancel}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring'20)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{2: Approximate Counting Continued, Hashing}{Jan 23,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Rebecca Calinsky}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Approximate Counting Continued . . .}
\textbf{Recap from last lecture:}
\\
\textbullet{} Problem simply concerns counting up to $n$\\
\textbullet{} Morris Algorithm was introduced, which has one register, $X$, initialized to $0$\\
\textbullet{} We increment as we see ticks, but much more slowly than if we just count \\
\textbullet{} The bigger $X$ becomes, the less likely it is to increment
\vspace{0.42cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Morris Algorithm}
- Initialize $X = 0$ 
\vspace{\baselineskip} \\
- At tick: $X = 
\begin{cases} 
X \text{, with probability }1-2^{-X} \\
X+1 \text{ with probability }2^{-X}\\
\end{cases}\\\\
\text{- The estimator: }\hat{n} = 2^X - 1$ 
\vspace{30px}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace{\baselineskip}
\textbf{PART 1: What we proved last lecture . . .}

%% CLAIM 1
\vspace{\baselineskip}
\begin{claim}
When we define  $X_{n} = X$ , the count after $n$ ticks, then $\E[\hat{n}]=\E[2^{X_n}-1]=n$
\end{claim}
\begin{proof}
(Supplied last lecture: showed expectation of the estimator equal to $n$ using induction on $n$)
\end{proof}
\vspace{30px}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{PART 2: We ask, ``Did we gain anything?"}

\noindent In Part 1, the estimator is in the right ballpark, and now we want to prove that the number of bits necessary has improved drastically (lg lg $n$, instead of lg $n$, where $\lg$ is implicitly $\lg_2$ from here on).
%% CLAIM 2
\begin{claim}
$\Pr[\lg{X} \leq c \cdot \lg \lg{n}] \geq 0.9$ for some $c \geq 1$
\end{claim}

\begin{proof}
  Apply the \textbf{Markov Bound} on $\hat{n}$:
  $$ \Pr [\hat{n} > 10n] \leq \frac{n}{10n} = 0.1 $$
  $$ \implies \Pr[2^{X_{n}}-1 \leq 10n] \geq 0.9 $$
  $$ 2^{X_{n}}-1 \leq 10n \implies \lg X_{n} \leq \lg \lg{(10n+1)} $$
  $$ \implies \exists \; c \geq 1 \text{ such that } \Pr[\lg{X_{n}} \leq c \cdot \lg \lg n] \geq \frac{9}{10}  $$
\end{proof}

\subsection{Intuition behind the algorithm}
We are counting up to $n$ ticks, and we can think about $n$ as being represented in binary in the following illustration:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{bits.PNG}
\end{figure}

In the above, the index of the most significant bit $i_{max}$ (whose contribution is $2^{\lfloor \lg{n}\rfloor} \in [n/2, n]$ ) is all you need in order to have a factor 2 approximation of the number $n$. The number of bits necessary to communicate the number $i_{max}$ is the $\lg$ of the number of bits needed to represent $n$, which results in $\lg \lg n$.

\vspace{\baselineskip}
\indent If $X = $ the most significant bit (index) of the current $n$, then $X$ should increase only when $n$ roughly doubles. In other words, the larger of number, the less frequently its max index changes.

\vspace{\baselineskip}
\indent $X$ is incremented with $\Pr \approx \frac{1}{n} \approx 2^{-X}$

\vspace{\baselineskip}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Show $\mathbf{\hat{n} \approx n}$ with good probability}

We will use another concentration bound called the \textbf{Chebyshev Bound}, and compute $\var[\hat{n}]$.\\
\vspace{\baselineskip}
%CLAIM 3
\begin{claim} 
$\var[\hat{n}] \leq \frac{3}{2}n(n+1)+1 $
\end{claim}
\vspace{\baselineskip}
\begin{proof}
$\var[\hat{n}] = \var[2^{X_{n}}-1] = \E[(2^{X_{n}}-1)^2]-n^2 = \E[2^{2X_{n}}]+ \underbrace{ 1-2  \underbrace{\E[2^{X_{n}}]}_{n+1}-n^2}_{\leq 0} \leq \E[2^{2X_{n}}]$\\
Inductive hypothesis:
$$\E[2^{2X_{n}}] \leq \frac{3}{2}n(n+1)+1$$
\\
\vspace{\baselineskip}
\noindent Base case: $n=0: \E[2^{0}] = 1 \leq 1$

\noindent Assume the inductive hypothesis for $\E[2^{2X_{n-1}}]$

\vspace{\baselineskip}
%%% 31:25
\noindent Now we want to compute the expectation:

$$\E[2^{2X_{n}}]=\E_{X_{n-1}}\Big[\E_{X_{n}}[2^{2X_{n}}]\Big]$$

$$ = \sum_{i \geq 0} \Pr[X_{n-1} = i] \cdot \E_{X_{n}}[2^{2X_{n}}| X_{n-1} = i] $$
$$ = \sum_{i \geq 0} \Pr[X_{n-1} = i] \cdot [2^{-i} \cdot 2^{2(i+1)}+(1-2^{-i}) \cdot 2^{2i}] $$

$$ = \sum_{i \geq 0} \Pr[X_{n-1} = i][\cancelto{3}{4} \cdot 2^{i} + 2^{2i}-\cancel{2^{i}}] $$
$$ = \sum_{i \geq 0} \Pr[X_{n-1} = i] \cdot 2^{i} \cdot 3 + \sum_{i \geq 0} \Pr[X_{n-1} = i] \cdot 2^{2i} $$
$$ = 3 \cdot \underbrace{ \E[2^{X_{n-1}}]}_{n, \text{ by Claim 1}} +  \underbrace{ \E[2^{2X_{n-1}}]}_{\leq \frac{3}{2}n(n-1)+1} $$

$$ \leq \frac{3}{2}n(n+1)+1 $$
\end{proof}

%%%%%% 40:17
\vspace{\baselineskip}
\subsection{Chebyshev}
By definition of Chebyshev:
$$ \Pr[\,|\hat{n} - \E{(\hat{n})}| > \lambda \,] \; \leq \; \frac{\var[\hat{n}]}{\lambda^2} \;\;\;\;\;\;\; \leq \;\; \frac{\frac{3}{2} n(n+1)+1  }{\lambda^2} < 0.1 $$

\vspace{\baselineskip}
\noindent It is good enough to have $\lambda = 5n$, since this is an analysis and Chebyshev holds for any bound.

\vspace{\baselineskip}
\noindent The algorithm does not give a good accuracy, but there is a standard trick to boost the accuracy to get a much better estimate. In particular, we want to do the following:

\vspace{\baselineskip}
\noindent \textbf{GOAL:} \;\; Estimate $n$ up to $\pm \; \epsilon \, n$ \, for small $\epsilon > 0 $.

\noindent \textbullet{}  Think of epsilon as being $0.1$ which is comparable to $10\%$ error.

\noindent \textbullet{}  ``Estimate up to" means $(1-\epsilon) n \leq   \hat{n}   \leq  (1+\epsilon) n $

\noindent \textbullet{}  To reach our goal, we will essentially do a bunch of counters and average them (\textbf{Morris+ Algorithm})

\vspace{\baselineskip}
\subsection{Morris+ Algorithm}
\noindent - Use $k=$ TBD counters $X^1, X^2, ..., X^k. $

\vspace{\baselineskip}
\noindent - Each $X^i$ uses Morris Algorithm and is i.i.d.

\vspace{\baselineskip}
\noindent - The new estimate will be $\hat{n} = \frac{1}{k}\sum_{i=1}^{k} \hat{n}^{i}$,   where $\hat{n}^{i} = 2^{X^i} - 1$

\vspace{\baselineskip}
\vspace{\baselineskip}
\subsection{Amplification / Variance Reduction via Repetition}

\vspace{\baselineskip}
We will do the analysis and see what we need to set $k$ to be such that we get the above goal.

%% 49:43
%% CLAIM 4
\begin{claim}
$\E[\hat{n}] = \E[ \frac{1}{k} \sum_{i=1}^{k} \hat{n}^i ] = n $, by linearity of expectation.

\end{claim}

%% CLAIM 5 (claim 2)
\begin{claim}
$\var[\hat{n}] = \frac{\var[\hat{n}^{1}]}{k}$
\end{claim}

\vspace{\baselineskip}
%% 51:33
\begin{proof}
$$\var[\hat{n}] = \var\Bigg[\frac{1}{k} \cdot \sum_{i = 1}^{k} \hat{n}^{i} \Bigg] = \frac{1}{k^{2}} \cdot \var \Bigg[ \sum_{i = 1}^{k} \hat{n}^{i} \Bigg] = \underbrace{ \frac{1}{k^{2}} \sum_{i = 1}^{k} \var[\hat{n}^{i}]}_\text{Due to linearity of variance} $$

\vspace{\baselineskip}
\vspace{\baselineskip}
\noindent Note that the variance of the sum of variables are independent of each other, because they each correspond to the estimate of a different run of the algorithm, where each run of the algorithm uses i.i.d. randomness. For this reason, we can use linearity of variance.

\vspace{\baselineskip}
\vspace{\baselineskip}
%%%%LINEARITY OF VARIANCE PROOF%%%%
Proof of \textbf{linearity of variance}:

\vspace{\baselineskip}
For two independent variables $X$ and $Y$, their covariance is zero: $Cov(X, Y) = 0$

\begin{align*}
\var{X + Y} &= \E[((X+Y) - \E[X+Y])^2] \\
&= \E[((X - \E[X]) + (Y - \E[Y]))^2] \\
&= \E[(X - \E[X])^2] + \E[(Y - \E[Y])^2] - 2\E[X - \E[X]]\E[Y - \E[Y]]\\
&= \var{X} + \var{Y} - 2\underbrace{Cov(X, Y)}_{= 0}\\\\
\therefore \;\; \var{X + Y} &= \var{X} + \var{Y}\\
\end{align*}

\vspace*{0.8cm}
Set $\lambda = \epsilon n$

\vspace{\baselineskip}
By the Chebyshev bound: $$ \Pr[ \;| \hat{n} -\E[n] | \; > \; \lambda \; ] \;\;\; \leq \;\;\; \frac{\var[\hat{n}]}{\lambda^{2}} $$

\vspace{\baselineskip}
$$ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \leq \;\;\; \underbrace{  \frac{ \frac{1}{k} \cdot (\frac{3}{2}n(n+1)+1   )  }{ \epsilon^{2}n^{2}  }}_{\text{We want this quantity to be $< 0.1$}} $$

\vspace{\baselineskip}
$$ \implies \frac{1}{k} \cdot \Bigg( \frac{3}{2} n (n+1)+1 \Bigg) < 0.1 \cdot \epsilon^{2}n^{2} $$

\vspace{\baselineskip}
$$ \implies \text{ It is enough to have }k > \Omega (\frac{1}{\epsilon^{2}}) \text{ ,\;\;\;\; where } \Omega \text{ is some large constant}  $$

\vspace{\baselineskip}
With $k$ as the above, all is satisfied and our goal is now satisfied.

\vspace{\baselineskip}
New space: \;\;\; O$\Big(  \frac{1}{\epsilon^{2}} \cdot \lg \lg n  \Big)$
\end{proof}

\vspace{\baselineskip}
\vspace{\baselineskip}
\vspace{\baselineskip}
\section{Hashing}

Hash function: $h: U \rightarrow [n]$ \;\;\;\;\;\;\;   (where U is the discrete universe)

\vspace{\baselineskip}
\noindent The main application we will be looking at is \textbf{Dictionary}.

\vspace{\baselineskip}
\vspace{\baselineskip}
\textbf{Dictionary}: fixed $U$; preprocess $S \subset U$,  $|S| = m$, s.t. given a query $x \in U$, report if $x \in S$.

\vspace{\baselineskip}
Possible solutions for this problem:

\vspace{\baselineskip}
\noindent \textbf{Sol 0 .} \;\;   Store S \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(Search time: O(m);\;\;\; Space: O($m \cdot \lg m$)  )

\noindent \textbf{Sol 0$'$.}\;\;\;\;  Binary Search Tree \; (Search time: O($\lg m$); Space: O($m \cdot \lg m$)  )

\noindent \textbf{Sol 0$''$.}\;\;\;  Bit Array \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (Search time: O($1$);\;\;\;\;\; Space: $|U|$  )  

\vspace{\baselineskip}
\vspace{\baselineskip}
\noindent \textbf{GOAL:} Ideally, we would like to combine the best of both worlds and get a deterministic algorithm with both a constant runtime and a space that is linear in the size of $S$.  We will use a hash function to get as close as possible to this goal.

\vspace{\baselineskip}
\vspace{\baselineskip}
\subsection{Solution via a Hash Function}
This solution can be thought of a variant of Solution $0''$. . .  Our universe is very large, and this is why our space is very large, so how about we reduce the universe size?

\vspace{\baselineskip}
\vspace{\baselineskip}
\textbf{Solution:} Store an array of size $n$ s.t. cell $i$ stores all items $j \; \in \; S$ s.t. $h(j) = i$.

\vspace{\baselineskip}
\noindent When this hash function is defined, it could be that a few elements from the set $S$ map into the same cell.

\vspace{\baselineskip}
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{col.PNG}
\end{figure}

In the above illustration, element $x^1$ and $x^7$ are mapped into the same cell (called a \textbf{collision}).

\vspace{\baselineskip}
\vspace{\baselineskip}
\noindent Possible ways we could store $x^1$ and $x^7$:

\vspace{\baselineskip}
\noindent \textbf{1. Hashing with chaining:} store them as a linked list.

\noindent \textbf{2. Linear probing:} instead of storing $x^7$ where it was mapped, store it in the next empty cell

\noindent \textbf{3. Cuckoo hashing}

\vspace{\baselineskip}
\noindent The main principle is that collisions are bad!
\end{document}
