68 problems found
A list consists only of letters \(A\) and \(B\) arranged in a row. In the list, there are \(a\) letter \(A\)s and \(b\) letter \(B\)s, where \(a\ge2\) and \(b\ge2\), and \(a+b=n\). Each possible ordering of the letters is equally probable. The random variable \(X_1\) is defined by \[ X_1 = \begin{cases} 1 & \text{if the first letter in the row is \(A\)};\\ 0 & \text{otherwise.} \end{cases} \] The random variables \(X_k\) (\(2 \le k \le n\)) are defined by \[ X_k = \begin{cases} 1 & \text{if the \((k-1)\)th letter is \(B\) and the \(k\)th is \(A\)};\\ 0 & \text{otherwise.} \end{cases} \] The random variable \(S\) is defined by \(S = \sum\limits_ {i=1}^n X_i\,\).
Solution:
I choose at random an integer in the range 10000 to 99999, all choices being equally likely. Given that my choice does not contain the digits 0, 6, 7, 8 or 9, show that the expected number of different digits in my choice is 3.3616.
Solution: We are choosing any \(5\) digit number from \(\{1,2,3,4,5\}\). There are \(5^5\) such numbers. \begin{align*} && \mathbb{E}(\text{different digits}) &= \frac1{5^5} \left (1 \cdot 5 + 2 \cdot \binom{5}{2}(2^5-2)+3 \cdot \binom{5}{3}(3^5-3 \cdot 2^5+3)+4 \cdot \binom{5}{4}(4^5 - 4 \cdot 3^5+6 \cdot 2^5-4) + 5 \cdot 5! \right) \\ &&&= \frac{2101}{625} = 3.3616 \end{align*}
Write down the general term in the expansion in powers of \(x\) of \((1-x^6)^{-2}\,\).
Solution: \(\displaystyle (1-x^6)^{-2} = \sum_{n=0}^{\infty} (n+1)x^{6n}\)
I am selling raffle tickets for \(\pounds1\) per ticket. In the queue for tickets, there are \(m\) people each with a single \(\pounds1\) coin and \(n\) people each with a single \(\pounds2\) coin. Each person in the queue wants to buy a single raffle ticket and each arrangement of people in the queue is equally likely to occur. Initially, I have no coins and a large supply of tickets. I stop selling tickets if I cannot give the required change.
Solution:
Rosalind wants to join the Stepney Chess Club. In order to be accepted, she must play a challenge match consisting of several games against Pardeep (the Club champion) and Quentin (the Club secretary), in which she must win at least one game against each of Pardeep and Quentin. From past experience, she knows that the probability of her winning a single game against Pardeep is \(p\) and the probability of her winning a single game against Quentin is \(q\), where \(0 < p < q < 1\).
Solution:
Prove that, for any real numbers \(x\) and \(y\), \(x^2+y^2\ge2xy\,\).
I seat \(n\) boys and \(3\) girls in a line at random, so that each order of the \(n+3\) children is as likely to occur as any other. Let \(K\) be the maximum number of consecutive girls in the line so, for example, \(K=1\) if there is at least one boy between each pair of girls.
Solution:
Three married couples sit down at a round table at which there are six chairs. All of the possible seating arrangements of the six people are equally likely.
Bag \(P\) and bag \(Q\) each contain \(n\) counters, where \(n\ge2\). The counters are identical in shape and size, but coloured either black or white. First, \(k\) counters (\(0\le k\le n\)) are drawn at random from bag \(P\) and placed in bag \(Q\). Then, \(k\) counters are drawn at random from bag \(Q\) and placed in bag \(P\).
Solution:
A box contains \(n\) pieces of string, each of which has two ends. I select two string ends at random and tie them together. This creates either a ring (if the two ends are from the same string) or a longer piece of string. I repeat the process of tying together string ends chosen at random until there are none left. Find the expected number of rings created at the first step and hence obtain an expression for the expected number of rings created by the end of the process. Find also an expression for the variance of the number of rings created. Given that \(\ln 20 \approx 3\) and that \(1+ \frac12 + \cdots + \frac 1n \approx \ln n\) for large \(n\), determine approximately the expected number of rings created in the case \(n=40\,000\).
Solution: Let \(X_i\) be the indicator variable a loop is formed when there are \(i\) strings in the bag, so \(\mathbb{P}(X_i = 1) = \frac{1}{2i-1}\). Therefore \begin{align*} && Y_n &= X_n + Y_{n-1} \\ && Y_n &= X_n + \cdots + X_1 \\ \Rightarrow && \E[Y_n] &= \frac{1}{2n-1} + \frac{1}{2n-3} + \cdots + \frac{1}{1} \\ && \var[Y_n] &= \sum_{i=1}^n \frac{1}{2i-1} \frac{2i-2}{2i-1} \\ &&&= 2\sum_{i=1}^n \frac{i-1}{(2i-1)^2} \end{align*} \begin{align*} && \E[Y_{n}] &= 1 + \frac13 + \cdots + \frac{1}{2n-1} \\ &&&= 1 + \frac12 + \cdots + \frac1{2n} - \frac12\left (1 + \frac12 + \cdots + \frac1n \right) \\ &&&\approx \ln 2n -\frac12 \ln n \\ &&&= \ln 2 \sqrt{n} \\ \\ && \E[Y_{40\,000}] &= \ln 2 \sqrt{40\,000} \\ &&&= \ln 400 \\ &&&= 2 \ln 20 \approx 6 \end{align*}
A positive integer with \(2n\) digits (the first of which must not be \(0\)) is called a balanced number if the sum of the first \(n\) digits equals the sum of the last \(n\) digits. For example, \(1634\) is a \(4\)-digit balanced number, but \(123401\) is not a balanced number.
Solution:
A bag contains eleven small discs, which are identical except that six of the discs are blank and five of the discs are numbered, using the numbers 1, 2, 3, 4 and 5. The bag is shaken, and four discs are taken one at a time without replacement. Calculate the probability that:
Solution: There are many ways to do the counting in each question, possibly the clearest way is to always consider the order in which discs are taken, although all methods should work equally well. For some examples Bayes rule also offers a fast solution.
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.
I know that ice-creams come in \(n\) different sizes, but I don't know what the sizes are. I am offered one of each in succession, in random order. I am certainly going to choose one - the bigger the better - but I am not allowed more than one. My strategy is to reject the first ice-cream I am offered and choose the first one thereafter that is bigger than the first one I was offered; if the first ice-cream offered is in fact the biggest one, then I have to put up with the last one, however small. Let \(\P_n(k)\) be the probability that I choose the \(k\)th biggest ice-cream, where \(k=1\) is the biggest and \(k=n\) is the smallest.