Uniform Distribution

Showing 1-6 of 6 problems
2019 Paper 2 Q11
D: 1500.0 B: 1500.0

  1. The three integers \(n_1\), \(n_2\) and \(n_3\) satisfy \(0 < n_1 < n_2 < n_3\) and \(n_1 + n_2 > n_3\). Find the number of ways of choosing the pair of numbers \(n_1\) and \(n_2\) in the cases \(n_3 = 9\) and \(n_3 = 10\). Given that \(n_3 = 2n + 1\), where \(n\) is a positive integer, write down an expression (which you need not prove is correct) for the number of ways of choosing the pair of numbers \(n_1\) and \(n_2\). Simplify your expression. Write down and simplify the corresponding expression when \(n_3 = 2n\), where \(n\) is a positive integer.
  2. You have \(N\) rods, of lengths \(1, 2, 3, \ldots, N\) (one rod of each length). You take the rod of length \(N\), and choose two more rods at random from the remainder, each choice of two being equally likely. Show that, in the case \(N = 2n + 1\) where \(n\) is a positive integer, the probability that these three rods can form a triangle (of non-zero area) is $$\frac{n - 1}{2n - 1}.$$ Find the corresponding probability in the case \(N = 2n\), where \(n\) is a positive integer.
  3. You have \(2M + 1\) rods, of lengths \(1, 2, 3, \ldots, 2M + 1\) (one rod of each length), where \(M\) is a positive integer. You choose three at random, each choice of three being equally likely. Show that the probability that the rods can form a triangle (of non-zero area) is $$\frac{(4M + 1)(M - 1)}{2(2M + 1)(2M - 1)}.$$ Note: \(\sum_{k=1}^{K} k^2 = \frac{1}{6}K(K + 1)(2K + 1)\).

Show Solution
  1. If \(n_3 = 9\) and we are looking for \(0 < n_1 < n_2 < n_3\) we can consider values for each \(n_2\). \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 4-5 & 2 \\ 7 & 3-6 & 4 \\ 8 & 2-7 & 6 \\ \hline & & 12 \end{array} When \(n_3 = 10\) \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 5 & 1 \\ 7 & 4-6 & 3 \\ 8 & 3-7 & 5 \\ 9 & 2-8 & 7 \\ \hline & & 16 \end{array} When \(n_3 = 2n+1\) we can have \(2 + 4 + \cdots + 2n-2 = n(n-1)\) When \(n_3 = 2n\) we can have \(1 + 3 + \cdots + 2n-3 = (n-1)^2\)
  2. For the 3 rods to form a triangle, it suffices for the sum of the lengths of the shorter rods to be larger than \(N\). When \(N = 2n+1\) there are \(n(n-1)\) ways this can happen, out of \(\binom{2n}{2}\) ways to choos the numbers, ie \begin{align*} && P &= \frac{n(n-1)}{\frac{2n(2n-1)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*} When \(N = 2n\) there are \((n-1)^2\) ways this can happen, out of \(\binom{2n-1}{2}\) ways, ie \begin{align*} && P &= \frac{(n-1)^2}{\frac{(2n-1)(2n-2)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*}
  3. The number of ways this can happen is: \begin{align*} C &= \sum_{k=3}^{2M+1} \# \{ \text{triangles where }k\text{ is largest} \} \\ &= \sum_{k=1}^{M} \# \{ \text{triangles where }2k+1\text{ is largest} \} +\sum_{k=1}^{M} \# \{ \text{triangles where }2k\text{ is largest} \}\\ &= \sum_{k=1}^{M} n(n-1)+\sum_{k=1}^{M} (n-1)^2\\ &= \sum_{k=1}^{M} (2n^2-3n+1)\\ &= \frac26M(M+1)(2M+1) - \frac32M(M+1) + M \\ &= \frac16 M(4M+1)(M-1) \end{align*} Therefore the probability is \begin{align*} && P &= \frac{M(4M+1)(M-1)}{6 \binom{2M+1}{3}} \\ &&&= \frac{M(4M+1)(M-1)}{(2M+1)2M(2M-1)} \\ &&&= \frac{(4M+1)(M-1)}{2(2M+1)(2M-1)} \end{align*}
2017 Paper 1 Q12
D: 1500.0 B: 1513.9

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

Show 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
2014 Paper 2 Q13
D: 1600.0 B: 1469.5

A random number generator prints out a sequence of integers \(I_1, I_2, I_3, \dots\). Each integer is independently equally likely to be any one of \(1, 2, \dots, n\), where \(n\) is fixed. The random variable \(X\) takes the value \(r\), where \(I_r\) is the first integer which is a repeat of some earlier integer. Write down an expression for \(\mathbb{P}(X=4)\).

  1. Find an expression for \(\mathbb{P}(X=r)\), where \(2\le r\le n+1\). Hence show that, for any positive integer \(n\), \[ \frac 1n + \left(1-\frac1n\right) \frac 2 n + \left(1-\frac1n\right)\left(1-\frac2n\right) \frac3 n + \cdots \ = \ 1 \,. \]
  2. Write down an expression for \(\mathbb{E}(X)\). (You do not need to simplify it.)
  3. Write down an expression for \(\mathbb{P}(X\ge k)\).
  4. Show that, for any discrete random variable \(Y\) taking the values \(1, 2, \dots, N\), \[ \mathbb{E}(Y) = \sum_{k=1}^N \mathbb{P}(Y\ge k)\,. \] Hence show that, for any positive integer \(n\), \[ \left(1-\frac{1^2}n\right) + \left(1-\frac1n\right)\left(1-\frac{2^2}n\right) + \left(1-\frac1n\right)\left(1-\frac{2}n\right)\left(1-\frac{3^2}n\right) + \cdots \ = \ 0. \]

Show Solution
\begin{align*} && \mathbb{P}(X > 4) &= 1 \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdot \frac{n-3}{n} \\ && \mathbb{P}(X > 3) &= 1 \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \\ \Rightarrow && \mathbb{P}(X =4) &= \mathbb{P}(X > 3) - \mathbb{P}(X > 4) \\ &&&= \frac{(n-1)(n-2)}{n^2} \left (1 - \frac{n-3}{n} \right) \\ &&&= \frac{3(n-1)(n-2)}{n^3} \end{align*}
  1. Notice that \begin{align*} && \mathbb{P}(X > r) &= \frac{n-1}{n} \cdots \frac{n-r+1}{n} \\ \Rightarrow && \mathbb{P}(X = r) &= \frac{n-1}{n} \cdots \frac{n-r+2}{n} \left (1 - \frac{n-r+1}{n} \right) \\ &&&= \frac{(n-1)\cdots(n-r+2)(r-1)}{n^{r-1}} \\ &&&= \left (1 - \frac{1}n \right)\left (1 - \frac{2}{n} \right) \cdots \left (1 - \frac{r-2}{n} \right) \frac{r-1}{n} \\ \Rightarrow && 1 &= \sum \mathbb{P}(X = r) \\ &&&= \sum_{r=2}^{n+1} \mathbb{P}(X = r) \\ &&&= \frac 1n + \left(1-\frac1n\right) \frac 2 n + \left(1-\frac1n\right)\left(1-\frac2n\right) \frac3 n + \cdots \end{align*}
  2. \(\,\) \begin{align*} \mathbb{E}(X) &= \sum_{r=2}^{n+1} r\cdot\mathbb{P}(X = r) \\ &= \frac 2n + \left(1-\frac1n\right) \frac {2\cdot3} n + \left(1-\frac1n\right)\left(1-\frac2n\right) \frac{3\cdot4} n + \cdots \end{align*}
  3. \(\displaystyle \mathbb{P}(X \geq k) = \frac{n-1}{n} \cdots \frac{n-r+2}{n}\)
  4. \(\,\) \begin{align*} && \mathbb{E}(Y) &= \sum_{r=1}^N r \cdot \mathbb{P}(Y = r) \\ &&&= \sum_{r=1}^N \sum_{j=1}^r \mathbb{P}(Y = r) \\ &&&= \sum_{j=1}^N \sum_{r=j}^N \mathbb{P}(Y=r) \\ &&&= \sum_{j=1}^N \mathbb{P}(Y \geq j) \end{align*} Let \(P_k = \left(1-\frac1n\right)\left(1-\frac2n\right) \cdots \left(1-\frac1n\right)\left(1-\frac{k}n\right) \) \begin{align*} && \mathbb{E}(X) &= P_1 \frac{1 \cdot 2 }{n} + P_2 \cdot \frac{2 \cdot 3}{n} + \cdots + P_k \cdot \frac{k(k+1)}{n} + \cdots \\ && &= \sum_{k=1}^{n} \frac{k^2}{n}P_k + \sum_{k=1}^{n} \frac{k}{n}P_k \\ && \text{Using the identity } & \frac{k}{n}P_k = \frac{k}{n} \prod_{i=1}^{k-1} \left(1-\frac{i}{n}\right) = P_k - P_{k+1}: \\ && \sum_{k=1}^{n} \frac{k}{n}P_k &= (P_1 - P_2) + (P_2 - P_3) + \cdots + (P_n - P_{n+1}) \\ && &= P_1 - P_{n+1} = 1 - 0 = 1 \\ \\ \Rightarrow && \mathbb{E}(X) &= \sum_{k=1}^{n} \frac{k^2}{n}P_k + 1 \\ && &= \mathbb{P}(X \geq 1) + \mathbb{P}(X \geq 2) + \mathbb{P}(X \geq 3) + \cdots \\ && &= 1 + P_1 + P_2 + P_3 + \cdots \\ && &= 1 + \sum_{k=1}^{n} P_k \\ \\ \Rightarrow && 1 + \sum_{k=1}^{n} P_k &= \sum_{k=1}^{n} \frac{k^2}{n}P_k + 1 \\ \Rightarrow && \sum_{k=1}^{n} P_k &= \sum_{k=1}^{n} \frac{k^2}{n}P_k \\ \Rightarrow && 0 &= \sum_{k=1}^{n} P_k \left( 1 - \frac{k^2}{n} \right) \end{align*}
1991 Paper 2 Q15
D: 1600.0 B: 1484.0

Integers \(n_{1},n_{2},\ldots,n_{r}\) (possibly the same) are chosen independently at random from the integers \(1,2,3,\ldots,m\). Show that the probability that \(\left|n_{1}-n_{2}\right|=k\), where \(1\leqslant k\leqslant m-1\), is \(2(m-k)/m^{2}\) and show that the expectation of \(\left|n_{1}-n_{2}\right|\) is \((m^{2}-1)/(3m)\). Verify, for the case \(m=2\), the result that the expection of \(\left|n_{1}-n_{2}\right|+\left|n_{2}-n_{3}\right|\) is \(2(m^{2}-1)/(3m).\) Write down the expectation, for general \(m\), of \[ \left|n_{1}-n_{2}\right|+\left|n_{2}-n_{3}\right|+\cdots+\left|n_{r-1}-n_{r}\right|. \] Desks in an examination hall are placed a distance \(d\) apart in straight lines. Each invigilator looks after one line of \(m\) desks. When called by a candidate, the invigilator walks to that candidate's desk, and stays there until called again. He or she is equally likely to be called by any of the \(m\) candidates in the line but candidates never call simultaneously or while the invigilator is attending to another call. At the beginning of the examination the invigilator stands by the first desk. Show that the expected distance walked by the invigilator in dealing with \(N+1\) calls is \[ \frac{d(m-1)}{6m}[2N(m+1)+3m]. \]

1988 Paper 2 Q15
D: 1600.0 B: 1516.0

An examination consists of several papers, which are marked independently. The mark given for each paper can be an integer from \(0\) to \(m\) inclusive, and the total mark for the examination is the sum of the marks on the individual papers. In order to make the examination completely fair, the examiners decide to allocate the mark for each paper at random, so that the probability that any given candidate will be allocated \(k\) marks \((0\leqslant k\leqslant m)\) for a given paper is \((m+1)^{-1}\). If there are just two papers, show that the probability that a given candidate will receive a total of \(n\) marks is \[ \frac{2m-n+1}{\left(m+1\right)^{2}} \] for \(m< n\leqslant2m\), and find the corresponding result for \(0\leqslant n\leqslant m\). If the examination consists of three papers, show that the probability that a given candidate will receive a total of \(n\) marks is \[ \frac{6mn-4m^{2}-2n^{2}+3m+2}{2\left(m+1\right)^{2}} \] in the case \(m< n\leqslant2m\). Find the corresponding result for \(0\leqslant n\leqslant m\), and deduce the result for \(2m< n\leqslant3m\).

Show Solution
In order to receive \(n\) marks over the two papers, where \(m < n \leq 2m\) the student must receive \(k\) and \(n-k\) marks in each paper. Since \(n > m\), \(n-k\) is a valid mark when \(n-k \leq m\) ie when \(n-m\leq k\), therefore the probability is: \begin{align*} \sum_{k = n-m}^m \mathbb{P}(\text{scores }k\text{ and }n-k) &= \sum_{k=n-m}^m \frac{1}{(m+1)^2} \\ &= \frac{m-(n-m-1)}{(m+1)^2} \\ &= \frac{2m-n+1}{(m+1)^2} \end{align*} If \(0 \leq n \leq m\) then we need \(n-k\) marks in the second paper to be positive, ie \(n-k \geq 0 \Rightarrow n \geq k\), so \begin{align*} \sum_{k = 0}^n \mathbb{P}(\text{scores }k\text{ and }n-k) &= \sum_{k = 0}^n \frac{1}{(m+1)^2} \\ &= \frac{n+1}{(m+1)^2} \end{align*} On the first paper, they can score any number of marks, since \(n > m\), so we must have: \begin{align*} \sum_{k=0}^m \mathbb{P}(\text{scores }k\text{ and }n-k) &= \frac{1}{m+1} \sum_{k=0}^m \mathbb{P}(\text{scores }n-k\text{ on second papers}) \\ &= \frac{1}{m+1}\l \sum_{k=0}^{n-m} \frac{2m-(n-k)+1}{(m+1)^2} +\sum_{k=n-m+1}^m \frac{n-k+1}{(m+1)^2}\r \end{align*}
1987 Paper 3 Q16
D: 1500.0 B: 1500.0

  1. \(X_{1},X_{2},\ldots,X_{n}\) are independent identically distributed random variables drawn from a uniform distribution on \([0,1].\) The random variables \(A\) and \(B\) are defined by \[ A=\min(X_{1},\ldots,X_{n}),\qquad B=\max(X_{1},\ldots,X_{n}). \] For any fixed \(k\), such that \(0< k< \frac{1}{2},\) let \[ p_{n}=\mathrm{P}(A\leqslant k\mbox{ and }B\geqslant1-k). \] What happens to \(p_{n}\) as \(n\rightarrow\infty\)? Comment briefly on this result.
  2. Lord Copper, the celebrated and imperious newspaper proprietor, has decided to run a lottery in which each of the \(4,000,000\) readers of his newspaper will have an equal probability \(p\) of winning \(\pounds 1,000,000\) and their changes of winning will be independent. He has fixed all the details leaving to you, his subordinate, only the task of choosing \(p\). If nobody wins \(\pounds 1,000,000\), you will be sacked, and if more than two readers win \(\pounds 1,000,000,\) you will also be sacked. Explaining your reasoning, show that however you choose \(p,\) you will have less than a 60\% change of keeping your job.

Show Solution
  1. \begin{align*} && p_n &= \mathrm{P}(A\leqslant k\mbox{ and }B\geqslant1-k) \\ &&&= \mathrm{P}(A\leqslant k) +\P(B\geqslant1-k) - \mathrm{P}(A\leqslant k\mbox{ or }B\geqslant1-k)\\ &&&= 1-\mathrm{P}(A\geq k) +1-\P(B \leq 1-k) - \l 1- \mathrm{P}(A\geq k\mbox{ and }B\leq 1-k)\r\\ &&&= 1 - \P(X_i \geq k) - \P(X_i \leq 1-k) + \P(k \leq X_i \leq 1-k) \\ &&&= 1 - k^n - (1-k)^n + (1-2k)^n \end{align*} Therefore as \(n \to \infty\) \(p_n \to 1\), since \(k, (1-k), (1-2k)\) are all between \(0\) and \(1\) and so their powers will tend to \(0\).
  2. Let \(N = 4\,000\,000\). The probability exactly one person wins is \(Np(1-p)^{N-1}\). The probability exactly two people win is \(\binom{N}{2} p^2 (1-p)^{N-2}\). We wish to maximise the sum of these probabilities. To find this maximum, differentiate wrt \(p\). \begin{align*} \frac{\d}{\d p} : && \small N(1-p)^{N-1}-N(N-1)p(1-p)^{N-2} + N(N-1)p(1-p)^{N-2} - \frac12 N(N-1)(N-2)p^2(1-p)^{N-3} \\ &&= N(1-p)^{N-3} \l (1-p)^2 - \frac12(N-1)(N-2)p^2\r \\ \Rightarrow && \frac{(1-p)}{p} = \sqrt{\frac{(N-1)(N-2)}{2}} \\ \Rightarrow && p = \frac{1}{1+ \sqrt{\frac{(N-1)(N-2)}{2}}} \end{align*} This will be a maximum, since this is an increasing function at \(p=0\) and decreasing at \(p=1\) and there's only one stationary point. Note that \(p > \frac{\sqrt{2}}{(N-2)}\) and \(p < \frac{\sqrt{2}}{N-1+\sqrt{2}} < \frac{\sqrt{2}}{N}\) and so: \begin{align*} Np(1-p)^{N-1} &< \sqrt{2}(1-\frac{\sqrt{2}}{N-2})^{N-1} \\ &\approx \sqrt{2} e^{-\sqrt{2}} \end{align*} \begin{align*} \frac{N(N-1)}{2}p^2(1-p)^{N-2} &<(1-\frac{\sqrt{2}}{N-2})^{N-1} \\ &\approx e^{-\sqrt{2}} \end{align*} Alternatively, we can use a Poisson approximation. The number of winners is \(B(N, p)\) where we are hoping \(np\) is small but not zero. Therefore it's reasonable to approximation \(B(N,p)\) by \(Po(Np)\). (Call this value \(\lambda\)). Then we wish to maximise: \begin{align*} && p &= e^{-\lambda} \l \lambda + \frac{\lambda^2}{2} \r \\ &&&= e^{-\lambda} \lambda \l 1+ \frac{\lambda}{2} \r \\ \Rightarrow && \ln p &= -\lambda + \ln \lambda + \ln(1+\frac12 \lambda) \\ \frac{\d}{\d \lambda}: && \frac{p'}{p} &= -1 + \frac{1}{\lambda} + \frac{1}{2+\lambda} \\ &&&= \frac{-(2+\lambda)\lambda+2+2\lambda}{\lambda(2+\lambda)} \\ &&&= \frac{2-\lambda^2}{\lambda(2+\lambda)} \\ \Rightarrow && \lambda &= \sqrt{2} \end{align*} \begin{align*} \frac{\sqrt{2}+1}{e^{\sqrt{2}}} &< \frac{\sqrt{2}+1}{1+\sqrt{2}+1+\frac{1}{3}\sqrt{2}+\frac{1}{6}} \\ &= \frac{30\sqrt{2}-18}{41} \end{align*} Either way, we find we want to estimate \(e^{-\sqrt{2}}(1+\sqrt{2})\)