Problems

Filters
Clear Filters

5 problems found

2014 Paper 2 Q13
D: 1600.0 B: 1469.5
probability uniform distribution discrete random variable expectation birthday problem summation identity proof

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

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

View
2010 Paper 1 Q12
D: 1500.0 B: 1508.1
probability discrete random variable expectation geometric distribution tail sum formula inequality optimisation coupon collector

A discrete random variable \(X\) takes only positive integer values. Define \(\E(X)\) for this case, and show that \[\E(X) =\sum^{\infty}_{n=1}\P\left(X\ge n \right).\] I am collecting toy penguins from cereal boxes. Each box contains either one daddy penguin or one mummy penguin. The probability that a given box contains a daddy penguin is \(p\) and the probability that a given box contains a mummy penguin is \(q\), where \(p\ne0\), \(q\ne0\) and \(p+q=1\,\). Let \(X\) be the number of boxes that I need to open to get at least one of each kind of penguin. Show that \(\P(X\ge 4)= p^{3}+q^{3}\), and that \[ \E(X)=\frac{1}{pq}-1.\, \] Hence show that \(\E(X)\ge 3\,\).

Solution: \[ \E[X] := \sum_{n=1}^{\infty} n \mathbb{P}(X=n) \] \begin{align*} && \sum^{\infty}_{n=1}\mathbb{P}\left(X\ge n \right) &= \sum^{\infty}_{n=1}\sum_{k=n}^\infty \mathbb{P}(X=k) \\ &&&= \sum_{k=1}^\infty k \cdot \mathbb{P}(X=k) \\ &&&= \E[X] \end{align*} \begin{align*} &&\mathbb{P}(X \geq 4) &= \mathbb{P}(\text{first 3 are daddies}) +\mathbb{P}(\text{first 3 are mummies}) \\ &&&= p^3 + q^3 \\ \Rightarrow && \E[X] &= \sum_{n=1}^{\infty} \mathbb{P}\left(X\ge n \right) \\ &&&= 1+\sum_{n=2}^{\infty} \left ( p^{n-1} + q^{n-1}\right) \\ &&&= 1+\frac{p}{1-p} + \frac{q}{1-q} \\ &&&= 1+\frac{p}q + \frac{q}p \\ &&&= 1+\frac{p^2+q^2}{pq} \\ &&&= 1+\frac{(p+q)^2-2pq}{pq} \\ &&&= \frac{1}{pq} -1 \\ &&& \underbrace{\geq}_{AM-GM} \frac{1}{4}-1 = 3 \end{align*}

View
2002 Paper 1 Q13
D: 1484.0 B: 1443.0
conditional probability quadratic equation real roots expected value cubic equation discrete random variable law of total probability

The random variable \(U\) takes the values \(+1\), \(0\) and \(-1\,\), each with probability \(\frac13\,\). The random variable \(V\) takes the values \(+1\) and \(-1\) as follows:

if \(U=1\,\),then \(\P(V=1)= \frac13\) and \(\P(V=-1)=\frac23\,\);
if \(U=0\,\),then \(\P(V=1)= \frac12\) and \(\P(V=-1)=\frac12\,\);
if \(U=-1\,\),then \(\P(V=1)= \frac23\) and \(\P(V=-1)=\frac13\,\).
  1. Show that the probability that both roots of the equation \(x^2+Ux+V=0\) are real is \(\frac12\;\).
  2. Find the expected value of the larger root of the equation \(x^2+Ux+V=0\,\), given that both roots are real.
  3. Find the probability that the roots of the equation $$x^3+(U-2V)x^2+(1-2UV)x + U=0$$ are all positive.

Solution:

  1. \(\,\) \begin{align*} && \mathbb{P}(\text{both roots real}) &= \mathbb{P}(\Delta \geq 0) \\ &&&= \mathbb{P}(U^2 \geq 4V) \\ &&&= \mathbb{P}(V = -1) \\ &&&= \tfrac13 ( \tfrac23 + \tfrac12 + \tfrac13) \\ &&&= \tfrac13 \cdot \tfrac 32 = \frac12 \end{align*}
  2. Our equations will be: \(x^2+x-1 = 0\) with larger root \(\frac{-1 + \sqrt{5}}{2}\) \(x^2-1 = 0\) with larger root \(1\) \(x^2-x-1 = 0\) with larger root \(\frac{1 + \sqrt5}{2}\) and the expected value is \begin{align*} && \E[\text{larger root}|\text{both real}] &= \frac23 \left ( \frac23 \cdot \frac{-1+\sqrt5}{2} + \frac12 \cdot 1 + \frac13 \cdot \frac{1+\sqrt5}{2} \right) \\ &&&= \frac23 \left ( \frac{2+3\sqrt5}{6} \right) \\ &&&= \frac{2+3\sqrt5}{9} \end{align*}
  3. Suppose we have \(x^3+(U-2V)x^2+(1-2UV)x + U = 0\), then for all roots to be positive, we need \(U < 0 \Rightarrow U = -1\) (otherwise there is a root at or below zero). Therefore our two possible cubics are: \(x^3 -3x^2+3x-1 = (x-1)^3\) (all roots positive) \(x^3+x^2-x-1 = (x-1)(x+1)^2\) (not all roots positive!) Therefore the probability is \(\frac13 \cdot \frac23 = \frac29\)

View
1996 Paper 3 Q13
D: 1700.0 B: 1516.0
probability expectation variance Chebyshev inequality discrete random variable inequality proof

