Problems

---

Solution:

1. The first pirate will have some gold coins as long as the very first coin drawn is a gold coin, ie \(\frac{n}{n+2}\).
2. The probability the second pirate will have some gold coins is the probability the two lead coins are separate. There are \((n+2)!\) ways to arrange the coins, and there are \((n+1)! \cdot 2\) ways to arrange the coins where they are together, therefore the probability is: \[ 1 - \frac{2(n+1)!}{(n+2)!} = 1 - \frac{2}{n+2} = \frac{n}{n+2} \]
3. For all three pirates to have some gold coins we need the lead coins to be separate and not first or last. If we line up all \(n\) gold coins, there are \(n-1\) gaps between them we could place the \(2\) lead coins in, therefore \(\binom{n-1}{2}\) ways to place the lead coins with the restriction. Without the restriction there are \(\binom{n+2}{2}\) ways to choose where to put the coins, therefore \begin{align*} && P &= \frac{\binom{n-1}{2}}{\binom{n+2}{2}} \\ &&&= \frac{(n-1)(n-2)}{(n+2)(n+1)} \end{align*} [Notice this is clearly \(0\) if there are only \(1\) or \(2\) gold coins]

---

Solution:

When we add everything in \(A\),\(B\), \(C\) we overcount the overlaps. When we remove the overlaps we remove the centre section too many times, so we have to add it back on in the end. Let \(X_i\) be the probability that the \(i\)th pudding contains a sixpence. \begin{align*} && \mathbb{P}(X_1^c \cup X_2^c \cup X_3^c) &=\mathbb{P}(X_1^c \cap X_2^c \cap X_3^c) + \mathbb{P}(X_1^c)+\mathbb{P}(X_2^c)-\mathbb{P}(X_3^c)+\\ &&&\quad\quad-\mathbb{P}(X_1^c \cap X_2^c )-\mathbb{P}( X_2^c \cap X_3^c)-\mathbb{P}(X_1^c \cap X_3^c) \\ &&&= 0 + (\tfrac23)^r+ (\tfrac23)^r+ (\tfrac23)^r + \\ &&&\quad\quad - (\tfrac13)^r- (\tfrac13)^r- (\tfrac13)^r \\ &&&= \frac{3\cdot2^r-3}{3^{r}} \\ \Rightarrow && \mathbb{P}(\text{all contain a sixpence}) &= 1 - \frac{3\cdot2^r-3}{3^{r}} \\ &&&= \frac{3^r-3\cdot2^r+3}{3^r} \end{align*} When \(r = 5\) we have \(\frac{3 \cdot 32-3}{3^5} = \frac{31}{81} > \frac13\) When \(r = 6\) we have \(\frac{3 \cdot 64-3}{3^6} = \frac{7}{27} < \frac13\) Therefore, the chef must stir in at least \(6\). \begin{align*} && \mathbb{P}(\text{two in each}|\text{at least 1 in each}) &= \frac{ \mathbb{P}(\text{two in each} \cap \text{at least 1 in each}) }{ \mathbb{P}(\text{at least 1 in each}) } \\ &&&= \frac{ \mathbb{P}(\text{two in each}) }{ \mathbb{P}(\text{at least 1 in each}) } \\ &&&= \frac{90/3^6}{20/27} \\ &&&= \frac{1/3}{2} = \frac16 \end{align*}

---

