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. \(G(x) = \frac{1}{6} (1 + x + x^2 + x^3 + x^4 + x^5)\) The pgf for \(R_2\) is: \begin{align*} \frac1{36}x^2 + \frac{2}{36}x^3 + \frac{3}{36}x^4 + \frac{4}{36}x^5 + \frac{5}{36} +\\ \quad \quad + \frac{6}{36}x^1 + \frac{5}{36}x^2 + \frac4{36}x^3 + \frac3{36}x^4 + \frac{2}{36}x^5 + \frac{1}{36} \\ = \frac{1}{6}(1 + x + x^2 + x^3 + x^4 + x^5) = G(x) \end{align*} Since rolling the dice twice is the same as rolling the dice once, rolling the dice \(n\) times will be the same as rolling it once, ie the pgf for \(R_n\) will be \(G(x)\) and the probability \(S_n\) is divisible by \(6\) is \(\frac16\)
2. \(G_1(x) = \frac{1}{6} + \frac{1}{3}x^1 + \frac{1}{6}x^2 + \frac16x^3+ \frac16x^4 = \frac16(1 + 2x+x^2+x^3+x^4)\). If \(G_n\) is the probability generating function for \(T_n\) then we can obtain \(G_n\) by multiplying \(G_{n-1}\) by \(G(x)\) and replacing any terms of order higher than \(5\) with their remainder on division by \(5\). (Or equivalently, working over \(\mathbb{R}[x]/(x^5-1)\). If \(y = 1 + x + x^2 + x^3 + x^4\) then: \begin{align*} xy &= x + x^2 + x^3 + x^4 +x^5 \\ &= x + x^2 + x^3 + x^4 + 1 \\ &= y \\ \\ y^2 &= (1 + x+x^2 + x^3+x^4)^2 \\ &= 1 + 2x + 3x^2 + 4x^3+5x^4+4x^5+3x^6 + 2x^7 + x^8 \\ &= (1+4) + (2+3)x+(3+2)x^2 + (4+1)x^3 + 5x^4 \\ &= 5y \end{align*} \begin{align*} \frac{1}{36}(y+x)(y+x) &= \frac1{36}(y^2 + 2xy + x^2) \\ &= \frac1{36}(5y + 2y + x^2 ) \\ &= \frac1{36}(7y + x^2) \end{align*} Similarly, \begin{align*} G_n(x) &= \l\frac{1}{6}(x+y) \r^n \\ &= \frac1{6^n} \l \sum_{i=0}^n \binom{n}{i} y^ix^{n-i} \r \\ &= \frac1{6^n} \l \sum_{i=1}^n \binom{n}{i} y^i + x^n \r \\ &= \frac1{6^n} \l \sum_{i=1}^n \binom{n}{i} 5^{i-1}y + x^n \r \\ &= \frac1{6^n} \l \frac{1}{5}y((5+1)^n-1) + x^n \r \\ &= \frac1{6^n} \l \frac{1}{5}y(6^n-1) + x^n \r \\ \end{align*} Therefore if \(n \not \equiv 0 \pmod{5}\), we can find the probability of \(T_n = 0\) by looking at the constant coefficient, ie plugging in \(x = 0\), which is: \[\frac1{6^n} \l \frac{1}{5}(6^n-1) \r = \frac{1}{5} \l 1- \frac{1}{6^n} \r \] When \(n \equiv 0 \pmod{5}\) we can also find the constant coefficient by plugging in \(x = 0\), which is: \[\frac1{6^n} \l \frac{1}{5}(6^n-1) + 1 \r = \frac{1}{5} \l 1+ \frac{4}{6^n} \r \]

Solution:

1. \(\,\) \begin{align*} \mathbb{P}(\text{stop after r}) &= \mathbb{P}(\text{both stop at r}) + 2\mathbb{P}(\text{first stops before r second stops at r})\\ &= (q^2)^{r-1} p^2 + 2\cdot q^{r-1} p\cdot(1-q^{r-1}) \\ &= q^{r-1}p\left (2-2q^{r-1}+pq^{r-1} \right) \\ &= q^{r-1}p\left (2-q^{r-1}(1+p+q-p) \right) \\ &= q^{r-1}p\left (2-q^{r-1}-q^r\right) \\ \end{align*} \begin{align*} \E[\text{throws}] &= \sum_{r=1}^{\infty} r \mathbb{P}(\text{stop after r}) \\ &= \sum_{r=1}^{\infty} r q^{r-1}p\left (2-q^{r-1}-q^r\right) \\ &= \sum_{r=1}^{\infty} 2r q^{r-1}p-\sum_{r=1}^{\infty}r pq^{2r-2}-\sum_{r=1}^{\infty}r q^{2r-1}p \\ &=2p \sum_{r=1}^{\infty} r q^{r-1}-pq^{-2}\sum_{r=1}^{\infty}r q^{2r}-pq^{-1}\sum_{r=1}^{\infty}r q^{2r} \\ &= 2p(1-q)^{-2} - pq^{-2}q^2(1-q^2)^{-2}-pq^{-1}q^2(1-q^2)^{-2} \\ &= 2pp^{-2} -p(1+q)(1-q^2)^{-2} \\ &= 2p^{-1}-p(1+q)(1+q)^{-2}p^{-2} \\ &= 2p^{-1}-p^{-1}(1+q)^{-1} \\ &= \frac{2(1+q)-1}{p(1+q)} \\ &= \frac{1+2q}{p(1+q)} \\ &= \frac{3-2p}{p(2-p)} \end{align*}
2. \(\,\) \begin{align*} && m &= \frac{3-2p}{p(2-p)} \\ \Rightarrow && 2mp-mp^2 &= 3-2p \\ \Rightarrow && 0 &= mp^2-(2m+2)p + 3 \\ \Rightarrow && p &= \frac{2m+2 \pm \sqrt{(2m+2)^2-12m}}{2m} \\ &&&= \frac{m+1- \sqrt{m^2-m + 1}}{m} \\ \end{align*} If we are looking for an approximation, we could say \(p^2 \approx 0\) and \(p \approx \frac{3}{2(m+1)}\)

Solution:

1. Notice that if \(x > 0\) we must have \begin{align*} && \left ( \sqrt{x} - \frac{1}{\sqrt{x}} \right)^2 &\geq 0 \\ \Leftrightarrow && x - 2 + x^{-1} & \geq 0 \\ \Leftrightarrow && x + x^{-1} & \geq 2 \end{align*} Let \(S\) be the sum, and assume all probabilities are equal \begin{align*} && \mathbb{P}(S = 2) &= q_1 r_1 \\ && \mathbb{P}(S = 12) &= q_6 r_6 \\ && \mathbb{P}(S = 7) &= \sum_{i=1}^6 q_i r_{7-i} \\ \Rightarrow && q_1r_1 &= q_6r_6 \\ \Rightarrow && q_1r_6+q_6r_1 &\leq q_1r_1 \\ \Rightarrow && \frac{r_6}{r_1} + \frac{q_6}{q_1} &\leq 1 \\ \Rightarrow && q_1r_6+q_6r_1 &\leq q_6r_6 \\ \Rightarrow && \frac{q_1}{q_6} + \frac{r_1}{r_6} &\leq 1 \\ \Rightarrow && \frac{r_6}{r_1} + \frac{q_6}{q_1}+\frac{q_1}{q_6} + \frac{r_1}{r_6} &\leq 2\\ \text{but} && \frac{r_6}{r_1} + \frac{q_6}{q_1}+\frac{q_1}{q_6} + \frac{r_1}{r_6} &\geq 4 \end{align*} Since we have a contradiction they cannot all be equal.
2. We would like \(\displaystyle \sum q_i^2 \leq 1/36\) (subject to \(\displaystyle \sum q_i = 1\), clearly this cannot be true since: \begin{align*} && 1 &= \left ( \sum_{i=1}^6 q_i \right)^2 \\ &&&= \sum_{i=1}^6 q_i^2 + \sum_{i \neq j} 2q_i q_j \\ &&&\leq \sum_{i=1}^6 q_i^2 + 5\sum_{i=1}^6 q_i^2 \\ &&&=6 \sum_{i=1}^6 q_i^2 \\ \Rightarrow && \sum_{i=1}^6 q_i^2 &\geq 1/6 > 1/36 \end{align*} [For a weaker solution to the last part, notice that the largest value of \(q_i\) is \(\geq 1/6\) and therefore \(q_{max}^2 \geq 1/36\), but if equality holds then the other values must also be non-zero, and therefore the inequality cannot hold]