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

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

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

%\noindent
%\parindent = 0 pt

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{3}{March 13, 2009}{Ronitt Rubinfeld}{Roza Pogalnikova and Yaron Orenstein}

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

\subsection*{Announcements}

Homework 1 is released, due 25/03.

\section*{Lecture Plan}
\begin{enumerate}
 \item Do we need randomness?
\begin{itemize}
 \item A simple randomized algorithm
 \item Pairwise independent sample spaces
 \item Derandomization
\end{itemize}
 \item How much randomness is needed?
\begin{itemize}
 \item 2-point sampling
\end{itemize}
\end{enumerate}

\section{A simple randomized algorithm.}

\subsection{}
\paragraph{Problem:} 
Finding a Maximum Cut in a Graph.
\paragraph{Input:} 
Graph $G=\left( V, E\right) $, $|V| = n$, $|E| = m$.
\paragraph{Output:} 
Partition of V that maximizes the size of the cut, i.e. partition to distinct sets S and T, that maximizes $\left( S, T\right) = \{ \left( u, v\right) | \left( u, v\right) \in E, u \in S, v \in T\}$ 


\paragraph{Remark:}
Max-Cut Problem is NP-complete, i.e no polynomial time solution is expected.

\subsection{A greedy algorithm.} 
Pick vertices one by one. Put a vertex in S or T to maximize number of edges to vertices already in the cut between S and T. \\
The algorithm gives cut that is at least half the size of the max-cut
since at least half the edges cross the cut. (This is not an
expectation -- it is a deterministic algorithm).

\subsection{A randomized algorithm.}
\paragraph{The algorithm to get a random cut:} 
\begin{itemize}
 \item Flip $n$ coins $r_{1}$, $r_{2}$, $\ldots$, $r_{n}$.
 \item Put vertex $i$ on side $r_{i}$ to get $\left( S, T\right) $.
\end{itemize}

\paragraph{Analysis:}

\begin{align*}
{\mathbb E}[Cut~size] 
& =^{1} \underset{(u,v) \in E} {\mathbb E} [\Sigma\ I_{(u,v)~in~Cut}] 
& =^{2} \underset{(u,v) \in E} \Sigma\ {\mathbb E} [I_{(u,v)~in~Cut}] 
& =^{3} \underset{(u,v) \in E} \Sigma\ Pr[r_v~\not=~r_u] 
& =^{4} \frac{\displaystyle |E|}{2}
\end{align*}

\moveright 20 pt
\vbox{
\hbox {$^1$ {Examine expectation of every edge to be in the cut}}
\hbox {$^2$ {Linearity of expectations (${\mathbb E}[\Sigma] = $ $\Sigma ({\mathbb E})$)}}
\hbox {$^3$ {Expectation of indicator variable is just its probability ($E[I]~=~Pr.$)}}
\hbox {$^4$ {$Pr[r_v = S]\cdot Pr[r_u = T] + Pr[r_v = T]\cdot Pr[r_u = S] = 1/2$}}
}

\paragraph{Remark 1:}
It is not sufficient to find an expectation. One also needs to show that we come close to expectation with reasonable probability (for example, via Chebyshev bounds), but we will not show it here.

\paragraph{Remark 2:}
In our probability calculations we used only pairwise independence, and it is a much weaker requirement, as we are going to show today.


\section{Constructing Pairwise Independent Sample Spaces.}

\subsection{Pairwise independent Random Variables.}
Pick $n$ values $x_{1}$, $x_{2}$, $\ldots$, $x_{n}$ from a domain $T$ of size $t$. There are $t^n$ possibilities for $x_{1}\ldots x_{n}$.

\paragraph{Definition 1:} 
$x_{1}$, $\ldots$, $x_{n}$ is {\em (uniform) "independent"}, if $\forall\  b_1\ldots b_n \in T^n$, $Pr[x_1\ldots x_n = b_1\ldots b_n]\ =\ \frac{1}{\displaystyle t^n}$ 

\paragraph{Definition 2:} 
$x_{1}$, $\ldots$, $x_{n}$ is {\em (uniform) "pairwise independent"}, if $\forall\ i,j$, $b_ib_j \in T^2$, $Pr[x_ix_j = b_ib_j]\ =\ \frac{1}{\displaystyle t^2}$ 

