Problems

Filters
Clear Filters

13 problems found

2025 Paper 3 Q12
D: 1500.0 B: 1484.0
probability discrete probability distributions conditional probability expectation recurrence relation double summation interchange of summation order geometric series

  1. Show that, for any functions \(f\) and \(g\), and for any \(m \geq 0\), $$\sum_{r=1}^{m+1} f(r)\sum_{s=r-1}^m g(s) = \sum_{s=0}^m g(s)\sum_{r=1}^{s+1} f(r)$$
  2. The random variables \(X_0, X_1, X_2, \ldots\) are defined as follows:
    • \(X_0\) takes the value \(0\) with probability \(1\);
    • \(X_{n+1}\) takes the values \(0, 1, \ldots, X_n + 1\) with equal probability, for \(n = 0, 1, \ldots\)
    1. Write down \(E(X_1)\). Find \(P(X_2 = 0)\) and \(P(X_2 = 1)\) and show that \(P(X_2 = 2) = \frac{1}{6}\). Hence calculate \(E(X_2)\).
    2. For \(n \geq 1\), show that $$P(X_n = 0) = \sum_{s=0}^{n-1} \frac{P(X_{n-1} = s)}{s+2}$$ and find a similar expression for \(P(X_n = r)\), for \(r = 1, 2, \ldots, n\).
    3. Hence show that \(E(X_n) = \frac{1}{2}(1 + E(X_{n-1}))\). Find an expression for \(E(X_n)\) in terms of \(n\), for \(n = 1, 2, \ldots\)

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

View
2024 Paper 2 Q12
D: 1500.0 B: 1500.0
discrete probability distributions combinatorics summation formulas conditional probability independence counting arguments

In this question, you may use without proof the results \[ \sum_{i=1}^{n} i^2 = \tfrac{1}{6}n(n+1)(2n+1) \quad \text{and} \quad \sum_{i=1}^{n} i^3 = \tfrac{1}{4}n^2(n+1)^2. \] Throughout the question, \(n\) and \(k\) are integers with \(n \geqslant 3\) and \(k \geqslant 2\).

  1. In a game, \(k\) players, including Ada, are each given a random whole number from \(1\) to \(n\) (that is, for each player, each of these numbers is equally likely and assigned independently of all the others). A player wins the game if they are given a smaller number than all the other players, so there may be no winner in this game. Find an expression, in terms of \(n\), \(k\) and \(a\), for the probability that Ada is given number \(a\), where \(1 \leqslant a \leqslant n-1\), and all the other players are given larger numbers. Hence show that, if \(k = 4\), the probability that there is a winner in this game is \[ \frac{(n-1)^2}{n^2}\,. \]
  2. In a second game, \(k\) players, including Ada and Bob, are each given a random whole number from \(1\) to \(n\). A player wins the game if they are given a smaller number than all the other players or if they are given a larger number than all the other players, so it is possible for there to be zero, one or two winners in this game. Find an expression, in terms of \(n\), \(k\) and \(d\), for the probability that Ada is given number \(a\) and Bob is given number \(a + d + 1\), where \(1 \leqslant d \leqslant n-2\) and \(1 \leqslant a \leqslant n - d - 1\), and all the other players are given numbers greater than \(a\) and less than \(a + d + 1\). Hence show that, if \(k = 4\), the probability that there are two winners in this game is \[ \frac{(n-2)(n-1)^2}{n^3}\,. \] If \(k = 4\), what is the minimum value of \(n\) for which there are more likely to be exactly two winners than exactly one winner in this game?

