CS 580 HW 2 Latex Template

hw-2.tex

\documentclass{article}
\usepackage{amsmath,amssymb,latexsym,amsthm}
\newcommand{\E}{\mathbb{E}}
\author{}
\date{Due April 24, in class}
\title{HW 2}
\begin{document}
\maketitle

\paragraph{Assignment:}
Exercises 1.6, 2.18, 2.21 (the ``hockey stick lemma'' might be
useful), 2.22, and 2.24. My guess is that you'll spend the most time
on 2.21 and 2.22, a few hours each. Exercise 2.24 will take some
cleverness, but it’s very quick to solve once you set up the problem
the right way.

\paragraph{Exercise 1.6:}
Consider the following balls-and-bin game. We start with one black
ball and one white ball in a bin. We repeatedly do the following:
choose one ball from the bin uniformly at random, and then put the
ball back in the bin with another ball of the same color. We repeat
until there are $n$ balls in the bin. Show that the number of white
balls is equally likely to be any number between $1$ and $n - 1$.

\paragraph{Exercise 2.18:}
The following approach is often called 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 it is uniformly
distributed over all the items that we have seen at each
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 $kth$ item appears, it replaces the item in memory
with probability $1 / k$. Explain why this algorithm solves the
problem.

\paragraph{Exercise 2.21:}
Let $a_l, a_2, \ldots , a_n$ be a random permutation of $\{1, 2,
\ldots, n\}$, equally likely to be any of the $n!$ possible
permutations. When sorting the list $a_l, a_2, \ldots , a_n$ the
element $a_i$ must move a distance of $| a_i - i |$ places from its
current position to reach its position in the sorted order. Find
\[
\E \left[ \sum_{i=1}^n | a_i - i | \right] ~,
\]
the expected total distance that elements will have to be moved.

\paragraph{Exercise 2.22:}
Let $a_l, a_2, \ldots , a_n$ be a list of $n$ distinct numbers. We say
that $a_i$ and $a_j$ are inverted if $i < j$ but $a_i > a_j$. The
Bubblesort sorting algorithm swaps pairwise adjacent inverted numbers
in the list until there are no more inversions, so the list is in
sorted order. Suppose that the input to Bubblesort is a random
permutation. equally likely to be any of the $n!$ permutations of $n$
distinct numbers. Determine the expected number of inversions that
need to be corrected by Bubblesort.

\paragraph{Exercise 2.24:} 
We roll a standard fair die over and over. What is the expected number
of rolls until the first pair of consecutive sixes appears? (Hint: The
answer is not 36.)

\end{document}