eth-summaries/semester2/algorithms-and-probability/parts/probability/algorithms.tex

\newpage
\subsection{Randomized Algorithms}
In comparison to \textit{deterministic} algorithms, here, the output is \textbf{\textit{not}} guaranteed to be equal for the same input data after reruns. 
While this can be an issue in some cases, it allows us to usually \textit{significantly} reduce time complexity and thus allows us to solve $\mathcal{N}\mathcal{P}$-complete problems in some cases in polynomial time even.

The problem with \textit{true} randomness is that it is hardly attainable inside computers, some kind of predictability will always be there in some form or another, especially if the random number generator is algorithm-based, not on random events from the outside.
In this course, we will though assume that random numbers generated by random number generators provided by programming languages actually provide independent random numbers

In the realm of randomized algorithms, one differentiates between two approaches
\begin{tables}{lcc}{Types of randomized algorithms}
                     & \shade{ForestGreen}{Monte-Carlo-Algorithm} & \shade{ForestGreen}{Las-Vegas-Algorithm} \\
    Always correct   & \ding{55}                                  & \ding{51}                                \\
    Constant runtime & \ding{51}                                  & \ding{55}                                \\
\end{tables}

While this is the normal case for Las-Vegas Algorithms, we can also consider the following:

Let the algorithm terminate if a certain runtime bound has been exceeded and return something like ``???'' if it has not found a correct answer just yet. We will most commonly use this definition of a Las-Vegas-Algorithm in this course

\subsubsection{Reduction of error}
\setcounter{all}{72}
\begin{theorem}[]{Error reduction Las-Vegas-Algorithm}
    Let $\mathcal{A}$ be a Las-Vegas-Algorithm, where $\Pr[\mathcal{A}(I) \text{correct}] \geq \varepsilon$

    Then, for all $\delta > 0$ we call $\mathcal{A}_{\delta}$ an algorithm that calls $\mathcal{A}$ until we either get a result that is not ``???'' or we have executed $N = \varepsilon^{-1} \ln(\delta^{-1})$ times. For $\mathcal{A}_{\delta}$ we then have
    \begin{align*}
        \Pr[\mathcal{A}_{\delta}(I) \text{correct}] \geq 1 - \delta
    \end{align*}
\end{theorem}

On the other hand, for Monte-Carlo-Algorithms, the probability of error decreases rapidly. It is not easy though to determine whether or not an answer is correct, unless the algorithm only outputs two different values \textit{and} we know that one of these values is \textit{always} correct

\setcounter{all}{74}
\begin{theorem}[]{Error reduction}
    Let $\mathcal{A}$ be a randomized algorithm, outputting either \textsc{Yes} or \textsc{No}, whereas
    \begin{align*}
        \Pr[\mathcal{A}(I) = \textsc{Yes}] & = 1 \mediumhspace \text{if $I$ is an instance of \textsc{Yes}}             \\
        \Pr[\mathcal{A}(I) = \textsc{No}]  & \geq \varepsilon \mediumhspace \text{if $I$ is an instance of \textsc{No}}
    \end{align*}
    Then, for all $\delta > 0$ we call $\mathcal{A}_{\delta}$ the algorithm that calls $\mathcal{A}$ until either \textsc{No} is returned or until we get \textsc{Yes} $N = \varepsilon^{-1} \ln(\delta^{-1})$ times. Then for all instances $I$ we have
    \begin{align*}
        \Pr[\mathcal{A}_{\delta}(I) \text{correct}] \geq 1 - \delta
    \end{align*}
\end{theorem}
This can also be inverted and its usage is very straight forward.

\newpage

If we however have Monte-Carlo-Algorithms that have two-sided errors, i.e. there is error in both directions, we have
\begin{theorem}[]{Two-Sided Error reduction}
    Let $\varepsilon > 0$ and $\mathcal{A}$ be a randomized algorithm, that always outputs either \textsc{Yes} or \textsc{No} whereas
    \begin{align*}
        \Pr[\mathcal{A}(I) \text{correct}] \geq \frac{1}{2} + \varepsilon
    \end{align*}
    Then, for all $\delta > 0$ we call $\mathcal{A}_{\delta}$ the algorithm that calls $\mathcal{A}$ $N = 4 \varepsilon^{-2} \ln(\delta^{-1})$ independent times and then returns the largest number of equal responses. Then we have
    \begin{align*}
        \Pr[\mathcal{A}_{\delta}(I) \text{correct}] \geq 1 - \delta
    \end{align*}
\end{theorem}

For randomized algorithms for optimization problems like the calculation of a largest possible stable set, as seen in Example 2.37 in the script, we usually only consider if they achieve the desired outcome.

