Events and their probabilities

Let $\left\{ A_{i}: i \in I\right\}$ be a collection of sets. Prove 'De Morgan's Laws' :

Let $A$ and $B$ belong to some $\sigma$-field $\mathcal{F}$. Show that $\mathcal{F}$ contains the sets $A \cap B, A \backslash B$, and $A \triangle B$.

A conventional knock-out tournament (such as that at Wimbledon) begins with $2^{n}$ competitors and has $n$ rounds. There are no play-offs for the positions $2,3, \ldots , 2^{n}-1$, and the initial table of draws is specified. Give a concise description of the sample space of all possible outcomes.

Let $\mathcal{F}$ be a $\sigma$-field of subsets of $\Omega$ and suppose that $B \in \mathcal{F}$. Show that $\mathcal{G} = \left\{ A \cap B: A \in \mathcal{F}\right\}$ is a $\sigma$-field of subsets of $B$.

Which of the following are identically true? For those that are not, say when they are true.

Let $A$ and $B$ be events with probabilities $\mathbb {P}\left(A\right) = \frac{3}{4}$ and $\mathbb {P}\left(B\right) = \frac{1}{3}$. Show that $\frac{1}{12} \leq \mathbb {P}\left(A \cap B\right) \leq \frac{1}{3}$, and give examples to show that both extremes are possible. Find corresponding bounds for $\mathbb {P}\left(A \cup B\right)$.

A fair coin is tossed repeatedly. Show that, with probability one, a head turns up sooner or later. Show similarly that any given finite sequence of heads and tails occurs eventually with probability one. Explain the connection with Murphy's Law.

Six cups and saucers come in pairs: there are two cups and saucers which are red, two white, and two with stars on. If the cups are placed randomly onto the saucers (one each), find the probability that no cup is upon a saucer of the same pattern.

Let $A_{1}, A_{2}, \ldots , A_{n}$ be events where $n \geq 2$, and prove that

In each packet of Corn Flakes may be found a plastic bust of one of the last five Vice-Chancellors of Cambridge University, the probability that any given packet contains any specific Vice-Chancellor being $\frac{1}{5}$, independently of all other packets. Show that the probability that each of the last three Vice-Chancellors is obtained in a bulk purchase of six packets is $1-3\left(\frac{4}{5}\right)^{6}+3\left(\frac{3}{5}\right)^{6}-\left(\frac{2}{5}\right)^{6}$.

Let $A_{r}, r \geq 1$, be events such that $\mathbb {P}\left(A_{r}\right) = 1$ for all $r$. Show that $\mathbb {P}\left(\bigcap_{r = 1}^{\infty } A_{r}\right) = 1$.

You are given that at least one of the events $A_{r}, 1 \leq r \leq n$, is certain to occur, but certainly no more than two occur. If $\mathbb {P}\left(A_{r}\right) = p$, and $\mathbb {P}\left(A_{r} \cap A_{s}\right) = q, r \neq s$, show that $p \geq 1 / n$ and $q \leq 2 / n$.

You are given that at least one, but no more than three, of the events $A_{r}, 1 \leq r \leq n$, occur, where $n \geq 3$. The probability of at least two occurring is $\frac{1}{2}$. If $\mathbb {P}\left(A_{r}\right) = p, \mathbb {P}\left(A_{r} \cap A_{s}\right) = q, r \neq s$, and $\mathbb {P}\left(A_{r} \cap A_{s} \cap A_{t}\right) = x, r < s < t$, show that $p \geq 3 /(2 n)$, and $q \leq 4 / n$.

Prove that $\mathbb {P}\left(A \mid B\right) = \mathbb {P}\left(B \mid A\right) \mathbb {P}\left(A\right) / \mathbb {P}\left(B\right)$ whenever $\mathbb {P}\left(A\right) \mathbb {P}\left(B\right) \neq 0$. Show that, if $\mathbb {P}\left(A \mid B\right) > \mathbb {P}\left(A\right)$, then $\mathbb {P}\left(B \mid A\right) > \mathbb {P}\left(B\right)$.

For events $A_{1}, A_{2}, \ldots , A_{n}$ satisfying $\mathbb {P}\left(A_{1} \cap A_{2} \cap \cdots \cap A_{n-1}\right) > 0$, prove that