Solution:

  1. Suppose Ada is given \(a\), then she wins if the other \(k-1\) players all get a number between \(a+1\) and \(n\). Since each of these choices are independent, this occurs with probability: \begin{align*} && \mathbb{P}(\text{Ada wins with }a) &= \left ( \frac{n-a}{n} \right)^{k-1} \\ \\ && \mathbb{P}(\text{Ada wins}) &= \sum_{a=1}^{n-1} \mathbb{P}(\text{Ada wins with }a) \mathbb{P}(\text{Ada has }a) \\ &&&= \sum_{a=1}^{n-1}\frac{1}{n}\left ( \frac{n-a}{n} \right)^{3}\\ &&&= \frac{1}{n^4} \sum_{a=1}^{n-1} (n-a)^3 \\ &&&= \frac{1}{n^4} \sum_{a=1}^{n-1} a^3 \\ &&&= \frac{1}{n^4} \tfrac14(n-1)^2n^2 \\ &&&= \frac{(n-1)^2}{4n^2} \end{align*} Since each the game is symmetric, each player is equally likely to win, therefore the probability anyone wins is \(\displaystyle \frac{(n-1)^2}{n^2}\)
  2. The probability that Ada gets \(a\), Bob gets \(a+d+1\) and the other players are in between is \begin{align*} && \mathbb{P}(\text{event}) &= \mathbb{P}(\text{Ada gets }a) \mathbb{P}(\text{Bob gets }a+d+1) \mathbb{P}(\text{everyone else between}) \\ &&&= \frac1{n^2} \cdot \left ( \frac{d}{n} \right) ^{k-2} \end{align*} Therefore the probability that Ada and Bob jointly win is \begin{align*} && \mathbb{P}(\text{Ada and Bob win}) &= \sum_{d=1}^{n-2} \sum_{a=1}^{n-d-1} \frac{1}{n^4} d^2 \\ &&&= \frac{1}{n^4} \sum_{d=1}^{n-2} (n-1-d) d^2 \\ &&&= \frac{n-1}{n^4} \frac{(n-2)(n-1)(2n-3)}{6} - \frac{1}{n^4} \frac{(n-2)^2(n-1)^2}{4} \\ &&&= \frac{(n-1)^2(n-2)}{12n^4} \left ( 2(2n-3)-3(n-2) \right) \\ &&&= \frac{(n-1)^2(n-2)}{12n^3} \\ \end{align*} There are \(4\) players so there are \(4\) ways to choose the lowest player and \(3\) remaining ways to choose the highest, so we get \(\displaystyle \frac{(n-2)(n-1)^2}{n^3}\) probability of a winner happening. The probability of there being a highest winner is the same as the probability of there being a lowest winner (both \(\frac{(n-1)^2}{n^2}\)) and the probability of there being exactly one winner is therefore \begin{align*} && P_1 &= P_{\geq1}-P_2+P_{\geq1}-P_2 \\ \end{align*} this is less than \(P_2\) iff \begin{align*} && P_{\geq1}+P_{\geq1}-2P_2 &< P_2 \\ \Leftrightarrow && 2P_{\geq 1} & < 3P_2 \\ \Leftrightarrow && \frac{2(n-1)^2}{n^2} &< \frac{3(n-1)^2(n-2)}{n^3} \\ \Leftrightarrow && 2n&<3(n-2) \\ \Leftrightarrow && 6 &< n \end{align*} So \(n = 7\)

View
2023 Paper 3 Q12
D: 1500.0 B: 1500.0
combinatorics discrete probability distributions expected value binomial coefficient counting arguments random variables

A drawer contains \(n\) pairs of socks. The two socks in each pair are indistinguishable, but each pair of socks is a different colour from all the others. A set of \(2k\) socks, where \(k\) is an integer with \(2k \leqslant n\), is selected at random from this drawer: that is, every possible set of \(2k\) socks is equally likely to be selected.

  1. Find the probability that, among the socks selected, there is no pair of socks.
  2. Let \(X_{n,k}\) be the random variable whose value is the number of pairs of socks found amongst those selected. Show that \[\mathrm{P}(X_{n,k} = r) = \frac{\dbinom{n}{r}\dbinom{n-r}{2(k-r)}\, 2^{2(k-r)}}{\dbinom{2n}{2k}}\] for \(0 \leqslant r \leqslant k\).
  3. Show that \[r\,\mathrm{P}(X_{n,k} = r) = \frac{k(2k-1)}{2n-1}\,\mathrm{P}(X_{n-1,k-1} = r-1)\,,\] for \(1 \leqslant r \leqslant k\), and hence find \(\mathrm{E}(X_{n,k})\).