\paragraph{Definition 3:} 
$x_{1}$, $\ldots$, $x_{n}$ is {\em (uniform) "k-wise independent"}, if $\forall\ i_1\ldots i_k$, $b_1\ldots b_k \in T^k$, $Pr[x_{i_1}\ldots x_{i_k} = b_1\ldots b_k]\ =\ \frac{1}{\displaystyle t^k}$ 

\paragraph{Example:}
$T\ = \{0,\ 1\}$, $P$ and $Q$ different distributions.\\

\moveright 20 pt
\vbox{\offinterlineskip
\halign{
\strut \vrule \quad $#$\quad \hfil
&\vrule \hfil \quad $#$\quad \hfil
&\vrule \hfil \quad $#$\quad \hfil
&\vrule \hfil \quad $#$\quad \hfil
&\vrule \hfil \quad $#$\quad \hfil
\vrule \cr
\noalign{\hrule}
x_0 & x_1 & x_2 & Pr[P] & Pr[Q] \cr
\noalign{\hrule}
0 & 0 & 0 & {1}/{8} & {1}/{4} \cr
0 & 0 & 1 & {1}/{8} & 0 \cr
0 & 1 & 0 & {1}/{8} & 0 \cr
0 & 1 & 1 & {1}/{8} & {1}/{4} \cr
1 & 0 & 0 & {1}/{8} & 0 \cr
1 & 0 & 1 & {1}/{8} & {1}/{4} \cr
1 & 1 & 0 & {1}/{8} & {1}/{4} \cr
1 & 1 & 1 & {1}/{8} & 0 \cr
\noalign{\hrule}
}}
It is easy to see that $P$ is uniform, totally independent.
\paragraph{Observe:} $Q$ is pairwise independent. It is uniform on the following subset of size four: \\

\moveright 20 pt
\vbox{\offinterlineskip
\halign{
\strut \vrule \quad $#$\quad \hfil
&\vrule \hfil \quad $#$\quad \hfil
&\vrule \hfil \quad $#$\quad \hfil
&\vrule \hfil \quad $#$\quad \hfil
\vrule \cr
\noalign{\hrule}
x_0 & x_1 & x_2 & Pr[Q] \cr
\noalign{\hrule}
0 & 0 & 0 & {1}/{4} \cr
0 & 1 & 1 & {1}/{4} \cr
1 & 0 & 1 & {1}/{4} \cr
1 & 1 & 0 & {1}/{4} \cr
\noalign{\hrule}
}}
Therefore only two bits are needed to pick a triple $(x_1,x_2,x_3)$ according to distribution $Q$ (whereas three bits are needed to pick a triple $(x_1,x_2,x_3)$ according to $P$).

\paragraph{Question:} How many random bits are needed to create N pairwise independent bits?

\subsection{Generating pairwise independent bits:}
\paragraph{The algorithm to generate pairwise independent \textit{bits}:} 
\begin{enumerate}
 \item Choose k truly random bits $b_{1}\ldots b_{k}$.
 \item $\forall S \subseteq [k] $ (where $[k]$ is set $1\ldots k $), $S \not= \emptyset$, set $C_S\ =\ \underset{i \in S}\oplus b_i$.
\begin{tabbing}
	$C_{\{1\}}\ =\ b_1$, 
	$C_{\{1, 2\}}\ =\ b_1\oplus b_2$, 
	$\ldots$
\end{tabbing}
 \item Output all $C_S$.
\end{enumerate}
The algorithm generates $2^k-1$ random bits $b_{1}\ldots b_{k}$. 

\paragraph{Answer:} To get N pairwise independent random bits only $K = \bigO(\log{N}) $ truly random bits are required.

\begin{claim}
For $S\ \not=\ T$, $C_S$ and $C_T$ are pairwise independent.
\end{claim}

\subsubsection{Derandomize Max-Cut}
\textit{Derandomization} here means using as little randomness as possible.
\paragraph{The algorithm to derandomize Max-Cut:} 
\begin{enumerate}
 \item choose $\log{N} + 1$ truly random bits $b_1\ldots b_{\log{N} + 1}$
 \item generate $r_1\ldots r_n$ pairwise independent bits from $b_i$'s
 \item use $r_1\ldots r_n$ directly in the Max-Cut algorithm and evaluate the cut size