\begin{theorem}[]{Optimization problem algorithms}
    Let $\varepsilon > 0$ and $\mathcal{A}$ be a randomized algorithm for a maximization problem, for which
    \begin{align*}
        \Pr[\mathcal{A}(I) \geq f(I)] \geq \varepsilon
    \end{align*}

    Then, for all $\delta > 0$ we call $\mathcal{A}_{\delta}$ the algorithm that calls $\mathcal{A}$ $N = 4 \varepsilon^{-2} \ln(\delta^{-1})$ independent times and then returns the \textit{best} result. Then we have
    \begin{align*}
        \Pr[\mathcal{A}_{\delta}(I) \geq f(I)] \geq 1 - \delta
    \end{align*}
\end{theorem}
For minimization problems, analogously, we can replace $\geq f(I)$ with $\leq f(I)$
% P154


\subsubsection{Sorting and selecting}
The QuickSort algorithm is a well-known example of a Las-Vegas algorithm. It is one of the algorithms that \textit{always} sorts correctly, but its runtime depends on the selection of the pivot elements, which happens randomly.

\begin{recall}[]{QuickSort}
    As covered in the Algorithms \& Data Structures lecture, here are some important facts
    \begin{itemize}
        \item Time complexity: $\tcl{n \log(n)}$, $\tct{n \log(n)}$, $\tco{n^2}$
        \item Performance is dependent on the selection of the pivot (the closer to the middle the better, but not in relation to its current location, but rather to its value)
        \item In the algorithm below, \textit{ordering} refers to the operation where all elements lower than the pivot element are moved to the left and all larger than it to the right of it.
    \end{itemize}
\end{recall}

\begin{algorithm}
    \caption{\textsc{QuickSort}}
    \begin{algorithmic}[1]
        \Procedure{QuickSort}{$A$, $l$, $r$}
            \If{$l < r$}
                \State $p \gets$ \textsc{Uniform}($\{l, l + 1, \ldots, r\}$) \Comment{Choose pivot element randomly}
                \State $t \gets$ \textsc{Partition}($A$, $l$, $r$, $p$) \Comment{Return index of pivot element (after ordering)}
                \State \Call{QuickSort}{$A$, $l$, $t - 1$} \Comment{Sort to the left of pivot}
                \State \Call{QuickSort}{$A$, $t$, $r$} \Comment{Sort to the right of pivot}
            \EndIf
        \EndProcedure
    \end{algorithmic}
\end{algorithm}


\newcommand{\qsv}{\mathcal{T}_{i, j}}
We call $\qsv$ the random variable describing the number of comparisons executed during the execution of \textsc{QuickSort}($A, l, r$).
To prove that the average case of time complexity in fact is $\tct{n \log(n)}$, we need to show that
\begin{align*}
    \E[\qsv] \leq 2(n + 1) \ln(n) + \tco{n}
\end{align*}
which can be achieved using a the linearity of the expected value and an induction proof. (Script: p. 154)


\fhlc{Cyan}{Selection problem}

For this problem, we want to find the $k$-th smallest value in a sequence $A[1], \ldots, A[n]$. An easy option would be to simply sort the sequence and then return the $k$-th element of the sorted array. The only problem: $\tco{n \log(n)}$ is the time complexity of sorting.

Now, the \textsc{QuickSelect} algorithm can solve that problem in $\tco{n}$
\begin{algorithm}
    \caption{\textsc{QuickSelect}}
    \begin{algorithmic}[1]
        \Procedure{QuickSelect}{$A, l, r, k$}
            \State $p \gets \textsc{Uniform}(\{l, l + 1, \ldots, r\})$ \Comment{Choose pivot element randomly}
            \State $t \gets \textsc{Partition}(A, l, r, p)$
            \If{$t = l + k - 1$}
                \State \Return{$A[t]$} \Comment{Found element searched for}
            \ElsIf{$t > l + k - 1$}
                \State \Return{\Call{QuickSelect}{$A, l, t - 1, k$}} \Comment{Searched element is to the left}
            \Else
                \State \Return{\Call{QuickSelect}{$A, t + 1, r, k - t$}} \Comment{Searched element is to the right}
            \EndIf
        \EndProcedure
    \end{algorithmic}
\end{algorithm}



\subsubsection{Primality test}
Deterministically testing for primality is very expensive if we use a simple algorithm, namely $\tco{\sqrt{n}}$. There are nowadays deterministic algorithms that can achieve this in polynomial time, but they are very complex.

Thus, randomized algorithms to the rescue, as they are much easier to implement and also much faster. With the right precautions, they can also be very accurate, see theorem 2.74 for example.

A simple randomized algorithm would be to randomly pick a number on the interval $[2, \sqrt{n}]$ and checking if that number is a divisor of $n$. 
The problem: The probability that we find a \textit{certificate} for the composition of $n$ is very low ($\tco{\frac{1}{n}}$). Looking back at modular arithmetic in Discrete Maths, we find a solution to the problem:

