Problems

Filters
Clear Filters

11 problems found

2019 Paper 3 Q12
D: 1500.0 B: 1485.6
probability independent events combinatorics subsets counting power set intersection of sets inclusion

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\).

  1. Write down the value of \(P(1 \in A_1)\).
  2. 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)\).
  3. 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)\).

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.

  1. \(\mathbb{P}(1 \in A_1) = \frac12\) (since \(1\) is in exactly half the subsets)
  2. \(\,\) \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*}
  3. \(\,\) \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\)
  4. \(\,\) \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*}

View
2008 Paper 2 Q12
D: 1600.0 B: 1500.0
probability tree diagrams expectation independent events conditional probability quadratic equation

In the High Court of Farnia, the outcome of each case is determined by three judges: the ass, the beaver and the centaur. Each judge decides its verdict independently. Being simple creatures, they make their decisions entirely at random. Past verdicts show that the ass gives a guilty verdict with probability \(p\), the beaver gives a guilty verdict with probability \(p/3\) and the centaur gives a guilty verdict with probability \(p^2\). Let \(X\) be the number of guilty verdicts given by the three judges in a case. Given that \(\E(X)= 4/3\), find the value of \(p\). The probability that a defendant brought to trial is guilty is \(t\). The King pronounces that the defendant is guilty if at least two of the judges give a guilty verdict; otherwise, he pronounces the defendant not guilty. Find the value of \(t\) such that the probability that the King pronounces correctly is \(1/2\).

Solution: \begin{align*} && \mathbb{E}(X) &= p + \frac{p}{3} + p^2 = \frac43p+p^2 \\ \Rightarrow && \frac43 &= \frac43p+p^2 \\ \Rightarrow && 0 &= 3p^2+4p-4 \\ &&&= (3p-2)(p+2) \\ \Rightarrow && p &= \frac23, -2 \end{align*} Since \(p \in [0,1]\) we must have \(p = \frac23\). \begin{align*} && \mathbb{P}(\text{correct verdict}) &= t p+ (1-t) (1-p) \\ &&&= t(2p-1)+(1-p)\\ \Rightarrow && \frac12 &= t(2p-1)+(1-p) \\ \Rightarrow && t &= \frac{\frac12-(1-p)}{2p-1} \\ &&&= \frac{2p-1}{2(2p-1)} = \frac12 \end{align*} (so it doesn't depend at all on what the judges are doing, the only way to be fair is if the trials happen at random!)

View
2007 Paper 2 Q13
D: 1600.0 B: 1669.0
probability birthday problem independent events exponential approximation combinatorics inequality logarithm

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\)?

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.

View
2003 Paper 1 Q14
D: 1500.0 B: 1475.2
probability Poisson distribution expectation truncation conditional expectation independent events

Jane goes out with any of her friends who call, except that she never goes out with more than two friends in a day. The number of her friends who call on a given day follows a Poisson distribution with parameter \(2\). Show that the average number of friends she sees in a day is~\(2-4\e^{-2}\,\). Now Jane has a new friend who calls on any given day with probability \(p\). Her old friends call as before, independently of the new friend. She never goes out with more than two friends in a day. Find the average number of friends she now sees in a day.

View
1998 Paper 1 Q12
D: 1484.0 B: 1606.9
probability independent events combinatorics divisibility integer solutions stars and bars complementary counting

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?

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*}

View
1998 Paper 3 Q12
D: 1700.0 B: 1482.8
probability independent events complementary counting graph theory tetrahedron connectivity inclusion-exclusion polynomial

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}\).

View
1997 Paper 2 Q12
D: 1600.0 B: 1500.1
probability binomial expansion geometric distribution coin flip independent events expected value series summation

The game of Cambridge Whispers starts with the first participant Albert flipping an un-biased coin and whispering to his neighbour Bertha whether it fell `heads' or `tails'. Bertha then whispers this information to her neighbour, and so on. The game ends when the final player Zebedee whispers to Albert and the game is won, by all players, if what Albert hears is correct. The acoustics are such that the listeners have, independently at each stage, only a probability of 2/3 of hearing correctly what is said. Find the probability that the game is won when there are just three players. By considering the binomial expansion of \((a+b)^n+(a-b)^n\), or otherwise, find a concise expression for the probability \(P\) that the game is won when is it played by \(n\) players each having a probability \(p\) of hearing correctly. % Show in particular that, if \(n\) is even, %\(P(n,1/10) = P(n,9/10)\).% How do you explain this apparent anomaly? To avoid the trauma of a lost game, the rules are now modified to require Albert to whisper to Bertha what he hears from Zebedee, and so keep the game going, if what he hears from Zebedee is not correct. Find the expected total number of times that Albert whispers to Bertha before the modified game ends. \noindent [You may use without proof the fact that \(\sum_1^\infty kx^{k-1}=(1-x)^{-2}\) for \(\vert x\vert<1\).]

