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. 

   + - ↺
   re} \end{center}