Problems

Solution:

1. Note that, \begin{align*} && \sum_{r = 0}^\infty x^r &= \frac{1}{1-x} && |x| < 1\\ \underbrace{\Rightarrow}_{\frac{\d}{\d x}} && \sum_{r = 0}^\infty rx^{r-1} &= \frac{1}{(1-x)^2} && |x| < 1\\ && \sum_{r = 1}^\infty rx^{r-1} &= \frac{1}{(1-x)^2} && |x| < 1\\ \end{align*}
2. 1. \begin{align*} && \mathbb{P}(\text{Ali wins in }s\text{ rounds}) &= \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ \Rightarrow && \mathbb{P}(\text{Ali wins}) &= \sum_{s=1}^\infty \mathbb{P}(\text{Ali wins in }s\text{ rounds}) \\ &&&=\sum_{s=1}^\infty \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ &&&= \frac{1}{2k} \sum_{s=0}^\infty \left ( \frac{k-1}{2k} \right)^{s} \\ &&&= \frac{1}{2k} \frac{1}{1 - \frac{k-1}{2k}} \\ &&&= \frac{1}{2k - (k-1)} \\ &&&= \frac{1}{k+1} \end{align*}
   2. \begin{align*} \mathbb{E}(\text{Ali score}) &= \sum_{s=1}^{\infty} s \mathbb{P}(\text{Ali wins in }s\text{ rounds}) \\ &= \sum_{s=1}^{\infty} s \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ &= \frac{1}{2k} \frac{1}{\left (1 - \frac{k-1}{2k} \right)^2} \\ &= \frac{2k}{(k+1)^2} \end{align*}
3. \begin{align*} && (1+x)^{n} &= \sum_{k=0}^n \binom{n}{k} x^k \\ \Rightarrow && x(1+x)^n &= \sum_{k=0}^n \binom{n}{k} x^{k+1} \\ \Rightarrow && (1+x)^n + nx(1+x)^{n-1} &= \sum_{k=0}^n (k+1)\binom{n}{k} x^k \\ \Rightarrow && (1+x)^{n-1}(1+(n+1)x) &= 1 + 2\binom{n}{1}x + 3\binom{n}{2}x^2 + \ldots + (n+1)x^n \end{align*}
4. \begin{align*} \mathbb{E}(\text{Zen score}) &= \sum_{s=1}^{2k} s \mathbb{P} \left ( \text{Zen gets }s\text{ numbers in increasing order ending with }2k \right) \\ &= \sum_{s=1}^{2k} s \binom{2k-1}{s-1} \frac{1}{(2k)^s} \\ &= \frac{1}{2k}\sum_{s=0}^{2k-1} (s+1) \binom{2k-1}{s} \frac{1}{(2k)^s} \\ &= \frac{1}{2k} \left ( 1 + \frac{1}{2k} \right)^{2k-2} \left ( 1 + (2k-1+1) \frac{1}{2k} \right) \\ &= \frac{1}{k}\left ( 1 + \frac{1}{2k} \right)^{2k-2} \end{align*}
5. Therefore as \(k \to \infty\) \begin{align*} \frac{\mathbb{E}(\text{Zen score})}{\mathbb{E}(\text{Ali score}) } &= \frac{1}{k}\left ( 1 + \frac{1}{2k} \right)^{2k-2} \big / \frac{2k}{(k+1)^2} \\ &= \frac{(k+1)^2}{2k^2} \cdot \left ( 1 + \frac{1}{2k} \right)^{2k} \cdot \left ( 1 + \frac{1}{2k} \right)^{-2} \\ &\to \frac12 e \approx 2.7/2 = 1.35 \end{align*} ie Zen's expected earnings are \(\approx 35\%\) more.

Solution:

1. Suppose \(d_r = p_r - p_{r-1}\) then \begin{align*} d_r &= p_r - p_{r-1} \\ &= \mathbb{P}(X = r) - \mathbb{P}(X = r-1) \\ &= e^{-\lambda} \left ( \frac{\lambda^r}{r!} - \frac{\lambda^{r-1}}{(r-1)!} \right) \\ &= e^{-\lambda} \frac{\lambda^{r-1}}{(r-1)!} \left ( \frac{\lambda}{r} - 1\right) \end{align*} Therefore \(d_r > 0 \Leftrightarrow \lambda > r\)ie, \(p_r\) is increasing while \(r < \lambda\) and reaches a (unique) maximum when \(r = \lfloor \lambda \rfloor\).
2. Let \(dd_r = d_r - d_{r-1}\), so: \begin{align*} dd_r &= d_r - d_{r-1} \\ &= p_r - 2p_{r-1} + p_{r-2} \\ &= e^{-\lambda} \frac{\lambda^{r-2}}{r!} \left ( \lambda^2 - 2 \lambda r + r(r-1)\right ) \end{align*} Therefore \(dd_r < 0 \Leftrightarrow \lambda^2 - 2\lambda r +r(r-1) < 0 \Leftrightarrow r^2 -(1+2\lambda)r + \lambda^2 < 0\), but this has roots \(r = \frac{(1+2\lambda) \pm \sqrt{(1+2\lambda)^2-4\lambda^2}}{2} = \lambda + \frac12 \pm \sqrt{\lambda + \frac14}\). Therefore \(d_r\) is decreasing when \(r \in \left (\lambda + \frac12 -\sqrt{\lambda + \frac14},\lambda + \frac12 + \sqrt{\lambda + \frac14} \right)\), therefore the possible minimums are \(d_1\) and \(d_k\) where \(k < \lambda + \frac{1}{2} + \sqrt{\lambda + \frac{1}{4}} < k + 1\). \(d_1 = e^{-\lambda}(\lambda - 1)\), \(d_k = e^{-\lambda} \frac{\lambda^{k-1}}{(k-1)!}(\frac{\lambda}{k}-1)\)
3. If the maximum value of \(d_r\) is \(r = 1\) then \(d_r\) must be decreasing, ie considering \(dd_2\) we have \(\lambda^2 -4\lambda + 2< 0 \Leftrightarrow 2 - \sqrt{2} < \lambda < 2 + \sqrt{2}\). It must also be the case that it doesn't get beaten as \(\lambda \to \infty\). In this case \(d_r \to 0\), so we need \(d_1 > 0\), ie \(\lambda > 1\). Therefore \(1 < \lambda < 2 + \sqrt{2}\)
4. 

   + - ↺

Solution:

