%-*- LaTeX -*-

\NeedsTeXFormat{LaTeX2e}
\documentclass{assign}
\usepackage{newcent}
\usepackage{amsmath,amssymb,enumitem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Start reading here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The four commands below are used to define the ordinal number of the
% lecture (can be found on the lecture syllabus), the title of the lecture
% (formulate the best description you can come up with; you can always
% resort to the tentative title on the lecture syllabus if you have
% difficulty), the date of the lecture (in this format: DD Month YYYY),
% and the name of the scribe (that's you).
%
% Please supply correct arguments for the four commands below:
%

    \lecturenumber{5}
    \lecturetitle{Homework\ }
    \lecturedate{Nov 21, 2007}
    \duedate{Dec 3, 2007}
    \lecturescribe{}

%
% In the space indicated below, please type out your lecture notes.  You
% should use all the standard LaTeX typesetting conventions, plus a couple
% of additional commands described below.  If you are unfamiliar with using
% LaTeX to typeset technical documents, please read the very useful summary
% entitled ``The Not So Short Introduction to LaTeX2e'' which is available
% on BlackBoard.  You can also examine the source files for the scribed
% lecture notes from lectures 1, 2, and 3 for some formatting ideas. 
%
% Use the standard commands \section{}, \subsection{}, and \subsubsection{}
% to format your document logically into sections, subsections, and 
% subsubsections (as needed). 
%
% If you reference a URL anywhere, use the provided command \urlclick{}
% like this: \urlclick{http://www.web.com/foo.html}.  This will create a
% clickable hyperlink in the resulting .pdf file. 
%
% To add a figure to your notes, use the provided command \figureadd{}
% like this: \figureadd{basename}{label}{caption}.  In this command,
% basename is the base name of your figure, which must exist in both .eps
% and .jpg formats.  For example, if you have created a figure named both
% foo.jpg and foo.eps, then the basename is simply foo.  The label field
% creates a label which you can reference elsewhere using the standard
% command \ref{}.  Please use the caption field to provide a descriptive
% caption for any figure you create.  When you submit your scribed notes,
% please also submit all your figure files in both .eps and .jpg formats.
%
% For a theorem, corollary, lemma, claim, fact, definition, assumption,
% observation, or example, consider using these provided commands to set it
% apart from other text: 
%     \theorem{...}
%     \corollary{...} 
%     \lemma{...}
%     \claim{...}
%       etc.
%
% For proofs, or sketches of proofs, use these provided environments: 
%     \begin{proof}        ... \end{proof}
%     \begin{proof_sketch} ... \end{proof_sketch}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\reals}{{\mathbb R}}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\ch}{\ensuremath\mathcal{CH}}
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{lemma}{Lemma}[section]
% \newtheorem{corollary}{Corollary}[section]
% \newtheorem{claim}{Claim}[section]
% \newtheorem{prop}{Proposition}[section]
% \newtheorem{fact}{Fact}[section]
% \newtheorem{problem}{Problem}[section]
% \numberwithin{equation}{section}
\newtheorem{defn}{Definition}[section]
\newenvironment{proofsketch}{\par{\textbf{Proof Sketch:}}}{\(\qed\) \par}

\begin{document}
\label{begin}



\section{Biased Coins}
\label{sec:biased-coins}

A fair coin is one that gives heads and tails with probability 0.5. In all
randomized algorithms, we assume that we have access to a source of bits
that is fair: i.e gives 0 and 1 with equal probability. 

But in general, we may not be so lucky. Coins can be biased, even if
slightly so. What's worse, we may not even know how they are biased, if at
all. So how do we generate fair bits ? 

\begin{enumerate}[label=\alph*)]
\item A trick that dates back to Von Neumann solves this problem. Suppose
  we have a coin that generates heads and tails with different
  probabilities (that sum to one, of course). Toss the coin twice: if it
  returns HT, return H; if it returns TH, return T. If it returns HH or
  TT, discard this pair of throws and repeat. Show that this scheme is
  correct, in that in the sequence of Hs and Ts it generates, each occurs
  with equal probability. Notice that you don't even need to know the
  actual biased probabilities !
\item The problem with the above scheme is that we waste some
  tosses. First of all, we have to toss the coin twice to get one bit, and
  secondly we might have to discard some throws. Suppose we toss the
  biased coin 2n times. What is the expected number of bits we will get
  out of it ? Assume that the probability of tossing H is $p \ne 1/2$. 
\end{enumerate}


\section{Discrepancy}
\label{sec:discrepancy}

When we toss a fair coin, we expect that we get roughly half-and-half Hs
and Ts. Of course, this might not happen in general: the question is, how
bad can the difference get ? 

Consider a sequence of $2n$ coin tosses, and let $X_H$ be the number of
heads and $X_T$ be the number of Ts in the resulting sequence. Obviously,
$EX_H = EX_T = n$, and therefore $E(X_H-X_T) = 0$. Show that for any
$\epsilon > 0$, there exists a constant $c$ such that 

\[ Pr[ X_H - X_T > c\sqrt{n}] \le \epsilon \]

Note the quantification: in general, $c$ will be a function of
$\epsilon$. 



\section{Contention Resolution}
\label{sec:cont-resol}

Solve Problem 13.3 from the textbook

\section{Randomized Load Balancing}
\label{sec:rand-load-balanc}

Solve Problem 13.14 from the textbook

\section{Decoding over a noisy channel}
\label{sec:decoding-over-noisy}

Solve Problem 13.16 from the textbook.

\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: