\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{blindtext}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{underscore}
\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-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \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, Intro to Hashing}{Jan 14,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Akshat Agarwal, Julia Martin}}

\section{Recap}
To exactly count up to $n$ we cannot do better than $\Omega(\log{}n)$ space.
\\Hence, we were trying to device an approximate algorithm to count up to $n$ which uses space $o(\log{}n)$.
\\Introduced Morris' Algorithm which is an Approximate and Randomized algorithm for doing just that.

\section{Morris' Algorithm Continued}
Approximate and Randomized counting algorithm with reduced space usage: \\
- Initialize $X = 0$ \\
- onButtonPress: $X = 
\begin{cases} 
X \text{, with probability }1-2^{-X} \\
X+1 \text{ with probability }2^{-X}\\
\end{cases}\\\\
\text{- Estimate: }\hat{n} = 2^X - 1$ \\
\\Note:\\
- The bigger $X$ becomes, the less likely it is to increment\\

\textbf{Doubt 1: Is it a good estimator?}\\
\\
\textbullet{} $\hat{n}$ is a Random Variable\\
\textbullet{} Our Goal is to get $\hat{n}$ as close to $n$ as possible\\
\textbullet{} A good start to achieve this goal could be to make sure that the expected value of $\hat{n}$ is $n$\\

\begin{claim}
Yes, it is good. $\E[\hat{n}]=n$
\end{claim}

\begin{proof}
Define $X_n$ as the value of counter $X$ after $n$ button presses, and with $X_0$ initialized to $0$. We want the show that $\E[\hat{n}]=\E[2^{X_n}-1]=n$. We will prove by induction.\\
\\
Base case: for $n=0$, $X_0=0$; $E[2^{X_0} - 1] = 0$\\
Inductive Step: Assume for inductive hypothesis that $E[2^{X_{n-1}} - 1] = n - 1$
\\We want to show $E[2^{X_n} -1] = n$. \\
We have:
\begin{align*}
    \notag E[2^{X_n} -1] &= E_{X_n,X_{n-1},...,X_1}[2^{X_n} -1] \\
    \notag &= E_{X_{n-1},...,X_1}[E_{X_n}[2^{X_n} -1]] \\
    \notag &= E_{X_{n-1},...,X_1}[2^{-X_{n-1}}(2^{X_{n-1}+1}-1) + (1- 2^{-X_{n-1}}) (2^{X_{n-1}}-1)] \\
    \notag &= E_{X_{n-1},...,X_1}[2 - 2^{-X_{n-1}} + 2^{X_{n-1}}-1 - 1 + 2^{-X_{n-1}}] \\
    \notag &= E_{X_{n-1},...,X_1}[2^{X_{n-1}}] \\
    \notag &= E[(2^{X_{n-1}} - 1) + 1] \\
    \notag &= (n - 1) + 1  \tag{by inductive hypothesis}\\
    \notag &= n
\end{align*}
\end{proof}

\textbf{Doubt 2: Did we save space?}\\
\\
\textbullet{} Did the hassle pay off?\\
\textbullet{} Now we want to prove that the number of bits necessary to denote $n$ has improved from log($n$)\\

\begin{claim}
Yes we saved space. The number of bits taken by X, i.e. log($X$), is of the order of log(log($n$)) with probability $\geq$ 90\% \\
\end{claim}

\begin{proof}
  Apply the \textbf{Markov Bound} on $\hat{n}$, we know $\E[\hat{n}] = n$:
  $$ \Pr [\hat{n} > 10n] \leq \frac{n}{10n} = 0.1 $$
  $$ \implies \Pr[2^{X_{n}}-1 \leq 10n] \geq 0.9 $$
  Now when $2^{X_{n}}-1 \leq 10n$ (this happens with 90\% probability)
  $$ \implies 2^{X_{n}} \leq 10n + 1 $$
  $$ \implies \log \log 2^{X_{n}} \leq \log \log{(10n+1)} $$
  $$ \implies \log X_{n} \leq \log \log{(10n+1)} $$
  Hence we get, $\Pr[\log{X} = O(\log \log{n})] \geq 0.9$\\
\end{proof}

\textbf{Doubt 3: How far below the actual $n$ can our estimator $\hat{n}$ be?}\\
\\
\textbullet{} Using Markov Bounds we saw that 90\% of times $\hat{n} \leq 10 n$\\
\textbullet{} With High Probability, our guess will be above $n$ by no more than a constant factor multiple\\
\textbullet{} Now we want to check how low below the actual $n$ can our guess be.\\
\textbullet{} We will find this using Chebyshev bounds. But for that we first need the Variance of $\hat{n}$\\

\begin{claim} 
$\var[\hat{n}] \leq \frac{3}{2}n(n+1)+1 = O(n^2)$\\
\end{claim}

\begin{proof}
We know,
\begin{align*}
\notag \var[\hat{n}] &= \var[2^{X_{n}}-1] \\
\notag &= \E[(2^{X_{n}}-1)^2]-\E[(2^{X_{n}}-1)]^2 \\
\notag &= \E[(2^{X_{n}}-1)^2]-n^2 \\
\notag &= \E[2^{2X_{n}}]+ \underbrace{ 1-2  \underbrace{\E[2^{X_{n}}]}_{n+1}-n^2}_{\leq 0} \tag{$-n^2-2n-1 \leq 0$}\\
\notag &\leq \E[2^{2X_{n}}] \\
\end{align*}
Inductive hypothesis: $\E[2^{2X_{n}}] \leq \frac{3}{2}n(n+1)+1$ \\
Base case: $n=0: \E[2^{0}] = 1 \leq 1$ \\
Assume the inductive hypothesis for $\E[2^{2X_{n-1}}]$ \\

\noindent Now we want to compute the expectation:
\begin{align*}
\notag E[2^{2X_{n}}] &= E_{X_n,X_{n-1},...,X_1}[2^{2X_{n}}] \\
\notag &= E_{X_{n-1},...,X_1}[E_{X_n}[2^{2X_n}]] \\
\notag &= E_{X_{n-1},...,X_1}[2^{-X_{n-1}}(2^{2(X_{n-1}+1)}) + (1- 2^{-X_{n-1}}) (2^{2X_{n-1}})] \\
\notag &= E_{X_{n-1},...,X_1}[4\cdot2^{X_{n-1}} + 2^{2X_{n-1}} - 2^{X_{n-1}}] \\
\notag &= E_{X_{n-1},...,X_1}[3\cdot2^{X_{n-1}} + 2^{2X_{n-1}}] \\
\notag &= E[3\cdot2^{X_{n-1}} + 2^{2X_{n-1}}] \\
\notag &= 3\cdot\underbrace{ \E[2^{X_{n-1}}]}_{n, \text{ by Claim 1}} +  \underbrace{ \E[2^{2X_{n-1}}]}_{\leq \frac{3}{2}(n-1)n+1} \\
\notag &\leq \frac{3}{2}n(n+1)+1 \\
\notag &= O(n^2) \\
\end{align*}
\end{proof}

\begin{claim} 
Using the Chebyshev bound, we can find a lower bound and a tighter upper bound, such that: $\hat{n} \in [n-5n, n+5n]$\\
\end{claim}
\begin{proof}
So far, we have:
$$E[\hat{n}] = n$$
$$\var[\hat{n}] \leq \frac{3}{2}n(n+1)+1 \leq 2n^2$$
Apply the \textbf{Chebyshev Bound} on $\hat{n}$
$$ \Pr[|\hat{n} - \E{(\hat{n})}| > \lambda] \leq \frac{\var[\hat{n}]}{\lambda^2} $$
$$ \Pr[|\hat{n} - n| > \lambda] \leq \frac{2n^2}{\lambda^2} $$
We approximately want this probability to be $\leq 0.1$, therefore:
$$ \frac{2n^2}{\lambda^2} = 0.1 $$
$$ 2n^2 \leq 0.1\lambda^2 $$
$$ \lambda \geq \sqrt{20n} $$
Enough to have $\lambda = 5n$, We have:
$$ \Pr[|\hat{n} - n| > 5n] \leq 0.1 $$
\text{With Probability 90\%:}
$$\hat{n} \in [n-5n, n+5n]$$
\end{proof}

\textbf{Doubt 4: Is this good enough?}\\
\\
\textbullet{} The upper bound is still fine. But the lower bound suggests that there is a high probability that we might end up with negative values of n.\\
\textbullet{} Can we do better?\\

\textbf{GOAL:} $\hat{n} \in [n-\epsilon n, n+\epsilon n]$; for small $\epsilon > 0$\\
\\
\textbullet{}  Basically, $\hat{n} \in (1\pm \epsilon)n$\\
\textbullet{}  $\epsilon$ will be a small quantity like 0.1, suggesting a 10\% error margin\\
\textbullet{}  For this we will see \textbf{Morris+ Algorithm}\\


\section{Morris+ Algorithm}

- Take k counters, compute i.i.d. \newline
- Press button for each counter completely independently \{x_1,x_2,...,x_k\} \newline
- Each of them is Morris Algorithm with counter x\textsuperscript{i}, \{i = 1,...,k\} \newline

Estimator $\hat{n}\textsuperscript{k}$ is equal to the average of estimators \{x\textsuperscript{1},...,x\textsuperscript{k}\}

\vspace{\baselineskip} 
\begin{claim} 
\(E[\hat{n}\textsuperscript{k}] = n\) 
\end{claim}
\begin{proof}
\textit{Note}: \(2\textsuperscript{{x\textsuperscript{i}}}-1 = n\)
\[E[\hat{n}^k] = E[\frac{1}{k}  \sum_{i=1}^{k} (2\textsuperscript{x\textsuperscript{i}}-1) ] = E[\frac{1}{k}  \sum_{i=1}^{k} n ] = n\]
\end{proof}

\vspace{\baselineskip}
\begin{claim}
Space is \(O(k log log n)\) with probability $\geq$ 90\%.
No counter is larger and occupying more than \(log n\) space
\end{claim}

\vspace{\baselineskip}
\begin{claim}
\(var[\hat{n}\textsuperscript{k}] = \frac{1}{k}var[\hat{n}]\) (variance of one counter)
\end{claim}
\begin{proof}
\[var[\hat{n}\textsuperscript{k}] = 
var[\frac{1}{k} \sum_{i=1}^{k} (2\textsuperscript{x\textsuperscript{i}}-1) ] = 
\frac{1}{k\textsuperscript{2}}var[ \sum_{i=1}^{k} (2\textsuperscript{x\textsuperscript{i}}-1)] =
\frac{1}{k\textsuperscript{2}} \sum_{i=1}^{k} var[(2\textsuperscript{x\textsuperscript{i}}-1)] = 
\frac{1}{k} var[\hat{n}]\]
\end{proof}

\noindent\textbf{Goal}: Want \(\hat{n} = (1 \pm \varepsilon)n\) \newline
Chebyshev: \(P[(\hat{n}^k - n)$>$\varepsilon n] \leq \frac{var[\hat{n}\textsuperscript{k}]}{\varepsilon\textsuperscript{2} n\textsuperscript{2}}\),\(\varepsilon\textsuperscript{2} n\textsuperscript{2} \leq 0.1\)
\[var[\hat{n}\textsuperscript{k}] \leq 0.1\varepsilon\textsuperscript{2} n\textsuperscript{2}\]
\[\frac{var[\hat{n}]}{k} \leq 0.1\varepsilon\textsuperscript{2} n\textsuperscript{2}\]
\[k \geq \frac{var[\hat{n}]}{0.1\varepsilon\textsuperscript{2} n\textsuperscript{2}}\]
It is enough to require \(k = \frac{2n\textsuperscript{2}}{0.1\varepsilon\textsuperscript{2} n\textsuperscript{2}} = \frac{20}{\varepsilon\textsuperscript{2}} = \Theta(\frac{1}{\varepsilon\textsuperscript{2}})\)
So, it is enough to repeat Morris Algorithm \(\frac{1}{\varepsilon^2}\) times
\textit{Theorem}: Morris + Algorithm can achieve \((1 \pm \varepsilon)\) approximation with 90\% probability using space \(O(\frac{log log n}{\varepsilon^2})\)


\section{Hashing}

\textbf{Problem}: Dictionary, data structure problem
Given a large, fixed universe \textit{U} of items
Given set \(S \epsilon U, |S|=n\), preprocess \textit{S} into data structure such that it can answer: "Is \(x \epsilon S\)?"

\vspace{\baselineskip}
\noindent\textbf{Solution}: \newline
1. Given \textit{S}, iterate over \(S \rightarrow O(n)\) runtime \newline
2. Binary search $\rightarrow$ \(O(log n)\) $\rightarrow$ querytime \textit{log n}, space: \textit{O(n)} \newline 
3. Full-index: Store a table \textit{T} of size |U| with \{T_i\} = 1 iff \(i \epsilon S\) $\rightarrow$ query time = \textit{O(1)} and space = \text{O(|U|)} \newline \\
Can we combine for \textit{O(1)} query time and \textit{O(n)} space? This is what hashing tries to do.
If we use IP addresses, each with 32 bits, as an example:
	|U| = 2\textsuperscript{32} = all possible IPs, all binary strings of length 32
Hashing says \textit{U} is large but the set in our data structure is small, so we reduce \textit{U} \newline
	\indent \textit{U (h)} $\rightarrow$ {1,...,m}
	
\vspace{\baselineskip}
\noindent \textbf{Property $\star$}:
	\textit{h: U $\rightarrow$ [m] satisfies:}
	\textit{$\forall$ i $\epsilon$ S and given x we have:}
	\textit{h(i) = h(x) iff i = x}. \\

\noindent \textbf{Solution to dictionary problem:} \newline
1. Compute \textit{h(i), i $\epsilon$ S} to reduce universe from \textit{U} to \textit{m} \newline
2. Store table \{T_j\} = 1 iff \textit{j = h(i), i $\epsilon$ S} \newline
3. At query \textit{x}, check if T_h(x) = 1 \\

\noindent Solution performance: space = \textit{O(m)} and query time = \textit{O(1)} to query table + time to compute \textit{h(x)} \\

\noindent \textbf{Solution 4}: pick \textit{h} randomly and hope that our property $\star$ holds with good probability \\
\noindent \textbf{Define}: Collision \textit{h(i) = h(x)}
	$\star$ says that they should only collide if \textit{i = x}, then solution 4 should be correct

\end{document}