Problems

Filters
Clear Filters

2 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
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