Problems

The mountain villages \(A,B,C\) and \(D\) lie at the vertices of a tetrahedron, and each pair of villages is joined by a road. After a snowfall the probability that any road is blocked is \(p\), and is independent of the conditions of any other road. The probability that, after a snowfall, it is possible to travel from any village to any other village by some route is \(P\). Show that $$ P =1- p^2(6p^3-12p^2+3p+4). $$ %In the case \(p={1\over 3}\) show that this probability is \({208 \over 243}\).

Write down the probability of obtaining \(k\) heads in \(n\) tosses of a fair coin. Now suppose that \(k\) is known but \(n\) is unknown. A maximum likelihood estimator (MLE) of \(n\) is defined to be a value (which must be an integer) of \(n\) which maximizes the probability of \(k\) heads. A friend has thrown a fair coin a number of times. She tells you that she has observed one head. Show that in this case there are two MLEs of the number of tosses she has made. She now tells you that in a repeat of the exercise she has observed \(k\) heads. Find the two MLEs of the number of tosses she has made. She next uses a coin biased with probability \(p\) (known) of showing a head, and again tells you that she has observed \(k\) heads. Find the MLEs of the number of tosses made. What is the condition for the MLE to be unique?

An experiment produces a random number \(T\) uniformly distributed on \([0,1]\). Let \(X\) be the larger root of the equation \[x^{2}+2x+T=0.\] What is the probability that \(X>-1/3\)? Find \(\mathbb{E}(X)\) and show that \(\mathrm{Var}(X)=1/18\). The experiment is repeated independently 800 times generating the larger roots \(X_{1}, X_{2}, \dots, X_{800}\). If \[Y=X_{1}+X_{2}+\dots+X_{800}.\] find an approximate value for \(K\) such that \[\mathrm{P}(Y\leqslant K)=0.08.\]

Mr Blond returns to his flat to find it in complete darkness. He knows that this means that one of four assassins Mr 1, Mr 2, Mr 3 or Mr 4 has set a trap for him. His trained instinct tells him that the probability that Mr \(i\) has set the trap is \(i/10\). His knowledge of their habits tells him that Mr \(i\) uses a deadly trained silent anaconda with probability \((i+1)/10\), a bomb with probability \(i/10\) and a vicious attack canary with probability \((9-2i)/10\) \([i=1,2,3,4]\). He now listens carefully and, hearing no singing, concludes correctly that no canary is involved. If he switches on the light and the trap is a bomb he has probability \(1/2\) of being killed but if the trap is an anaconda he has probability \(2/3\) of survival. If he does not switch on the light and the trap is a bomb he is certain to survive but, if the trap is an anaconda, he has a probability \(1/2\) of being killed. His professional pride means that he must enter the flat. Advise Mr Blond, giving reasons for your advice.

The maximum height \(X\) of flood water each year on a certain river is a random variable with density function \begin{equation*} {\mathrm f}(x)= \begin{cases} \exp(-x)&\text{if \(x\geqslant 0\),}\\ 0&\text{otherwise}. \end{cases} \end{equation*} It costs \(y\) megadollars each year to prepare for flood water of height \(y\) or less. If \(X\leqslant y\) no further costs are incurred but if \(X\geqslant y\) the cost of flood damage is \(r+s(X-y)\) megadollars where \(r,s>0\). The total cost \(T\) megadollars is thus given by \begin{equation*} T= \begin{cases} y&\text{if \(X\leqslant y\)},\\ y+r+s(X-y)&\text{if \(X>y\)}. \end{cases} \end{equation*} Show that we can minimise the expected total cost by taking \[y=\ln(r+s).\]

The game of Cambridge Whispers starts with the first participant Albert flipping an un-biased coin and whispering to his neighbour Bertha whether it fell `heads' or `tails'. Bertha then whispers this information to her neighbour, and so on. The game ends when the final player Zebedee whispers to Albert and the game is won, by all players, if what Albert hears is correct. The acoustics are such that the listeners have, independently at each stage, only a probability of 2/3 of hearing correctly what is said. Find the probability that the game is won when there are just three players. By considering the binomial expansion of \((a+b)^n+(a-b)^n\), or otherwise, find a concise expression for the probability \(P\) that the game is won when is it played by \(n\) players each having a probability \(p\) of hearing correctly. % Show in particular that, if \(n\) is even, %\(P(n,1/10) = P(n,9/10)\).% How do you explain this apparent anomaly? To avoid the trauma of a lost game, the rules are now modified to require Albert to whisper to Bertha what he hears from Zebedee, and so keep the game going, if what he hears from Zebedee is not correct. Find the expected total number of times that Albert whispers to Bertha before the modified game ends. \noindent [You may use without proof the fact that \(\sum_1^\infty kx^{k-1}=(1-x)^{-2}\) for \(\vert x\vert<1\).]

