Problems

Filters
Clear Filters

3 problems found

2017 Paper 1 Q12
D: 1500.0 B: 1513.9
probability expected value uniform distribution lottery binomial distribution approximation exponential approximation optimisation

In a lottery, each of the \(N\) participants pays \(\pounds c\) to the organiser and picks a number from \(1\) to \(N\). The organiser picks at random the winning number from \(1\) to \(N\) and all those participants who picked this number receive an equal share of the prize, \(\pounds J\).

  1. The participants pick their numbers independently and with equal probability. Obtain an expression for the probability that no participant picks the winning number, and hence determine the organiser's expected profit. Use the approximation \[ \left( 1 - \frac{a}{N} \right)^N \approx \e^{-a} \tag{\(*\)} \] to show that if \(2Nc = J\) then the organiser will expect to make a loss. Note: \(\e > 2\).
  2. Instead of the numbers being equally popular, a fraction \(\gamma\) of the numbers are popular and the rest are unpopular. For each participant, the probability of picking any given popular number is \(\dfrac{a}{N}\) and the probability of picking any given unpopular number is \(\dfrac{b}{N}\,\). Find a relationship between \(a\), \(b\) and \(\gamma\). Show that, using the approximation \((*)\), the organiser's expected profit can be expressed in the form \[ A\e^{-a} + B\e^{-b} +C \,, \] where \(A\), \(B\) and \(C\) can be written in terms of \(J\), \(c\), \(N\) and \(\gamma\). In the case \(\gamma = \frac18\) and \(a=9b\), find \(a\) and \(b\). Show that, if \(2Nc = J\), then the organiser will expect to make a profit. Note: \(\e < 3\).

Solution:

  1. The probability no-one picks the winning number is \(\left ( 1 - \frac{1}{N}\right)^N \approx \frac1e\). \begin{align*} && \mathbb{E}(\text{profit}) &= Nc - (1-e^{-1})J \\ &&& < Nc -(1- \tfrac12 )J \\ &&& < Nc - \frac12 J \\ &&&= \frac{2Nc-J}{2} \end{align*} Therefore if \(J = 2Nc\) the expected profit is negative.
  2. \(\,\) \begin{align*} && 1 &= \sum_{\text{all numbers}} \mathbb{P}(\text{pick }i) \\ &&&= \sum_{\text{popular numbers}} \mathbb{P}(\text{pick }i)+\sum_{\text{unpopular numbers}} \mathbb{P}(\text{pick }i) \\ &&&=\gamma N \frac{a}{N} + (1-\gamma)N \frac{b}{N} \\ &&&= \gamma a + (1-\gamma)b \end{align*} \begin{align*} && \mathbb{P}(\text{no-one picks winning number}) &= \mathbb{P}(\text{no-one picks winning number} | \text{winning number is popular})\mathbb{P})(\text{winning number is popular}) + \\ &&&\quad + \mathbb{P}(\text{no-one picks} | \text{unpopular})\mathbb{P}(\text{unpopular}) \\ &&&= \left (1 - \frac{a}{N} \right)^N \gamma + \left (1 - \frac{b}{N} \right)^N (1-\gamma) \\ &&&\approx \gamma e^{-a} + (1-\gamma)e^{-b} \\ \\ && \mathbb{E}(\text{profit}) &= Nc - (1-\gamma e^{-a} - (1-\gamma)e^{-b})J \\ &&&= Nc-J+J\gamma e^{-a} +J(1-\gamma)e^{-b} \end{align*} If \(\gamma = \frac18\) and \(a=9b\), then \(1=\frac18 a + \frac78b = 2b \Rightarrow b = \frac12, a = \frac92\) and \begin{align*} && \mathbb{E}(\text{profit}) &= Nc-J +J\tfrac18e^{-9/2}+J\tfrac78e^{-1/2} \\ &&&= Nc-J+\tfrac18Je^{-1/2}(e^{-4}+7) \end{align*} If we can show \(e^{-1/2}\frac{e^{-4}+7}{8} > \frac12\) we'd be done, so \begin{align*} && e^{-1/2}\frac{e^{-4}+7}{8} &> \frac12 \\ \Leftrightarrow && e^{-4}+7 &>4e^{1/2} \\ \Leftrightarrow && 49+14e^{-4}+e^{-8} &>16e \\ \end{align*} But clearly the LHS \(>49\) and the RHS \(<48\) so we're done

View
2016 Paper 2 Q3
D: 1600.0 B: 1517.4
differentiation polynomials exponential approximation roots of polynomials proof by contradiction Rolle's theorem intermediate value theorem curve sketching

