\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol10}
  \newcommand{\handouttitle}{Problem Set 10 Solutions}
  \newcommand{\handoutdate}{May 2, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps10}
  \newcommand{\handouttitle}{Problem Set 10}
  \newcommand{\handoutdate}{April 25, 2000}
  \newcommand{\duedate}{May 2, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] Games of unbounded length \\
    Handout [[[XXX]]]
%[[[Robert:  This is Handout 63 from Fall 99.  A nice handout Albert
%   Meyer prepared on probabilities in an infinite game.  Can you make
%   a new handout out of this one, give to Carl for producing for class
%   on Tuesday? ]]]
    Self-study problems: Exercises 1, 2 and 3 in Handout [[[XXX]]]
%[[[We need to add two exercises to the end of Handout XXX, and number
%the existing exercise as number 3.  The two new exercises should be
%easy problems very much like the one described in the main handout.
%E.g.:
% 1.  Game involves tossing a fair coin until a head first arises.
%     What's the probability that a head first arises on an
%     even-numbered throw?
% 2.  Two players throwing 2 dice until the first time one gets 7 or
%     11.  What's the probability it's the first player?]]]
    
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
    \item[6.042 Fall 97 Lecture notes (available from course webpage):] %
      Lectures 21 and 22
    \end{description}
  \end{description}
  }

\section*{Problems:}

% [[[ Should be about 8 problems.
% 
% Coverage:
% L21:
% Random variables
% Probability distributions: Bernoulli, uniform, binomial
% Uniform: Numbers game
% Binomial: 
%   Bounding tails
%   Polling
%
% L22:
% Expectation
%   Shortcut for computing
%   MTTF
%   Expectation based on divergent series
%   Linearity of expectation
%   Expectation and combinatorial equalities
% ]]]


\begin{problems}

% [[[ My lecture notes for TUesday already appear in the lectures
%    directory, under lecture21.tex.
% I haven't gotten to Thursday yet.  But it will be pretty close to
%    the previous lecture 22.tex.
% 
% I've been trying to think of a nice problem involving independence of
% random variables.  No luck...]]]


\problem %
% (Numbers game, uniform distribution) 

%[[[Try to find the problem alluded to in the Fall 99 notes, showing
%optimality.  It sounds like a good exercise.]]]

\begin{problemparts}
\problempart

\solution{
}


\problempart

\solution{
}

\problempart

\solution{
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\clearpage
\problem % 
% (Bounding tails of binomial dist)

%[[[ I made this one up, starting from problem 4 of pset 11 of fall
%99.  I changed the numbers.  Please work out the solution to make
%sure nothing unexpected happens.]]]

A new fault-tolerant computer network contains 100,000 computer nodes,
and is designed to function adequately when no more than 5000
computers are down. 
Suppose that the probability that any particular computer is down
is 4%; moreover, these probabilities are independent for different
computers.

\begin{problemparts}

\problempart
Estimate the probability that exactly 5000 computers are down.
\solution{
}

\problempart
Estimate the probability that the network can function adequately.

\solution{
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem %
% (Polling)

%[[[New problem, check that it works out.]]]

The Gallup polling service is conducting a poll to see what percentage
of Americans believe that 6-year-olds should be
given the legal right to decide where they should live. 
They would like to be accurate (after all, this is a very serious
issue) to within a 2% margin of error, with at least 98% probability.  
Estimate how many people they would need to poll to be able to make
this claim of reliability.

%[[[We could guide them through this one in parts if we like, but it
%seems to follow the notes pretty well.  ???]]]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
% (Random vars, expected value)

%[[[ New problem, from Feller Vol. 1, p. 223, prob. 8.]]]

Let $X_1$, $X_2$, and $X_3$ be three mutually independent random
variables, each having the uniform distribution, pr Xi = k equal to 1,
2, or 3 with probability 1/3.
Let M be another random variable giving the max of these three random
vars.

part
What is the distribution of M?

part
What is the expected value of M?

part
Generalize to k instead of 3.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%[[[This is similar to fall 98, hw 11, problem 5.]]]

\problem
% ( expectation, substrings)

Suppose a length n string of 0s and 1s is chosen randomly
(e.g., by n independent tosses of fair coin).
and then wrapped around to form a circle.

part
What is the expected number of occurrences of the string 0000  (k 0s)
in this circle?
(Note: A string of k+1 0s counts as 2 strings of length k -- starting
in the first position of the string and the second position.)

[[[This should be a matter of adding up probabilities of the separate
events that the string occurs starting at position i, which should be
n over 2^k.]]]

part:
Suppose k is even.
What is the expected number of occurrences of 000111 (total length k)?

[[[Should be the same.]]]

part:
Now fix n = 8, k = 4.
Is the probability that 0000 appears in the circle equal to the
probability that 0011 appears?

[[[I haven't worked this out in detail.  I believe there's a lower
probability for 0000 than for 0011]]]

part
If your answers in the previous parts seem to be ``contradictory'',
explain.
If not, don't do anything...

[[[Although the expectations are the same, the extra overlapping
possibilities for 0000 seem to me to make the conditional probability
of a second occurrence, conditioned on a first occurence, higher than
it is for 0011.]]]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem %
%( expectation, indicator variables, harmonic numbers)

fall 98, pset 11, problem 4

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem %

[[[Something with MTTF?]]]

E.g.:
Every day in Boston, a rainstorm occurs with probability 1/3.
Independent (we'll assume).
Each day it rains, the radar system at the Nashua airport fails with
probability 1/50.
Also independent.
Starting from today or when they next fix the radar system, whichever
comes later, 
how many days can we expect the Nashua radar system to work correctly?




\begin{problemparts}
\problempart 

\solution{
}

\problempart 

\solution{
}

\problempart 

\solution{
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
fall 98, pset 11, some version of problem 6.
This does conditional expectation.
An important idea.
Change the details of the problem, though, especially, in the parts
other than (c). 
It seems to me that parts (a), (b), and (c) are intended to be combined into
a claim about E(R), but that's never actually said.  Add a part for
this.
\end{problems}

\end{document}

Tutorial:

Miniquiz:
E.g., problem 2.

Tutorial problems:
1. Flipping coins looking for patterns:
Tutorial 19, fall 99, problem 2

2. Coupon Collector Problem:
Tutorial 19, fall 99, problem 2

3. 






