\magnification=1200
\input macros
\def \twothirds {\raise1pt\hbox{$\scriptstyle
        {2 \over 3}\displaystyle$}} 
\def\startsection #1{\noindent\hbox to\parindent{#1\hfil}}
%%
\noindent
\line{\twelvebf MATHEMATICAL TRIPOS: PART IA\hfil (Lent 2001)}
\med
\line{\bf Probability -- Example Sheet 1\hfil FPK}
\med
[{\it First sheet of 4}]
\bigb
{\bf Exercises}

\bigb
\startsection{\bf 1.} Let $A,B,C$ be three events. The event {\it only
$A$ occurs\/} may be expressed as $A\cap B^c\cap C^c$. Find expressions
for the events that of $A$, $B$ and $C$
\smallskip
\i{} (i) all three occur
\i{} (ii) at least one occurs
\i{} (iii) none occurs
\i{} (iv) not more than two occur.
\bigb
\startsection{\bf 2.} In how many ways can $n$ non-attacking rooks 
(i.e. no two in the same row or column) be placed on an $n\times n$
chessboard?
\bigb
\startsection{\bf 3.} From a table of random digits, $k$ are chosen.
What are the probabilities that for $0\leq r\leq 9$,
\smallskip
\i{} (i) no digit exceeds $r$?
\i{} (ii) $r$ is the greatest digit drawn?
\med
For which value of $r$ is the probability calculated in part (ii)
largest?
\bigb
\startsection{\bf 4.} Four mice are chosen (without replacement) from
a litter, two of which are white. The probability that both white mice
are chosen is twice the probability that neither is chosen. How many
mice are there in the litter?
\bigb
\startsection{\bf 5.} A table-tennis championship for $2^n$ players is
organized as a knock-out tournament with $n$ rounds, the last round
being the final. Two players are chosen at random. Calculate the
probabilities they meet
\smallskip
\i{} (i) in the first round
\i{} (ii) in the final
\i{} (iii) in any round.
\smallskip\noindent
[Hint: Can the same sample space be used for all three calculations?]
\bigb
\startsection{\bf 6.} You and I play a coin-tossing game. If the coin
falls heads I score one, otherwise you score one. We both start
scoring from zero. Show that after $2n$ throws the probability that
our scores are equal is $(2n)!/[2^n(n!)]^2$.
\smallskip
Use Stirling's formula to show that this probability is approximately
$1/\sqrt{\pi n}$ when $n$ is large.
\bigb
\startsection{\bf 7.} A full deck of cards is divided into half at
random. Use Stirling's formula to estimate the probability that each
half contains the same number of red and black cards. [You may wish to
compute the exact answers to questions {\bf 6} and {\bf 7} and compare
them with your estimates.]
\bigb
\startsection{\bf 8.} (i) If $A,B,C$ are three events, show that
$$P(A^c\cap (B\cup C))=P(B)+P(C)-P(B\cap C)-P(C\cap A)-P(A\cap
B)+P(A\cap B\cap C).$$

(ii) How many of the numbers $1,\ldots ,500$ are not divisible by 7
but are divisible by 3 or 5?
\bigb
\startsection{\bf 9.} A committee of size $r$ is chosen at random from
a set of $n$ people. Calculate the probability that $m$ given people
will all be on the committee (a) directly, and (b) using the
inclusion-exclusion formula. Deduce that
$$\pmatrix{n-m\cr r-m\cr} =\sum_{j=0}^m (-1)^j {m\choose j}
{{n-j}\choose r}\, .$$
\med
\startsection{\bf 10.} Examination candidates are graded into four
classes known conventionally as I, II--1, II--2 and III, with
probabilities 1/8, 2/8, 3/8 and 2/8 respectively. A candidate who
misreads the rubric -- a common event with probability 2/3 --
generally does worse, his or her probabilities being 1/10, 2/10, 4/10 and
3/10. What is the probability:
\smallskip
\i{} (i) that a candidate who reads the rubric correctly is placed in the
class II--1?
\i{} (ii) that a candidate who is placed in the class II--1 has read the
rubric correctly?
\bigb
\startsection{\bf 11.} Parliament contains a proportion $p$ of
Labour members, who are incapable of changing their minds about
anything, and a proportion $1-p$ of Conservative members who change their
minds completely at random (with probability $r$) between successive
votes on the same issue. A randomly chosen member is noticed to have
voted twice in succession in the same way. What is the probability
that this member will vote in the same way next time?
\bigb
\bigb
{\bf Problems}
%\med
%{\it Note: These problems should not be tackled at the expense of
%examples on later sheets.}
\bigb
\startsection{\bf 12.} There are $n$ people gathered in a room.
\smallskip
\startsection{} (i) What is the probability that 2 (at least) have the same
birthday? Calculate the probability for $n=22,23$.
\smallskip
\startsection{} (ii) What is the probability that at least one has
the same birthday as you? What value of $n$ makes this close to $1/2$?
\bigb
\startsection{\bf 13.} Let $f_n$ be the number of ways of tossing a
coin $n$ times such that successive heads never appear. Argue that
$$f_n=f_{n-1}+f_{n-2}\qq n\geq 2, f_0=1, f_1=2\, .$$
\bigb
\startsection{\bf 14.} If $n$ balls are placed at random into $n$
cells, find the probability that exactly one cell remains empty.
\bigb
\startsection{\bf 15.} A fair coin is tossed until either the sequence
$HHH$ occurs, in which case $A$ wins, or the sequence $THH$ occurs,
when $B$ wins. Calculate the probability $B$ wins.
\vfill\eject
\startsection{\bf 16.} Mary tosses two coins and John tosses one coin.
What is the probability that Mary gets more heads than John? Answer the
same question if Mary tosses three coins and John tosses two. Make a
conjecture for the probability when Mary tosses $n+1$ and John tosses
$n$. Can you prove your conjecture? 
\bigb
\startsection{\bf 17.} The Polya urn model for contagion is as
follows. We start with an urn which contains one white ball and one
black ball. At each second we choose a ball at random from the urn and
replace it together with one more ball of the same colour. Is there a
tendency to have a large fraction of balls of the same colour in the
long run? [Computer simulations are interesting.] Calculate the
probability that when $n$ balls are in the urn, $i$ of them are
white.
\bigb
\startsection{\bf 18.} A total of $n$ psychologists remembered to
attend a meeting about absentmindedness. After the meeting, none could
recognize his own coat so they took coats at random. Furthermore, each
was liable, with probability $p$ and independently of the others, to
lose the coat on the way home. Assuming, optimistically, that all
arrived home, find the probability that none had his own coat with
him, and deduce that it is approximately $e^{-(1-p)}$.
\bigb
\startsection{\bf 19.} A fair die is thrown $n$ times. Show that the
probability that there are an even number of sixes is
$\half (1+(\twothirds )^n)$. For the purpose of this question, 0 is an
even number.
\bigb
\startsection{\bf 20.} You throw $6n$ dice at random. Show that the
probability that each number appears exactly $n$ times is
$$
{(6n)!\over (n!)^6}\;\left({1\over 6}\right)^{6n}.
$$
Use Stirling's formula $(n!\sim n^{n+\half} e^{-n}\sqrt{2\pi})$ to
show that this is approximately $cn^{-5/2}$ for some constant $c$ to
be found.

\end