% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

\newcount\probno
\probno=0 
\def\prob#1{\advance\probno by 1 \par \bigskip
    \noindent {\it #1} {\bf (\the\probno)} }
\def\prac{\advance\probno by 1 \par \bigskip
    \noindent {\it Practice Problem } {\bf (\the\probno)} }
\def\answer#1{}

\def\var{{\rm var}}
\def\ep{\epsilon}
\def\famc{{\mathcal C}}
\def\famf{{\mathcal F}}
\def\kk{{\mathcal K}}
\def\ll{{\mathcal L}}
\def\mm{{\mathcal M}}
\def\om{{\omega}}
\def\pp{{\mathcal P}}
\def\proves{{\vdash}}
\def\qq{{\mathbb Q}}
\def\reals{{\mathbb R}}
\def\rmiff{\mbox{ iff }}
\def\sent{{\mathcal S}}
\def\su{{\subseteq}}
\def\comb(#1,#2){ \left(\begin{array}{c} #1 \\ #2  \end{array}\right)}
\def\sm{\setminus}
\def\rmand{\mbox{ and }}

\newenvironment{enum}
{\begin{list}{(\alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}

\begin{document}

\begin{flushright}
A.Miller\\
M331\\
Spring 2012
\end{flushright}

Homework problems are due in class one week from the 
day assigned.
The date they are due proceeds them.  
Please do not hand in the problems early or late.
But in any case do not put problems with different due
dates on the same piece of paper.

It is OK to collaborate with other students on these problems.
There will be no penalty.  However, you should give credit
where credit is due.   Just mention who you were working with
and/or got help from.




\prob{Mon Jan 30}
Prove that 
$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$.

Use either a Venn diagram or logical reasoning about elements.

\prob{M Jan 30}
Prove that\footnote{This had an extra complement$^c$.}
$\;\;A\sm B=B^c\sm A^c$
and that $A\su B$ iff $B^c\su A^c$.

\prob{M Jan 30}
Prove that
$(A\sm B)\cup (B\sm A)=(A\cup B)\sm (A\cap B)$.

\prob{M Jan 30}
Define the symmetric difference of two sets to be:
$$A\triangle B=(A\sm B)\cup (B\sm A)$$
Prove that
$(A\triangle B)\triangle C=A\triangle (B\triangle C)$.

\prob{W Feb 01}
Consider the experiment of throwing four coins and noting
heads H and tails T. For example HTTH means first and fourth coin H,
second and third coin T.
\par(a) What is the size $|S|$ of S?
\par(b) $E$ is the event that exactly two coins are H and two are T.
List all the outcomes in $E$.
\par(c) Assume that all outcomes are equally-likely, what is
$P(E)$?

\prob{W Feb 01}
$S=\{a,b,c,d\}$ and $P$ is a probability measure on $S$.  Suppose  $a=P(\{a\})$, $b=P(\{b\})$, $c=P(\{c\})$, and 
$d=P(\{d\})$.
Suppose $b$ is twice $a$, $c$ is three times $b$, and $d$ is four times
$c$.  \par What are $a,b,c,$ and $d$?  \par What is $P(\{b,d\})$?

\prob{F Feb 03} 
Prove 
$P(A\cup B\cup C)=$
$$P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)
+P(A\cap B\cap C)$$

\prob{F Feb 03}
A number is chosen randomly from the integers $1,2,...,10000$. What is
the probability that it is divisible by at least one of
$2,9,$ or $13$?

\prob{M Feb 06}
Suppose that $\lim_{n\to \infty}A_n=B$.  This means:
$$\bigcup_{n=1}^\infty \;\bigcap_{k\geq n} A_k \;\;=\;\;B=\;\;
\bigcap_{n=1}^\infty \;\bigcup_{k\geq n} A_k$$
Prove that $\lim_{n\to \infty}P(A_n)=P(B)$.

\prob{M Feb 06}
Prove that $P(A\triangle B)=P(A)+P(B)-2P(A\cap B)$.

\prob{M Feb 06}
You are the grader of CS101.  The student are to write two programs
$A$ and $B$.  Suppose that 50\% get both right, 35\%
have a bug in Program A, and 45\% get Program B wrong.  What
is the probability that a randomly chosen student got both
programs wrong? 

\prob{W Feb 08}
How many license plates can be made consisting of three distinct letters
from A-Z followed by four distinct numerals 1-9?.  For example,
CZE 2936.  No letter or numeral may be used more than once.

\prob{W Feb 08}
How many batting lineups can be formed from a baseball team with 15 players,
three of which are pitchers, if for each line up exactly one of the 
pitchers plays
and he bats last?
 
A batting line-up consists of 9 distinct
players and the order in which they come up to bat: 
first batter, second batter, and so on, until the ninth batter.


\prob{F Feb 10}
How many ways are there to put 75 distinguishable books onto 5
distinguishable
shelves?  The ordering of books on each shelf counts.
Assume that each possible shelving is equally likely.  What is
the probability that there are exactly two books on the fourth shelf?

\prob{F Feb 10}
Assume that each seven letter word with letters from A-Z is equally likely
to be chosen.  
\par (a) What is the probability that at least one letter occurs 
at least twice in the word?  E.g., ABADEDF or PXYXXXZ

\par (b)  What is the probability that the letter A does not occur in
the word?  (The probability that it does occur? The probability that
occurs at least twice?)

\par (c) What is the probability that at least one vowel (AEIOU) occurs
in the word?

\prob{M Feb 13}
(a) Write out Pascal's triangle for $0\leq n\leq 9$.
\par (b) If a random number from the above triangle is chosen
what is the probability that it is even?
\par (c) Write out $(a+b)^9$ completely expanded.

\prob{M Feb 13}
(a) What is the coefficient of $x^2y^5$ when
$(2x-y)^7$ is completely expanded?
\par (b) What is the coefficient of $u^{10}v^{12}$ when 
$(u^2+v^3)^9$ is completely expanded?


\prob{W Feb 15}
(a) How many 8 letter words can be made by permuting the
letters xxyyyzzw?
\par(b) Assuming each of these words is equally likely to
be chosen, what is the probability that a random word begins
and ends with the same letter?
\par(c) What is the probability that the letter y's occur
consecutively?

\prob{W Feb 15}
What is the coefficient of $a^2\;b\;c^3\;d^4$ in the complete expansion of
$(a+b+c+d)^{10}$?

\prob{F Feb 17}
Suppose an Urn contains 6 red, 6 blue, and 6 white balls and we
simultaneously randomly choose 3 balls from the Urn.

(a) What is the probability that none of the three are red?

(b) What is the probability that at least one is red?

(c) What is the probability that all three are red?

(d) What is the probability that all three are red given
that at least one is red?

(e) What is the probability that all three have different colors
given that at least two colors appear?

Remark. Does it matter if instead we choose the balls sequentially without
replacement?   What about with replacement?

\def\comb(#1,#2){\left(\begin{array}{cc}{#1}\\{#2}\end{array}\right)}


\prob{M Feb 20}
How many triples are there of integers $(x,y,z)$ such that
$$\comb(12,{2,3,7})=\comb(12,x)\comb(y,z)\;\;?$$
Extra credit: write a program to find them all.


\prob{M Feb 20}
In ordinary bridge each of the four players has 13 cards.  There
are four suits: clubs, spades, hearts, and diamonds, each of which
has 13 cards.

(a) What is the probability that you are void in both clubs and diamonds?

(b) What is the probability that you are void in hearts given that
your partner is void in diamonds?


\prob{M Feb 20}
Which is more probable?

(a) You and your partner have all the clubs between you.

(b) You and your partner are both void in spades.


\prob{W Feb 22}
Monty Hall's Lets make a deal.   Suppose the following:

(1) Contestant randomly chooses one of three doors. Behind one
of the doors is a fabulous {\bf P}rize and the other two doors a
{\bf G}oat.

(2) After opening one of the doors not chosen and
displaying a goat, Monty Hall does the following:

If the contestant has chosen {\bf P}, then with probability $p$
Monty Hall offers to switch doors.  If the contestant has
chosen {\bf G}, then with probability $q$
Monty Hall offers to switch doors.  

(3) If the contestant is allowed to switch doors, then
with probability $r$ he or she takes the switch offer. 


(a) Draw a tree representing all outcomes of this ``Deal''.

(b) As a function of $p$, $q$, and $r$ what is the probability
that the Contestant gets the {\bf P}rize? (i.e., winning)

(c) Show that for any fixed values of $p$ and $q$ that either $r=0$
or $r=1$ will maximize the probability that the Contestant wins.

(d) For what values of $p$ and $q$ is it true that the
probability of winning is the same for all values of $r$?

(e) Show that for any  $s$ with $0\leq s\leq 1$ there are
values $p,q$ such that if the contestant always
takes the switch when offered ($r=1$), then
the probability of the Contestant winning is $s$.



\prob{F Feb 24}
How many 8 letter words can be made by permuting the
letters xxyyyzzw and have the property that no two y's
occur next to each other?

\prob{F Feb 24}
A basket contains 5 White balls and 6 Green balls.

1. Choose one ball from the basket at random.

2. If it is White replace it in the basket with 2 Green.
If it is Green replace it with 3 White.  In either case
do not put the chosen ball back in the basket.

3. Randomly choose a second ball from the basket.

(a) What is the probability that the first ball was White
given that the second ball chosen was Green?  i.e., $P(W_1|G_2)$.

(b) What is $P(G_1|W_2)$?


\prob{M Feb 27}
Given $S$, $H$, $W_1$, and $W_2$ in some probability space, let
$p_1=P(S|W_1)$ and $p_2=P(S|W_2)$.
$S$ and $H$ are complimentary events.\footnote{These stand for Spam and Ham,
see Wikipedia on Bayesian spam filtering.}
Consider the following three
statements:

\medskip
(1) $S\cap W_1$, $S\cap W_2$ are independent and
$H\cap W_1$, $H\cap W_2$ are independent.

\medskip
(2) $$P(S|W_1\cap W_2)=\frac{p_1p_2}{p_1p_2+(1-p_1)(1-p_2)}$$

(3) $$\frac{P(H\cap W_1\cap W_2)}{P(S\cap W_1\cap W_2)}=
\frac{P(H\cap W_1)P(H\cap W_2)}{P(S\cap W_1)P(S\cap W_2)}
$$

\bigskip
Assume all six probabilities 
in statement (3) are positive.

\noindent Prove that $(1)\to (2)$.

\prob{M Feb 27}
Prove that $(2)\to (3)$ and $(3)\to (2)$.

\prob{M Feb 27}
Give an example where $(3)$
is true (and therefore (2)) but $(1)$ is false.

\prob{W Feb 29} Here is a way\footnote{This is from
Scientific American June 2011 page 30.} to use randomness to encourage 
people to tell the truth when answering an embarrassing survey
question.    The survey has
one question:

\bigskip
Q. Have you ever ``X-ed''?

\bigskip
Where ``X-ed'' stands for some embarrassing X-rated sexual activity
for which people are likely to lie and say No even if that
have in fact X-ed.

\bigskip
Randomized Procedure:  Call up a random person on the phone
and ask them to flip a coin but not tell you of the outcome.
If the coin comes up H they are to say yes to the question
whatever the true answer is.
If the coin comes up T they are to give the true answer.

\bigskip
The idea is that the person is more likely to give the true
answer since the researcher does not know if the person answered
yes because the coin flip was H or because it was T and the
person truly X-ed.   After asking 1000 people and receiving
550 yes answers the researcher can guess that about 500 got
H and answered yes and 500 got T and 50 answered yes and so
about $\frac{50}{500}$ or 10\% have X-ed.

\bigskip
Suppose you are told that the probability a random person has X-ed
is $p$.  In terms of $p$ what is the probability that
the randomly chosen person has X-ed given that he answered
yes when he was called and the randomized procedure above
was followed?
Check your answer for $p$ equal 10\%.

Extra credit.  What happens if instead the person flips the coin
twice and always answer yes except if TT occurs and
then the person answers truthfully?


\prob{W Feb 29}
Suppose $A_1,A_2,A_3$ are independent.  Show
that  $A_1^c,A_2,A_3$ are independent.  Remark: By symmetry
it follows that any of the eight sequences $B_1,B_2,B_3$ is independent
where each $B_k$ is either $A_k$ or $A_k^c$.


\bigskip
Recall that $A_1,A_2,A_3$ are independent iff the following
are all true:
\begin{enumerate}
\item $P(A_1\cap A_2\cap A_3)=P(A_1)P(A_2)P(A_3)$

\item $P(A_1\cap A_2)=P(A_1)P(A_2)$

\item $P(A_1\cap A_3)=P(A_1)P(A_3)$

\item $P(A_2\cap A_3)=P(A_2)P(A_3)$

\end{enumerate}


\prob{W Feb 29}
Give an example of $A_1,A_2,A_3$ where 1,2,3 are all true
but 4 is false.

\prob{W Feb 29}
Give an example of $A_1,A_2,A_3$ where 2,3,4 are all true
but 1 is false.

\prob{F Mar 2}
Suppose that $A,B$ are independent and $A,C$ are independent.
Prove that $A,B\cup C$ are independent iff $A,B\cap C$ are independent.

\prob{F Mar 2}
This is a multiple choice problem.

\noindent Q. If you randomly chose one of the following answers, what is
the probability that you chose correctly?

(a) 25\%

(b) 50\%

(c) 50\%

(d) 100\%

\prob{M Mar 5}
Three distinguishable dice are thrown.  The random variable
$X$ is the number of different numbers that appear,
e.g., $X(\langle 5,3,5\rangle )=2$.  Find $E(X)$.

\prob{W Mar 7}
Suppose a basket contains 10 red, 20 white, and 30 blue balls.
Thirty are chosen randomly at the same time.  Let $R$ be the number of
red balls chosen, $W$ the number of white balls chosen, and $B$
the number of blue balls chosen.  Find $E(R+2W-B)$.

\prob{F Mar 9}
Find an example of three ball players $A$,  $B$, and $C$ and two
seasons such that in terms of their batting average:

$A$ beats $B$ each season and $B$ beats $C$ each season,
but $C$ beats $B$ and  $B$ beats $A$ when the season stats
are combined.

\bigskip
(World Series of Baseball)
Suppose that a coin has probability $p$ of falling Heads.
Repeatedly toss it until at least four $H$ appear or four
$T$,  i.e., best out of seven games is the winner.
Let $X$ be the number of tosses this takes, i.e., $4\leq X\leq 7$

\prob{F Mar 9}
In terms of $p$ what is the probability distribution of $X$?

\prob{F Mar 9}
For $p=\frac12$ in problem (39) find the expectation $\mu=E(X)$, 
variation $\nu=$var$(X)$, and the standard deviation $\sigma$ 
of $X$.

\prob{M Mar 12}
(Russian Roulette) The Master of Ceremonies (MC) puts one
bullet into a six shooter and randomly rotates the chamber.
There are six players who one-by-one take the pistol put
it to there head and squeeze the trigger.  $X$ is the
player that shoots himself.  ( A less bloody description
would be: throw a die.  $X$ is the number showing on the die)
Find the expected value, variation, and standard deviation
of $X$.

\prob{M Mar 12}
(Russian Roulette Variation) The Master of Ceremonies (MC) puts one
bullet into a six shooter and randomly rotates the chamber.
He gives it to player 1 who squeezes the
trigger.  If he shoots himself the game is over.  Otherwise
the MC randomly rotates the chamber again and gives the pistol
to player 2.  $Y$ is the player who is shot.  If all players
survive one round then $Y=0$.
(A less bloody description
would be: throw a die 6 times.  Let $Y$ be the first time
a one is thrown, if any is, otherwise $Y=0$ if there
are no ones.)
Find the expected value, variation, and standard deviation
of $Y$.






\prob{M Mar 12}
Suppose $X$ and $Y$ are random variables on the same probability
space 

\begin{minipage}{2in}
$$P(X=2)=\frac13$$ $$ P(X=3)=\frac13$$ $$P(X=6)=\frac13$$ 
\end{minipage}
\begin{minipage}{2in}
$$P(Y=1)=\frac14$$ $$P(Y=2)=\frac14$$ $$P(Y=3)=\frac12$$
\end{minipage}

\bigskip \noindent (a) Compute $E(X)$, $E(Y)$, and $E(X)E(Y)$.

\bigskip\noindent  (b) Suppose $X$ and $Y$ are independent and compute $E(XY)$.

\bigskip\noindent (c) Suppose $P(X=a \rmand Y=b)=\frac19$ 
for all $a$, $b$ except\footnote{I
made a mistake in class - they can't all be $\frac19$.}
$$P(X=6 \rmand Y=1)=\frac14-\frac29$$
$$P(X=6 \rmand Y=2)=\frac14-\frac29$$
$$P(X=6 \rmand Y=3)=\frac12-\frac29$$
then compute $E(XY)$.

\prob{W Mar 14}
Does $E(XY)=E(X)E(Y)$ imply that $X,Y$ are independent? No.
Suppose $A,B \;\su \;\Omega$ have probability $\ep$ and
are disjoint and $a,b$ are real numbers.
Define
$$X(\om)=\left\{
\begin{array}{ll}
a & \mbox{ if }\om\in A\\
1 & \mbox{ if }\om\in B\\
0 &\mbox{ otherwise }
\end{array}\right.
\;\;\;\;\;
Y(\om)=\left\{
\begin{array}{ll}
1 & \mbox{ if }\om\in A\\
b & \mbox{ if }\om\in B\\
0 &\mbox{ otherwise }
\end{array}\right.
$$

(a) Find $E(X)$, $E(Y)$, $E(X)E(Y)$, and $E(XY)$.

(b) Show that there is an $\ep$ with
$0<\ep<\frac12$ and $a,b$ different from 1, so that
$X,Y$ are not independent but $E(XY)=E(X)E(Y)$.

\prob{W Mar 14} (a) Give an example of a random variable $X$ such
that $E(X)=2$ and $E(X^2)=3$ or show that this is impossible.
(b) Give an example of a random variable $X$ such
that $E(X)=1$ and $E(X^2)=3$ or show that this is impossible.

\prob{W Mar 14} Let $X$ and $Y$ be random variables (which may
not be independent) but for which $\var(X+Y)=\var(X)+\var(Y)$.
Prove that $E(XY)=E(X)E(Y)$.

\prob{F Mar 16}
Suppose a basketball player has a probability of making
a 1-point shot (free throw) of $\frac12$, 
a 2-point shot of  $\frac13$, and a 3-point shot of
$\frac15$.  During a game he makes 10 1-point attempts,
21 2-point attempts, and 5 3-point attempts.  Let
$X$ be the total number of points he scores.  Assuming
all shot attempts are pairwise independent Bernoulli trials,
find the expected value, variance, and standard deviation of $X$.

\prob{M Mar 19}
Let $X_1,X_2,\ldots,X_n$ be pairwise independent Bernoulli trials
with probability of success $p=\frac13$.  Using Chebyshev find the
smallest $n$ such that the probability is at least 99\%
that $X_1+X_2+\cdots+X_n$ is
$\frac{n}3$ with error no worse than plus or minus one percent of
$\frac{n}3$.

\prob{M Mar 19}
Suppose $X\geq 0$ and $P(X<3)< \frac15$.  If $\mu=E(X)$
what is the smallest possible value $\mu$ can have?

Remark: If $X$ takes on negative values also, could $\mu$ be smaller?

\prob{M Mar 19}
Suppose $\sigma$ is the standard deviation of $X$ and $\mu$ its
expectation.  Prove:

(a) $P(\mu-2\sigma < X < \mu+2\sigma)\geq .75$

(b) $P(\mu-3\sigma < X < \mu+3\sigma)\geq .88$


\prob{F Mar 23} (Drunkard's walk) Define a sequence
$$x_0=0\;\;\;\;\;\;\;\; x_{k+1}=\left\{
\begin{array}{ll}
0     & \mbox{ if $k\geq 1$ and $x_k=0$ otherwise:} \\
x_k+1 & \mbox{ with probability }\frac12\\
x_k-1 & \mbox{ with probability }\frac12\\
\end{array}\right.$$
The drunk staggers back and forth randomly but
if he ever returns to the origin he stops, i.e., from
that point on $x_k$ is constantly zero.
Use the Monte Carlo method to estimate the probability
that $x_{10}=0$. Use any programming language
you want and any large number of trials, say a million.
With a reliability of
95\% how close is your estimate to the exact value?
What is your estimate of the probability that $x_{50}=0$ or the probability
that $x_{100}=0$?

\prob{F Mar 23}  Suppose that $u^2\leq v$.  Construct
a random variable $X$ with $E(X)=u$ and $E(X^2)=v$.

\prob{F Mar 23}  Suppose that the score of a student on an exam is
modeled by a random variable $X$.   Given that the expected value
of $X$ is 68 points, find an upper bound on the probability that
the student scores 78 or more.

\prob{F Mar 23} Suppose that it also known that the standard deviation
of $X$ is 6 points.   Find a better upper bound on the probability that
the student scores 78 or more. 

\prob{F Mar 23} Suppose that there are $n$ students in the class and their
scores on the exam are modeled by pairwise independent random variables
with the same mean 68 and standard deviation 6 as in the previous
two problems.   Estimate the smallest
value of $n$ such that the probability is at least 95\% 
that the average score of the class on the exam 
is within 5 points of the mean 68.


\prob{M Mar 26}
In the Las Vegas game of KENO (which is similar to a lotterie)
a player chooses (marks) from 1 to 15 numbers out of 80 and makes a bet.
The casino randomly chooses  20 out these 80.  It pays out an
amount that depends on the number of ``catches'' or ``winning spots''
the player's card has.
For more information on KENO see ``How to play Keno''.

% www.math.wisc.edu/$\sim$miller/m331/

Mark 5
\begin{tabular}{|c|r|r|}
\hline
catch & Bally: bet 10 pays out & Barbary: bet 1 pays out\\
\hline
3 & 10 & 1\\
4 & 200 & 25\\
5 & 5500 & 600\\
\hline
\end{tabular}

Let $X$ be a random variable which is the amount Bally casino will payout
on a 10 dollar bet where the player has marked 5 spots on his card.
Find the expected value of $X$.  Similarly let
$Y$ be the amount that Barbary casino will pay out on a 1 dollar bet.
Find the expected value of $X$ and the expected value of $Y$.

Let $Z_k$ be the number of catches for a card with k spots marked
out of a possible 80.  Find the expected value and variance of
$Z_k$ for $k=5,6,7$.

\def\pr{\prime}

\prob{M Mar 26}
Beeno is like Keno but uses a binomial distribution.   Instead of
choosing exactly 20 out of 80 the casino chooses each number independently
with probability $\frac14$.  On average this will be 20. 
Repeat problem (56) for the analogous variables,
$X^\pr, Y^\pr, Z_k^\pr$.

\prob{W Mar 28}  Suppose a woman has probability $b$ of having a
boy and $g$ of having a girl.  Assume $0<b<1$ and $g=1-b$.  She
decides to keep having children until she has a child of each sex.
Let $X$ be the number of children she has in the end.   
Find the
expected value, variance, and standard deviation  ($\mu,\nu,\sigma$) of
$X$ in terms of $b$ and $g$.

\prob{W Mar 28}
For each of $b=\frac12$ and $b=\frac13$ in problem (58)
compute the exact values of $\mu,\nu,$ and $\sigma$.

\prob{F Mar 30} 
Given $0<p<1$ and $p+q=1$, suppose that for every $n=1,2,\dots$ that
$P(X=n)=q^{n-1}p$.  
Find 
$$E\left(\frac{1}{X!}\right)$$
Extra credit: find $E(X^3)$ or $E(\frac1X)$.

\prob{F Mar 30} Give an example of a discrete random variable 
$X\geq 0$ such that
$E(X)$ is finite but $E(X^2)=\infty$.

\prob{W Apr 11}
Let $0<p<1$ and $p+q=1$.  Fix $n$ and
let 
$$r_k=\comb(n,k)p^kq^{n-k}$$

(a) Prove for all $k$ that $r_{k} < r_{k+1}$ iff $k<np-q$.

(b) Prove for all $k$ that $r_{k}\geq r_{k+1}$ iff $k\geq np-q$.

(c) Define $M_n=\max\{r_k\;:\; k=0,1,2,\dots,n\}$.
Show that $M_n=r_{k_0}$ where $k_0$ is the least $k$
such that $np-q\leq k$.

(d) For $n=10$ and $p=1/3$ find $M_n$.

(e) For $n=11$ and $p=2/3$ find $M_n$.

\medskip
\noindent Remark. Is $k_0$ always the closest integer to $np$?
If $np-q=k$, then is $r_k=r_{k+1}$?

\prob{F Apr 13}
Suppose you have 6 red balls and 6 black balls in a basket.
Consider the following algorithm:

\bigskip
1. Choose a ball randomly from the basket.

2. If it is a red ball, put it back in the basket.

3. If it is a black ball, remove it from the basket.

4. If there are any black balls still in the basket, go to step 1.

5. Stop.


\bigskip
Find the expected value of the number of times that step 1 is executed.

\prob{F Apr 13}
Tom, Dick, and Harry flip a silver dollar repeatedly in the order:

T, D, H, T, D, H, T, D, H, T, $\ldots$

\noindent until finally one of them gets a HEAD and wins the dollar.
For each of the players find the expected value of the amount they
win.  Assume that the probability of HEADs is $p$ with $0<p<1$ and
TAILs is $q$ with $p+q=1$.    What are these three values when
$p=\frac12$?   What happens as $p\to 0$?


\prob{M Apr 16} Auto accidents occur at the corner of University
and Charter at the Poisson rate of three per month. What is
the probability that at least two accidents will occur during
the month of June?

\prob{M Apr 16} (Continuation) What is the probability that no
accidents occur during exactly three of the next six months?

\prob{M Apr 16} Let $X_P$ be Poisson with parameter $\lambda$.
Show that
$$E(X_P^3)=\lambda\; E((X_P+1)^2)$$
and use it to compute $E(X_P^3)$.

\prob{W Apr 18}
Suppose Bob starts with \$10 and Mike starts with \$30.  They
repeatedly bet \$1 until one of them goes broke.  Let
$p$ be the probability that Bob wins each individual bet.
For each of $p=.5, \;.49,$ and $.45$, find the probability that
Bob goes broke before Mike does.

\prob{W Apr 18} Repeat problem (68) but instead assume that each
individual bet is for \$5 instead of \$1.

\prob{F Apr 20}
Six red and six blue marbles are randomly put into two urns, A and B.
Urn A has two marbles and Urn B has ten marbles.  One marble from A
and one marble from B are chosen randomly and switched.   Draw
a Markov transition graph and give the transition matrix for
this problem.

\prob{F Apr 20} Let
$$A_1=\left[
\begin{array}{rrr}
3 & 2 & 1 \\
-1 & 0 & 1\\
\end{array}\right]\;\;\;
A_2=\left[
\begin{array}{rr}
1 & -1  \\
2 & 0 \\
\end{array}\right]\;\;\;
A_3=\left[
\begin{array}{rr}
1 & 0  \\
2 & 3 \\
0 & -1 \\
\end{array}\right]
$$
For all nine possible pairs $A_i$ and $A_j$ compute
$A_iA_j$ or say that it is undefined.
For how many of the 27 triples is $A_iA_jA_k$ defined?

\prob{W Apr 25} The Raisin-Bran Game. On the back of box of
raisin bran cereal appears the following game.  There
are six squares numbered 

(1) Start 

(2) OK

(3) OK

(4) OK

(5) GoBack to (2)

(6) Finish

The game starts at (1) and ends when you arrive at (6).
For each move
you throw a fair coin, if it lands Heads you advance from (i) to
(i+1), if it lands Tails you advance from (i) to (i+2).   
If you land on (5) you immediately return to (2).
Landing on (5) and returning to (2) counts as one move, not two.

Find the expected number of moves in the Raisin-Bran game.

\bigskip\noindent
Remark.  It is easy to find an on-line matrix inverter calculator.
For example, bluebit looks easy to use:

 http://www.bluebit.gr/matrix-calculator/

\prob{F Apr 27} Take a random walk along this graph: 
\def\text#1{\makebox(0,0)[cc]{#1}}

\noindent
\unitlength=1.36mm
\begin{picture}(100, 40)
\put(10, 30){\line(0, -1){20}}
\put(30, 10){\line(0, 1){20}}
\put(50, 10){\line(0, 1){20}}
\put(10, 10){\line(1, 0){40}}
\put(10, 30){\line(1, 0){40}}
\put(10, 10){\circle*{1}}
\put(30, 10){\circle*{1}}
\put(50, 10){\circle*{1}}
\put(10, 30){\circle*{1}}
\put(30, 30){\circle*{1}}
\put(50, 30){\circle*{1}}
\put(10,30){\line(1,-1){20}}
\put(8,7){\text{6 stop}}
\put(52,32){\text{5 stop}}
\put(8,32){\text{1}}
\put(30,33){\text{2}}
\put(30,7){\text{3}}
\put(50,7){\text{4}}
\end{picture}


At any of the nodes 1,2,3,4 the chain is equally likely to follow any of
the out-going edges.  At the nodes marked stop the Markov process terminates.
For each of the
nodes 1-4 calculate the probability that a random walk starting
there will eventually arrive at 5 and the probability it will
eventually arrive at 6.

\prob{F Apr 27} Same graph but no stop states:

\noindent
\unitlength=1.36mm
\begin{picture}(100, 40)
\put(10, 30){\line(0, -1){20}}
\put(30, 10){\line(0, 1){20}}
\put(50, 10){\line(0, 1){20}}
\put(10, 10){\line(1, 0){40}}
\put(10, 30){\line(1, 0){40}}
\put(10, 10){\circle*{1}}
\put(30, 10){\circle*{1}}
\put(50, 10){\circle*{1}}
\put(10, 30){\circle*{1}}
\put(30, 30){\circle*{1}}
\put(50, 30){\circle*{1}}
\put(10,30){\line(1,-1){20}}
\put(8,7){\text{6}}
\put(52,32){\text{5}}
\put(8,32){\text{1}}
\put(30,33){\text{2}}
\put(30,7){\text{3}}
\put(50,7){\text{4}}
\end{picture}

Prove that this Markov chain is regular.

\prob{M Apr 30}
Prove that the random walk on an $n$-cycle is regular
iff $n$ is odd.

\prob{W May 2}
In a long line of children you happen to notice that
about 30\% of the time a girl is followed by a boy and
about 80\% of the time a boy is followed by another boy.
If you randomly choose a child from the line, what
is the probability that its a girl?


\prob{W May 2}
For a random walk on the graph:

\noindent
\unitlength=1.36mm
\begin{picture}(100, 40)(-30,0)
\put(10, 30){\line(0, -1){20}}
\put(30, 10){\line(0, 1){20}}
\put(10, 10){\line(1, 0){20}}
\put(10, 30){\line(1, 0){20}}
\put(10, 10){\circle*{1}}
\put(30, 10){\circle*{1}}
\put(10, 30){\circle*{1}}
\put(30, 30){\circle*{1}}
\put(10,30){\line(1,-1){20}}
\put(8,7){\text{3}}
\put(8,32){\text{1}}
\put(30,33){\text{2}}
\put(30,7){\text{4}}
\end{picture}

find the steady state probability vector.

\prob{W May 2} (from the Snell book)
Suppose that $P$ is the transition matrix for
an ergodic Markov chain.  Let
$$Q=\frac12 I\;+\frac12 P$$
(a) Prove that $Q$ is regular.
\par\noindent (b) Prove that if
$\vec{s}\;Q=\;\vec{s}$, then
$\vec{s}\;P=\;\vec{s}$.

\prob{F May 4}
Calculate the Lebesgue measure of the set
$$\bigcup_{n=1}^\infty\; \left(n!+\frac1{3^n},\;\;n!+\frac1{2^n}\right]$$


\prob{M May 7}
Fix $K$ a large integer and $s=(s_0,\ldots, s_{K-1})\in 2^{<\omega}$
a finite sequence of zeros and ones.  Define
$$D_n=\{x\in 2^\omega\;:\; x_{n+i}=s_i \mbox{ for all } i=0,\ldots,K-1\}$$
Show that
$$\mu(\bigcap_{n=0}^\infty \bigcup_{k>n} D_k)=1$$ 

\prob{M May 7}
Define
$$E_n=\{x\in 2^\omega\;:\; x_{n+i}=0 \mbox{ for all } i=0,\ldots,n-1\}$$
Show that
$$\mu(\bigcap_{n=0}^\infty \bigcup_{k>n} E_k)=0$$ 

\prob{W May 9}
Suppose in Feller's infinite URN game, at each of the steps $n=1,2,\ldots$
you add enough to have $n^2+1$ balls in the URN and then you randomly
choose one of the balls in the URN and discard it.  Prove
that the probability that ball 1 is never discarded is positive.

Remark.  With probability 1 infinitely many of the balls are never
discarded.  Note that you must add $(n^2+1)-(n-1)^2=2n$ balls at step
$n$.   This result remains true if you add $2n$, $n$, or even $\frac12n$
balls at step $n$.

\prob{W May 9}  Suppose $x,y,z $ are three random reals in $[0,1]$ chosen
independently and uniformly.   What is the probability that there
is a triangle with sides of length $x,y,$ and $z$?

\newpage

\begin{center}
Practice Problems - Do not hand in.
\end{center}


\prac
Prove that $A_1,\ldots,A_n$ are independent if and only if
for any sequence $B_1,\ldots,B_n$ where each $B_k$ is
either $A_k$ or $A_k^c$ we have that
$$P(B_1\cap B_2\cap\cdots\cap B_n)=P(B_1)\, P(B_2)\cdots P(B_n)$$

\prac
Suppose we have two red, two white, two blue balls in a basket.

Choose 2, if they have the same color you win.

Choose 2 more (without replacing first two), if they
have the same color you win.

Finally if the two left in the basket are the same color, you
win.

Would you take an even money bet?  I.e., if you win you get a dollar,
if you lose you pay a dollar.  What is the probability that you win?

\prac
There are two fair die, a red one and a blue one.

A is the event that the red die is a 1 or 6.

B is the event that the total of the two die is 7,

C is the event that the red die is a 1 or the blue die is a 6.

\noindent For each of the following determine if is true or false and
explain why.

1. A and B are independent events.

2. A and C are independent events.

3. B and C are independent events.

4.  $A$ and $B\cup C$ are independent events.

5. $A\cap C$ and $B\cup C$ are independent events.

\prac You have 8 cards, 4 aces and 4 kings,

a. Choose three at random simultaneously.
What is the probability that one is a king given that 2 are aces?

b. Choose three in order 1,2,3 without replacement.
What is the  probability that card 3 is a king given
that cards 1,2 are aces.

c. Choose three at random and
suppose at least 2 are aces.
Randomly permute them and sequentially show then 1,2,3.
What is probability the card 3 is a king given 1,2 are aces?

d. Choose three at random simultaneously, What is the probability
all are kings given that not all are aces?

\prac
Prove or disprove;

 Suppose A,B,C are independent,
 must $A \cup B$ and  $B \cup C$ be independent?

\answer{
No throw a coin 3 times  A first coin H , B second H, C third H
(A U B)  cap (B U C)  = B U (A cai C cap B^c)
which has prob 1/2 + 1/8 = 5/8
A U B has prob 1/2 + 1/2 - 1/4 = 3/4
B U C has prob 3/4
3/4 3/4 neq 5/8
}

\prac
A box contains 3 cards:

one card has both sides white

one card has both sides black

one card has a white side and a black side

\noindent A card is randomly drawn out
of the box and placed on a table

Given that the side facing up is black
what is the probability that the other
side of the card is black?

\answer {
2/3
six possible ways to draw
card out of box
down/up
w1w2
w2w1
b1b2
b2b1
b0w0
w0b0
choices 3 4 6 show black
2/3 of these have hidden black card}

\prac In problem (30) change the randomization procedure:

If first flip is H, then
flip again and say yes if H and no if T.
If first flip is T then answer truthfully.

\prac For any regular Markov chain transition matrix $P$
show that there must be $k$ such that for all
$m\geq k$ all entries of $P^m$ are positive.

\prac
Assume $X_k$'s are pairwise independent Bernoulli variables
with parameter $p$.
Use Chebyshev's inequality and the Borel-Cantelli Lemma
to show that for any $\epsilon>0$ 
the probability that there are infinitely
many $n$ with 
$$\left|\frac{X_1+\ldots X_{n^2}}{n^2} - p\right|\geq \epsilon$$
is zero.

\prac
For independent uniformly distributed random variables
$x$ and $y$ in the unit interval $[0,1]$ find
the expected value of the distance between $x$ and $y$.

\prac
For a random point $P$ in the unit disk
find the expected value of $r$, the distance from $P$ to
the origin. 
Hint: you can differentiate the cummalative distribution function
to find the density function for $r$.


\prac For a pair of independent random reals in the unit
interval what is the expected value of $xy$?   Why should
it be $\frac12\cdot\frac12$?

\prac In Laplace's famous example of ``what is the probability
that the sun rises tomorrow'' he shows the following:

Randomly
choose a probability $p$ in the unit interval and toss a
coin with probability $p$ of being a Head.  Then the probability
it comes out Heads $n$-times in a row is
$$\int^1_0 p^n\;dp=\frac1{n+1}$$
Show that for any $k$ that
$$\int^1_0 \comb(n,k)p^k(1-p)^{n-k}\;dp=\frac1{n+1}$$
Hint: use integration by parts.  
Can you give a probabilistic argument?

\prac In Bertrand's random chord 
paradox\footnote{wikipedia.org : Bertrand's paradox}
suppose we pick a random
chord on the unit disk using the following procedures:

(4) Randomly choose two points inside the unit disk and take the
chord containing them.


(5) Randomly choose one point inside the unit disk and one point
on the circle and take the chord containing them.


(6) Randomly choose a length in $[0,2]$ and then a chord of that length.


(7) Randomly choose an area $0\leq A\leq\frac{\pi}2$ and choose a chord
cutting off that area from the unit disk.

What is the probability that the chord chosen has length greater than
one of the sides of the inscribed equilateral triangle?

Can you come up with an eight method?


\prac Suppose you choose a random real number $x$ in $[0,1]$.  What
is the probability that $x$ is a rational number?





\end{document}