Let \(X\) be a random variable which takes only the finite number of different possible real values \(x_{1},x_{2},\ldots,x_{n}.\) Define the expectation \(\mathbb{E}(X)\) and the variance \(\var(X)\) of \(X\). Show that , if \(a\) and \(b\) are real numbers, then \(\E(aX+b)=a\E(X)+b\) and express \(\var(aX+b)\) similarly in terms of \(\var(X)\). Let \(\lambda\) be a positive real number. By considering the contribution to \(\var(X)\) of those \(x_{i}\) for which \(\left|x_{i}-\E(X)\right|\geqslant\lambda,\) or otherwise, show that \[ \mathrm{P}\left(\left|X-\E(X)\right|\geqslant\lambda\right)\leqslant\frac{\var(X)}{\lambda^{2}}\,. \] Let \(k\) be a real number satisfying \(k\geqslant\lambda.\) If \(\left|x_{i}-\E(X)\right|\leqslant k\) for all \(i\), show that \[ \mathrm{P}\left(\left|X-\E(X)\right|\geqslant\lambda\right)\geqslant\frac{\var(X)-\lambda^{2}}{k^{2}-\lambda^{2}}\,. \]

Solution: Definition: \(\displaystyle \mathbb{E}(X) = \sum_{i=1}^n x_i \mathbb{P}(X = x_i)\) Definition: \(\displaystyle \mathrm{Var}(X) = \sum_{i=1}^n (x_i-\mathbb{E}(X))^2 \mathbb{P}(X = x_i)\) Claim: \(\mathbb{E}(aX+b) = a\mathbb{E}(X)+b\) Proof: \begin{align*} \mathbb{E}(aX+b) &= \sum_{i=1}^n (ax_i+b) \mathbb{P}(X = x_i) \\ &= a\sum_{i=1}^n x_i \mathbb{P}(X = x_i) + b\sum_{i=1}^n \mathbb{P}(X = x_i)\\ &= a \mathbb{E}(X) + b \end{align*} Claim: \(\mathrm{Var}(aX+b) = a^2 \mathrm{Var}(X)\) Claim: \(\mathrm{P}\left(\left|X-\mathrm{E}(X)\right|\geqslant\lambda\right)\leqslant\frac{\mathrm{var}(X)}{\lambda^{2}}\) Proof: \begin{align*} \mathrm{Var}(X) &= \sum_{i=1}^n (x_i-\mathbb{E}(X))^2 \mathbb{P}(X = x_i) \\ &\geq \sum_{|x_i - \mathbb{E}(X)| \geq \lambda} (x_i-\mathbb{E}(X))^2 \mathbb{P}(X = x_i) \\ &\geq \sum_{|x_i - \mathbb{E}(X)| \geq \lambda} \lambda^2 \mathbb{P}(X = x_i) \\ &= \lambda^2 \sum_{|x_i - \mathbb{E}(X)| \geq \lambda} \mathbb{P}(X = x_i) \\ &= \lambda^2 \mathrm{P}\left(\left|X-\mathrm{E}(X)\right|\geqslant\lambda\right) \end{align*} Claim: \[ \mathrm{P}\left(\left|X-\mathrm{E}(X)\right|\geqslant\lambda\right)\geqslant\frac{\mathrm{var}(X)-\lambda^{2}}{k^{2}-\lambda^{2}}\,. \] Proof: \begin{align*} && \mathrm{Var}(X) &= \sum_{i=1}^n (x_i-\mathbb{E}(X))^2 \mathbb{P}(X = x_i) \\ &&&= \sum_{|x_i - \mathbb{E}(X)| \geq \lambda} (x_i-\mathbb{E}(X))^2 \mathbb{P}(X = x_i) + \sum_{|x_i - \mathbb{E}(X)| < \lambda} (x_i-\mathbb{E}(X))^2 \mathbb{P}(X = x_i) \\ &&& \leq \sum_{|x_i - \mathbb{E}(X)| \geq \lambda} k^2 \mathbb{P}(X = x_i) + \sum_{|x_i - \mathbb{E}(X)| < \lambda} \lambda^2 \mathbb{P}(X = x_i) \\ &&&= k^2 \mathbb{P}\left(\left|X-\mathrm{E}(X)\right|\geqslant\lambda\right) + \lambda^2 \mathbb{P}\left(\left|X-\mathrm{E}(X)\right| < \lambda\right) \\ &&&= k^2 \mathbb{P}\left(\left|X-\mathrm{E}(X)\right|\geqslant\lambda\right) + \lambda^2(1- \mathbb{P}\left(\left|X-\mathrm{E}(X)\right| \leq \lambda\right) \\ &&&= (k^2 - \lambda^2) \mathbb{P}\left(\left|X-\mathrm{E}(X)\right|\geqslant\lambda\right) + \lambda^2 \\ \Rightarrow&& \frac{\mathrm{Var}(X)-\lambda^2}{k^2 - \lambda^2} &\leq \mathbb{P}\left(\left|X-\mathrm{E}(X)\right|\geqslant\lambda\right) \end{align*} [Note: This result is known as Chebyshev's inequality, and is an important starting point to understanding the behaviour of tails of random variables]

View
1991 Paper 2 Q15
D: 1600.0 B: 1484.0
probability uniform distribution expectation absolute difference summation discrete random variable random walk linearity of expectation

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

View