\end{enumerate}
Repeat steps 1-3 on all possible choices of $b_1\ldots b_{\log{N} + 1}$, and output the biggest Cut that was found. \\

%todo improve picture of how alg. works
\hbox{
	\vbox{
		\hbox to 25 pt {\rightarrowfill}
		\hbox{$\xrightarrow[input]{}$}
	}
	\boxed {
			\vbox{
				\hbox{
$\xrightarrow[truly~random~bits]{\log n}$
\boxed{Generator}
$\xrightarrow[pairwise~independent~bits]{n}$ 
				}
				\hbox to 240 pt {\rightarrowfill}
			}
			\vbox{
\hrule
\hbox{\strut \vrule{} $Randomized$ \vrule} 
\hbox{\strut \vrule{} $Algorithm$ } 
\hrule
}
	}
	\vbox{
		\hbox{$\xrightarrow[output]{}$}
	}
}

\paragraph{Comments:}
\begin{itemize}
 \item This technique uses derandomization via enumeration.
 \item The running time of the randomized algorithm is $N^2$ (same as deterministically running Max-Cut $N$ times), and the Cut size expectancy is no different. 
 \item There are other deterministic algorithms which are more efficient than the derandomization of the randomized algorithm, but this is a demonstration of an interesting
technique.
\end{itemize}

\paragraph{Remark:}
Pairwise and k-wise independence has been used in parallel algorithms.

\subsection{Generating pairwise independent numbers}
Now we will show how to generate random numbers (as opposed to bits), which are pairwise independent. But first, a definition:

\paragraph{Definition:}
$H = \left\{ h : [N] \rightarrow [M]\right\}$ is a {\em "pairwise independent family of functions"}, if $\forall\ x\not=y \in [N]$ and $\forall\ c,d \in [M]$, $Pr[h(x) = c \wedge h(y) = d] = \frac{\displaystyle 1}{\displaystyle M^2} $ 

This definition is equivalent to the definition of pairwise independent we mentioned before. $x$ and $y$ are the indices, and the probability for every two values for $x$ and $y$ is $\frac{\displaystyle 1}{\displaystyle M^2}$. There is no pairwise independent function, but a class of functions which is pairwise independent, and from which a function is randomly chosen.

\paragraph{Example:} 
We "pick" \textit{hash-function}:\\
pairwise independent bits: $\bigl\{ f_b |\ f_b(S) = \underset{i \in S}\oplus b_i$ for $S \not= \emptyset \bigr\}$ \\
pairwise independent numbers (see below): $\bigl\{ f_{a,b} |\ f_{a,b}(i) = (a\cdot i + b)$ mod $q \bigr\}$ \\

\subsubsection{Constructing pairwise independent numbers over prime fields}
\paragraph{The algorithm to generate pairwise independent \textit{numbers}:} 
on ($Z_q\equiv[0...(q-1)]$)
\begin{enumerate}
 \item Pick $a,\ b\ \in_R\ Z_q$ (uses $2\cdot log(q)$ truly random bits).
 \item $r_i$ = $(a\cdot i\ +\ b)$ mod $q$, $\forall\ i \in [q]$.
 \item Output $r_1\ \ldots \ r_q$ ($q$ pairwise independent numbers).
\end{enumerate}

\begin{claim}
The algorithm outputs $q$ different numbers, which are pairwise independent.
\end{claim}

\begin{proof}
Fix $i\neq j, c, d$. Examine the probability: ${Pr}_{a,b}[ai+b=c\wedge aj+b=d]$. This probability is over the hash function ($a$ and $b$ define the function).

This probability is equal to:
${Pr}_{a,b} \left[ \left( \begin{array}{cc}
i & 1 \\
j & 1 \\
\end{array} \right) \cdot
\left( \begin{array}{c}
a \\
b \\
\end{array}\right) = 
\left( \begin{array}{c}
c\\
d \\
\end{array}\right) \right] = \frac{\displaystyle 1}{\displaystyle q^2}
$. 
The determinant of the matrix is $i-j$ and since $i\neq j$, its determinant does not equal 0. So, there exists one unique solution to the set of equations for every $(c, d)$. So, every pair $c,d$ are mapped to by $i,j$ with the same probability. In other words, if you just look at two indices $i,j$ of the output, they will be independent and uniformly distributed.
\end{proof}

