The set \(S\) is the set of all integers from 1 to \(n\). The set \(T\) is the set of all distinct subsets of \(S\), including the empty set \(\emptyset\) and \(S\) itself. Show that \(T\) contains exactly \(2^n\) sets.
The sets \(A_1, A_2, \ldots, A_m\), which are not necessarily distinct, are chosen randomly and independently from \(T\), and for each \(k\) \((1 \leq k \leq m)\), the set \(A_k\) is equally likely to be any of the sets in \(T\).
- Write down the value of \(P(1 \in A_1)\).
- By considering each integer separately, show that \(P(A_1 \cap A_2 = \emptyset) = \left(\frac{3}{4}\right)^n\).
Find \(P(A_1 \cap A_2 \cap A_3 = \emptyset)\) and \(P(A_1 \cap A_2 \cap \cdots \cap A_m = \emptyset)\).
- Find \(P(A_1 \subseteq A_2)\), \(P(A_1 \subseteq A_2 \subseteq A_3)\) and \(P(A_1 \subseteq A_2 \subseteq \cdots \subseteq A_m)\).
Show Solution
For every element in \(S\) we can choose whether or not it appears in a subset of \(S\), therefore there are \(2^n\) choices so \(2^n\) distinct subsets.
- \(\mathbb{P}(1 \in A_1) = \frac12\) (since \(1\) is in exactly half the subsets)
- \(\,\) \begin{align*}
&& \mathbb{P}(A_1 \cap A_2 = \emptyset) &= \mathbb{P}(i \not \in (A_1 \cap A_2) \forall i) \\
&&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1 \cap A_2) \right) \\
&&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1)\mathbb{P}(i \in \cap A_2) \right) \\
&&&= \prod_{i=1}^n \left ( 1-\frac12 \cdot \frac12\right) \\
&&&= \left (\frac34 \right)^n
\end{align*}
- \(\,\) \begin{align*}
&& \mathbb{P}(A_1 \cap A_2 \cap A_3 = \emptyset) &= \mathbb{P}(i \not \in (A_1 \cap A_2 \cap A_3) \forall i) \\
&&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1 \cap A_2 \cap A_3) \right) \\
&&&= \prod_{i=1}^n \left ( 1-\mathbb{P}(i \in A_1)\mathbb{P}(i \in \cap A_2))\mathbb{P}(i \in \cap A_3) \right) \\
&&&= \prod_{i=1}^n \left ( 1-\frac12 \cdot \frac12 \cdot \frac12\right) \\
&&&= \left (\frac78 \right)^n
\end{align*}
Similarly, \(\displaystyle \mathbb{P}(A_1 \cap A_2 \cap \cdots \cap A_m = \emptyset) = \left ( \frac{2^m-1}{2^m} \right)^n\)
- \(\,\) \begin{align*}
&& \mathbb{P}(A_1 \subseteq A_2) &= \mathbb{P}(A_1 \cap A_2^c = \emptyset) \\
&&&= \left (\frac34 \right)^n \\
\\
&& \mathbb{P}(A_1 \subseteq A_2 \subseteq A_3) &= \prod_{i=1}^n \mathbb{P}(\text{once }i\text{ appears it keeps appearing}) \\
&&&= \prod_{i=1}^n \frac{\#\{(0,0,0), (0,0,1), (0,1,1), (1,1,1) \}}{2^3} \\
&&&= \prod_{i=1}^n \frac{4}{8} \\
&&&= \frac{1}{2^n} \\
\\
&& \mathbb{P}(A_1 \subseteq A_2 \subseteq \cdots \subseteq A_m) &= \prod_{i=1}^n \frac{m+1}{2^m} \\
&&&= \left ( \frac{m+1}{2^m} \right)^n
\end{align*}
Given that \(0 < r < n\) and \(r\) is much smaller than \(n\), show that \(\dfrac {n-r}n \approx \e^{-r/n}\). There are \(k\) guests at a party. Assuming that there are exactly 365 days in the year, and that the birthday of any guest is equally likely to fall on any of these days, show that the probability that there are at least two guests with the same birthday is approximately \(1-\e^{-k(k-1)/730}\). Using the approximation \( \frac{253}{365} \approx \ln 2\), find the smallest value of \(k\) such that the probability that at least two guests share the same birthday is at least \(\frac12\). How many guests must there be at the party for the probability that at least one guest has the same birthday as the host to be at least \(\frac12\)?
Show Solution
Given \(0 < r \ll n\), then \(\frac{r}{n}\) is small and so, \(e^x \approx 1+x\), therefore: \(\displaystyle e^{-r/n} \approx 1 - \frac{r}{n} = \frac{n-r}{n}\).
Line everyone in the room up in some order. The first person is always going to have a birthday we haven't seen before. The probability the second person has a new birthday is \(\displaystyle 1 - \frac{1}{365}\) since they can't be born on the same day as the first person. The third person has a \(\displaystyle 1 - \frac{2}{365}\) probability of having a birthday we've not seen before, since they can't share a birthday with either of the first two people. Similarly the \(k\)th person has a \(\displaystyle 1 - \frac{k-1}{365}\) chance of having a unique birthday.
\begin{align*}
\prod_{i=1}^k \mathbb{P}(\text{the } i \text{th person has a new birthday}) &= \prod_{i=1}^k \l 1 - \frac{i-1}{365}\r \\
&\approx \prod_{i=1}^k \exp \l -\frac{i-1}{365}\r \\
&= \exp\l - \sum_{i=1}^k\frac{i-1}{365}\r \\
&= \exp\l - \frac{k(k-1)}{2\cdot365}\r \\
&= e^{-k(k-1)/730}
\end{align*}
But this the probability no-one shares a birthday, so the answer we are looking for is \(1-\) this, ie \(1 - e^{-k(k-1)/730}\)
Suppose \(1 - e^{-k(k-1)/730} = \frac12\), then
\begin{align*}
&& 1 - e^{-k(k-1)/730} &= \frac12 \\
\Rightarrow && e^{-k(k-1)/730} &= \frac12 \\
\Rightarrow && -k(k-1)/730 &= -\ln 2 \\
\Rightarrow && k(k-1)/730 &\approx \frac{253}{365} \\
\Rightarrow && k(k-1) &\approx 506
\end{align*}
Therefore since \(22 \cdot 23 = 506\), we should expect the number to be approximately \(23\). Since \(e^{-r/n} > \frac{n-r}{n}\) we should expect this to be an overestimate, therefore \(23\) should suffice.
Suppose that a solution \((X,Y,Z)\) of the equation
\[X+Y+Z=20,\]
with \(X\), \(Y\) and \(Z\) non-negative integers, is chosen at random (each such solution being equally likely).
Are \(X\) and \(Y\) independent? Justify your answer.
Show that the probability that \(X\) is divisible by \(5\) is \(5/21\).
What is the probability that \(XYZ\) is divisible by 5?
Show Solution
They are not independent:
\begin{align*}
&& \mathbb{P}(X = 20 \,\, \cap Y = 20) = 0 \\
&& \mathbb{P}(X = 20 )\mathbb{P}(Y = 20) \neq 0 \\
\end{align*}
\begin{align*}
X = 0: && 21 \text{ solutions} \\
X = 5: && 16 \text{ solutions} \\
X = 10: && 11 \text{ solutions} \\
X = 15: && 6 \text{ solutions} \\
X = 20: && 1 \text{ solutions} \\
5 \mid X: && 55 \text{ solutions} \\
\\
&& \binom{20+2}{2} = 11 \cdot 21 \text{ total solutions} \\
\Rightarrow && \mathbb{P}(5 \mid X) = \frac{55}{11 \cdot 21} = \frac{5}{21}
\end{align*}
\begin{align*}
\mathbb{P}(5 \mid XYZ) &= 3\cdot \mathbb{P}(5 \mid X) - 2\mathbb{P}(5 \mid X, Y, Z) \\
&= \frac{3 \cdot 55 - 2 \cdot \binom{4+2}{2}}{11 \cdot 21} = \frac{35}{77}
\end{align*}
The mountain villages \(A,B,C\) and \(D\) lie at the vertices of a
tetrahedron, and each pair of villages is joined by a road. After
a snowfall the probability that any road is blocked is \(p\), and
is independent of the conditions of any other road. The
probability that, after a snowfall,
it is possible to travel from any village to
any other village by some route is \(P\). Show that
$$
P =1- p^2(6p^3-12p^2+3p+4).
$$
%In the case \(p={1\over 3}\) show that this probability is \({208 \over 243}\).
In certain forms of Tennis two players \(A\) and \(B\) serve alternate
games. Player \(A\) has probability \(p\low_{A}\) of winning a game in which
she serves and \(p\low_{B}\) of winning a game in which player \(B\) serves.
Player \(B\) has probability \(q\low_{B}=1-p\low_{B}\) of winning a game in
which she serves and probability \(q\low_{A}=1-p\low_{A}\) of winning a game
in which player \(A\) serves. In Shortened Tennis the first player
to lead by 2 games wins the match. Find the probability \(P_{\text{short}}\)
that \(A\) wins a Shortened Tennis match in which she serves first
and show that it is the same as if \(B\) serves first.
In Standard Tennis the first player to lead by 2 or more games after
4 or more games have been played wins the match. Show that the probability
that the match is decided in 4 games is
\[
p^{2}_Ap_{B}^{2}+q_{A}^{2}q_{B}^{2}+2(p\low_{A}p\low_{B}+q\low_{A}q\low_{B})(p\low_{A}q\low_{B}+q\low_{A}p\low_{B}).
\]
If \(p\low_{A}=p\low_{B}=p\) and \(q\low_{A}=q\low_{B}=q,\) find the probability \(P_{\text{stan}}\)
that \(A\) wins a Standard Tennis match in which she serves first.
Show that
\[
P_{\text{stan}}-P_{\text{short}}=\frac{p^{2}q^{2}(p-q)}{p^{2}+q^{2}}.
\]
The four towns \(A,B,C\) and \(D\) are linked by roads \(AB,AC,CB,BD\)
and \(CD.\) The probability that any one road will be blocked by snow
on the 1st of January is \(p\), independent of what happens to any
other \([0 < p < 1]\). Show that the probability that any open route from
\(A\) to \(D\) is \(ABCD\) is
\[
p^{2}(1-p)^{3}.
\]
In order to increase the probability that it is possible to get from
\(A\) to \(D\) by a sequence of unblocked roads the government proposes
either to snow-proof the road \(AB\) (so that it can never be blocked)
or to snow-proof the road \(CB.\) Because of the high cost it cannot
do both. Which road should it choose (or are both choices equally
advantageous)?
In fact, \(p=\frac{1}{10}\) and the government decides that it is only
worth going ahead if the present probability of \(A\) being cut off
from \(D\) is greater than \(\frac{1}{100}.\) Will it go ahead?
A point moves in unit steps on the \(x\)-axis starting from the origin. At each step the point is equally likely to move in the positive or negative direction. The probability that after \(s\) steps it is at one of the points \(x=2,x=3,x=4\) or \(x=5\) is \(\mathrm{P}(s).\) Show that \(\mathrm{P}(5)=\frac{3}{16},\) \(\mathrm{P}(6)=\frac{21}{64}\) and
\[
\mathrm{P}(2k)=\binom{2k+1}{k-1}\left(\frac{1}{2}\right)^{2k}
\]
where \(k\) is a positive integer. Find a similar expression for \(\mathrm{P}(2k+1).\)
Determine the values of \(s\) for which \(\mathrm{P}(s)\) has its greatest value.
Show Solution
After \(5\) steps we can get to:
\begin{array}{c|c}
x & \text{ways} \\ \hline
5 & 1 \text { - go positive every time}\\
4 & 0 \\
3 & \binom{5}{1} \text { - go positive every time but 1} \\
2 &0 \\ \hline
& 6
\end{array}
Therefore there are \(\frac{6}{2^5} = \frac{3}{16}\) ways to get to \(\{2,3,4,5\}\)
After \(6\) steps we can get to:
\begin{array}{c|c}
x & \text{ways} \\ \hline
5 & 0 \\
4 & \binom{6}{1} \text { - go positive every time but 1}\\
3 & 0 \\
2 & \binom{6}{2} - \text{ - go positive every time but 2} \\ \hline
& 21
\end{array}
Therefore there are \(\frac{21}{2^6} = \frac{21}{64}\) ways to get to \(\{2,3,4,5\}\)
After \(2k\) steps we can reach \(2\) or \(4\).
To get to \(2\) we must take \(k+1\) positive steps and \(k-1\) negative steps, ie \(\binom{2k}{k-1}\).
To get to \(4\) we must take \(k+2\) positive steps and \(k-2\) negative steps, ie \(\binom{2k}{k-2}\)
Therefore there are \(\binom{2k+1}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k}} \binom{2k+1}{k-1}\)
After \(2k+1\) steps we can reach \(3\) or \(5\).
To get to \(3\) we must take \(k+2\) positive steps and \(k-1\) negative steps, ie \(\binom{2k+1}{k-1}\).
To get to \(5\) we must take \(k+3\) positive steps and \(k-2\) negative steps, ie \(\binom{2k+1}{k-2}\)
Therefore there are \(\binom{2k+2}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k+1}} \binom{2k+2}{k-1}\)
To find the maximum of \(P(s)\) notice that
\begin{align*}
&& \frac{P(2k+1)}{P(2k)} &= \frac12 \frac{\binom{2k+2}{k-1}}{\binom{2k+1}{k-1}} \\
&&&= \frac12 \frac{(2k+2)!(k-1)!(k+2)!}{(2k+1)!(k-1)!(k+3)!} \\
&&&= \frac12 \frac{2k+2}{k+3} = \frac{k+1}{k+3} < 1
\end{align*}
So we should only look at the even terms.
\begin{align*}
&& \frac{P(2k+2)}{P(2k)} &= \frac14 \frac{\binom{2k+3}{k}}{\binom{2k+1}{k-1}} \\
&&&= \frac14 \frac{(2k+3)!(k-1)!(k+2)!}{(2k+1)!k!(k+3)!} \\
&&&= \frac14 \frac{(2k+3)(2k+2)}{k(k+3)} \\
&&&= \frac{(2k+3)(k+1)}{2k(k+3)} \geq 1 \\
\Leftrightarrow && (2k+3)(k+1) &\geq 2k(k+3) \\
\Leftrightarrow && 2k^2+5k+3 &\geq 2k^2+6k \\
\Leftrightarrow && 3 &\geq k \\
\end{align*}
Therefore the maximum is when \(s = 2\cdot 3\) or \(s = 2\cdot 4\) which we computed earlier to be \(\frac{21}{64}\)