View
2022 Paper 2 Q11
D: 1500.0 B: 1500.0
discrete probability distributions expected value optimisation binomial distribution calculus hypothesis testing conditional probability

A batch of \(N\) USB sticks is to be used on a network. Each stick has the same unknown probability \(p\) of being infected with a virus. Each stick is infected, or not, independently of the others. The network manager decides on an integer value of \(T\) with \(0 \leqslant T < N\). If \(T = 0\) no testing takes place and the \(N\) sticks are used on the network, but if \(T > 0\), the batch is subject to the following procedure.

  • Each of \(T\) sticks, chosen at random from the batch, undergoes a test during which it is destroyed.
  • If any of these \(T\) sticks is infected, all the remaining \(N - T\) sticks are destroyed.
  • If none of the \(T\) sticks is infected, the remaining \(N - T\) sticks are used on the network.
If any stick used on the network is infected, the network has to be disinfected at a cost of \(\pounds D\), where \(D > 0\). If no stick used on the network is infected, there is a gain of \(\pounds 1\) for each of the \(N - T\) sticks. There is no cost to testing or destroying a stick.
  1. Find an expression in terms of \(N\), \(T\), \(D\) and \(q\), where \(q = 1 - p\), for the expected net loss.
  2. Let \(\alpha = \dfrac{DT}{N(N - T + D)}\). Show that \(0 \leqslant \alpha < 1\). Show that, for fixed values of \(N\), \(D\) and \(T\), the greatest value of the expected net loss occurs when \(q\) satisfies the equation \(q^{N-T} = \alpha\). Show further that this greatest value is \(\pounds\dfrac{D(N-T)\,\alpha^k}{N}\), where \(k = \dfrac{T}{N-T}\).
  3. For fixed values of \(N\) and \(D\), show that there is some \(\beta > 0\) so that for all \(p < \beta\), the expression for the expected loss found in part (i) is an increasing function of \(T\). Deduce that, for small enough values of \(p\), testing no sticks minimises the expected net loss.

View
2020 Paper 2 Q12
D: 1500.0 B: 1500.0
discrete probability distributions inequality biased die sum of squares expected value double summation probability comparison

The score shown on a biased \(n\)-sided die is represented by the random variable \(X\) which has distribution \(\mathrm{P}(X = i) = \dfrac{1}{n} + \varepsilon_i\) for \(i = 1, 2, \ldots, n\), where not all the \(\varepsilon_i\) are equal to \(0\).

  1. Find the probability that, when the die is rolled twice, the same score is shown on both rolls. Hence determine whether it is more likely for a fair die or a biased die to show the same score on two successive rolls.
  2. Use part (i) to prove that, for any set of \(n\) positive numbers \(x_i\) (\(i = 1, 2, \ldots, n\)), \[\sum_{i=2}^{n}\sum_{j=1}^{i-1} x_i x_j \leqslant \frac{n-1}{2n}\left(\sum_{i=1}^{n} x_i\right)^2.\]
  3. Determine, with justification, whether it is more likely for a fair die or a biased die to show the same score on three successive rolls.

View
2020 Paper 3 Q12
D: 1500.0 B: 1500.0
geometric distribution independence joint distribution discrete probability distributions convolution order statistics absolute difference

