Problems

Filters
Clear Filters

2 problems found

2016 Paper 2 Q12
D: 1600.0 B: 1503.2
probability principle of inclusion-exclusion derangements combinatorics proof fixed points permutations

Starting with the result \(\P(A\cup B) = \P(A)+P(B) - \P(A\cap B)\), prove that \[ \P(A\cup B\cup C) = \P(A)+\P(B)+\P(C) - \P(A\cap B) - \P(B\cap C) - \P(C \cap A) + \P(A\cap B\cap C) \,. \] Write down, without proof, the corresponding result for four events \(A\), \(B\), \(C\) and \(D\). A pack of \(n\) cards, numbered \(1, 2, \ldots, n\), is shuffled and laid out in a row. The result of the shuffle is that each card is equally likely to be in any position in the row. Let \(E_i\) be the event that the card bearing the number \(i\) is in the \(i\)th position in the row. Write down the following probabilities:

  1. \(\P(E_i)\);
  2. \(\P(E_i\cap E_j)\), where \(i\ne j\);
  3. \(\P(E_i\cap E_j\cap E_k)\), where \(i\ne j\), \(j\ne k\) and \(k\ne i\).
Hence show that the probability that at least one card is in the same position as the number it bears is \[ 1 - \frac 1 {2!} + \frac 1{3!} - \cdots + (-1)^{n+1} \frac 1 {n!}\,. \] Find the probability that exactly one card is in the same position as the number it bears

Solution: \begin{align*} && \mathbb{P}(A \cup B \cup C) &= \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cup B) \cap C) \tag{applying with \(A\cup B\) and \(C\)} \\ &&&= \mathbb{P}(A \cup B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C)) \\ &&&= \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \mathbb{P}((A \cap C) \cup (B \cap C)) \tag{applying with \(A\) and \(B\)}\\ &&&= \mathbb{P}(A)+\mathbb{P}(B) - \mathbb{P}(A\cap B) + \mathbb{P}(C) - \left ( \mathbb{P}(A \cap C) +\mathbb{P}(B \cap C) - \mathbb{P}( (A \cap C) \cap (B \cap C) )\right) \\ &&&= \mathbb{P}(A)+\mathbb{P}(B) +\mathbb{P}(C)- \mathbb{P}(A\cap B)- \mathbb{P}(A \cap C) -\mathbb{P}(B \cap C)+\mathbb{P}( A \cap B \cap C) \end{align*} \[ \mathbb{P}(A_1 \cup A_2 \cup A_3 \cup A_4) = \sum_i \mathbb{P}(A_i) - \sum_{i \neq j} \mathbb{P}(A_i \cap A_j) + \sum_{i \neq j \neq j} \mathbb{P}(A_i \cap A_j \cap A_k) - \mathbb{P}(A_1 \cap A_2 \cap A_3 \cap A_4) \]

  1. \(\mathbb{P}(E_i) = \frac{1}{n}\)
  2. \(\mathbb{P}(E_i \cap E_j) = \frac{1}{n} \cdot \frac{1}{n-1} = \frac{1}{n(n-1)}\)
  3. \(\mathbb{P})(E_i \cap E_j \cap E_k) = \frac{1}{n(n-1)(n-2)}\)
First notice that the probability that \(k\) (or more) cards are in the correct place is \(\frac{(n-k)!}{n!}\) (place the other \(n-k\) cards in any order. We are interested in: \begin{align*} \mathbb{P} \left ( \bigcup_{i=1}^n E_i \right) &= \sum_{i} \mathbb{P}(E_i) - \sum_{i \neq j} \mathbb{P}(E_i \cap E_j) + \sum_{i \neq j \neq k} \mathbb{P}(E_i \cap E_j \cap E_k) - \cdots \\ &= \sum_i \frac1n - \sum_{i\neq j} \frac{1}{n(n-1)} + \sum_{i \neq j \neq k} \frac{1}{n(n-1)(n-2)} - \cdots + (-1)^{k+1} \sum_{i_1 \neq i_2 \neq \cdots \neq i_k} \frac{(n-k)!}{n!} + \cdots\\ &= 1 - \binom{n}{2} \frac{1}{n(n-1)} + \binom{n}{3} \frac{1}{n(n-1)(n-2)} - \cdots + (-1)^{k+1} \binom{n}{k} \frac{(n-k)}{n!} + \cdots \\ &= 1 - \frac12 + \frac1{3!} - \cdots + (-1)^{k+1} \frac{n!}{k!(n-k)!} \frac{(n-k)!}{n!} + \cdots \\ &= 1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n+1} \frac{1}{n!} \end{align*} The probability exactly one card is in the right place is the probability none of the other \(n-1\) are in the right place, which is: \(\frac1n \left (1 - \left (1 - \frac1{2!} + \frac1{3!} - \cdots + (-1)^{k+1} \frac{1}{k!} + \cdots + (-1)^{n} \frac{1}{(n-1)!} \right) \right)\) but there are also \(n\) cards we can choose to be the card in the right place, hence \(\frac{1}{2!} - \frac{1}{3!} + \cdots +(-1)^n \frac{1}{(n-1)!}\)