Solution: There are \(m!\) different ways of assigning the shirts, and in \((m-1)!\) of them player \(1\) gets their own shirt, ie \(\mathbb{E}(C_1) = \mathbb{P}(\text{player }1\text{ gets own shirt}) = \frac{(m-1)!}{m!} = \frac{1}{m}\). \(\var(C_1) = \mathbb{E}(C_1^2) - [\mathbb{E}(C_1)]^2 = \frac{1}{m} - \frac{1}{m^2} = \frac{m-1}{m^2}\). If we have two players, there are \((m-2)!\) ways they both get their own shirts, therefore \(\textrm{Cov}(C_1,C_2) = \mathbb{E}(C_1C_2) - \mathbb{E}(C_1)\mathbb{E}(C_2) = \frac{(m-2)!}{m!} - \frac{1}{m^2} = \frac{1}{m(m-1)} - \frac{1}{m^2} = \frac{m-m+1}{m^2(m-1)} = \frac{1}{m^2(m-1)}\). \begin{align*} \mathbb{E}(N) &= \mathbb{E}(C_1 + C_2 + \cdots + C_m) \\ &= \mathbb{E}(C_1) + \mathbb{E}(C_2) + \cdots + \mathbb{E}(C_m) \\ &= \frac{1}{m} + \frac{1}{m} +\cdots+ \frac1m \\ &= 1 \\ \\ \var(N) &= \sum_{r=1}^m \var(C_r) + 2\sum_{r=1}^{m-1} \sum_{s=2}^{m} \textrm{Cov}(C_r,C_s) \\ &= m \frac{m-1}{m^2} + 2 \frac{m(m-1)}{2}\frac{1}{m^2(m-1)} \\ &=\frac{m-1}{m} + \frac{1}{m} \\ &= 1 \end{align*} If we were to take a normal approximation, we would want to take \(N(1,1)\), but this would say things like \(-1\) is as likely as \(3\) shirts being correct, which is clearly a bad model. A Poisson is much more likely to be a sensible model as they have the same mean and variance as the parameter, and if \(m\) is large, the covariance between shirts is going to be very small, so it will appear similar to random events occurring. We can have \begin{align*} BADC \\ BCDA \\ BDAC \\ CADB \\ CDAB\\ CDBA \\ DABC\\ DCAB \\ DCBA \end{align*} Ie \(\frac{9}{24}\) ways to have no player wearing their own shirt with \(4\) players. \(Po(1)\) would say this probability is \(e^{-1}\), giving a relative error of: \begin{align*} \frac{e^{-1}-\frac{9}{24}}{\frac9{24}} &\approx \frac{\frac{100}{272} - \frac{9}{24}}{\frac9{24}} \\ &= -\frac{1}{51} \\ &\approx -2\% \end{align*}

---

Solution:

1. This is the same as the sum of the probability that they all drop out in the \(k\)th round for all values of \(k\), ie \begin{align*} \mathbb{P}(\text{all drop in same round}) &= \sum_{k=0}^\infty \mathbb{P}(\text{all drop out in the }k+1\text{th round}) \\ &= \sum_{k=0}^{\infty}(p^k(1-p))^3 \\ &= (1-p)^3 \sum_{k=0}^{\infty}p^{3k} \\ &= \frac{(1-p)^3}{1-p^3} \\ &= \frac{1+3p(1-p)(p-(1-p))-p^3}{1-p^3} \\ &= \frac{1-p^3-3p(1-p)(1-2p)}{1-p^3} \end{align*}
2. There are \(3\) ways to choose the person who drops out earlier, and then they can drop out in round \(0, 1, \cdots r-1\) \begin{align*} \mathbb{P}(\text{exactly two drop out in round }r\text{ and one before}) &= 3\sum_{k=0}^{r-2} (p^{r-1}(1-p))^2p^k(1-p) \\ &= 3p^{2r-2}(1-p)^3 \sum_{k=0}^{r-2}p^k \\ &= 3p^{2r-2}(1-p)^3 \frac{1-p^{r-1}}{1-p} \\ &= 3p^{2r-2}(1-p)^2(1-p^{r-1}) \end{align*}
3. The probability exactly \(2\) finish after the third \begin{align*} \mathbb{P}(\text{exactly two drop out after third}) &= \sum_{r=2}^{\infty}\mathbb{P}(\text{exactly two drop out in round }r\text{ and one before}) \\ &= \sum_{r=2}^{\infty}3p^{2r-2}(1-p)^2(1-p^{r-1}) \\ &= 3(1-p)^2p^{-2}\sum_{r=2}^{\infty}(p^{2r}-p^{3r-1}) \\ &= 3(1-p)^2p^{-2} \left( \frac{p^4}{1-p^2} - \frac{p^5}{1-p^3} \right) \\ &= \frac{3(1-p)^2(p^2(1-p^3)-p^3(1-p^2))}{(1-p^2)(1-p^3)}\\ &= \frac{3(1-p)^3p^2}{(1-p^2)(1-p^3)}\\ \end{align*} Therefore the probability the grand prize is not awarded is \begin{align*} P &= 1 - \frac{(1-p)^3}{1-p^3} - \frac{3(1-p)^3p^2}{(1-p^2)(1-p^3)} \\ &= \frac{(1-p^3)(1-p^2) - (1-p)^3(1-p^2)-3(1-p)^3p^2}{(1-p^2)(1-p^3)} \\ &= \frac{(1-p^3)(1-p^2) - (1-p)^3(1+2p^2)}{(1-p^2)(1-p^3)} \\ \end{align*}