\paragraph{Remark:} 
It is possible to prove $k$-wise independent in the same way, using polynomials instead
of linear functions. This is based on the fact that a Vandermonde matrix has a determinant which is different from 0. For 3-wise independence, the construction of the numbers uses $a\cdot i^2 + b\cdot i + c$, for truly random $a, b, c$.

\subsubsection{Constructing pairwise independent n-bit numbers}

We also note that there exists an algorithm for picking up pairwise independent numbers from a finite field of size $2^n$. We can view the elements of $GF(2^n)$ as polynomials with $\left\{0,1\right\}$ coefficients of degree $(n-1)$ (mod 2): $\sum_{i=0}^{n-1}{a_i\cdot x^i} (mod 2)$ s.t. $a_i,x\in\left\{0,1\right\}$.

In this case $a\cdot i+b$ belongs to $GF(2^n)$ and the operations $+$ and $\cdot$ (addition and multiplication) are over $GF(2^n)$. The hash function is $h_{a,b}(x)=a\cdot x+b$. The difference is that the number is picked from a field of size $2^n$ instead of some prime $q$. This is a family of pairwise independent functions.

\begin{claim}
$\exists$ family of pairwise independent hash functions from ${\left\{0,1\right\}}^{n}\rightarrow{\left\{0,1\right\}}^{n}$.
\end{claim}

\section{Randomness-efficient error reduction in sampling}
If the algorithm needs only pairwise independent numbers, then it is enough to have $log N$ truly random bits. This way we can save in truly random bits used.

We introduce another algorithm, which uses pairwise independent random numbers, and we show how to lower its dependency on truly random numbers. In this example we show a one-sided error algorithm.

\paragraph{Notation:} 
$A(x, R)$ = output of algorithm $A$ on input $x$ and random string $R$.

\paragraph{Given $A$ with one-sided error:}
\begin{itemize}
	\item if $x\in L$ ${Pr}_{R}[A(x, R)=0]<\frac{1}{2}$
	\item if $x\notin L$ ${Pr}_{R}[A(x, R)=0]=1$
\end{itemize}

\paragraph{Definition:} A \emph{witness} is $R$, such that $A(x, R)=1$.

\subsection{Error probability reduction}

\paragraph{We can reduce the error probability by repetition:}
Repeat $k$ times and output $'x\in L'$ if see any 1. Then we have
the following behavior:
\begin{itemize}
	\item if $x\in L$ $Pr[A^k(x, R^k)=0]<\frac{1}{2^k}$
	\item if $x\notin L$ $Pr[A^k(x, R^k)=0]=1$
\end{itemize}

\paragraph{How many random bits are used?} $|R|\cdot k$

\paragraph{Can we save some random bits?}
We can choose $R$ more efficiently by choosing $R$'s which are pairwise independent. The error probability is almost the same. The result and analysis are taken from a paper by Chor and Goldreich called: 'On the Power of Two-Point Based Sampling'. The number of random bits used by the Chor Goldreich method is $O(|R| + k)$. Note that the runtime is not better, just the number of random bits used.

\paragraph{Use pairwise independence to save random bits.}
\begin{itemize}
	\item Pick $h:{\left\{0,1\right\}}^{m}\rightarrow{\left\{0,1\right\}}^{m}$ randomly from pairwise independent family $H$ (we showed we can construct such a family)
	%\item Construct $R_1\ldots R_{2^m}$ where $R_i=h(i)$ $\forall i\in{\left\{0,1\right\}}^{m}$
	%\item Compute $A(x,R_1),\ldots,A(x,R_{2^m})$. If see $i$ such that $A(x,R_i)=1$ output `$x\in L$', else `$x\notin L$'
	\item Construct $R_1\ldots R_{q}$ where $R_i=h(i)$, where $i\in{\left\{0,1\right\}}^{m}$
	\item Compute $A(x,R_1),\ldots,A(x,R_{q})$. If see $i$ such that $A(x,R_i)=1$ output `$x\in L$', else `$x\notin L$'
\end{itemize}