\(A\) and \(B\) both toss the same biased coin. The probability that the coin shows heads is \(p\), where \(0 < p < 1\), and the probability that it shows tails is \(q = 1 - p\). Let \(X\) be the number of times \(A\) tosses the coin until it shows heads. Let \(Y\) be the number of times \(B\) tosses the coin until it shows heads.

  1. The random variable \(S\) is defined by \(S = X + Y\) and the random variable \(T\) is the maximum of \(X\) and \(Y\). Find an expression for \(\mathrm{P}(S = s)\) and show that \[ \mathrm{P}(T = t) = pq^{t-1}(2 - q^{t-1} - q^t). \]
  2. The random variable \(U\) is defined by \(U = |X - Y|\), and the random variable \(W\) is the minimum of \(X\) and \(Y\). Find expressions for \(\mathrm{P}(U = u)\) and \(\mathrm{P}(W = w)\).
  3. Show that \(\mathrm{P}(S = 2 \text{ and } T = 3) \neq \mathrm{P}(S = 2) \times \mathrm{P}(T = 3)\).
  4. Show that \(U\) and \(W\) are independent, and show that no other pair of the four variables \(S\), \(T\), \(U\) and \(W\) are independent.

View
2009 Paper 1 Q13
D: 1500.0 B: 1504.1
probability discrete probability distributions expectation combinatorics arrangements counting arguments permutations

I seat \(n\) boys and \(3\) girls in a line at random, so that each order of the \(n+3\) children is as likely to occur as any other. Let \(K\) be the maximum number of consecutive girls in the line so, for example, \(K=1\) if there is at least one boy between each pair of girls.

  1. Find \(\P(K=3)\).
  2. Show that \[\P(K=1)= \frac{n(n-1)}{(n+2)(n+3)}\,. \]
  3. Find \(\E(K)\).

Solution:

  1. If all the girls are say together there are \(n+1\) ways to place the block of 3 girls. There are \(\binom{n+3}{3}\) ways to choose where to place the girls in total, therefore: \begin{align*} && \mathbb{P}(K =3) &= \frac{n+1}{\binom{n+3}3} \\ &&&= \frac{6(n+1)}{(n+3)(n+2)(n+1)} \\ &&&= \frac{6}{(n+3)(n+2)} \end{align*}
  2. If \(K= 1\) then all of the girls are separated. We can place three girls and two boys separating them, then we are allocating \(N-2\) boys to \(4\) gaps, ie \(\binom{N-2+3}{3} = \binom{N+1}{3}\). \begin{align*} && \mathbb{P}(K=3) &= \frac{\binom{n+1}{3}}{\binom{n+3}{3}} \\ &&&= \frac{(n+1)n(n-1)}{(n+3)(n+2)(n+1)} \\ &&&= \frac{n(n-1)}{(n+3)(n+2)} \end{align*}
  3. \(\,\) \begin{align*} \mathbb{E}(K) &= \sum_{k=1}^3 k \mathbb{P}(K=k) \\ &= \frac{6}{(n+3)(n+2)} + 2 \left (1 - \frac{6}{(n+3)(n+2)} - \frac{n(n-1)}{(n+3)(n+2)} \right) + 3\frac{n(n-1)}{(n+3)(n+2)} \\ &= 2+\frac{6-12+n(n-1)}{(n+3)(n+2)} \\ &= 2 + \frac{n^2-n-6}{(n+2)(n+3)}\\ &= 2 + \frac{(n-3)(n+2)}{(n+2)(n+3)} \\ &= 2 + \frac{n-3}{n+3} \\ &= \frac{2n}{n+3} \end{align*}

View
2008 Paper 3 Q13
D: 1700.0 B: 1500.0
probability expected value variance indicator random variables linearity of expectation harmonic series combinatorics discrete probability distributions

A box contains \(n\) pieces of string, each of which has two ends. I select two string ends at random and tie them together. This creates either a ring (if the two ends are from the same string) or a longer piece of string. I repeat the process of tying together string ends chosen at random until there are none left. Find the expected number of rings created at the first step and hence obtain an expression for the expected number of rings created by the end of the process. Find also an expression for the variance of the number of rings created. Given that \(\ln 20 \approx 3\) and that \(1+ \frac12 + \cdots + \frac 1n \approx \ln n\) for large \(n\), determine approximately the expected number of rings created in the case \(n=40\,000\).