---

Solution:

1. Since the second draw is independently of the first draw \(\mathbb{P}(F=r, S=s) = \mathbb{P}(F=r)\mathbb{P}(S=s) = \frac{1}{n^2}\) and so \begin{align*} && \E[FS] &= \sum_{r=1}^n \sum_{s=1}^n rs \mathbb{P}(F=r, S = s) \\ &&&= \frac{1}{n^2} \sum_{r=1}^n \sum_{s=1}^n rs \\ &&&= \frac{1}{n^2} \left ( \sum_{r=1}^n r \right)\left ( \sum_{s=1}^n s \right) \\ &&&= \frac{1}{n^2} \left ( \frac{n(n+1)}{2} \right)^2 \\ &&&= \frac{(n+1)^2}{4} \end{align*}
2. Under this methodology, \(\mathbb{P}(F=r, S=s) = \frac{1}{n(n-1)}\) as long as \(r \neq s\), therefore \begin{align*} && \E[FS] &= \sum_{r=1}^n \sum_{s\neq r} rs \mathbb{P}(F = r, S = s) \\ &&&= \frac{1}{n(n-1)} \sum_{r=1}^n \left ( \sum_{s=1}^n rs - r^2 \right) \\ &&&= \frac{1}{n(n-1)} \left ( \frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} \right) \\ &&&= \frac{n+1}{12(n-1)} \left ( 3n(n+1)-2(2n+1) \right) \\ &&&= \frac{n+1}{12(n-1)} \left ( 3n^2 -n -2 \right) \\ &&&= \frac{n+1}{12(n-1)} (3n+2)(n-1)\\ &&&= \frac{(n+1)(3n+2)}{12} \end{align*}

---

Solution: Note that in the first \(10\)-short period the number of goals scored by each team is \(B(5, \p_i)\). For them to be equal they must both have scored the same number of goals, ie \begin{align*} && \alpha &= \sum_{i=0}^5 \mathbb{P}(\text{both teams score }5-i) \\ &&&= \sum_{i=0}^5 \binom{5}{i} (1-p_A)^ip_A^{5-i} \binom{5}{i} (1-p_B)^i p_B^{5-i} \\ &&&= \sum_{i=0}^5 \binom{5}{i} ^2(1-p_A)^i (1-p_B)^i p_A^{5-i} p_B^{5-i} \\ \end{align*} Suppose we make it to the end of the shoot out with scores tied. The probability that we finish each round is \(p_A(1-p_B) + p_B(1-p_A)\) (the probability \(A\) wins or \(B\) wins). This is \(p_A + p_B - 2p_Ap_B = \beta\)). Therefore the number of additional rounds is geometric with parameter \(\beta\) and the expected number of rounds is \(\frac{1}{\beta}\). Each round has two shots, and there is a probability \(\alpha\) of this occuring, ie \(\frac{2\alpha}{\beta}\). Added to the \(10\) guaranteed shots we get the desired result

---

