\documentclass[11pt,fleqn]{article}
\usepackage{fullpage}
\usepackage{latexsym,epsf,epsfig}
\usepackage{amsmath,amsthm}
\begin{document}
\newcommand{\mbf}[1]{\mbox{{\bfseries #1}}}
\newcommand{\N}{\mbf{N}}
\newcommand{\E}{\mbf{E}}
\renewcommand{\O}{\mbf{O}}
\newtheorem{thm}{Theorem}
\section*{CS 70 homework 11 solutions}
Your full name: PUT YOUR NAME HERE
\newline
Your login name: PUT YOUR LOGIN NAME HERE
\newline
Homework 11
\newline
Your section number: PUT YOUR SECTION NUMBER HERE
\newline
Your list of partners: LIST YOUR PARTNERS HERE
\newline
\begin{enumerate}
\item
~ [\ldots]
What is the expected number of quadruply-repeated ones
in a random $n$-bit string, when $n \ge 3$ and all $n$-bit
strings are equally likely? Justify your answer.
YOUR ANSWER GOES HERE.
\item
Two players, Alice and Bob, each stake 32 pistoles on a three-point,
winner-take-all game of chance.
The game is played in rounds;
at each round, one of the two players gains a point and the other gains none.
Normally the first player to reach 3 points would win the 64 pistoles.
[\ldots]
play is suspended at a point where Alice has 2 points and Bob has 1 point.
Calculate a fair way to distribute the 64 pistoles [\ldots].
How many pistoles does Alice receive? Bob?
YOUR ANSWER GOES HERE.
\item
Consider the following bad method for ``shuffling'' (i.e. randomly permuting
the elements of) a 52-element array A. [\ldots]
Determine the expected number of random integers $j$ that will be generated
to produce $newA[k]$.
YOUR ANSWER GOES HERE.
\item
~ [\ldots]
Find the actual probability that an elevator responding to a call
on the eighth floor of Evans is going up,
and explain how you got that figure.
YOUR ANSWER GOES HERE.
\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}
\item What is the expected number of plays before your
first win (including the play on which you win)?
YOUR ANSWER GOES HERE.
\item
~ [\ldots]
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.
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.
\item Colin and Diane enter the casino with \$10 and
\$1,000,000 respectively. Both play the martingale strategy
(leaving the casino either when they first win, or when they lack
sufficient funds to place the next bet as required by the strategy).
What is the probability that Colin wins? What is the probability
that Diane wins?
YOUR ANSWER GOES HERE.
\end{enumerate}
\end{enumerate}
\end{document}