1. \begin{align*} \sum_{r=1}^{m+1} \left (f(r) \sum_{s=r-1}^m g(s) \right) &= \sum_{r=1}^{m+1} \sum_{s=r-1}^m f(r)g(s) \\ &= \sum_{(r,s) \in \{(r,s) : 1 \leq r \leq m+1, 0 \leq s \leq m, s \geq r-1\}} f(r)g(s) \\ &= \sum_{(r,s) \in \{(r,s) : 0 \leq s \leq m, 1 \leq r \leq m+1, r \leq s+1\}} f(r)g(s) \\ &= \sum_{s=0}^m \sum_{r=1}^{s+1} f(r)g(s) \\ &= \sum_{s=0}^m \left ( g(s) \sum_{r=1}^{s+1} f(r) \right) \end{align*}
2. \(X_1\) takes the values \(0, 1\) with equal probabilities (since \(X_0 = 0\)). Therefore \(\mathbb{E}(X_1) = \frac12\).
   1. \begin{align*} \mathbb{P}(X_2 = 0) &= \mathbb{P}(X_2 = 0 | X_1 = 0) \mathbb{P}(X_1 = 0) + \mathbb{P}(X_2 = 0 | X_1 = 1) \mathbb{P}(X_1 = 1) \\ &= \frac12 \cdot \frac12 + \frac13 \cdot \frac12 \\ &= \frac5{12} \\ \\ \mathbb{P}(X_2 = 1) &= \mathbb{P}(X_2 = 1 | X_1 = 0) \mathbb{P}(X_1 = 0) + \mathbb{P}(X_2 = 1 | X_1 = 1) \mathbb{P}(X_1 = 1) \\ &= \frac12 \cdot \frac12 + \frac13 \cdot \frac12 \\ &= \frac5{12} \\ \\ \mathbb{P}(X_2 = 3) &= 1 - \mathbb{P}(X_2 = 0) - \mathbb{P}(X_2 = 1) \\ &= 1 - \frac{10}{12} = \frac16 \\ \\ \mathbb{E}(X_2) &= \frac{5}{12} + 2\cdot \frac{1}{6} \\ &= \frac34 \end{align*}
   2. \begin{align*} \mathbb{P}(X_n = 0) &= \sum_{s=0}^{n-1} \mathbb{P}(X_n = 0 | X_{n-1} = s)\mathbb{P}(X_{n-1} = s) \\ &= \sum_{s=0}^{n-1} \frac{1}{s+2}\mathbb{P}(X_{n-1} = s) \\ \end{align*} as required. (Where \(\mathbb{P}(X_n = 0 | X_{n-1} = s) = \frac{1}{s+2}\) since if \(X_{n-1} = s\) there are \(0, 1, \ldots, s + 1\) values \(X_n\) can take with equal chance (ie \(s+2\) different values). \begin{align*} \mathbb{P}(X_n = r) &= \sum_{s=0}^{n-1} \mathbb{P}(X_n = r | X_{n-1} = s)\mathbb{P}(X_{n-1} = s) \\ &= \sum_{s=r-1}^{n-1} \frac{\mathbb{P}(X_{n-1}=s)}{s+2} \end{align*}
   3. \begin{align*} \mathbb{E}(X_n) &= \sum_{r=1}^{n} r \cdot \mathbb{P}(X_n = r) \\ &= \sum_{r=1}^{n} r \cdot \sum_{s=r-1}^{n-1} \frac{\mathbb{P}(X_{n-1}=s)}{s+2} \\ &= \sum_{s=0}^{n-1} \frac{\mathbb{P}(X_{n-1}=s)}{s+2} \sum_{r=1}^{s+1} r \\ &= \sum_{s=0}^{n-1} \frac{\mathbb{P}(X_{n-1}=s)}{s+2} \frac{(s+1)(s+2)}{2} \\ &= \frac12 \sum_{s=0}^{n-1} (s+1)\mathbb{P}(X_{n-1}=s) \\ &= \frac12 \sum_{s=0}^{n-1} s\mathbb{P}(X_{n-1}=s) + \frac12 \sum_{s=0}^{n-1} \mathbb{P}(X_{n-1}=s) \\\\ &= \frac12 \left ( \mathbb{E}(X_{n-1}) + 1 \right) \end{align*} Suppose \(\mathbb{E}(X_n) = 1-2^{-n}\), then notice that this expression matches for \(n = 0, 1, 2\) and also: \(\frac12(1 - 2^{-n} + 1) = 1-2^{-n-1}\) satisfies the recusive formula. Therefore by induction (or similar) we can show that \(\mathbb{E}(X_n) = 1- 2^{-n}\).

Solution:

1. The probability they don't make a decision in a round is \(qp + pq = 2qp\) (TH and HT). The probability they make a decision in a round is \(q^2+p^2\) (TT and HH). Therefore the probability they make a decision in the \(n\)th round is: \[ (q^2+p^2)(2qp)^{n-1} \] by having \(n-1\) failures and one success. The probability they make a decision on or before the \(n\)th round is the \(1-\) the probability they don't, ie \(1 - (2qp)^n\). Notice that \(\sqrt{qp} \leq \frac{p+1}{2} = \frac12 \Rightarrow qp \leq \frac14\) so \(1-(2pq)^n \leq 1 - \frac1{2^n}\)
2. The probability it's decided in the first round is \(p^3 + q^3\) (HHH, TTT). The probability it's decided in the second round is \(3p^2q \cdot p^2 + 3qq^2 \cdot q^2 = 3pq(p^3+q^3)\) (HHT -> HHH) and (TTH -> TTT) with reorderings). Therefore the probability of making a decision in the first or second round is \((p^3+q^3)(1 + 3pq)\) which is minimised when \(p = q\) by Muirhead (or whatever your favourite inequality is). So \(\frac{2}{8} \cdot \left ( 1 + \frac{3}{4} \right) = \frac{7}{16}\)

Solution:

1. If \(n_3 = 9\) and we are looking for \(0 < n_1 < n_2 < n_3\) we can consider values for each \(n_2\). \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 4-5 & 2 \\ 7 & 3-6 & 4 \\ 8 & 2-7 & 6 \\ \hline & & 12 \end{array} When \(n_3 = 10\) \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 5 & 1 \\ 7 & 4-6 & 3 \\ 8 & 3-7 & 5 \\ 9 & 2-8 & 7 \\ \hline & & 16 \end{array} When \(n_3 = 2n+1\) we can have \(2 + 4 + \cdots + 2n-2 = n(n-1)\) When \(n_3 = 2n\) we can have \(1 + 3 + \cdots + 2n-3 = (n-1)^2\)
2. For the 3 rods to form a triangle, it suffices for the sum of the lengths of the shorter rods to be larger than \(N\). When \(N = 2n+1\) there are \(n(n-1)\) ways this can happen, out of \(\binom{2n}{2}\) ways to choos the numbers, ie \begin{align*} && P &= \frac{n(n-1)}{\frac{2n(2n-1)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*} When \(N = 2n\) there are \((n-1)^2\) ways this can happen, out of \(\binom{2n-1}{2}\) ways, ie \begin{align*} && P &= \frac{(n-1)^2}{\frac{(2n-1)(2n-2)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*}
3. The number of ways this can happen is: \begin{align*} C &= \sum_{k=3}^{2M+1} \# \{ \text{triangles where }k\text{ is largest} \} \\ &= \sum_{k=1}^{M} \# \{ \text{triangles where }2k+1\text{ is largest} \} +\sum_{k=1}^{M} \# \{ \text{triangles where }2k\text{ is largest} \}\\ &= \sum_{k=1}^{M} n(n-1)+\sum_{k=1}^{M} (n-1)^2\\ &= \sum_{k=1}^{M} (2n^2-3n+1)\\ &= \frac26M(M+1)(2M+1) - \frac32M(M+1) + M \\ &= \frac16 M(4M+1)(M-1) \end{align*} Therefore the probability is \begin{align*} && P &= \frac{M(4M+1)(M-1)}{6 \binom{2M+1}{3}} \\ &&&= \frac{M(4M+1)(M-1)}{(2M+1)2M(2M-1)} \\ &&&= \frac{(4M+1)(M-1)}{2(2M+1)(2M-1)} \end{align*}

Solution:

1. \(\,\) \begin{align*} && \mu &= \E[X] \\ &&&= \int_0^1 x f(x) \d x \\ &&&= \int_0^1 nx^n \d x \\ &&&= \frac{n}{n+1} \\ \\ && \var[X] &= \sigma^2 \\ &&&= \E[X^2] - \mu^2 \\ &&&= \int_0^1 x^2 f(x) \d x - \mu^2 \\ &&&= \int_0^1 nx^{n+1} \d x - \mu^2 \\ &&&= \frac{n}{n+2} - \frac{n^2}{(n+1)^2} \\ &&&= \frac{n(n+1)^2 - n^2(n+2)}{(n+1)^2(n+2)} \\ &&&= \frac{n}{(n+1)^2(n+2)} \end{align*}
2. \(\,\) \begin{align*} && \frac14 &= \int_0^{Q_1} 2x \d x \\ &&&= Q_1^2 \\ \Rightarrow && Q_1 &= \frac12 \\ && \frac34 &= \int_0^{Q_3} 2x \d x \\ &&&= Q_3^2 \\ \Rightarrow && Q_3 &= \frac{\sqrt{3}}2 \\ \\ \Rightarrow && IQR &= Q_3 - Q_1 = \frac{\sqrt{3}-1}{2} \\ && 2 \sigma &= 2\sqrt{\frac{2}{3^2 \cdot 4}} \\ &&&= \frac{\sqrt{2}}{3} \\ \\ && 2\sigma - IRQ &= \frac{\sqrt{2}}{3} - \frac{\sqrt{3}-1}{2} \\ &&&= \frac{2\sqrt{2}-3\sqrt{3}+3}{6} \\ && (3+2\sqrt{2})^2 &= 17+12\sqrt{2} > 29 \\ && (3\sqrt{3})^2 &= 27 \end{align*} Therefore \(2\sigma > IQR\)
3. \[ (1+x)^n = 1 + nx + \frac{n(n-1)}2 x^2 + \cdots + \binom{n}{k} x^k+ \cdots \] \begin{align*} && Q_1^{-n} &= 4 \\ && Q_2^{-n} &= 2\\ && \mu &=\frac{n}{n+1} \\ \Rightarrow && \mu^{-n} &= \left (1 + \frac1n \right)^n\\ &&&\geq 1 + n \frac1n + \cdots > 2 \\ \Rightarrow && \mu &< Q_2 \\ \\ && \mu^{-n} &= \left (1 + \frac1n \right)^n\\ &&&= 1 + n \frac1n + \frac{n(n-1)}{2!} \frac{1}{n^2} + \cdots + \frac{n(n-1) \cdots (n-k+1)}{k!} \frac{1}{n^k} + \cdots \\ &&&= 1 + 1 + \left (1 - \frac1n \right ) \frac1{2!} + \cdots + \left (1 - \frac1n \right)\cdot\left (1 - \frac2n \right) \cdots \left (1 - \frac{k-1}n \right) \frac{1}{k!} + \cdots \\ &&&< 1 + 1 + \frac1{2!} + \cdots + \frac1{k!} \\ &&&< 4 \\ \Rightarrow && \mu &> Q_1 \end{align*}

Solution:

1. Let \(X\) be the number of people arriving on a given day, and \(Y\) be the number taking sand, then \begin{align*} && \mathbb{P}(Y = k) &= \sum_{x=k}^{\infty} \mathbb{P}(x \text{ arrive and }k\text{ of them take sand}) \\ &&&= \sum_{x=k}^{\infty} \mathbb{P}(X=x)\mathbb{P}(k \text{ out of }x\text{ of them take sand})\\ &&&= \sum_{x=k}^{\infty} e^{-\lambda} \frac{\lambda^x}{x!}\binom{x}{k}p^k(1-p)^{x-k}\\ &&&= e^{-\lambda} \left ( \frac{p}{1-p} \right)^k \sum_{x=k}^{\infty} \frac{((1-p)\lambda)^x}{k!(x-k)!} \\ &&&= e^{-\lambda} \left ( \frac{p}{1-p} \right)^k \frac{((1-p)\lambda)^k}{k!} \sum_{x=0}^{\infty} \frac{((1-p)\lambda)^x}{x!} \\ &&&= e^{-\lambda} \left ( \frac{p}{1-p} \right)^k \frac{((1-p)\lambda)^k}{k!}e^{(1-p)\lambda)} \\ &&&= e^{-p\lambda} \frac{(p\lambda)^k}{k!} \end{align*} which is precisely a Poisson with parameter \(p\lambda\). Alternatively, \(Y = B_1 + B_2 + \cdots + B_X\) where \(B_i \sim Bernoulli(p)\) so \(G_Y(t) = G_X(G_B(t)) = G_X(1-p+pt) = e^{-\lambda(1-(1-p+pt))} = e^{-p\lambda(1-t)}\) so \(Y \sim Po(\lambda)\) Alternatively, alternatively, let \(Z\) be the number of people not taking sand, so \begin{align*} && \mathbb{P}(Y = y, Z= z) &= \mathbb{P}(X=y+z) \cdot \binom{y+z}{y} p^y(1-p)^z \\ &&&= e^{-\lambda} \frac{\lambda^{y+z}}{(y+z)!} \frac{(y+z)!}{y!z!} p^y(1-p)^z \\ &&&=\left ( e^{-p\lambda} \frac{(p\lambda)^y}{y!} \right) \cdot \left ( e^{-(1-p)\lambda} \frac{((1-p)\lambda)^z}{z!}\right) \end{align*} So clearly \(Y\) and \(Z\) are both (independent!) Poisson with parameters \(p\lambda \) and \((1-p)\lambda\)
2. The amount taken is \(Sk + S(1-k)k + \cdots +Sk(1-k)^{Y-1} = Sk\cdot \frac{1-(1-k)^Y}{k} = S(1-(1-k)^Y)\) so \begin{align*} \E[\text{taken sand}] &= \E \left [ S(1-(1-k)^Y)\right] \\ &= S-S\E\left [(1-k)^Y \right] \\ &= S - SG_Y(1-k)\\ &=S - Se^{-p\lambda(1-(1-k))} \tag{pgf for Poisson} \\ &= S\left (1-e^{-kp\lambda} \right) \end{align*}
3. The fraction of grains the assistant takes home is: \((1-k)^Yk\), which has expected value \(ke^{-kp\lambda}\). This the the probability he takes home the golden grain. When \(k = 0\) the probability is \(0\) which makes sense (no-one takes home any sand, including the merchant's assistant). As \(k \to 1\) we get \(e^{-p\lambda}\) which is the probability that no-one gets any sand other than him. \begin{align*} && \frac{\d }{\d k} \left ( ke^{-kp\lambda} \right) &= e^{-kp\lambda} - (p\lambda)ke^{-kp\lambda} \\ &&&= e^{-kp\lambda}(1 - (p\lambda)k) \end{align*} Therefore maximised at \(k = \frac{1}{p\lambda}\). (Clearly this is a maximum just by sketching the function)

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

Solution:

1. \(\mathbb{P}(\text{head}) = \mathbb{P}(\text{head}|1)\mathbb{P}(\text{coin 1}) + \mathbb{P}(\text{head}|2)\mathbb{P}(\text{coin 2})+\mathbb{P}(\text{head}|3)\mathbb{P}(\text{coin 3}) = \frac13(p_1+p_2+p_3)\)
2. \(N_1 = X_1 + X_2\) where \(X_i \sim Bernoulli(p)\), therefore \(\mathbb{E}(N_1) = 2p\) and \(\textrm{Var}(N_1) = \textrm{Var}(X_1)+ \textrm{Var}(X_2) = p(1-p)+p(1-p) = 2p(1-p)\)
3. Let \(Y_i\) be the indicator for the \(i\)th coin is heads. Then \(\mathbb{E}(Y_i) = p\) and so \(\mathbb{E}(N_2) = 2p\). \begin{align*} && \textrm{Var}(N_2) &= \mathbb{E}(N_2^2) - [\mathbb{E}(N_2)]^2\\ &&&= 2^2 \cdot \left (\frac13 \left (p_1p_2+p_2p_3+p_3p_1 \right) \right) + 1 \cdot \left (\frac13 \left (p_1 (1-p_2) + (1-p_1)p_2 + p_2(1-p_3) +(1-p_2)p_3 + p_3(1-p_1) + (1-p_3)p_1 \right) \right) - [\mathbb{E}(N_2)]^2 \\ &&&= \frac43\left (p_1p_2+p_2p_3+p_3p_1 \right) + \frac13 \left ( 2(p_1+p_2+p_3) - 2(p_1p_2+p_2p_3+p_3p_1)\right)-[\mathbb{E}(N_2)]^2 \\ &&&= \frac23\left (p_1p_2+p_2p_3+p_3p_1 \right) + \frac23 \left ( p_1+p_2+p_3 \right)-[\mathbb{E}(N_2)]^2\\ &&&= \frac23\left (p_1p_2+p_2p_3+p_3p_1 \right) + \frac23 \left ( p_1+p_2+p_3 \right)-\left[\frac23(p_1+p_2+p_3)\right]^2\\ &&&= \frac23\left (p_1p_2+p_2p_3+p_3p_1 \right) +2p(1-2p)\\ \end{align*}
4. \(\,\) \begin{align*} && \textrm{Var}(N_1) - \textrm{Var}(N_2) &= 2p(1-p) - \left (\frac23\left (p_1p_2+p_2p_3+p_3p_1 \right) +2p(1-2p) \right) \\ &&&= 2p^2-\frac23\left (p_1p_2+p_2p_3+p_3p_1 \right) \\ &&&= \frac23 \left ( \frac13(p_1+p_2+p_3)^2 -\left (p_1p_2+p_2p_3+p_3p_1 \right)\right)\\ &&&= \frac29 \left (p_1^2+p_2^2+p_3^2 -(p_1p_2+p_2p_3+p_3p_1) \right)\\ &&&= \frac19 \left ((p_1-p_2)^2+(p_2-p_3)^2+(p_3-p_1)^2 \right) &\geq 0 \end{align*} with equality iff \(p_1 = p_2 = p_3\)

Solution:

1. Her probability of passing if she answers \(k \leq 2\) is \(0\), since she can attain at most \(4\) marks. If she attempts \(3\) questions, she needs to get all of them right, hence \(\mathbb{P}(\text{gets all }3\text{ correct}) = \frac{1}{n^3}\). If she attempts \(4\) questions, we can afford to get one wrong \begin{align*} && \mathbb{P}(\text{passes}|\text{attempts }4) &=\mathbb{P}(4/4) +\mathbb{P}(3/4) \\ &&&= \frac{1}{n^4} + 4\cdot\frac{1}{n^3} \cdot \frac{n-1}{n} \\ &&&= \frac{4n-3}{n^4} \end{align*} If she attempts \(5\) questions she can get \(5\) right (10), \(4\) right, \(1\) wrong (7), but \(3\) right will not work (\(6 - 2 = 4< 5\)), hence: \begin{align*} && \mathbb{P}(\text{passes}|\text{attempts }5) &=\mathbb{P}(5/5) +\mathbb{P}(4/5) \\ &&&= \frac{1}{n^5} + 5\cdot\frac{1}{n^4} \cdot \frac{n-1}{n} \\ &&&= \frac{5n-4}{n^5} \end{align*} If \(4n-3 > n \Leftrightarrow n \geq 2\) then \(4\) attempts is better than \(3\). If \(4n^2-3n > 5n-4 \Leftrightarrow 4n^2-8n+4 = 4(n-1)^2 > 0 \Leftrightarrow n \geq\) then \(4\) is better than \(5\), but \(n\) is \(\geq 2\) so, \(4\) is the best option.
2. \(\,\) \begin{align*} && \mathbb{P}(\text{passes}) &= \frac16 \cdot 0 + \frac16 \cdot 0 + \frac16 \cdot 0 + \frac16 \cdot \frac1{n^3} + \frac16 \frac{4n-3}{n^4} + \frac16 \frac{5n-4}{n^5} \\ &&&= \frac{n^2+4n^2-3n+5n-4}{6n^5} \\ &&&= \frac{5n^2+2n-4}{6n^5} \\ && \mathbb{P}(\text{answered }4|\text{passes}) &= \frac{\mathbb{P}(\text{answered }4\text{ and passes})}{ \mathbb{P}(\text{passes})} \\ &&&= \frac{\frac16 \cdot \frac{4n-3}{n^4}}{\frac{5n^2-2n-4}{6n^5} } \\ &&&= \frac{4n^2-3n}{5n^2+2n-4} \end{align*} Notice that the function takes all values for \(n\) between the roots of the denominator (which are either side of \(0\) and below \(3/4\). Therefore after \(3/4\) the function must be increase since otherwise we would have a quadratic equation with more than \(2\) roots.
3. \(\,\) \begin{align*} &&\mathbb{P}(C \text{ passes}) &= \binom{5}{3} \left ( \frac{n}{n+1} \right)^3 \left ( \frac{1}{n+1}\right)^2 \frac{1}{n^3} + \binom{5}{4} \left ( \frac{n}{n+1} \right)^4 \left ( \frac{1}{n+1}\right) \frac{4n-3}{n^4} +\\ &&&\quad \quad + \binom{5}{5} \left ( \frac{n}{n+1} \right)^5 \frac{5n-4}{n^5} \\ &&&= \frac{10}{(n+1)^5} + \frac{5(4n-3)}{(n+1)^5} + \frac{(5n-4)}{(n+1)^5} \\ &&&= \frac{10+20n-15+5n-4}{(n+1)^5}\\ &&&= \frac{25n-9}{(n+1)^5}\\ \end{align*}

Solution:

1. Since we either win \(h\) or \(0\), to calculate the expected winnings we just need to calculate the probability that we get \(h\) consecutive heads, therefore: \begin{align*} && \mathbb{E}(\text{winnings}) &= E_h \\ &&&= h \cdot \left ( \frac{N}{N+1} \right)^h \\ && \frac{E_{h+1}}{E_h} &= \frac{h+1}{h }\left ( \frac{N}{N+1} \right) \end{align*} Therefore \(E_h\) is increasing if \(h \leq N\), so we can maximise our winnings by taking \(h = N\). (In fact, we could take \(h = N\) or \(h = N+1\), but arguably \(h = N\) is better as we have the same expected value but lower variance).
2. We can have up to \(h\) tails appearing (if we imagine slots for tails of the form \(\underbrace{\_H\_H\_H\_\cdots\_H}_{h\text{ spaces and }h\, H}\) so, we have \begin{align*} && \mathbb{P}(\text{wins}) &= \sum_{t = 0}^h \mathbb{P}(\text{wins and } t\text{ tails}) \\ &&&= \sum_{t = 0}^h\binom{h}{t} \left ( \frac{N}{N+1} \right)^h\left ( \frac{1}{N+1} \right)^t \\ &&&= \left ( \frac{N}{N+1} \right)^h \sum_{t = 0}^h\binom{h}{t}\left ( \frac{1}{N+1} \right)^t \cdot 1^{h-t} \\ &&&= \left ( \frac{N}{N+1} \right)^h \left ( 1 + \left ( \frac{1}{N+1} \right) \right)^h \\ &&&= \left ( \frac{N}{N+1} \right)^h \left ( \frac{N+2}{N+1}\right)^h \\ &&&= \frac{N^h(N+2)^h}{(N+1)^{2h}} \\ \Rightarrow && \E(\text{winnings}) &= h \cdot \frac{N^h(N+2)^h}{(N+1)^{2h}} \end{align*} If \(N = 2\), we have \begin{align*} && \E(\text{winnings}) &= E_h \\ &&&= h \cdot \frac{2^h\cdot2^{2h}}{3^{2h}}\\ &&&= h \cdot \frac{2^{3h}}{3^{2h}} \\ \Rightarrow && \frac{E_{h+1}}{E_h} &= \frac{h+1}{h} \frac{8}{9} \\ \end{align*} Therefore to maximise the winnings we should take \(h = 8\), and the expected winnings will be: \begin{align*} && E_8 &= 8 \cdot \frac{2^{24}}{3^{16}} \\ \Rightarrow && \log_3 E_8 &= 27 \log_3 2 - 16 \\ &&&\approx 24 \cdot 0.63 - 16 \\ &&&\approx 17 - 16 \\ &&&\approx 1 \\ \Rightarrow && E_8 &\approx 3 \end{align*}

Solution:

1. \(\,\) \begin{align*} && A_1 &= \frac12 \\ && B_1 &= \frac14 \\ && C_1 &= 0 \\ && D_1 &= \frac14 \end{align*} \begin{align*} && A_2 &= \frac12 \cdot \frac12 + 2 \cdot \frac14 \cdot \frac14 = \frac38 \\ && B_2 &= \frac14 \cdot \frac12 + \frac12 \cdot \frac14 = \frac14 \\ && C_2 &=2 \cdot \frac14 \cdot \frac14 =\frac18 \\ && D_2 &= B_2 = \frac14 \end{align*}
2. \begin{align*} && A_{n+1} &= \frac12 A_n+ \frac14(B_n + D_n) \\ && B_{n+1} &= \frac12 B_n+ \frac14(A_n + C_n) \\ && C_{n+1} &= \frac12 C_n+ \frac14(D_n +B_n) \\ && D_{n+1} &= \frac12 D_n+ \frac14(C_n +A_n) \\ \\ \Rightarrow && B_{n+1}+D_{n+1} &= \frac12 (B_n+D_n) + \frac12(A_n+C_n) \\ &&&= \frac12 \\ \Rightarrow && B_{n+1}&=D_{n+1} = \frac14 \\ \\ && C_{n+1} &= \frac12C_n + \frac14 \cdot \frac12 \\ &&&= \frac12 C_n + \frac18\\ &&&= \frac12 C_{n-1} + \frac1{8} + \frac1{16} \\ &&&= \frac1{8} + \frac{1}{16} + \cdots + \frac{1}{8 \cdot 2^{n-1}} \\ &&&= \frac18 \left (1 + \frac12 + \cdots + \frac1{2^{n-1}} \right) \\ &&&= \frac18\left ( \frac{1-\frac1{2^n}}{1-\frac12} \right) \\ &&&= \frac18 \left (2 - \frac{1}{2^{n-1}} \right) \\ &&&= \frac14 - \frac{1}{2^{n-1}} \\ \Rightarrow && A_n &= \frac14 + \frac1{2^{n-1}} \end{align*}

Solution:

1. \begin{align*} && \mathbb{P}(Y_k \leq y) &= \sum_{j=k}^n\mathbb{P}(\text{exactly }j \text{ values less than }y) \\ &&&= \sum_{j=k}^m \binom{m}{j} y^j(1-y)^{n-j} \end{align*}
2. This is the number of ways to choose a committee of \(m\) people with the chair from those \(m\) people. This can be done in two ways. First: choose the committee in \(\binom{n}{m}\) ways and choose the chair in \(m\) ways so \(m \binom{n}{m}\). Alternatively, choose the chain in \(n\) ways and choose the remaining \(m-1\) committee members in \(\binom{n-1}{m-1}\) ways. Therefore \(m \binom{n}{m} = n \binom{n-1}{m-1}\) \begin{align*} (n-m) \binom{n}{m} &= (n-m) \binom{n}{n-m} \\ &= n \binom{n-1}{n-m-1} \\ &= n \binom{n-1}{m} \end{align*} \begin{align*} f_{Y_k}(y) &= \frac{\d }{\d y} \l \sum^{n}_{m=k}\binom{n}{m}y^{m}\left(1-y\right)^{n-m} \r \\ &= \sum^{n}_{m=k} \l \binom{n}{m}my^{m-1}\left(1-y\right)^{n-m} -\binom{n}{m}(n-m)y^{m}\left(1-y\right)^{n-m-1} \r \\ &= \sum^{n}_{m=k} \l n \binom{n-1}{m-1}y^{m-1}\left(1-y\right)^{n-m} -n \binom{n-1}{m} y^{m}\left(1-y\right)^{n-m-1} \r \\ &= n\sum^{n}_{m=k} \binom{n-1}{m-1}y^{m-1}\left(1-y\right)^{n-m} -n\sum^{n+1}_{m=k+1} \binom{n-1}{m-1} y^{m-1}\left(1-y\right)^{n-m} \\ &= n \binom{n-1}{k-1} y^{k-1}(1-y)^{n-k} \end{align*} \begin{align*} &&1 &= \int_0^1 f_{Y_k}(y) \d y \\ &&&= \int_0^1 n \binom{n-1}{k-1} y^{k-1}(1-y)^{n-k} \d y \\ &&&= n \binom{n-1}{k-1} \int_0^1 y^{k-1}(1-y)^{n-k} \d y \\ \Rightarrow && \frac{1}{n \binom{n-1}{k-1}} &= \int_0^1 y^{k-1}(1-y)^{n-k} \d y \\ \end{align*}
3. \begin{align*} && \mathbb{E}(Y_k) &= \int_0^1 y f_{Y_k}(y) \d y \\ &&&= \int_0^1 n \binom{n-1}{k-1} y^{k}(1-y)^{n-k} \\ &&&= n \binom{n-1}{k-1}\int_0^1 y^{k}(1-y)^{n-k} \d y \\ &&&= n \binom{n-1}{k-1}\int_0^1 y^{k+1-1}(1-y)^{n+1-(k+1)} \d y \\ &&&= n \binom{n-1}{k-1} \frac{1}{(n+1) \binom{n}{k}}\\ &&&= \frac{n}{n+1} \cdot \frac{k}{n} \\ &&&= \frac{k}{n+1} \end{align*}