Problems

---

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

---

Solution: \begin{align*} \mathbb{P}(\text{run out reading for toffee on } N\text{th occassion}) &= \binom{N-1}{n}p^nq^{N-1-n}p \end{align*} Since out of the first \(N-1\) times, we need to choose toffee \(n\) times, and then choose it again for the \(N\)th time. Therefore: \begin{align*} \mathbb{P}(\text{reaching for toffee} | \text{run out on }N\text{th occassion}) &= \frac{\mathbb{P}(\text{reaching for toffee and run out on }N\text{th occassion})}{\mathbb{P}(\text{reaching for toffee and run out on }N\text{th occassion}) + \mathbb{P}(\text{reaching for mint and run out on }N\text{th occassion})} \\ &= \frac{ \binom{N-1}{n}p^nq^{N-1-n}p}{ \binom{N-1}{n}p^nq^{N-1-n}p + \binom{N-1}{m}q^mp^{N-1-m}q} \\ &= \frac{ \binom{N-1}{n}}{ \binom{N-1}{n} + \binom{N-1}{m} \l \frac{q}{p} \r^{m+ n+ 2-N}} \end{align*} Some conclusions we can draw from this are: As \(p \to 1, q \to 0\), the probability they were reaching for a Toffee tends to \(1\). (And vice versa). If \(p = q\), then the probability is: \begin{align*} \frac{ \binom{N-1}{n}}{ \binom{N-1}{n} + \binom{N-1}{m} } \end{align*} Since \(n+1 \leq N \leq n+m+1\) where \(n \geq m\) we can notice that: \begin{align*} \text{if } N = m + n + 1 && \binom{m+n+1 - 1}{n} &= \binom{m+n+1 - 1}{m} & \text{ so } \mathbb{P} = \frac12 \\ \text{if } N = n+k && \binom{n+k-1}{n} &< \binom{n+k-1}{m} & \text{ so } \mathbb{P} < \frac12 \\ \end{align*}

---

Solution:

1. \(\binom{m+n}{m} p^m (1-p)^n\)
2. \(\,\) \begin{align*} \mathbb{P}(\text{failed to spot }n\text{ misprints}|\text{spotted }m\text{ misprints}) &= \frac{\mathbb{P}(\text{failed to spot }n\text{ misprints and spotted }m\text{ misprints}) }{\mathbb{P}(\text{spotted }m\text{ misprints})} \\ &= \frac{\binom{m+n}{n}p^m(1-p)^n e^{-\lambda} \lambda^{m+n}/(n+m)!}{\sum_{k=0}^{\infty} \binom{m+k}{k}p^m(1-p)^k e^{-\lambda} \lambda^{m+k}/(n+k)!} \\ &= \frac{\binom{m+n}{n}(1-p)^n \lambda^{n}/(n+m)!}{\sum_{k=0}^{\infty} \binom{m+k}{k}(1-p)^k \lambda^{k}/(n+k)!} \\ &= \frac{(1-p)^n \lambda^{n}/n!}{\sum_{k=0}^{\infty} (1-p)^k \lambda^{k}/k!} \\ &= \frac{(1-p)^n\lambda^n}{n!} e^{-(1-p)\lambda} \end{align*} Alternatively, given the missed misprints and spotted misprints are independent, we can view them as both following \(Po(p\lambda)\) and \(Po((1-p)\lambda)\) and so we obtain exactly this result, without calculation.

---