For each non-negative integer \(n\), the polynomial \(\f_n\) is defined by \[ \f_n(x) = 1 + x + \frac{x^2}{2!} + \frac {x^3}{3!} + \cdots + \frac{x^n}{n!} \]

  1. Show that \(\f'_{n}(x) = \f_{n-1}(x)\,\) (for \(n\ge1\)).
  2. Show that, if \(a\) is a real root of the equation \[\f_n(x)=0\,,\tag{\(*\)}\] then \(a<0\).
  3. Let \(a\) and \(b\) be distinct real roots of \((*)\), for \(n\ge2\). Show that \(\f_n'(a)\, \f_n'(b)>0\,\) and use a sketch to deduce that \(\f_n(c)=0\) for some number \(c\) between \(a\) and \(b\). Deduce that \((*)\) has at most one real root. How many real roots does \((*)\) have if \(n\) is odd? How many real roots does \((*)\) have if \(n\) is even?

Solution:

  1. \(\,\) \begin{align*} && f'_n(x) &= 0 + 1 + \frac{2x}{2!} + \frac{3x^2}{3!} + \cdots + \frac{nx^{n-1}}{n!} \\ &&&= 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots + \frac{x^{n-1}}{(n-1)!} \\ &&&= f_{n-1}(x) \end{align*}
  2. Claim: \(f_n(x) > 0\) for all \(x > 0\) Proof: (By induction) Base case: (\(n = 1\)) \(f_1(x) = 1 + x > 1\) therefore \(f_1(x) > 0\) Suppose it's true for \(n = k\), then consider \(f_{k+1}\), if we differentiate it, we find it is increasing on \((0, \infty)\) by our inductive hypothesis. But then \(f_{k+1}(0) = 1 > 0\). Therefore \(f_{k+1}(x) > 0\) as well. Therefore by the principle of mathematical induction we are done. Since \(f_n(x) > 0\) for non-negative \(x\), if \(a\) is a root it must be negative.
  3. Suppose \(f_n(a) = f_n(b) = 0\) then \(f'_n(a) = -\frac{a^n}{n!}\) and \(f'_n(b) = -\frac{b^n}{n!}\), but then \(f_n'(a) f_n'(b) = \frac{(-a)^n(-b)^n}{(n!)^2} > 0\) since \(a < 0, b < 0\). \(_n'(a) f_n'(b)\) is positive, the two gradients must have the same sign (and not be zero). Therefore if they are both increasing, at some point the curve must cross the axis in between. Therefore there is some root \(c\) between \(a\) and \(b\). But then there is also a root between \(c\) and \(a\) and \(c\) and \(b\), and very quickly we find more than \(n\) roots which is not possivel. Therefore there must be at most \(1\) root. If \(n\) is odd there must be exactly one root, since \(f_n\) changes sign as \(x \to -\infty\) vs \(x = 0\). If \(n\) is even then there can't be any roots, since if it crossed the \(x\)-axis there would be two roots (not possible) and it cannot touch the axis, since \(f'_n(a) \neq 0\) unless \(a = 0\), and we know \(a < 0\)

View
2007 Paper 2 Q13
D: 1600.0 B: 1669.0
probability birthday problem independent events exponential approximation combinatorics inequality logarithm

Given that \(0 < r < n\) and \(r\) is much smaller than \(n\), show that \(\dfrac {n-r}n \approx \e^{-r/n}\). There are \(k\) guests at a party. Assuming that there are exactly 365 days in the year, and that the birthday of any guest is equally likely to fall on any of these days, show that the probability that there are at least two guests with the same birthday is approximately \(1-\e^{-k(k-1)/730}\). Using the approximation \( \frac{253}{365} \approx \ln 2\), find the smallest value of \(k\) such that the probability that at least two guests share the same birthday is at least \(\frac12\). How many guests must there be at the party for the probability that at least one guest has the same birthday as the host to be at least \(\frac12\)?

Solution: Given \(0 < r \ll n\), then \(\frac{r}{n}\) is small and so, \(e^x \approx 1+x\), therefore: \(\displaystyle e^{-r/n} \approx 1 - \frac{r}{n} = \frac{n-r}{n}\). Line everyone in the room up in some order. The first person is always going to have a birthday we haven't seen before. The probability the second person has a new birthday is \(\displaystyle 1 - \frac{1}{365}\) since they can't be born on the same day as the first person. The third person has a \(\displaystyle 1 - \frac{2}{365}\) probability of having a birthday we've not seen before, since they can't share a birthday with either of the first two people. Similarly the \(k\)th person has a \(\displaystyle 1 - \frac{k-1}{365}\) chance of having a unique birthday. \begin{align*} \prod_{i=1}^k \mathbb{P}(\text{the } i \text{th person has a new birthday}) &= \prod_{i=1}^k \l 1 - \frac{i-1}{365}\r \\ &\approx \prod_{i=1}^k \exp \l -\frac{i-1}{365}\r \\ &= \exp\l - \sum_{i=1}^k\frac{i-1}{365}\r \\ &= \exp\l - \frac{k(k-1)}{2\cdot365}\r \\ &= e^{-k(k-1)/730} \end{align*} But this the probability no-one shares a birthday, so the answer we are looking for is \(1-\) this, ie \(1 - e^{-k(k-1)/730}\) Suppose \(1 - e^{-k(k-1)/730} = \frac12\), then \begin{align*} && 1 - e^{-k(k-1)/730} &= \frac12 \\ \Rightarrow && e^{-k(k-1)/730} &= \frac12 \\ \Rightarrow && -k(k-1)/730 &= -\ln 2 \\ \Rightarrow && k(k-1)/730 &\approx \frac{253}{365} \\ \Rightarrow && k(k-1) &\approx 506 \end{align*} Therefore since \(22 \cdot 23 = 506\), we should expect the number to be approximately \(23\). Since \(e^{-r/n} > \frac{n-r}{n}\) we should expect this to be an overestimate, therefore \(23\) should suffice.

View