Problems

Filters
Clear Filters

1 problem found

2017 Paper 2 Q13
D: 1600.0 B: 1516.0
probability negative binomial distribution geometric distribution expected value binomial expansion partial fractions divergent series sampling with replacement sampling without replacement

In a television game show, a contestant has to open a door using a key. The contestant is given a bag containing \(n\) keys, where \(n\ge2\). Only one key in the bag will open the door. There are three versions of the game. In each version, the contestant starts by choosing a key at random from the bag.

  1. In version 1, after each failed attempt at opening the door the key that has been tried is put back into the bag and the contestant again selects a key at random from the bag. By considering the binomial expansion of \(( 1 - q)^{-2}\), or otherwise, find the expected number of attempts required to open the door.
  2. In version 2, after each failed attempt at opening the door the key that has been tried is put aside and the contestant selects another key at random from the bag. Find the expected number of attempts required to open the door.
  3. In version 3, after each failed attempt at opening the door the key that has been tried is put back into the bag and another incorrect key is added to the bag. The contestant then selects a key at random from the bag. Show that the probability that the contestant draws the correct key at the \(k\)th attempt is \[ \frac{n-1}{(n+k-1)(n+k-2)} \,.\] Show also, using partial fractions, that the expected number of attempts required to open the door is infinite. You may use without proof the result that \(\displaystyle\sum_{m=1}^N \dfrac 1 m \to \infty \,\) as \(N\to \infty\,\).

Solution:

  1. The probability they pull the key out on the \(k\)th attempt will be \(\left ( \frac{n-1}{n} \right)^{k-1} \frac1n\), so we want: \begin{align*} \E[G_1] &= \sum_{k=1}^{\infty} k \cdot \left ( \frac{n-1}{n} \right)^{k-1} \frac1n \\ &= \frac{1}n \sum_{k=1}^{\infty} k \cdot \left ( \frac{n-1}{n} \right)^{k-1} \\ &= \frac1n \frac{1}{\left (1 - \frac{n-1}{n} \right)^2} \\ &= \frac{1}{n} \frac{n^2}{1^2} = n \end{align*}
  2. In version 2, the probability the correct key comes out at the \(k\)th attempt is \(\frac1n\) (assume we take out all the keys, then the correct key is equally likely to appear in all of the space). Therefore \(\E[G_2] = \frac1n (1 + 2 + \cdots + n) = \frac{n+1}{2}\)
  3. The probability the key comes out on the correct attempt is: \begin{align*} && \mathbb{P}(G_3 = k) &= \frac{n-1}{n} \cdot \frac{n}{n+1} \cdot \frac{n+1}{n+2} \cdots \frac{n+k-3}{n+k-2} \cdot \frac{1}{n+k-1} \\ &&&= \frac{n-1}{(n+k-2)(n+k-1)} \\ \\ &&k \cdot \mathbb{P}(G_3 = k) &= \frac{k(n-1)}{(n+k-2)(n+k-1)} \\ &&&= \frac{(n-1)(2-n)}{n+k-2} + \frac{(n-1)^2}{n+k-1} \\ &&&= \frac{(n-1)^2}{n+k-1} - \frac{(n-1)^2}{n+k-2} + \frac{n-1}{n-k+2} \\ \Rightarrow && \E[G_3] &= \sum_{k=1}^{\infty} k \cdot \mathbb{P}(G_3 = k) \\ &&&= \sum_{k=1}^{\infty} \left ( \frac{(n-1)^2}{n+k-1} - \frac{(n-1)^2}{n+k-2} + \frac{n-1}{n+k-2} \right) \\ &&&= \sum_{k=1}^{\infty} \left ( \frac{(n-1)^2}{n+k-1} - \frac{(n-1)^2}{n+k-2} \right) +\underbrace{\sum_{k=1}^{\infty} \frac{n-1}{n-k+2}}_{\to \infty} \\ \end{align*}

View