Solution: Notice that we can see the total number generated as \(X_n \sim B(2X_{n-1},p)\), since a Binomial is a sum of independent Bernoullis, and there are two Bernoullis per particle. \begin{align*} && \mathbb{P}(X_1=2 \mbox { and } X_2=2) &= \underbrace{p^2}_{\text{two generated in first iteration}} \cdot \underbrace{\binom{4}{2}p^2q^2}_{\text{two generated from the first two}} \\ &&&= 6p^4q^2 \end{align*} \begin{align*} && \mathbb{P})(X_1 = 2 |X_2 = 2) &= \frac{ \mathbb{P}(X_1=2 \mbox { and } X_2=2) }{ \mathbb{P}( X_2=2) } \\ &&&= \frac{6p^4q^2}{6p^4q^2+2pq \cdot p^2} \\ &&&= \frac{3pq}{3pq+1} \\ \Rightarrow && \frac{9}{25} &= \frac{3pq}{3pq+1} \\ \Rightarrow && 27pq + 9 &= 75pq \\ \Rightarrow && 9 &= 48pq \\ \Rightarrow && pq &= \frac{3}{16} \\ \Rightarrow && 0 &= p^2 - p + \frac3{16} \\ \Rightarrow && p &= \frac14, \frac34 \end{align*} By the same reasoning about the Bernoullis, we must have \(\E[X_n] = \E[\E[X_n | X_{n-1}]] = \E[2pX_{n-1}] = 2p \E[X_{n-1}]\) therefore \(\E[X_n] = (2p)^n\). If \(p = \frac14\) then \(\E[X_n] = \frac1{2^n} \to 0\) If \(p = \frac34\) then \(\E[X_n] = \left(\frac32 \right)^n \to \infty\)

---

Solution: Let \(Y \sim Po(\lambda)\) \begin{align*} && 1 &= \sum_{k=1}^\infty \mathbb{P}(X = k ) \\ &&&= \sum_{k=1}^\infty A \frac{\lambda^k e^{-\lambda}}{k!}\\ &&&= Ae^{-\lambda} \sum_{k=1}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \\ &&&= Ae^{-\lambda} \left (e^{\lambda}-1 \right) \\ \Rightarrow && A &= (1-e^{-\lambda})^{-1} \\ \\ && \E[X] &= \sum_{k=1}^{\infty} k \cdot \mathbb{P}(X=k) \\ &&&= A\sum_{k=1}^{\infty} k \frac{\lambda^k e^{-\lambda}}{k!} \\ &&&= A\E[Y] = A\lambda = \lambda(1-e^{-\lambda})^{-1} \\ \\ && \var[X] &= \E[X^2] - (\E[X])^2 \\ &&&= A\sum_{k=1}^{\infty} k^2 \frac{\lambda^k e^{-\lambda}}{k!} - \mu^2 \\ &&&= A\E[Y^2] - \mu^2 \\ &&&= A(\var[Y]+\lambda^2) - \mu^2 \\ &&&= A(\lambda + \lambda^2) - \mu^2 \\ &&&= A\lambda(1+\lambda) - \mu^2 \\ &&&= \mu(1+\lambda - \mu) \end{align*} Since \(A > 1\) we must have \(\mu > \lambda\) and since \(\var[X] > 0\) we must have \(1 + \lambda > \mu\) as required. If \(\lambda = 100\), then \(A \approx 1\) and \(P(X=\lambda) \approx P(Y = \lambda)\) and \(Y \approx N(\lambda, \lambda)\) so the value is approximately \(\displaystyle \int_{-\frac12}^{\frac12} \frac{1}{\sqrt{2\pi \lambda}} e^{-\frac{x^2}{2\lambda}} \d x \approx \frac{1}{\sqrt{200\pi}} = \frac{1}{\sqrt{630.\ldots}} \approx \frac{1}{25} = 0.04 \)

---