\begin{theorem}[]{Fermat's little theorem}
    If $n \in \N$ is prime, for all numbers $0 < a < n$ we have
    \begin{align*}
        a^{n - 1} \equiv 1 \texttt{ mod } n
    \end{align*}
\end{theorem}
Using exponentiation by squaring, we can calculate $a^{n - 1} \texttt{ mod } n$ in $\tco{k^3}$.

\begin{algorithm}
    \caption{\textsc{Miller-Rabin-Primality-Test}}\label{alg:miller-rabin-primality-test}
    \begin{algorithmic}[1]
        \Procedure{Miller-Rabin-Primality-Test}{$n$}
            \If{$n = 2$}
                \State \Return \texttt{true}
            \ElsIf{$n$ even or $n = 1$}
                \State \Return \texttt{false}
            \EndIf
            \State Choose $a \in \{2, 3, \ldots, n - 1\}$ randomly
            \State Calculate $k, d \in \Z$ with $n - 1 = d2^k$ and $d$ odd \Comment{See below for how to do that}
            \State $x \gets a^d \texttt{ mod } n$
            \If{$x = 1$ or $x = n - 1$}
                \State \Return \texttt{true}
            \EndIf
            \While{not repeated more than $k - 1$ times} \Comment{Repeat $k - 1$ times}
                \State $x \gets x^2 \texttt{ mod } n$
                \If{$x = 1$}
                    \State \Return \texttt{false}
                \EndIf
                \If{$x = n - 1$}
                    \State \Return \texttt{true}
                \EndIf
            \EndWhile
            \State \Return \texttt{false}
        \EndProcedure
    \end{algorithmic}
\end{algorithm}
This algorithm has time complexity $\tco{\ln(n)}$. If $n$ is prime, the algorithm always returns \texttt{true}. If $n$ is composed, the algorithm returns \texttt{false} with probability at least $\frac{3}{4}$.

\newpage

\fhlc{Cyan}{Notes} We can determine $k, d \in \Z$ with $n - 1 = d2^k$ and $d$ odd easily using the following algorithm
\begin{algorithm}
    \caption{Get $d$ and $k$ easily}
    \begin{algorithmic}[1]
        \State $k \gets 1$
        \State $d \gets n - 1$
        \While{$d$ is even}
            \State $d \gets \frac{d}{2}$
            \State $k \gets k + 1$
        \EndWhile
    \end{algorithmic}
\end{algorithm}

What we are doing here is removing the all even divisors from $d$, to make it odd.


\subsubsection{Target-Shooting}
The Target-Shooting problem is the following: Given a set $U$ and a subset thereof $S \subseteq U$, whose cardinality is unknown, how large is the quotient $\frac{|S|}{|U|}$. We define an indicator variable for $S$ by $I_S : U \rightarrow \{0, 1\}$, where $I_S(u) = 1$ if and only if $u \in S$

The Target-Shooting algorithm approximates the above quotient:
\begin{algorithm}
    \caption{Target-Shooting}\label{alg:target-shooting}
    \begin{algorithmic}[1]
        \Procedure{TargetShooting}{$N, U$}
            \State Choose $u_1, \ldots, u_N \in U$ randomly, uniformly and independently
            \State \Return $N^{-1} \cdot \sum_{i = 1}^{N} I_S(u_i)$
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

For this algorithm, two assumptions have to be made:
\begin{itemize}
    \item $I_S$ has to be efficiently computable
    \item We need an efficient procedure to choose a uniformly random element from the set $U$.
\end{itemize}

\begin{theorem}[]{Target-Shooting}
    Let $\delta, \varepsilon > 0$. If $N \geq 3 \frac{|U|}{|S|} \cdot \varepsilon^{-2} \cdot \ln\left(\frac{2}{\delta}\right)$, the output of \textsc{Target-Shooting} is, with probability \textit{at least} $1 - \delta$, on the Interval $\left[ (1 - \varepsilon) \frac{|S|}{|U|}, (1 + \varepsilon) \frac{|S|}{|U|} \right]$
\end{theorem}


\subsubsection{Finding dulicates}
Deterministically, this could be achieved using a \textsc{HashMap} or the like, iterating over all items, hashing them and checking if the hash is available in the map.
This though uses significant amounts of extra memory and is also computationally expensive.
A cheaper option (in terms of memory and time complexity) is to use a \textit{Bloomfilter}.

The randomized algorithm also use Hash-Functions, but are not relevant for the exam.

\begin{definition}[]{Hash Function}
    If we have $\mathcal{S} \subseteq U$, i.e. our dataset $\mathcal{S}$ is subset of a \textit{universe} $U$, a \textit{hash function} is an image $h: U \rightarrow [m]$, whereas $[m] = \{1, \ldots, m\}$ and $m$ is the number of available memory cells. It is assumed that we can \textit{efficiently} calculate a hash for an element and that all elements are randomly distributed, i.e. we have for $u \in U$ $\Pr[h(u) = i] = \frac{1}{m}$ for all $i \in [m]$
\end{definition}