Traffic enters a tunnel which is 9600 metres long, and in which overtaking is impossible. The number of vehicles which enter in any given time is governed by the Poisson distribution with mean 6 cars per minute. All vehicles travel at a constant speed until forced to slow down on catching up with a slower vehicle ahead. I enter the tunnel travelling at 30 m\(\,\)s\(^{-1}\) and all the other traffic is travelling at 32 m\(\,\)s\(^{-1}\). What is the expected number of vehicles in the queue behind me when I leave the tunnel? Assuming again that I travel at 30 m\(\,\)s\(^{-1}\), but that all the other vehicles are independently equally likely to be travelling at 30 m\(\,\)s\(^{-1}\) or 32 m\(\,\)s\(^{-1}\), find the probability that exactly two vehicles enter the tunnel within 20 seconds of my doing so and catch me up before I leave it. Find also the probability that there are exactly two vehicles queuing behind me when I leave the tunnel. \noindent [Ignore the lengths of the vehicles.]

An examiner has to assign a mark between 1 and \(m\) inclusive to each of \(n\) examination scripts (\(n\leqslant m\)). He does this randomly, but never assigns the same mark twice. If \(K\) is the highest mark that he assigns, explain why \[ \mathrm{P}(K=k)=\left.\binom{k-1}{n-1}\right/\binom{m}{n} \] for \(n\leqslant k\leqslant m,\) and deduce that \[ \sum_{k=n}^{m}\binom{k-1}{n-1}=\binom{m}{n}\,. \] Find the expected value of \(K\).

I have a Penny Black stamp which I want to sell to my friend Jim, but we cannot agree a price. So I put the stamp under one of two cups, jumble them up, and let Jim guess which one it is under. If he guesses correctly, I add a third cup, jumble them up, and let Jim guess correctly, adding another cup each time. The price he pays for the stamp is \(\pounds N,\) where \(N\) is the number of cups present when Jim fails to guess correctly. Find \(\mathrm{P}(N=k)\). Show that \(\mathrm{E}(N)=\mathrm{e}\) and calculate \(\mathrm{Var}(N).\)

A biased coin, with a probability \(p\) of coming up heads and a probability \(q=1-p\) of coming up tails, is tossed repeatedly. Let \(A\) be the event that the first run of \(r\) successive heads occurs before the first run of \(s\) successive tails. If \(H\) is the even that on the first toss the coin comes up heads and \(T\) is the event that it comes up tails, show that \begin{alignat*}{1} \mathrm{P}(A|H) & =p^{\alpha}+(1-p^{\alpha})\mathrm{P}(A|T),\\ \mathrm{P}(A|T) & =(1-q^{\beta})\mathrm{P}(A|H), \end{alignat*} where \(\alpha\) and \(\beta\) are to be determined. Use these two equations to find \(\mathrm{P}(A|H),\) \(\mathrm{P}(A|T),\) and hence \(\mathrm{P}(A).\)

By considering the coefficients of \(t^{n}\) in the equation \[(1+t)^{n}(1+t)^{n}=(1+t)^{2n},\] or otherwise, show that \[\binom{n}{0}\binom{n}{n}+\binom{n}{1}\binom{n}{n-1}+\cdots +\binom{n}{r}\binom{n}{n-r}+\cdots+\binom{n}{n}\binom{n}{0} =\binom{2n}{n}.\] The large American city of Triposville is laid out in a square grid with equally spaced streets running east-west and avenues running north-south. My friend is staying at a hotel \(n\) avenues west and \(n\) streets north of my hotel. Both hotels are at intersections. We set out from our own hotels at the same time. We walk at the same speed, taking 1 minute to go from one intersection to the next. Every time I reach an intersection I go north with probability \(1/2\) or west with probability \(1/2\). Every time my friend reaches an intersection she goes south with probability \(1/2\) or east with probability \(1/2\). Our choices are independent of each other and of our previous decisions. Indicate by a sketch or by a brief description the set of points where we could meet. Find the probability that we meet. Suppose that I oversleep and leave my hotel \(2k\) minutes later than my friend leaves hers, where \(k\) is an integer and \(0\leqslant 2k\leqslant n\). Find the probability that we meet. Have you any comment? If \(n=1\) and I leave my hotel \(1\) minute later than my friend leaves hers, what is the probability that we meet and why?