Solution: Let \(X_i\) be the indicator variable a loop is formed when there are \(i\) strings in the bag, so \(\mathbb{P}(X_i = 1) = \frac{1}{2i-1}\). Therefore \begin{align*} && Y_n &= X_n + Y_{n-1} \\ && Y_n &= X_n + \cdots + X_1 \\ \Rightarrow && \E[Y_n] &= \frac{1}{2n-1} + \frac{1}{2n-3} + \cdots + \frac{1}{1} \\ && \var[Y_n] &= \sum_{i=1}^n \frac{1}{2i-1} \frac{2i-2}{2i-1} \\ &&&= 2\sum_{i=1}^n \frac{i-1}{(2i-1)^2} \end{align*} \begin{align*} && \E[Y_{n}] &= 1 + \frac13 + \cdots + \frac{1}{2n-1} \\ &&&= 1 + \frac12 + \cdots + \frac1{2n} - \frac12\left (1 + \frac12 + \cdots + \frac1n \right) \\ &&&\approx \ln 2n -\frac12 \ln n \\ &&&= \ln 2 \sqrt{n} \\ \\ && \E[Y_{40\,000}] &= \ln 2 \sqrt{40\,000} \\ &&&= \ln 400 \\ &&&= 2 \ln 20 \approx 6 \end{align*}

View
2007 Paper 3 Q13
D: 1700.0 B: 1500.0
probability discrete probability distributions recurrence relation expected value random walk first passage time geometric series approximation

A frog jumps towards a large pond. Each jump takes the frog either \(1\,\)m or \(2\,\)m nearer to the pond. The probability of a \(1\,\)m jump is \(p\) and the probability of a \(2\,\)m jump is \(q\), where \(p+q=1\), the occurence of long and short jumps being independent.

  1. Let \(p_n(j)\) be the probability that the frog, starting at a point \((n-\frac12)\,\)m away from the edge of the pond, lands in the pond for the first time on its \(j\)th jump. Show that \(p_2(2)=p\).
  2. Let \(u_n\) be the expected number of jumps, starting at a point \((n-\frac12)\,\)m away from the edge of the pond, required to land in the pond for the first time. Write down the value of \(u_1\). By finding first the relevant values of \(p_n(m)\), calculate \(u_2\) and show that $u_3= 3-2q+q^2\(.
  3. Given that \)u_n\( can be expressed in the form \)u_n= A(-q)^{n-1} +B +Cn$, where \(A\), \(B\) and \(C\) are constants (independent of \(n\)), show that \(C= (1+q)^{-1}\) and find \(A\) and \(B\) in terms of \(q\). Hence show that, for large \(n\), \(u_n \approx \dfrac n{p+2q}\) and explain carefully why this result is to be expected.

View
2004 Paper 2 Q13
D: 1600.0 B: 1500.0
probability conditional discrete probability distributions expected value optimisation without replacement hypergeometric sequential decision

A bag contains \(b\) balls, \(r\) of them red and the rest white. In a game the player must remove balls one at a time from the bag (without replacement). She may remove as many balls as she wishes, but if she removes any red ball, she loses and gets no reward at all. If she does not remove a red ball, she is rewarded with \pounds 1 for each white ball she has removed. If she removes \(n\) white balls on her first \(n\) draws, calculate her expected gain on the next draw and show that %her expected total reward would be the same as before it is zero if \(\ds n = {b-r \over r+1}\,\). Hence, or otherwise, show that she will maximise her expected total reward if she aims to remove \(n\) balls, where \[ n = \mbox{ the integer part of } \ds {b + 1 \over r + 1}\;. \] With this value of \(n\), show that in the case \(r=1\) and \(b\) even, her expected total reward is \(\pounds {1 \over 4}b\,\), and find her expected total reward in the case \(r=1\) and \(b\) odd.

