\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amsthm,amssymb,fullpage,enumerate}
\newcommand{\N}{\mathbb{N}}
\newcommand{\E}{\mathbf{E}}
\begin{document}
\section*{CS 70 homework 11 submission}
Your full name: PUT YOUR NAME HERE
\\
Your login name: PUT YOUR LOGIN NAME HERE
\\
Homework 11
\\
Your section number: PUT YOUR SECTION NUMBER HERE
\\
Your list of partners: LIST THE PEOPLE YOU WORKED WITH HERE (OR ``none'')
\begin{enumerate}
\item
%Write down the numbers $1,2,\dots,n$ in a random order,
%with all $n!$ orders equally likely.
%Underline each number in the sequence that is smaller than the
%number immediately following it.
%Let the random variable $X$ count the number of underlined numbers.
%For instance, if $n=5$, one possible sequence is
%$5,3,2,4,1$, and after underlining we get
%$5,3,\underline{2},4,1$, so in this example $X=1$.
Compute $\E[X]$. Your answer should be expressed as a simple
function of $n$.
YOUR ANSWER GOES HERE
\item
%We have a LCD display with $8 \times 40$ pixels, i.e., 8 rows
%with 40 pixels in each row.
%The display has a vertical line in some column if all 8 pixels in
%a particular column are turned on.
%Suppose that each pixel is turned on or off with equal probability,
%and all pixels are independent.
%Let the r.v. $X$ denote the number of vertical lines in the display.
\begin{enumerate}[{(}a{)}]
\item Calculate $\E[X]$.
YOUR ANSWER GOES HERE
\item Calculate $\textrm{Var}(X)$.
YOUR ANSWER GOES HERE
\end{enumerate}
\item
\begin{enumerate}[{(}a{)}]
\item
%In a certain biological experiment, a piece of DNA
%consisting of a linear sequence (or string) of 4000 nucleotides is
%subjected to bombardment by various enzymes.
%The effect of the bombardment is to randomly cut the string between
%pairs of adjacent nucleotides: each of the 3999 possible cuts occurs
%independently and with probability~$1\over{500}$.
What is the expected number of pieces into which the string is cut?
Justify your calculation.
%[Hint: Use linearity of expectation! If you do it this
%way, you can avoid a huge amount of messy calculation. Remember
%to justify the steps in your argument; i.e., do not appeal to
%``common sense.'']
YOUR ANSWER GOES HERE
\item
%Suppose that the cuts are no longer independent, but highly
%correlated, so that when a cut occurs in a particular place other
%cuts close by are much more likely. The probability of each individual
%cut remains~$1\over{500}$.
Does the expected number of pieces increase,
decrease, or stay the same? Justify your answer with a precise explanation.
YOUR ANSWER GOES HERE
\item
%Let the r.v.\ $X =$ the number of pieces into which the string
%is cut in part (a), where all cuts occur independently.
Calculate $\textrm{Var}(X)$.
YOUR ANSWER GOES HERE
\end{enumerate}
\item
%Consider a {\it fair game\/} in a casino: on each play, you may
%stake any amount \$$S$; you win or lose with probability~$\frac12$ each
%(all plays being independent); if you win you get your stake back
%plus~\$$S$; if you lose you lose your stake.
\begin{enumerate}[{(}a{)}]
\item What is the expected number of plays before your
first win (including the play on which you win)?
YOUR ANSWER GOES HERE
\item
%The following gambling strategy, known as the ``martingale,''
%was popular in European casinos in the 18th century: on the first play,
%stake~\$1; on the second play~\$2; on the third play~\$4; on the $k$th
%play~\$$2^{k-1}$. Stop (and leave the casino!) when you first win.
Show that, if you follow the martingale strategy, and assuming you
have unlimited funds available, you will
leave the casino \$1 richer with probability~1.
%[Maybe this is
%why the strategy is banned in most modern casinos.]
YOUR ANSWER GOES HERE
\item
%To discover the catch in this seemingly infallible strategy,
%let $X$ be the random variable that measures your maximum loss before
%winning (i.e., the amount of money you have lost {\it before\/} the play
%on which you win).
Show that $\E[X]=\infty$. What does this imply
about your ability to play the martingale strategy in practice?
YOUR ANSWER GOES HERE
\end{enumerate}
\item
What's wrong with this proof?
Please explain the flaw in this writeup.
YOUR ANSWER GOES HERE
%{\bf Theorem:} For every $n \in \N$ with $n\ge 2$, we have
%$\sum_{i=2}^n {i \choose 2} = {n+1 \choose 3}$.
%\begin{proof}
%We will use (simple) induction on $n$.\\
%\emph{Base case:} If $n=2$, then $\sum_{i=2}^2 {i \choose 2} = {2 \choose 2}
%= 1 = {3 \choose 3}$.\\
%\emph{Inductive hypothesis:}
%Suppose $\sum_{i=2}^n {i \choose 2} = {n+1 \choose 3}$ for every
%$n \in \N$ with $n \ge 2$.\\
%\emph{Inductive step:} We must show that
%$\sum_{i=2}^{n+1} {i \choose 2} = {n+2 \choose 3}$.
%Let's calculate:
%\begin{align*}
%\sum_{i=2}^{n+1} {i \choose 2}
% &= \left(\sum_{i=2}^{n} {i \choose 2} \right) + {n+1 \choose 2}\\
% &= {n+1 \choose 3} + {n+1 \choose 2}\\
% &= {n+2 \choose 3}.
%\end{align*}
%In the second line, we used the inductive hypothesis.
%In the third line, we used the fact that
%${a \choose b} + {a \choose b+1} = {a+1 \choose b+1}$,
%which follows from this calculation:
%\begin{align*}
%{a \choose b} + {a \choose b+1}
%&= {a! \over b!(a-b)!} + {a! \over (b+1)!(a-b-1)!}\\
%&= {a! \cdot (b+1) \over (b+1)!(a-b)!} + {a! \cdot (a-b) \over (b+1)!(a-b)!}\\
%&= {a! \cdot (a+1) \over (b+1)!(a-b)!}\\
%&= {(a+1)! \over (b+1)!(a-b)!}\\
%&= {a \choose b+1}.
%\end{align*}
%This concludes the proof.
%\end{proof}
%\q{0+5}{Optional bonus puzzle}\\
%We're going to play a game. You have a team of 7 people,
%seated around a circular table.
%When the game begins,
%the referee is going to put a colored hat on
%each person's head, with each color chosen from a palette of 7
%alternatives (so there are $7^7$ combinations of hats
%possible).
%Each player can see everyone else's hats, but no one can see the
%color of their own hats. (There are no mirrors.)
%Also, once the game begins, the players are not allowed to communicate
%by any means whatsoever (no hand signals, no footsie, nothing).
%However, you may coordinate before the game begins on the strategy
%that you will use.
%After everyone receives their hats, each player is handed a slip
%of paper, and after looking at everyone else's hat colors, the player
%secretly writes down a guess at his own hat color.
%
%Once everyone has marked their slip of paper, the referee checks
%them to see whether the team wins.
%If everyone guessed incorrectly,
%the whole team loses.
%If at least one person guessed correctly, the whole team wins.
%Note that you either win or lose as a team, i.e., either everyone
%wins or everyone loses.
%Therefore it is in everyone's interests to cooperate.
%
%Question: Identify a strategy that ensures a \emph{guaranteed} win,
%i.e., so that the team is certain to win no matter which of
%the $7^7$ combinations of hat colors the referee picks.
%
%YOUR ANSWER GOES HERE (if you solved the puzzle)
\end{enumerate}
\end{document}