Problems

Filters
Clear Filters

1 problem found

2024 Paper 2 Q11
D: 1500.0 B: 1500.0
binomial distribution expected value curve sketching differentiation optimisation approximation group testing

  1. Sketch a graph of \(y = x^{\frac{1}{x}}\) for \(x > 0\), showing the location of any turning points. Find the maximum value of \(n^{\frac{1}{n}}\), where \(n\) is a positive integer.
\(N\) people are to have their blood tested for the presence or absence of an enzyme. Each person, independently of the others, has a probability \(p\) of having the enzyme present in a sample of their blood, where \(0 < p < 1\). The blood test always correctly determines whether the enzyme is present or absent in a sample. The following method is used.
  • The people to be tested are split into \(r\) groups of size \(k\), with \(k > 1\) and \(rk = N\).
  • In every group, a sample from each person in that group is mixed into one large sample, which is then tested.
  • If the enzyme is not present in the combined sample from a group, no further testing of the people in that group is needed.
  • If the enzyme is present in the combined sample from a group, a second sample from each person in that group is tested separately.
  1. Find, in terms of \(N\), \(k\) and \(p\), the expected number of tests.
  2. Given that \(N\) is a multiple of \(3\), find the largest value of \(p\) for which it is possible to find an integer value of \(k\) such that \(k > 1\) and the expected number of tests is at most \(N\). Show that this value of \(p\) is greater than \(\frac{1}{4}\).
  3. Show that, if \(pk\) is sufficiently small, the expected number of tests is approximately \[ N\!\left(\frac{1}{k} + pk\right). \] In the case where \(p = 0.01\), show that choosing \(k = 10\) gives an expected number of tests which is only about \(20\%\) of \(N\).

Solution:

  1. \(\,\)
    TikZ diagram
    \begin{align*} && y & = x^{1/x} = \exp \left ( \tfrac1x \ln x \right ) \\ \Rightarrow && y' &= \exp \left ( \tfrac1x \ln x \right ) \cdot \left ( \frac{1}{x^2} - \frac{\ln x}{x^2} \right ) \\ &&&= \frac{\exp \left ( \tfrac1x \ln x \right ) }{x^2}(1 - \ln x) \\ y' =0: && x &= e \end{align*} Therefore the largest integer values will be \(2\) or \(3\). Comparing \((2^{\frac12})^6 = 8 < 9 = (3^{1/3})^6\) we see the maximum value of \(n^{1/n}\) where \(n\) is an integer is \(\sqrt[3]{3}\)
  2. The number of tests is \(r\) plus however many groups fail times \(k\). The probability of a group failing is \(g = 1-(1-p)^k\) and the number of failing groups is \(\sim B(r, g)\) so the expected number of additional groups is \(rg\) and the expected total number of tests is \[ \frac{N}{k} + N(1-(1-p)^k) \]
  3. \(\,\) \begin{align*} && N &\geq E = \frac{N}{k} + N(1-(1-p)^k) \\ \Rightarrow && 1 &\geq \frac{1}{k} + 1-(1-p)^k \\ \Rightarrow && (1-p)^k &\geq \frac1k \\ \Rightarrow && k \ln(1-p) &\geq - \ln k \\ \Rightarrow && \ln(1 - p) &\geq -\frac{1}{k} \ln k \geq -\frac13 \ln 3 \\ \Rightarrow && 1-p &\geq \frac{1}{\sqrt[3]{3}} \\ \Rightarrow && p &\leq 1-\frac{1}{\sqrt[3]{3}} \end{align*} (taking \(k=3\)) Claim: \(1 - \frac{1}{\sqrt[3]{3}} > \frac14\) Proof: This is equivalent to \(\sqrt[3]{3} > \frac43\) or \(81 > 4^3 = 64\) which is clearly true.
  4. If \(pk\) is small then \((1-p)^k \approx 1 - pk\) and so we obtain \(N \left ( \frac1k +pk \right)\) as required. If \(p = 0.01\) and \(k = 10\) then \(\frac{1}{10} + 0.01 \cdot 10 = 0.2\) so the expected number of tests is \(\sim 20\%\) of \(N\)

View