\paragraph{When does the algorithm misclassify?}
\begin{itemize}
	\item if $x\notin L$ never, since the algorithm always outputs 0.
	\item if $x\in L$, the algorithm misclassifies if it never sees an $R$ such that $A(x, R)=1$.
\end{itemize}
If we look at all the possible $R$'s, meaning all the binary strings of length $m$, then at least half of them make $A$ output 1. In this case we missed each one of them. 

\paragraph{Definition:} $Y \equiv \sum_{i=1}^{q}{A(x,R_i)}$ ($q$ here is $2^m$). 
\paragraph{Error reduction.}
\begin{itemize}
	\item If the sum is 0, we output 0. 
	\item If positive, we output 1.
\end{itemize}

\paragraph{Error reduction analysis:}
%$E[Y]=\sum_{i=1}^{2^m}{E[A(x,R_i)]}=\sum_{i=1}^{2^m}{Pr[A(x,R_i)=1]}\geq \sum_{i=1}^{2^m}{\frac{1}{2}} = 2^{m-1}$
$E[Y]=\sum_{i=1}^{q}{E[A(x,R_i)]}=\sum_{i=1}^{q}{Pr[A(x,R_i)=1]}\geq \sum_{i=1}^{q}{\frac{1}{2}} = \frac{q}{2}$

\paragraph{Observe:}
$A(x, R)$ is an indicator variable. It equals 1 when the algorithm outputs 1 for the specific input of $(x, R)$. Thus its expectancy is equal to the probability it is equal to 1. Since each $R$ is uniformly distributed (1-wise independent) we get that the probability is as before, bigger then $\frac{1}{2}$.

Now we need to calculate what is the probability that $Y=0$. In order to give a bound on the probability we use Chebyshev's inequality. 

\paragraph{An important note:}
When the random variables are pairwise independent we cannot use Chernoff bound. Chernoff is good only in the case where the variables are totally independent. Chebyshev is suitable for pairwise independent variables.

\paragraph{Chebyshev's Inequality:}
$Pr(\left|X-\mu\right|\geq\epsilon)\leq\frac{Var[X]}{{\epsilon}^{w}}$ \\
$X$ is a random variable with expectancy $E[X]=\mu$, and the inequality gives the probability that $X$ is far from its expectancy.


But $Y$ is a sum of random variables, so we can use the Pairwise Independent Tail Inequality:

\paragraph{Pairwise Independent Tail Inequality}

\begin{displaymath}
\left.%
\begin{array}{ ccccrr }
\textrm {a}) & &\hbox{Pairwise independent random variables}~x_1\ldots x_t~\hbox{in}~$[0,1]$ \\
\textrm {b}) & &\hbox{The average}~X=\frac{1}{t}\cdot\sum_{i=1}^{t}{x_i}\\
\textrm {c}) & &\hbox{The average expectancy}~\mu=E[X]=\frac{1}{t}\cdot\sum E[x_i]
\end{array}%
\right \} \textrm { $\Rightarrow$ $Pr[|X-\mu|\geq\epsilon]\leq\frac{1}{t{\epsilon}^{2}}$ }
\end{displaymath}

We see that the dependency is linear in $t$, while in Chernoff we get an exponential dependency (which is tighter). But again Chernoff can be used only for totally independent variables.

\paragraph{Error reduction analysis continued:}
We look at the average value $\frac{Y}{q}$. \\
$\mu=E[\frac{Y}{q}] = \frac{E[Y]}{q}\geq\frac{q/2}{q}=\frac{1}{2}$
$\Rightarrow Pr[Y=0]\leq^{1} Pr[|\frac{Y}{q}-\mu|\geq\mu]\leq\frac{1}{q\cdot{\mu}^2}\leq^{2} \frac{1}{q}\cdot 4=\frac{4}{q}=O({q}^{-1})$

\moveright 20 pt
\vbox{
\hbox {$^1$ {Derives from the fact the $Y=0$ is the only time that the output is the wrong answer.}}
\hbox {$^{1\star}$ {This event is included in the event that $\frac{Y}{q}$ is far from the expectancy by at least $\mu$.}}
\hbox {$^2$ {Regarding $\mu$ we proved that $\mu\geq\frac{1}{2}$ and thus $\frac{1}{{\mu}^{2}}\leq4$.}}
}

\end{document}