A man possesses five coins, two of which are double-headed, one is double-tailed, and two are normal. He shuts his eyes, picks a coin at random, and tosses it. What is the probability that the lower face of the coin is a head?

He opens his eyes and sees that the coin is showing heads; what is the probability that the lower face is a head? He shuts his eyes again, and tosses the coin again. What is the probability that the lower face is a head? He opens his eyes and sees that the coin is showing heads; what is the probability that the lower face is a head?

He discards this coin, picks another at random, and tosses it. What is the probability that it shows heads?

What do you think of the following 'proof' by Lewis Carroll that an urn cannot contain two balls of the same colour? Suppose that the urn contains two balls, each of which is either black or white; thus, in the obvious notation, $\mathbb {P}\left(\mathrm{BB}\right) = \mathbb {P}\left(\mathrm{BW}\right) = \mathbb {P}\left(\mathrm{WB}\right) = \mathbb {P}\left(\mathrm{WW}\right) = \frac{1}{4}$. We add a black ball, so that $\mathbb {P}\left(\mathrm{BBB}\right) = \mathbb {P}\left(\mathrm{BBW}\right) = \mathbb {P}\left(\mathrm{BWB}\right) = \mathbb {P}\left(\mathrm{BWW}\right) = \frac{1}{4}$. Next we pick a ball at random; the chance that the ball is black is (using conditional probabilities) $1 \cdot \frac{1}{4}+\frac{2}{3} \cdot \frac{1}{4}+\frac{2}{3} \cdot \frac{1}{4}+\frac{1}{3} \cdot \frac{1}{4} = \frac{2}{3}$. However, if there is probability $\frac{2}{3}$ that a ball, chosen randomly from three, is black, then there must be two black and one white, which is to say that originally there was one black and one white ball in the urn.

The Monty Hall problem: goats and cars.

Let $G$ be the event that an accused is guilty, and $T$ the event that some testimony is true. Some lawyers have argued on the assumption that $\mathbb {P}\left(G \mid T\right) = \mathbb {P}\left(T \mid G\right)$. Show that this holds if and only if $\mathbb {P}\left(G\right) = \mathbb {P}\left(T\right)$.

There are $n$ urns of which the $r$ th contains $r-1$ red balls and $n-r$ magenta balls. You pick an urn at random and remove two balls at random without replacement. Find the probability that:

Boys and girls, Example (1.4.3) revisited. Consider a family of two children in a population in which each child is equally likely to be male as female; each child has red hair with probability $r$; these characteristics are independent of each other and occur independently between children.

What is the probability that both children are boys given that the family contains at least one redhaired boy? Show that the probability that both are boys, given that one is a boy born on a Monday, is $13 / 27$.

Let $A$ and $B$ be independent events; show that $A^{\complement }, B$ are independent, and deduce that $A^{\complement }, B^{\complement }$ are independent.

We roll a die $n$ times. Let $A_{i j}$ be the event that the $i$ th and $j$ th rolls produce the same number. Show that the events $\left\{ A_{i j}: 1 \leq i < j \leq n\right\}$ are pairwise independent but not independent.

A fair coin is tossed repeatedly. Show that the following two statements are equivalent:

(a) the outcomes of different tosses are independent,

(b) for any given finite sequence of heads and tails, the chance of this sequence occurring in the first $m$ tosses is $2^{-m}$, where $m$ is the length of the sequence.

Let $\Omega = \left\{ 1,2, \ldots , p\right\}$ where $p$ is prime, $\mathcal{F}$ be the set of all subsets of $\Omega$, and $\mathbb {P}\left(A\right) = |A| / p$ for all $A \in \mathcal{F}$. Show that, if $A$ and $B$ are independent events, then at least one of $A$ and $B$ is either $\varnothing$ or $\Omega$.

Show that the conditional independence of $A$ and $B$ given $C$ neither implies, nor is implied by, the independence of $A$ and $B$. For which events $C$ is it the case that, for all $A$ and $B$, the events $A$ and $B$ are independent if and only if they are conditionally independent given $C$?

Safe or sorry? Some form of prophylaxis is said to be 90 per cent effective at prevention during one year's treatment. If the degrees of effectiveness in different years are independent, show that the treatment is more likely than not to fail within 7 years.

Jane has three children, each of which is equally likely to be a boy or a girl independently of the others. Define the events:

You flip three fair coins. At least two are alike, and it is an evens chance that the third is a head or a tail. Therefore $\mathbb {P}\left(\text{ all alike }\right) = \frac{1}{2}$. Do you agree?

Two fair dice are rolled. Show that the event that their sum is 7 is independent of the score shown by the first die.

Let $X$ and $Y$ be the scores on two fair dice taking values in the set $\left\{ 1,2, \ldots , 6\right\}$. Let $A_{1} = \left\{ X+Y = 9\right\} , A_{2} = \left\{ X \in \left\{ 1,2,3\right\} \right\}$, and $A_{3} = \left\{ X \in \left\{ 3,4,5\right\} \right\}$. Show that

Are these three events independent?

There are two roads from A to B and two roads from B to C. Each of the four roads is blocked by snow with probability $p$, independently of the others. Find the probability that there is an open road from A to B given that there is no open route from A to C.

If, in addition, there is a direct road from A to C, this road being blocked with probability $p$ independently of the others, find the required conditional probability.

Calculate the probability that a hand of 13 cards dealt from a normal shuffled pack of 52 contains exactly two kings and one ace. What is the probability that it contains exactly one ace given that it contains exactly two kings?

A symmetric random walk takes place on the integers $0,1,2, \ldots , N$ with absorbing barriers at 0 and $N$, starting at $k$. Show that the probability that the walk is never absorbed is zero.

The so-called 'sure thing principle' asserts that if you prefer $x$ to $y$ given $C$, and also prefer $x$ to $y$ given $C^{\mathrm{c}}$, then you surely prefer $x$ to $y$. Agreed?

A pack contains $m$ cards, labelled $1,2, \ldots , m$. The cards are dealt out in a random order, one by one. Given that the label of the $k$ th card dealt is the largest of the first $k$ cards dealt, what is the probability that it is also the largest in the pack?

A group of $2 b$ friends meet for a bridge soirée. There are $m$ men and $2 b-m$ women where $2 \leq m \leq b$. The group divides into $b$ teams of pairs, formed uniformly at random. What is the probability that no pair comprises 2 men?

A traditional fair die is thrown twice. What is the probability that:

A fair coin is thrown repeatedly. What is the probability that on the $n$th throw:

Let $\mathcal{F}$ and $\mathcal{G}$ be $\sigma$-fields of subsets of $\Omega$.

Describe the underlying probability spaces for the following experiments:

Show that the probability that exactly one of the events $A$ and $B$ occurs is

Prove that $\mathbb {P}\left(A \cup B \cup C\right) = 1-\mathbb {P}\left(A^{\complement } \mid B^{\complement } \cap C^{\complement }\right) \mathbb {P}\left(B^{\complement } \mid C^{\complement }\right) \mathbb {P}\left(C^{\complement }\right)$.

Let $\mathcal{F}$ be a $\sigma$-field of subsets of $\Omega$, and suppose $\mathbb {P}: \mathcal{F} \rightarrow [0,1]$ satisfies: (i) $\mathbb {P}\left(\Omega \right) = 1$, and (ii) $\mathbb {P}$ is additive, in that $\mathbb {P}\left(A \cup B\right) = \mathbb {P}\left(A\right)+\mathbb {P}\left(B\right)$ whenever $A \cap B = \varnothing$. Show that $\mathbb {P}\left(\varnothing \right) = 0$.

Suppose $(\Omega , \mathcal{F}, \mathbb {P})$ is a probability space and $B \in \mathcal{F}$ satisfies $\mathbb {P}\left(B\right) > 0$. Let $\mathbb {Q}: \mathcal{F} \rightarrow [0,1]$ be defined by $\mathbb {Q}(A) = \mathbb {P}\left(A \mid B\right)$. Show that $(\Omega , \mathcal{F}, \mathbb {Q})$ is a probability space. If $C \in \mathcal{F}$ and $\mathbb {Q}(C) > 0$, show that $\mathbb {Q}(A \mid C) = \mathbb {P}\left(A \mid B \cap C\right)$; discuss.

Let $B_{1}, B_{2}, \ldots$ be a partition of the sample space $\Omega$, each $B_{i}$ having positive probability, and show that

Prove Boole's inequalities:

Prove that

Let $A_{1}, A_{2}, \ldots , A_{n}$ be events, and let $N_{k}$ be the event that exactly $k$ of the $A_{i}$ occur. Prove the result sometimes referred to as Waring's theorem:

Use this result to find an expression for the probability that a purchase of six packets of Corn Flakes yields exactly three distinct busts (see Exercise (1.3.4)).

Prove Bayes's formula: if $A_{1}, A_{2}, \ldots , A_{n}$ is a partition of $\Omega$, each $A_{i}$ having positive probability, then

A random number $N$ of dice is thrown. Let $A_{i}$ be the event that $N = i$, and assume that $\mathbb {P}\left(A_{i}\right) = 2^{-i}, i \geq 1$. The sum of the scores is $S$. Find the probability that:

Let $A_{1}, A_{2}, \ldots$ be a sequence of events. Define

Clearly $C_{n} \subseteq A_{n} \subseteq B_{n}$. The sequences $\left\{ B_{n}\right\}$ and $\left\{ C_{n}\right\}$ are decreasing and increasing respectively with limits

The events $B$ and $C$ are denoted $\lim \sup_{n \rightarrow \infty } A_{n}$ and $\liminf_{n \rightarrow \infty } A_{n}$ respectively. Show that

In Problem (1.8.16) above, show that $B$ and $C$ are independent whenever $B_{n}$ and $C_{n}$ are independent for all $n$. Deduce that if this holds and furthermore $A_{n} \rightarrow A$, then $\mathbb {P}\left(A\right)$ equals either zero or one.

Show that the assumption that $\mathbb {P}$ is countably additive is equivalent to the assumption that $\mathbb {P}$ is continuous. That is to say, show that if a function $\mathbb {P}: \mathcal{F} \rightarrow [0,1]$ satisfies $\mathbb {P}\left(\varnothing \right) = 0, \mathbb {P}\left(\Omega \right) = 1$, and $\mathbb {P}\left(A \cup B\right) = \mathbb {P}\left(A\right)+\mathbb {P}\left(B\right)$ whenever $A, B \in \mathcal{F}$ and $A \cap B = \varnothing$, then $\mathbb {P}$ is countably additive (in the sense of satisfying Definition (1.3.1b)) if and only if $\mathbb {P}$ is continuous (in the sense of Lemma (1.3.5)).

Anne, Betty, Chloë, and Daisy were all friends at school. Subsequently each of the $\binom {4}{2} = 6$ subpairs meet up; at each of the six meetings the pair involved quarrel with some fixed probability $p$, or become firm friends with probability $1-p$. Quarrels take place independently of each other. In future, if any of the four hears a rumour, then she tells it to her firm friends only. If Anne hears a rumour, what is the probability that:

A biased coin is tossed repeatedly. Each time there is a probability $p$ of a head turning up. Let $p_{n}$ be the probability that an even number of heads has occurred after $n$ tosses (zero is an even number). Show that $p_{0} = 1$ and that $p_{n} = p\left(1-p_{n-1}\right)+(1-p) p_{n-1}$ if $n \geq 1$. Solve this difference equation.

A biased coin is tossed repeatedly. Find the probability that there is a run of $r$ heads in a row before there is a run of $s$ tails, where $r$ and $s$ are positive integers.

The 'ménages' problem poses the following question. Some consider it to be desirable that men and women alternate when seated at a circular table. If $n$ heterosexual couples are seated randomly according to this rule, show that the probability that nobody sits next to his or her partner is

You may find it useful to show first that the number of ways of selecting $k$ non-overlapping pairs of adjacent seats is $\binom {2 n-k}{k} 2 n(2 n-k)^{-1}$.

An urn contains $b$ blue balls and $r$ red balls. They are removed at random and not replaced. Show that the probability that the first red ball drawn is the $(k+1)$ th ball drawn equals $\binom {r+b-k-1}{r-1} /\binom {r+b}{b}$. Find the probability that the last ball drawn is red.

An urn contains $a$ azure balls and $c$ carmine balls, where $a c \neq 0$. Balls are removed at random and discarded until the first time that a ball ($B$, say) is removed having a different colour from its predecessor. The ball $B$ is now replaced and the procedure restarted. This process continues until the last ball is drawn from the urn. Show that this last ball is equally likely to be azure or carmine.

A pack of four cards contains one spade, one club, and the two red aces. You deal two cards faces downwards at random in front of a truthful friend. She inspects them and tells you that one of them is the ace of hearts. What is the chance that the other card is the ace of diamonds? Perhaps $\frac{1}{3}$?

Suppose that your friend's protocol was:

(i) with no red ace, say "no red ace",

(ii) with the ace of hearts, say "ace of hearts",

(iii) with the ace of diamonds but not the ace of hearts, say "ace of diamonds".

Four witnesses, A, B, C, and D, at a trial each speak the truth with probability $\frac{1}{3}$ independently of each other. In their testimonies, $A$ claimed that $B$ denied that $C$ declared that D lied. What is the (conditional) probability that D told the truth?

10 per cent of the surface of a sphere is coloured blue, the rest is red. Show that, irrespective of the manner in which the colours are distributed, it is possible to inscribe a cube in $S$ with all its vertices red.

The event $A$ is said to be repelled by the event $B$ if $\mathbb {P}\left(A \mid B\right) < \mathbb {P}\left(A\right)$, and to be attracted by $B$ if $\mathbb {P}\left(A \mid B\right) > \mathbb {P}\left(A\right)$. Show that if $B$ attracts $A$, then $A$ attracts $B$, and $B^{\complement }$ repels $A$. If $A$ attracts $B$, and $B$ attracts $C$, does $A$ attract $C$?

At a lecture, there a $m$ students born on independent days in 2007.

You choose $r$ of the first $n$ positive integers, and a lottery chooses a random subset $L$ of the same size. What is the probability that:

During a game of bridge, you are dealt at random a hand of thirteen cards. With an obvious notation, show that $\mathbb {P}\left(4 \mathrm{~ S}, 3 \mathrm{H}, 3 \mathrm{D}, 3 \mathrm{C}\right) \simeq 0.026$ and $\mathbb {P}\left(4 \mathrm{~ S}, 4 \mathrm{H}, 3 \mathrm{D}, 2 \mathrm{C}\right) \simeq 0.018$. However if suits are not specified, so numbers denote the shape of your hand, show that $\mathbb {P}\left(4,3,3,3\right) \simeq 0.11$ and $\mathbb {P}\left(4,4,3,2\right) \simeq 0.22$.

During a game of poker, you are dealt a five-card hand at random. With the convention that aces may count high or low, show that:

There are five dice each displaying $9,10, \mathrm{~ J}, \mathrm{Q}, \mathrm{K}, \mathrm{A}$. Show that, when rolled:

You are lost in the National Park of Bandrika. Tourists comprise two-thirds of the visitors to the park, and give a correct answer to requests for directions with probability $\frac{3}{4}$. (Answers to repeated questions are independent, even if the question and the person are the same.) If you ask a Bandrikan for directions, the answer is always false.

Tom is in the same position as you were in the previous problem, but he has reason to believe that, with probability $\epsilon$, East is the correct answer. Show that:

Show that

Show that

The $n$ passengers for a Bell-Air flight in an airplane with $n$ seats have been told their seat numbers. They get on the plane one by one. The first person sits in the wrong seat. Subsequent passengers sit in their assigned seats whenever they find them available, or otherwise in a randomly chosen empty seat. What is the probability that the last passenger finds his or her assigned seat to be free?

What is the answer if the first person sits in a seat chosen uniformly at random from the $n$ available?

A number $n$ of spaceships land independently and uniformly at random on the surface of planet Mongo. Each ship controls the hemisphere of which it is the centre. Show that the probability that every point on Mongo is controlled by at least one ship is $1-2^{-n}\left(n^{2}-n+2\right)$.

Let $X$ be uniformly distributed on $\left\{ 1,2, \ldots , n-1\right\}$, where $n \geq 2$. Given $X$, a team of size $X$ is selected at random from a pool of $n$ players (including you), each such subset of size $X$ being equally likely. Call the selected team A, and the remainder team B.

Alice and Bob flip a fair coin in turn. A wins if she gets a head, provided her preceding flip was a tail; B wins if he gets a tail, provided his preceding flip was a head. Let $n \geq 3$. Show that the probability the game ends on the $n$th flip is $(n+1)(n-1) / 2^{n+2}$ if $n$ is odd, and $(n+2)(n-2) / 2^{n+2}$ if even.

What is the probability that A wins the game?

A coin comes up heads with probability $p \in (0,1)$. Let $k \geq 1$, and let $\rho_{m}$ be the probability that, in $m( \geq 1)$ coin flips, the longest run of consecutive heads has length strictly less than $k$. Show that

and find $\rho_{m}$ when $k = 2$.