View
2004 Paper 3 Q12
D: 1700.0 B: 1500.0
probability expectation variance covariance indicator random variables Poisson approximation Normal approximation derangements random permutation

A team of \(m\) players, numbered from \(1\) to \(m\), puts on a set of a \(m\) shirts, similarly numbered from \(1\) to \(m\). The players change in a hurry, so that the shirts are assigned to them randomly, one to each player. Let \(C_i\) be the random variable that takes the value \(1\) if player \(i\) is wearing shirt \(i\), and 0 otherwise. Show that \(\mathrm{E}\left(C_1\right)={1 \over m}\) and find \(\var \left(C_1\right)\) and \(\mathrm{Cov}\left(C_1 \, , \; C_2 \right) \,\). Let \(\, N = C_1 + C_2 + \cdots + C_m \,\) be the random variable whose value is the number of players who are wearing the correct shirt. Show that \(\mathrm{E}\left(N\right)= \var \left(N\right) = 1 \,\). Explain why a Normal approximation to \(N\) is not likely to be appropriate for any \(m\), but that a Poisson approximation might be reasonable. In the case \(m = 4\), find, by listing equally likely possibilities or otherwise, the probability that no player is wearing the correct shirt and verify that an appropriate Poisson approximation to \(N\) gives this probability with a relative error of about \(2\%\). [Use \(\e \approx 2\frac{72}{100} \,\).]

Solution: There are \(m!\) different ways of assigning the shirts, and in \((m-1)!\) of them player \(1\) gets their own shirt, ie \(\mathbb{E}(C_1) = \mathbb{P}(\text{player }1\text{ gets own shirt}) = \frac{(m-1)!}{m!} = \frac{1}{m}\). \(\var(C_1) = \mathbb{E}(C_1^2) - [\mathbb{E}(C_1)]^2 = \frac{1}{m} - \frac{1}{m^2} = \frac{m-1}{m^2}\). If we have two players, there are \((m-2)!\) ways they both get their own shirts, therefore \(\textrm{Cov}(C_1,C_2) = \mathbb{E}(C_1C_2) - \mathbb{E}(C_1)\mathbb{E}(C_2) = \frac{(m-2)!}{m!} - \frac{1}{m^2} = \frac{1}{m(m-1)} - \frac{1}{m^2} = \frac{m-m+1}{m^2(m-1)} = \frac{1}{m^2(m-1)}\). \begin{align*} \mathbb{E}(N) &= \mathbb{E}(C_1 + C_2 + \cdots + C_m) \\ &= \mathbb{E}(C_1) + \mathbb{E}(C_2) + \cdots + \mathbb{E}(C_m) \\ &= \frac{1}{m} + \frac{1}{m} +\cdots+ \frac1m \\ &= 1 \\ \\ \var(N) &= \sum_{r=1}^m \var(C_r) + 2\sum_{r=1}^{m-1} \sum_{s=2}^{m} \textrm{Cov}(C_r,C_s) \\ &= m \frac{m-1}{m^2} + 2 \frac{m(m-1)}{2}\frac{1}{m^2(m-1)} \\ &=\frac{m-1}{m} + \frac{1}{m} \\ &= 1 \end{align*} If we were to take a normal approximation, we would want to take \(N(1,1)\), but this would say things like \(-1\) is as likely as \(3\) shirts being correct, which is clearly a bad model. A Poisson is much more likely to be a sensible model as they have the same mean and variance as the parameter, and if \(m\) is large, the covariance between shirts is going to be very small, so it will appear similar to random events occurring. We can have \begin{align*} BADC \\ BCDA \\ BDAC \\ CADB \\ CDAB\\ CDBA \\ DABC\\ DCAB \\ DCBA \end{align*} Ie \(\frac{9}{24}\) ways to have no player wearing their own shirt with \(4\) players. \(Po(1)\) would say this probability is \(e^{-1}\), giving a relative error of: \begin{align*} \frac{e^{-1}-\frac{9}{24}}{\frac9{24}} &\approx \frac{\frac{100}{272} - \frac{9}{24}}{\frac9{24}} \\ &= -\frac{1}{51} \\ &\approx -2\% \end{align*}

View