Solution: \(X \sim Geo(p)\). \(\alpha = \mathbb{P}(X > M | p = B) = (1-B)^{M}\) \(\beta = \mathbb{P}(X \leq M | p = A) = 1 - \mathbb{P}(X > M | p = A) = 1 - (1-A)^{M}\) \begin{align*} \ln \alpha &= M \ln(1-B) \\ \ln (1-\beta) &= M \ln(1-A) \\ \frac{\ln \alpha}{\ln (1-\beta)} &= \frac{\ln(1-B)}{\ln(1-A)} \\ \ln(1-\beta) &= \ln \alpha \frac{\ln (1-A)}{\ln(1-B)} \\ \beta &= 1- \alpha^{ \frac{\ln (1-A)}{\ln(1-B)} } \end{align*} and \(K = \frac{\ln (1-A)}{\ln(1-B)} \) Since \(0 < A < B < 1\) we must have that \(0 < 1 - B < 1-A < 1\) and \(\ln(1-B) < \ln(1-A) < 0\) so \(0 < K < 1\)

---

Solution: Without loss of generality, let's assume that Harry is putting the center of his hoof within one square.

Based on the colour he places his foot in (red \(1\), green \(2\), blue \(3\) and orange \(4\)) we can see that the probability of him hitting \(1\) is \(\frac14\) and the probability of him getting \(4\) is \(\pi 0.25^2 = \frac{\pi}{16}\) just as you expected. The expected value of randomly placinging his hoof is: \begin{align*} \E[A] &= \frac14 \cdot 1 + \frac{4}{8} \cdot 2 + \left ( \frac14 - \frac{\pi}{16}\right) \cdot 3 + \frac{\pi}{16} \cdot 4 \\ &= 2 + \frac{\pi}{16} \end{align*} The expected value we should get is \(2.5\). That he is worse than random means we should probably investigate further. There is probably some bias, which might be solvable (it's hard for the horse to answer \(3\) for example), but it may just be we need a new horse.

---

Solution: Let \(H_i\) be the random variable of how many heads the \(i\)th coin throws on a given day. Then \(H_i \sim B(M,p)\), and the probability that a given coin produces fewer than \(m\) heads is \(p_h = \P(H_i < m)\) Let \(C\) be the random variable the number of coins producing fewer than \(m\) heads, then \(C \sim B(L, p_h)\). The probability that more than \(l\) of the coins produce fewer than \(m\) heads is therefore \(\P(C > l)\). Finally, the probability that on exactly \(k\) days more than \(l\) of the coins will produce fewer than \(m\) heads is: \[ \binom{K}{k} \cdot \P(C > l)^k \cdot (1-\P(C > l))^{K-k} \] Let's start by assuming that all our Binomials can be approximated by a normal distribution. \(B(M,p) \approx N(Mp, Mp(1-p))\) and so: \begin{align*} p_h &= \P(H_i < m) \\ &\approx \P( \sqrt{Mp(1-p)}Z+Mp < m-\frac12) \\ &= \P \l Z < \frac{2m-2Mp-1}{2\sqrt{Mp(1-p)}} \r \\ &= \Phi\l\frac{2m-2Mp-1}{2\sqrt{Mp(1-p)}} \r \end{align*} \(B(L, p_h) \approx B \l L, \P \l Z < \frac{2m-2Mp-1}{2\sqrt{Mp(1-p)}} \r\r = B(L, \frac{h}{L}) \approx N(h, \frac{h(L-h)}{L})\) Therefore \begin{align*} \P(C > l) &= 1-\P(C \leq l) \\ &\approx 1- \P \l \sqrt{\frac{h(L-h)}{L}} Z + h \leq l+\frac12 \r \\ &= 1 - \P \l Z \leq \frac{2l-2h+1}{2\sqrt{\frac{h(L-h)}{L}}}\r \\ &= 1- \Phi\l \frac{2l-2h+1}{2\sqrt{\frac{h(L-h)}{L}}} \r \\ &= \Phi\l \frac{2h-2l-1}{2\sqrt{\frac{h(L-h)}{L}}} \r \end{align*} If we can approximate \(\sqrt{1-\frac{h}{L}}\) by \(1\) then we obtain the approximation in the question. Alternatively, \(B(L, \frac{h}{L}) \approx Po(h)\) and \(Po(h) \approx N(h,h)\) so we obtain: \begin{align*} \P(C > l) &= 1-\P(C \leq l) \\ &\approx 1 - \P(\sqrt{h} Z +h < l + \frac12) \\ &= 1 - \P \l Z < \frac{2l-2h+1}{2\sqrt{h}} \r \\ &= \Phi \l \frac{2h - 2l -1}{2\sqrt{h}}\r \end{align*} as required. [I think this is what the examiners expected]. Considering the case \(K=7\), \(k=2\), \(L=500\), \(l=4\), \(M=100\), \(m=48\) and \(p=0.6\), we have the first normal approximation depends on \(Mp\) and \(M(1-p)\) being large. They are \(60\) and \(40\) respectively, so this is likely a good approximation. The first approximation finds that \begin{align*} h &= 500 \cdot \Phi \l \frac{2 \cdot 48 - 2 \cdot 60 - 1}{2\sqrt{24}} \r \\ &= 500 \cdot \Phi \l \frac{2 \cdot 48 - 2 \cdot 60 - 1}{2\sqrt{24}} \r \\ &= 500 \cdot \Phi \l \frac{-25}{2 \sqrt{24}} \r \\ &\approx 500 \cdot \Phi (-2.5) \\ &= 500 \cdot 0.0062 \\ &\approx 3.1 \end{align*} The second binomial approximation will be good if \(500 \cdot \frac{3.1}{500} = 3.1\) is large, but this is quite small. Therefore, we shouldn't expect this to be a good approximation. However, since \(m = 48\) is far from the mean (in a normalised sense), we might expect the percentage error to be large. [Alternatively, using what I expect the desired approach] The approximation of \(B(L, \frac{h}{L}) \approx Po(h)\) is acceptable since \(n>50\) and \(h < 5\). The approximation of \(Po(h) \sim N(h,h)\) is not acceptable since \(h\) is small (in particular \(h < 15\)) Finally, we can compute all these values exactly using a modern calculator. \begin{array}{l|cc} & \text{correct} & \text{approx} \\ \hline p_h & 0.005760\ldots & 0.005362\ldots \\ \P(C > l) & 0.164522\ldots & 0.133319\ldots \\ \text{ans} & 0.231389\ldots & 0.182516\ldots \end{array} We can also see how the errors propagate, by doing the calculations assuming the previous steps are correct, and also including the Poisson step. \begin{array}{lccc} & \text{correct} & \text{approx} & \text{using approx } p_h \\ \hline p_h & 0.005760\ldots & 0.005362\ldots & - \\ \P(C > l)\quad [Po(h)] & 0.164522\ldots & 0.165044\ldots & 0.134293\ldots \\ \P(C > l)\quad [N(h,h)] & 0.164522\ldots & 0.169953\ldots & 0.133319\ldots \\ \P(C > l)\quad [N(h,h(1-\frac{h}{L})] & 0.164522\ldots & 0.169255\ldots & 0.132677\ldots \\ \text{ans} & 0.231389\ldots & 0.231389\ldots \end{array} By doing this, we discover that the largest errors are actually coming not from approximating the second approximation but from the small absolute (but large relative error) in the first approximation. This is, in fact, a coincidence; we can observe it by investigating the specific values being used. The first approximation looks as follows:

You might not be able to tell, but there's actually two plots on this chart. However, let's zoom in on the area we are worried about: We can see there are small differences, which could be large in percentage terms. (As we found when we computed them directly). First, we can immediately see that if we just look at the distribution of \(B(L, p_h)\) and \(B(L, p_{h_\text{approx}})\) we get quite different results, even before we do any approximations. If we plot the probability distribution of \(B(L, p_h)\) vs \(N(Lp_h, Lp_h(1-p_h))\) we find that it is not a great approximation. However, the CDF happens to be a very good approximation *just* for the value we care about. Very lucky, but not possible for someone sitting STEP to know at the time!