Solution: Suppose we have \(a = 2k\), it is necessary (by the triangle inequality) that \(b + c > a\). So the smallest \(b\) can be is \(k+1\), and then \(c\) must be \(k\) (1 choice). Then \(b\) could be \(k+2\) and \(c\) can be \(k+1\), \(k\), \(k-1\) (3 choices). Suppose \(b = k+i\) then \(c\) can be \(k+i-1, \ldots, k-i+1\) which is \(2i-1\) choices. This works until \(b = 2k-1\) and there are \(2(k-1)-1 = 2k-3 = a-3\) choices. Therefore there are \(1 + 3 + 5 + \cdots + (a-3)\) total choices. If \(a = 2k+1\) then, \(b = k+1\) is not possible \(b = k+2\) we have \(a = k+1, k\) (2 choices) \(b = k+3\) we have \(a = k+2, k+1, k, k-1\) (4 choices) \(b = k + i\) we have \(a = k+i-1, \cdots, k-i+2\) (\(2i-2\) choices) This works until \(b = k+k\) with \(2k-2 = a-3\) choices. So \(2 + 4 + \cdots + (a-3)\) If \(a\) is even, we have \(\left ( \frac{a-2}{2} \right)^2\) If \(a\) is odd we have \(\frac{(a-3)(a-1)}{4}\) Therefore the total number is: \begin{align*} C &= \sum_{k=2}^N \left ( \frac{(2k-2)^2}{4} + \frac{(2k+1-3)(2k+1-1)}{4} \right) \\ &= \sum_{k=2}^N \left ( (k-1)^2 + (k-1)k\right) \\ &= \sum_{k=2}^N (2k^2-3k+1) \\ &= \sum_{k=1}^N (2k^2-3k+1) \\ &= \frac{N(N+1)(2N+1)}{3} - \frac{3N(N+1)}{2} + N \\ &= \frac{N((N+1)(4N+2-9)+6)}{6} \\ &= \frac{N(4N+1)(N-1)}{6} \\ \end{align*} When \(N = 3\) we have \(1, 2, \cdots, 7\) sticks, and so \(a = 4\), \(1\) option \(a = 5\), \(2\) options \(a = 6\) \(4\) options \(a = 7\) \(6\) options for a total of \(13\). \(\frac{3 \cdot 13 \cdot 2}{6} = 13\) so this is promising, There are \(\binom{2N+1}{3}\) ways to choose three sticks (in order) and of those our formula tells us how many are valid, therefore \begin{align*} && P &= \frac{ \frac{N(4N+1)(N-1)}{6} }{\frac{(2N+1)2N(2N-1)}{6}} \\ &&&= \frac{(4N+1)(N-1)}{2(4N^2-1)} \end{align*}

---

Solution: Notice that \(\mathbb{E}(X_i) = 0, \mathbb{E}(X_i^2) = 1\) and so \(\mathbb{E}(S_n) =0, \textrm{Var}(S_n) = n\).

1. Then by the central limit theorem (or alternatively the normal approximation to the binomial), \begin{align*} && \mathbb{P}(S_n > 100) &\underbrace{\approx}_{\text{CLT}} \mathbb{P} \left (Z > \frac{100}{\sqrt{10\, 000}} \right) \\ &&&= \mathbb{P}(Z > 1) \\ &&&= 1-\Phi(1) \\ &&&\approx 15.9\% \end{align*}
2. \begin{align*} &&\mathbb{P}(S_n > 0.01n) &\approx \mathbb{P} \left (Z > \frac{0.01n}{\sqrt{n}} \right) \\ &&&= \mathbb{P}(Z > 0.01 \sqrt{n}) \\ &&&= 1-\Phi(0.01\sqrt{n}) \\ &&&< 0.01 \\ && \Phi^{-1}(0.01) &= -2.3263\ldots \\ \Rightarrow && 0.01 \sqrt{n} &= 2.3263\ldots \\ \Rightarrow && n &\approx 233^2 \end{align*}

\begin{array}{cc|cc} 1\text{st throw}& k\text{th throw} & X_1 + X_k & Y_k \\ \hline \text{head} & \text{head} & 1 + 1 & 2 \\ \text{head} & \text{tail} & 1 - 1 & 0 \\ \text{tail} & \text{head} & -1 + 1 & 0 \\ \text{tail} & \text{tail} & -1- 1 & -2 \\ \end{array} Across all possible cases \(Y_k = X_1 + X_k\) so therefore these random variables are equal. \begin{align*} \mathbb{E}(Y_k) &= \mathbb{E}(X_1) + \mathbb{E}(Y_k) \\ &= 0 + 0 = 0 \\ \\ \textrm{Var}(Y_k) &= \textrm{Var}(X_1)+\textrm{Var}(X_k) \\ &= 2 \\ \\ \mathbb{E}\left (\sum_{k=2}^n Y_k \right) &= 0 \\ \textrm{Var}\left (\sum_{k=2}^n Y_k \right) &= 2(n-1) \end{align*} Therefore approximately \(\displaystyle \sum_{k=2}^n Y_k \approx N(0, 2(n-1))\) \begin{align*} \mathbb{P} \left (\sum_{k=2}^n Y_k > 0.01(n-1) \right) &\approx \mathbb{P} \left (Z > \frac{0.01(n-1)}{\sqrt{2(n-1)}} \right) \\ &= \mathbb{P} \left (Z > c \sqrt{n-1} \right) \\ &\to 0 \text{ as } n \to \infty \end{align*}