View
2003 Paper 1 Q12
D: 1500.0 B: 1484.0
probability expected value discrete probability distributions sampling with replacement sampling without replacement summation double summation

In a bag are \(n\) balls numbered 1, 2, \(\ldots\,\), \(n\,\). When a ball is taken out of the bag, each ball is equally likely to be taken.

  1. A ball is taken out of the bag. The number on the ball is noted and the ball is replaced in the bag. The process is repeated once. Explain why the expected value of the product of the numbers on the two balls is \[ \frac 1 {n^2} \sum_{r=1}^n\sum_{s=1}^n rs \] and simplify this expression.
  2. A ball is taken out of the bag. The number on the ball is noted and the ball is not replaced in the bag. Another ball is taken out of the bag and the number on this ball is noted. Show that the expected value of the product of the two numbers is \[ \frac{(n+1)(3n+2)}{12}\;. \]
Note: \(\displaystyle \sum_{r=1}^n r = \frac12 n(n+1)\) and \(\displaystyle \sum_{r=1}^n r^2 = \frac16 n(n+1)(2n+1)\;\).

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

View
1999 Paper 2 Q14
D: 1600.0 B: 1516.0
probability expected value optimisation strategy fair die sequential decision discrete probability distributions stopping problem

You play the following game. You throw a six-sided fair die repeatedly. You may choose to stop after any throw, except that you must stop if you throw a 1. Your score is the number obtained on your last throw. Determine the strategy that you should adopt in order to maximize your expected score, explaining your reasoning carefully.

Solution: Once you have thrown, all previous throws are irrelevant so the only thing which can affect your decision is the current throw. Therefore the strategy must consist of a list of states we re-throw from, and a list of states we stick on. It must also be the case that if we stick on \(k\) we stick on \(k+1\) (otherwise we can improve our strategy by switching those two values around). Therefore we can form a table of our expected score: \begin{array}{c|c|c} \text{stop on} & \text{possible outcomes} & \E[\text{score}] \\ \hline \geq 2 & \{1,2,3,4,5,6\} & \frac{21}{6} = 3.5 \\ \geq 3 & \{1,3,4,5,6\} & \frac{19}{5} = 3.8 \\ \geq 4 & \{1,4,5,6\} & \frac{16}{4} = 4 \\ \geq 5 & \{1,5,6\} & \frac{12}{3} = 4 \\ =6 & \{1,6\} & \frac{7}{2} = 3.5 \end{array} Therefore the optimal strategy is to stop on \(4\) or higher. If we cared about variance we might look at the variance of the two best strategies, \(4\) or higher has a variance of \(\frac{1+16+25+36}{4} - 16 = 3.5\) and \(5\) or higher has a variance of \(\frac{1+25+36}3 - 16 = \frac{14}3 > 3.5\) so \(4\) or higher is probably better in most scenarios.

View
1990 Paper 1 Q14
D: 1500.0 B: 1500.7
probability conditional expected value discrete probability distributions optimisation strategy sequential decision balls in bag

A bag contains 5 white balls, 3 red balls and 2 black balls. In the game of Blackball, a player draws a ball at random from the bag, looks at it and replaces it. If he has drawn a white ball, he scores one point, while for a red ball he scores two points, these scores being added to his total score before he drew the ball. If he has drawn a black ball, the game is over and his final score is zero. After drawing a red or white ball, he can either decide to stop, when his final score for the game is the total so far, or he may elect to draw another ball. The starting score is zero. Juggins' strategy is to continue drawing until either he draws a black ball (when of course he must stop, with final score zero), or until he has drawn three (non-black) balls, when he elects to stop. Find the probability that in any game he achieves a final score of zero by employing this strategy. Find also his expected final score. Muggins has so far scored \(N\) points, and is deciding whether to draw another ball. Find the expected score if another ball is drawn, and suggest a strategy to achieve the greatest possible average final score in each game.

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

View