\documentclass{cs155}
\usepackage[most]{tcolorbox}
\hwk{0}
\due{N/A}

\begin{document}

\textit{This problem set is optional and will not be graded.  Feel free to ask questions about these problems at hours! Solutions will be posted on January 30.}

\input{collab}

\problem{Problem 1}

The following approach is often called \textit{reservoir sampling}.  Suppose we have a sequence of items passing by one at a time.  We want to maintain a sample of one item with the property that at each step it is uniformly distributed over all the items that we have seen up to this step.  Moreover, we want to accomplish this without knowing the total number of items in advance or storing all of the items that we see.

Consider the following algorithm, which stores just one item in memory at all times.  When the first item appears, it is stored in the memory.  When the $k$th item appears, it replaces the item in memory with probability $1/k$.  Explain why this algorithm solves the problem.

\problem{Problem 2} 

If you reload the home page of the course website a few times, you might notice that the picture of the mathematician changes.  Ever wonder how many different pictures there are, and how you can find out?

Consider the following scenario.  There are $n$ different pictures, where $n$ is unknown to you.  Each time you load the website, it chooses one of the $n$ pictures uniformly at random and displays it.

Suppose we want to design an algorithm that outputs $n$.  The algorithm can load the website and see the displayed picture (it \textit{cannot} view the page source, etc.).  For example, the following is a valid algorithm that loads the website 100 times and outputs the number of different pictures displayed:\\

\begin{tcolorbox}[
	standard jigsaw,
	opacityback=0,
	breakable
	]
	\textbf{Algorithm.}
	\begin{enumerate}[1.]
		\item Initialize $S$ to be the empty set. ($S$ will store the different pictures seen so far.)
		\item Repeat 100 times:
		\begin{enumerate}[i.]
			\item Load the website.
			\item If the displayed picture is not in $S$, then add it to $S$.
		\end{enumerate}
		\item Output the size of $S$.
	\end{enumerate}
\end{tcolorbox}

This algorithm would probably find the right answer for our course website because we don't have too many different pictures.  But if $n$ were larger, say 50, then it's not so clear how well this algorithm would work.  And if $n$ were more than 100, then this algorithm cannot possibly succeed.

We want to design an algorithm that succeeds (outputs the correct value of $n$) with probability at least $\frac{1}{2}$, \textit{regardless of the value of $n$}.  Feel free to stop and think about how you might design such an algorithm.  In the rest of this problem, we'll describe one solution and ask you to analyze it.

The following algorithm keeps loading the website, keeping track of the different pictures that have been seen so far.  If $s$ is the number of different pictures that have been seen, the algorithm stops if no new pictures have been seen in the last $4s$ website visits.\\

\begin{tcolorbox}[
	standard jigsaw,
	opacityback=0,
	breakable
	]
	\textbf{Algorithm.}
	\begin{enumerate}[1.]
		\item Initialize $S$ to be the empty set. ($S$ will store the different pictures seen so far.)
		\item $s\leftarrow 0$. ($s$ represents the size of $S$.)
		\item $Count\leftarrow -1$.
		\item Repeat until $Count > 4s$:
		\begin{enumerate}[i.]
			\item Load the website.
			\item If the displayed picture is not in $S$: add it to $S$, $s\leftarrow s+1$, and $Count\leftarrow 0$.  Else, $Count\leftarrow Count+1$.
		\end{enumerate}
		\item Output the size of $S$.
	\end{enumerate}
\end{tcolorbox}


\begin{enumerate}[a.]
	\item Assume $s<n$. Given that at some point the algorithm has observed $s$ different pictures, prove that the probability that it terminates before observing $s+1$ pictures is bounded by
	$$\left(1-\frac{n-s}{n}\right)^{4s} \leq e^{-4s(n-s)/n} $$
	
	Hint: Here is an inequalities that might help in your analysis and will be useful throughout the course: for any real number $x$,
		$$1 - x \le e^{-x}.$$
 
	\item Prove that the probability that the algorithm terminates before observing all the $n$ pictures is bounded by $1/2$.

 Hints: (1) recall that for $0< q <1$
 $$\sum_{i=1}^k q^k \leq \frac{q}{1-q}.$$
 (2) Partition the sun to two parts,  $s\leq n/2$ and $s>n/2$.

\end{enumerate}

\end{document}