View
1994 Paper 3 Q12
D: 1700.0 B: 1473.3
probability independent events geometric series tennis conditional probability algebraic manipulation infinite series

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}}. \]

View
1993 Paper 1 Q15
D: 1500.0 B: 1532.0
conditional probability Bayes' theorem repeated evidence independent events truth-teller and liar probability update

Captain Spalding is on a visit to the idyllic island of Gambriced. The population of the island consists of the two lost tribes of Frodox and the latest census shows that \(11/16\) of the population belong to the Ascii who tell the truth \(3/4\) of the time and \(5/16\) to the Biscii who always lie. The answers of an Ascii to each question (even if it is the same as one before) are independent. Show that the probability that an Ascii gives the same answer twice in succession to the same question is \(5/8\). Show that the probability that an Ascii gives the same answer twice is telling the truth is \(9/10.\) Captain Spalding addresses one of the natives as follows. \hspace{1.5em} \textsl{Spalding: }My good man, I'm afraid I'm lost. Should I go left or right to reach the nearest town?\nolinebreak \hspace{1.5em}\textsl{Native: }Left. \hspace{1.5em}\textsl{Spalding: }I am a little deaf. Should I go left or right to reach the nearest town? \hspace{1.5em}\textsl{Native (patiently): }Left. Show that, on the basis of this conversation, Captain Spalding should go left to try and reach the nearest town and that there is a probability \(99/190\) that this is the correct direction. The conversation resumes as follows. \hspace{1.5em}\textsl{Spalding: }I'm sorry I didn't quite hear that. Should I go left or right to reach the nearest town? \hspace{1.5em}\textsl{Native (loudly and clearly): }Left. Shouls Captain Spalding go left or right and why? Show that if he follows your advice the probability that this is the correct direction is \(331/628\).

View
1992 Paper 1 Q16
D: 1500.0 B: 1504.2
probability independent events graph theory network reliability road network complementary counting optimisation

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?

View
1987 Paper 2 Q16
D: 1500.0 B: 1500.0
conditional probability Bayes' theorem independent events prior probability truth-telling probability revision

My two friends, who shall remain nameless, but whom I shall refer to as \(P\) and \(Q\), both told me this afternoon that there is a body in my fridge. I'm not sure what to make of this, because \(P\) tells the truth with a probability of only \(p\), while \(Q\) (independently) tells the truth with probability \(q\). I haven't looked in the fridge for some time, so if you had asked me this morning, I would have said that there was just as likely to be a body in it as not. Clearly, in view of what \(P\) and \(Q\) told me, I must revise this estimate. Explain carefully why my new estimate of the probability of there being a body in the fridge should be \[ \frac{pq}{1-p-q+2pq}. \] I have now been to look in the fridge, and there is indeed a body in it; perhaps more than one. It seems to me that only my enemy \(A\), or my enemy \(B\), or (with a bit of luck) both \(A\) and \(B\) could be in my fridge, and this morning I would have judged these three possibilities to be equally likely. But tonight I asked \(P\) and \(Q\) separately whether or not \(A\) was in the fridge, and they each said that he was. What should be my new estimate of the probability that both \(A\) and \(B\) are in my fridge? Of course, I tell the truth always.

Solution: \begin{align*} \mathbb{P}(\text{body in fridge} | \text{P and Q say so}) &= \frac{\mathbb{P}(\text{body in fridge and P and Q say so})}{\mathbb{P}(\text{P and Q say so})} \\ &= \frac{\frac12 pq}{\mathbb{P}(\text{body in fridge and P and Q say so})+\mathbb{P}(\text{no body in fridge and P and Q say so})} \\ &= \frac{\frac12 pq}{\frac12 pq + \frac12(1-p)(1-q)} \\ &= \frac{pq}{pq + 1-p-q+pq} \\ &= \frac{pq}{1-p-q+2pq} \end{align*} \begin{align*} \mathbb{P}(\text{A and B in fridge} | \text{P and Q say A is in fridge}) &= \frac{\mathbb{P}(\text{A and B in fridge and P and Q say A is in fridge}) }{\mathbb{P}( \text{P and Q say A is in fridge}) } \\ &= \frac{\frac13pq}{\frac13pq+\frac13pq+\frac13(1-p)(1-q)} \\ &= \frac{pq}{1-p-q+3pq} \end{align*}

View