---

Solution: Since the toad never crosses when it's not safe, she is certain to cross. (Probability she hasn't crossed after the \(n\)th minute is \(0.9^n \to 0\)). \begin{array}{c|c|c|c|c|c|c|c} \text{will try dangerously} & \text{is safe} & \text{has tried} & \text{tries safely} & \text{tries unsafely} & \text{succeeds} & \text{succeeds unsafely} & \text{fails} \\ \hline 0 & 0.1 & 0 & 0.1 & 0 & 0.1 & 0 & 0\\ \frac13 & 0.1 & 0.1 & 0.09 & 0.27 & 0.144 & 0.054 & 0.216\\ \frac23 & 0.1 & 0.46 & 0.054 & 0.324 & 0.1188 & 0.0648 & 0.2592\\ 1 & 0.1 & 0.838 & 0.0162 & 0.1458 & 0.04536 & 0.02916 & 0.11664\\ \hline & & & & & 0.40816 & 0.14796 & \\ \hline \end{array} So \(\mathbb{P}(\text{frog crosses safely}) = 0.40816\) and \(\mathbb{P}(\text{frog beats toad across}) = 0.14796\). \begin{align*} \mathbb{P}(\text{frog run over} | \text{frog not crossed after 2 minutes}) &= \frac{\mathbb{P}(\text{frog run over and frog not crossed after 2 minutes})}{\mathbb{P}(\text{frog not crossed after 2 minutes})} \\ &= \frac{\mathbb{P}(\text{frog run over within 2 minutes})}{\mathbb{P}(\text{frog not crossed after 2 minutes})} \\ &= \frac{\mathbb{P}(\text{frog run over within 2 minutes})}{1-\mathbb{P}(\text{crossed after 2 minutes})} \\ &= \frac{0.216+0.2592}{1-0.3628} \\ &= 0.7457\ldots \end{align*}

---

Solution:

1. It cannot overflow on the first day, since it is already \(V\) below the top. The only way it can overflow is if it rains both days. This will occur with probability \(p^2\). The probability it overflows therefore is the probability that bad timing hampers us, ie \(V - u(1+t_2) > 0\) where \(t_2\) is the timing of the rain on day 2 (as a fraction of a day). Ie \(t_2 < \frac{V}{u}-1\). Therefore \begin{align*} && Q &= p^2 \left (\frac{V}{u} - 1 \right) \\ \Rightarrow && u &= \frac{Vp^2}{p^2+Q} \end{align*}
2. The probability the reservoir overflows during this \(18\) days is \(\mathbb{P}(\text{rains more than }k\text{ times})\). The number of times it rains (\(X\)) is \(B(18, \tfrac13)\), since \(18 \cdot \tfrac13 = 6 > 5\) a normal approximation is reasonable, ie \(X \approx N(6, 4)\). We wish to find \(k\) such that \(\mathbb{P}( X > k + 0.5) < \tfrac1{10}\) therefore \(k \approx 1.28 \cdot 2 + 6 - 0.5 \approx 8.1\) so they should set \(k\) to \(9\)
3. In this case we have \(B(36, \tfrac16)\) approximated by \(B(6, 5)\) which has a larger standard deviation, therefore we need to choose a larger value for \(k\). [It turns out to actually be the same, but there's no reason to be able to expect students without a calculator to establish this]

---

Solution: The probability Juggin's has a non-zero score is the probability he never draws a black ball in his three goes. This is \((1-\frac15)^3 = \frac{64}{125}\). Let's consider the \(\frac{61}{125}\) probability world where he never draws a black ball. In this conditional probability space, he has \(\frac{5}{8}\) chances of pulling out white balls and \(\frac38\) or pulling out red. His expected score per pull is \(\frac58 \cdot 1 + \frac38 \cdot 2 = \frac{11}{8}\). Therefore his expected score in this universe is \(\frac{33}8\) and his expected score is \(\frac{33}{8} \cdot \frac{61}{125} = \frac{2013}{1000} = 2.013\) . The expected score after drawing another ball is \(( N + 1)\frac{5}{10} + (N+2) \frac{3}{10} + 0 \cdot \frac{2}{10} = \frac{8}{10}N + \frac{11}{10}\). A sensible strategy would be to only draw if \(\frac{8}{10}N + \frac{11}{10} > N \Rightarrow N < \frac{11}{2}\), ie keep drawing until \(N \geq 6\) or we bust out. [The expected score for this strategy is: \begin{array}{ccc} \text{score} & \text{route} & \text{count} & \text{prob} \\ \hline 6 & \text{6 1s} & 1 & \left ( \frac12 \right)^6 \\ 6 & \text{4 1s, 1 2} & 5 & 5 \cdot \left ( \frac12 \right)^4 \cdot \frac{3}{10} \\ 6 & \text{2 1s, 2 2s} & 6 & 6 \cdot \left ( \frac12 \right)^2 \cdot \left ( \frac{3}{10} \right)^2 \\ 6 & \text{3 2s} & 1 & 1 \cdot \left ( \frac{3}{10} \right)^3 \\ 7 & \text{5 1s, 1 2} & 1 &\left ( \frac12 \right)^5 \cdot \frac{3}{10} \\ 7 & \text{3 1s, 2 2s} & 4 & 4\cdot \left ( \frac12 \right)^3 \cdot \left ( \frac{3}{10} \right)^2 \\ 7 & \text{1 1, 3 2s} & 3 & 3\cdot \left ( \frac12 \right) \cdot \left ( \frac{3}{10} \right)^3 \\ \end{array} For an expected value of \(\frac{2171}{8000} \cdot 6 + \frac{759}{8000} \cdot 7 = \frac{18\,339}{8000} = 2.29 \quad (3\text{ s.f.})\)]

---

Solution: We must have a sequence consisting of \(\underbrace{HTT\cdots TH}_{k-1\text{ heads and }n-k\text{ tails}}\underbrace{H}_{k\text{th head}}\). There are \(\binom{n-1}{k-1}\) ways to chose how to place the \(k-1\) heads in the first \(n-1\) flips, and each sequence has probability \(p^{k-1}(1-p)^{n-k}p\) which gives a probability of \(\displaystyle \binom{n-1}{k-1} p^k (1-p)^{n-k}\). Given that it took an even number of tosses to achieve \(k-1\) heads, this is equivalent to the problem of what is the probability that the first head occurs on an even flip, ie \begin{align*} \mathbb{P}(\text{even flip}) &= \mathbb{P}(2\text{nd flip}) +\mathbb{P}(4\text{th flip}) +\mathbb{P}(6\text{th flip}) + \cdots \\ &= (1-p)p + (1-p)^3p + (1-p)^5p + \cdots \\ &= (1-p)p \left ( \sum_{r=0}^\infty (1-p)^{2r}\right) \\ &= \frac{p(1-p)}{1-(1-p)^2} \\ &= \frac{p(1-p)}{2p-p^2} \\ &= \frac{1-p}{2-p} \end{align*} The ways to achieve \(2\) heads on even tosses are \(EEO\), \(EOE\), \(OEE\). The probability of going from \(O\) to \(E\) is the same as the initial probability of an \(O\) flip, etc. Therefore \begin{align*} \mathbb{P}(EEO) &=\left( \frac{1-p}{2-p} \right)^2 \left ( 1- \frac{1-p}{2-p} \right) \\ &= \left( \frac{1-p}{2-p} \right)^2 \left ( \frac{1}{2-p} \right) \\ \mathbb{P}(EOE) &= \left( \frac{1-p}{2-p} \right) \left ( \frac{1}{2-p} \right)^2 \\ \mathbb{P}(OEE) &= \left ( \frac{1}{2-p} \right)^2 \left( \frac{1-p}{2-p} \right)\\ \mathbb{P}(2 \text{ heads on even tosses}) &= \frac{(1-p)^2 + 2(1-p)}{(2-p)^3} \\ &= \frac{(1-p)(2-p)}{(2-p)^3} \\ &= \frac{1-p}{(2-p)^2} \end{align*}

---

Solution: The probability density function will look like a triangle with base \(20\) minutes and therefore height \(\frac{1}{10}\) per minute, ie: \begin{align*} f_T(t) &= \begin{cases} \frac{1}{100}(t+10) & \text{if } -10 \leq t \leq 0 \\ \frac{1}{100}(10-t) & \text{if } 0 \leq t \leq 10 \\ 0 & \text{otherwise} \end{cases} \end{align*} \begin{align*} \mathbb{P}(\text{catch bus}) &=0.5 \mathbb{P}(\text{bus arrives after 7:55})+0.4 \mathbb{P}(\text{bus arrives after 7:58}) + 0.1 \mathbb{P}(\text{bus arrives after 8:02}) \\ &= \frac12 \cdot \left (1 - \frac18 \right) + \frac{2}{5} \cdot \left ( 1 - \frac{4^2}{5^2} \cdot \frac{1}{2} \right) + \frac{1}{10} \cdot \frac{4^2}{5^2} \cdot \frac12 \\ &= \frac{1\,483}{2\,000} \\ &\approx 74\% \end{align*} \begin{align*} \mathbb{P}(\text{catch bus}) &= \mathbb{P}(\text{bus arrives after 7:55}) \mathbb{P}(\text{catch next bus by 9:00}) \\ &= \frac78 + \frac18 \cdot \frac12 \\ &= \frac{15}{16} \end{align*} He should expect to miss \(6.25\) buses, so missing \(5\) seems about right. (Using a binomial calculation, seeing 5 or fewer buses is ~\(40\%\) which isn't suspicious).

---

Solution: Another way to describe \(Y\) is the maximum distance of any shot from \(O\). Let \(X_i\), \(1 \leq i \leq n\) be the \(n\) shots then, \begin{align*} F_Y(y) &= \mathbb{P}(Y \leq y) \\ &= \mathbb{P}(X_i \leq y \text{ for all } i) \\ &= \prod_{i=1}^n \mathbb{P}(X_i \leq y) \tag{each shot independent}\\ &= \prod_{i=1}^n y^2\\ &= y^{2n} \end{align*} Therefore \(f_Y(y) = \frac{\d}{\d y} (y^{2n}) = 2n y^{2n-1}\). \begin{align*} \mathbb{E}(\pi Y^2) &= \int_0^1\pi y^2 \f_Y(y) \d y \\ &=\pi \int_0^1 2n y^{2n+1} \d y \\ &=\left ( \frac{n}{n+1} \right )\pi \end{align*}. Let \(Z\) be the distance of the second furthest shot, then: \begin{align*} && F_Z(z) &= \mathbb{P}(Z \leq z) \\ &&&= \mathbb{P}(X_i \leq z \text{ for at least } n - 1\text{ different } i) \\ &&&= n\mathbb{P}(X_i \leq z \text{ for all but 1}) + \mathbb{P}(X_i \leq z \text{ for all } i) \\ &&&= n \left ( \prod_{i=1}^{n-1} \mathbb{P}(X_i \leq z) \right) \mathbb{P}(X_n > z) + z^{2n} \\ &&&= nz^{2n-2}(1-z^2) + z^{2n} \\ &&&= nz^{2n-2} -(n-1)z^{2n} \\ \Rightarrow && f_Z(z) &= n(2n-2)z^{2n-3}-2n(n-1)z^{2n-1} \\ \Rightarrow && \mathbb{E}(\pi Z^2) &= \int_0^1 \pi z^2 \left (n(2n-2)z^{2n-3}-2n(n-1)z^{2n-1} \right) \d z \\ &&&= \pi \left ( \frac{n(2n-2)}{2n} - \frac{2n(n-1)}{2n+2}\right) \\ &&&= \left ( \frac{n-1}{n+1} \right) \pi \end{align*}