Show Solution

---

Solution: \begin{align*} && (1+t)^{n}(1+t)^{n}&=(1+t)^{2n} \\ [t^n]: &&\sum_{k=0}^n \underbrace{\binom{n}{k}}_{t^k\text{ from left bracket}} \underbrace{\binom{n}{n-k}}_{t^{n-k}\text{ from right bracket}} &= \binom{2n}{n} \end{align*}

+ - ↺

From each point, we can get to the diagonal ahead of us, so each move only takes us one diagonal closer together. Therefore we can only meet on the diagonal. The number of routes we can meet at is \begin{align*} && R &= \sum_{k=0}^n \underbrace{\binom{n}{k}}_{\text{I go up } k}\underbrace{\binom{n}{n-k}}_{\text{she goes down }n-k} \\ &&&= \binom{2n}{n} \end{align*} Therefore the probability is \(\displaystyle \frac1{2^{2n}} \binom{2n}n\). If I leave \(2k\) minutes late, then we will be attempting meet on a diagonal which is \(2k\) closer to me. The probability this occurs is \begin{align*} && \frac{1}{2^{2n}}\sum_{j=0}^{n-k}\binom{n-k}{j}\binom{n+k}{n-j} &= \frac{1}{2^{2n}}\binom{2n}{n} \end{align*} (by considering the coefficient of \(t^n\) in \((1+t)^{n+k}(1+t)^{n-k} =(1+t)^{2n}\)) This probability is unchanged, because you can consider the two paths as one path by one random person, conditional on them meeting and the delay doesn't change anything. If \(n = 1\) and I leave late, the only way we meet is if we end up walking towards each other down the same street (not at an intersection). This means I need to walk towards the intersection she reaches after the first minute \(\frac12\) and she needs to walk towards me \(\frac12\) so we have probability \(\frac14\)

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

Whenever I go cycling I start with my bike in good working order. However if all is well at time \(t\), the probability that I get a puncture in the small interval \((t,t+\delta t)\) is \(\alpha\,\delta t.\) How many punctures can I expect to get on a journey during which my total cycling time is \(T\)? When I get a puncture I stop immediately to repair it and the probability that, if I am repairing it at time \(t\), the repair will be completed in time \((t,t+\delta t)\) is \(\beta\,\delta t.\) If \(p(t)\) is the probability that I am repairing a puncture at time \(t\), write down an equation relating \(p(t)\) to \(p(t+\delta t)\), and derive from this a differential equation relating \(p'(t)\) and \(p(t).\) Show that \[ p(t)=\frac{\alpha}{\alpha+\beta}(1-\mathrm{e}^{-(\alpha+\beta)t}) \] satisfies this differential equation with the appropriate initial condition. Find an expression, involving \(\alpha,\beta\) and \(T\), for the time expected to be spent mending punctures during a journey of total time \(T\). Hence, or otherwise, show that, the fraction of the journey expected to be spent mending punctures is given approximately by \[ \quad\frac{\alpha T}{2}\quad\ \mbox{ if }(\alpha+\beta)T\text{ is small, } \] and by \[ \frac{\alpha}{\alpha+\beta}\quad\mbox{ if }(\alpha+\beta)T\text{ is large.} \]

A school has \(n\) pupils, of whom \(r\) play hocket, where \(n\geqslant r\geqslant2.\) All \(n\) pupils are arranged in a row at random.

1. What is the probability that there is a hockey player at each end of the row?
2. What is the probability that all the hockey players are standing together?
3. By considering the gaps between the non-hockey-players, find the probability that no two hockey players are standing together, distinguishing between cases when the probability is zero and when it is non-zero.

1. Find the maximum value of \(\sqrt{p(1-p)}\) as \(p\) varies between \(0\) and \(1\).
2. Suppose that a proportion \(p\) of the population is female. In order to estimate \(p\) we pick a sample of \(n\) people at random and find the proportion of them who are female. Find the value of \(n\) which ensures that the chance of our estimate of \(p\) being more than \(0.01\) in error is less than 1\%.
3. Discuss how the required value of \(n\) would be affected if (a) \(p\) were the proportion of people in the population who are left-handed; (b) \(p\) were the proportion of people in the population who are millionaires.