Problems

Filters
Clear Filters

8 problems found

2018 Paper 2 Q13
D: 1600.0 B: 1502.8
probability tree diagram recurrence relation Markov chain random walk circular motion symmetry pass the parcel

Four children, \(A\), \(B\), \(C\) and \(D\), are playing a version of the game `pass the parcel'. They stand in a circle, so that \(ABCDA\) is the clockwise order. Each time a whistle is blown, the child holding the parcel is supposed to pass the parcel immediately exactly one place clockwise. In fact each child, independently of any other past event, passes the parcel clockwise with probability \(\frac{1}{4}\), passes it anticlockwise with probability \(\frac{1}{4}\) and fails to pass it at all with probability \(\frac{1}{2}\). At the start of the game, child \(A\) is holding the parcel. The probability that child \(A\) is holding the parcel just after the whistle has been blown for the \(n\)th time is \(A_n\), and \(B_n\), \(C_n\) and \(D_n\) are defined similarly.

  1. Find \(A_1\), \(B_1\), \(C_1\) and \(D_1\). Find also \(A_2\), \(B_2\), \(C_2\) and \(D_2\).
  2. By first considering \(B_{n+1}+D_{n+1}\), or otherwise, find \(B_n\) and \(D_n\). Find also expressions for \(A_n\) and \(C_n\) in terms of \(n\).

Solution:

  1. \(\,\) \begin{align*} && A_1 &= \frac12 \\ && B_1 &= \frac14 \\ && C_1 &= 0 \\ && D_1 &= \frac14 \end{align*} \begin{align*} && A_2 &= \frac12 \cdot \frac12 + 2 \cdot \frac14 \cdot \frac14 = \frac38 \\ && B_2 &= \frac14 \cdot \frac12 + \frac12 \cdot \frac14 = \frac14 \\ && C_2 &=2 \cdot \frac14 \cdot \frac14 =\frac18 \\ && D_2 &= B_2 = \frac14 \end{align*}
  2. \begin{align*} && A_{n+1} &= \frac12 A_n+ \frac14(B_n + D_n) \\ && B_{n+1} &= \frac12 B_n+ \frac14(A_n + C_n) \\ && C_{n+1} &= \frac12 C_n+ \frac14(D_n +B_n) \\ && D_{n+1} &= \frac12 D_n+ \frac14(C_n +A_n) \\ \\ \Rightarrow && B_{n+1}+D_{n+1} &= \frac12 (B_n+D_n) + \frac12(A_n+C_n) \\ &&&= \frac12 \\ \Rightarrow && B_{n+1}&=D_{n+1} = \frac14 \\ \\ && C_{n+1} &= \frac12C_n + \frac14 \cdot \frac12 \\ &&&= \frac12 C_n + \frac18\\ &&&= \frac12 C_{n-1} + \frac1{8} + \frac1{16} \\ &&&= \frac1{8} + \frac{1}{16} + \cdots + \frac{1}{8 \cdot 2^{n-1}} \\ &&&= \frac18 \left (1 + \frac12 + \cdots + \frac1{2^{n-1}} \right) \\ &&&= \frac18\left ( \frac{1-\frac1{2^n}}{1-\frac12} \right) \\ &&&= \frac18 \left (2 - \frac{1}{2^{n-1}} \right) \\ &&&= \frac14 - \frac{1}{2^{n-1}} \\ \Rightarrow && A_n &= \frac14 + \frac1{2^{n-1}} \end{align*}

View
2007 Paper 3 Q13
D: 1700.0 B: 1500.0
probability discrete probability distributions recurrence relation expected value random walk first passage time geometric series approximation

A frog jumps towards a large pond. Each jump takes the frog either \(1\,\)m or \(2\,\)m nearer to the pond. The probability of a \(1\,\)m jump is \(p\) and the probability of a \(2\,\)m jump is \(q\), where \(p+q=1\), the occurence of long and short jumps being independent.

  1. Let \(p_n(j)\) be the probability that the frog, starting at a point \((n-\frac12)\,\)m away from the edge of the pond, lands in the pond for the first time on its \(j\)th jump. Show that \(p_2(2)=p\).
  2. Let \(u_n\) be the expected number of jumps, starting at a point \((n-\frac12)\,\)m away from the edge of the pond, required to land in the pond for the first time. Write down the value of \(u_1\). By finding first the relevant values of \(p_n(m)\), calculate \(u_2\) and show that $u_3= 3-2q+q^2\(.
  3. Given that \)u_n\( can be expressed in the form \)u_n= A(-q)^{n-1} +B +Cn$, where \(A\), \(B\) and \(C\) are constants (independent of \(n\)), show that \(C= (1+q)^{-1}\) and find \(A\) and \(B\) in terms of \(q\). Hence show that, for large \(n\), \(u_n \approx \dfrac n{p+2q}\) and explain carefully why this result is to be expected.

View
2003 Paper 3 Q13
D: 1700.0 B: 1500.0
probability conditional probability recurrence relation Markov chain symmetry simultaneous equations random walk

In a rabbit warren, underground chambers \(A, B, C\) and \(D\) are at the vertices of a square, and burrows join \(A\) to \(B\), \ \(B\) to \(C\), \ \(C\) to \(D\) and \(D\) to \(A\). Each of the chambers also has a tunnel to the surface. A rabbit finding itself in any chamber runs along one of the two burrows to a neighbouring chamber, or leaves the burrow through the tunnel to the surface. Each of these three possibilities is equally likely. Let \(p_A\,\), \(p_B\,\), \(p_C\) and \(p_D\) be the probabilities of a rabbit leaving the burrow through the tunnel from chamber \(A\), given that it is currently in chamber \(A, B, C\) or \(D\), respectively.

  1. Explain why \(p_A = \frac13 + \frac13p_B + \frac13 p_D\).
  2. Determine \(p_A\,\).
  3. Find the probability that a rabbit which starts in chamber \(A\) does not visit chamber~\(C\), given that it eventually leaves the burrow through the tunnel in chamber \(A\).

View
1996 Paper 2 Q13
D: 1600.0 B: 1516.0
binomial distribution Vandermonde identity combinatorial proof random walk grid probability binomial coefficients generating functions

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?

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

TikZ diagram
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\)

View
1992 Paper 2 Q15
D: 1600.0 B: 1523.5
probability random walk binomial distribution combinatorics optimisation symmetric random walk binomial coefficients

A point moves in unit steps on the \(x\)-axis starting from the origin. At each step the point is equally likely to move in the positive or negative direction. The probability that after \(s\) steps it is at one of the points \(x=2,x=3,x=4\) or \(x=5\) is \(\mathrm{P}(s).\) Show that \(\mathrm{P}(5)=\frac{3}{16},\) \(\mathrm{P}(6)=\frac{21}{64}\) and \[ \mathrm{P}(2k)=\binom{2k+1}{k-1}\left(\frac{1}{2}\right)^{2k} \] where \(k\) is a positive integer. Find a similar expression for \(\mathrm{P}(2k+1).\) Determine the values of \(s\) for which \(\mathrm{P}(s)\) has its greatest value.

Solution: After \(5\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 1 \text { - go positive every time}\\ 4 & 0 \\ 3 & \binom{5}{1} \text { - go positive every time but 1} \\ 2 &0 \\ \hline & 6 \end{array} Therefore there are \(\frac{6}{2^5} = \frac{3}{16}\) ways to get to \(\{2,3,4,5\}\) After \(6\) steps we can get to: \begin{array}{c|c} x & \text{ways} \\ \hline 5 & 0 \\ 4 & \binom{6}{1} \text { - go positive every time but 1}\\ 3 & 0 \\ 2 & \binom{6}{2} - \text{ - go positive every time but 2} \\ \hline & 21 \end{array} Therefore there are \(\frac{21}{2^6} = \frac{21}{64}\) ways to get to \(\{2,3,4,5\}\) After \(2k\) steps we can reach \(2\) or \(4\). To get to \(2\) we must take \(k+1\) positive steps and \(k-1\) negative steps, ie \(\binom{2k}{k-1}\). To get to \(4\) we must take \(k+2\) positive steps and \(k-2\) negative steps, ie \(\binom{2k}{k-2}\) Therefore there are \(\binom{2k+1}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k}} \binom{2k+1}{k-1}\) After \(2k+1\) steps we can reach \(3\) or \(5\). To get to \(3\) we must take \(k+2\) positive steps and \(k-1\) negative steps, ie \(\binom{2k+1}{k-1}\). To get to \(5\) we must take \(k+3\) positive steps and \(k-2\) negative steps, ie \(\binom{2k+1}{k-2}\) Therefore there are \(\binom{2k+2}{k-1}\) routes, ie a probability of \(\frac{1}{2^{2k+1}} \binom{2k+2}{k-1}\) To find the maximum of \(P(s)\) notice that \begin{align*} && \frac{P(2k+1)}{P(2k)} &= \frac12 \frac{\binom{2k+2}{k-1}}{\binom{2k+1}{k-1}} \\ &&&= \frac12 \frac{(2k+2)!(k-1)!(k+2)!}{(2k+1)!(k-1)!(k+3)!} \\ &&&= \frac12 \frac{2k+2}{k+3} = \frac{k+1}{k+3} < 1 \end{align*} So we should only look at the even terms. \begin{align*} && \frac{P(2k+2)}{P(2k)} &= \frac14 \frac{\binom{2k+3}{k}}{\binom{2k+1}{k-1}} \\ &&&= \frac14 \frac{(2k+3)!(k-1)!(k+2)!}{(2k+1)!k!(k+3)!} \\ &&&= \frac14 \frac{(2k+3)(2k+2)}{k(k+3)} \\ &&&= \frac{(2k+3)(k+1)}{2k(k+3)} \geq 1 \\ \Leftrightarrow && (2k+3)(k+1) &\geq 2k(k+3) \\ \Leftrightarrow && 2k^2+5k+3 &\geq 2k^2+6k \\ \Leftrightarrow && 3 &\geq k \\ \end{align*} Therefore the maximum is when \(s = 2\cdot 3\) or \(s = 2\cdot 4\) which we computed earlier to be \(\frac{21}{64}\)

View
1992 Paper 2 Q16
D: 1600.0 B: 1500.0
probability conditional Bayes' theorem binomial distribution combinatorics random walk

A taxi driver keeps a packet of toffees and a packet of mints in her taxi. From time to time she takes either a toffee (with probability \(p\)) or mint (with probability \(q=1-p\)). At the beginning of the week she has \(n\) toffees and \(m\) mints in the packets. On the \(N\)th occasion that she reaches for a sweet, she discovers (for the first time) that she has run out of that kind of sweet. What is the probability that she was reaching for a toffee?

Solution: \begin{align*} \mathbb{P}(\text{run out reading for toffee on } N\text{th occassion}) &= \binom{N-1}{n}p^nq^{N-1-n}p \end{align*} Since out of the first \(N-1\) times, we need to choose toffee \(n\) times, and then choose it again for the \(N\)th time. Therefore: \begin{align*} \mathbb{P}(\text{reaching for toffee} | \text{run out on }N\text{th occassion}) &= \frac{\mathbb{P}(\text{reaching for toffee and run out on }N\text{th occassion})}{\mathbb{P}(\text{reaching for toffee and run out on }N\text{th occassion}) + \mathbb{P}(\text{reaching for mint and run out on }N\text{th occassion})} \\ &= \frac{ \binom{N-1}{n}p^nq^{N-1-n}p}{ \binom{N-1}{n}p^nq^{N-1-n}p + \binom{N-1}{m}q^mp^{N-1-m}q} \\ &= \frac{ \binom{N-1}{n}}{ \binom{N-1}{n} + \binom{N-1}{m} \l \frac{q}{p} \r^{m+ n+ 2-N}} \end{align*} Some conclusions we can draw from this are: As \(p \to 1, q \to 0\), the probability they were reaching for a Toffee tends to \(1\). (And vice versa). If \(p = q\), then the probability is: \begin{align*} \frac{ \binom{N-1}{n}}{ \binom{N-1}{n} + \binom{N-1}{m} } \end{align*} Since \(n+1 \leq N \leq n+m+1\) where \(n \geq m\) we can notice that: \begin{align*} \text{if } N = m + n + 1 && \binom{m+n+1 - 1}{n} &= \binom{m+n+1 - 1}{m} & \text{ so } \mathbb{P} = \frac12 \\ \text{if } N = n+k && \binom{n+k-1}{n} &< \binom{n+k-1}{m} & \text{ so } \mathbb{P} < \frac12 \\ \end{align*}

View
1991 Paper 1 Q15
D: 1516.0 B: 1484.0
central limit theorem normal approximation probability fair coin random walk mean and variance dependent random variables Bernoulli distribution

A fair coin is thrown \(n\) times. On each throw, 1 point is scored for a head and 1 point is lost for a tail. Let \(S_{n}\) be the points total for the series of \(n\) throws, i.e. \(S_{n}=X_{1}+X_{2}+\cdots+X_{n},\) where \[ X_{j}=\begin{cases} 1 & \text{ if the }j \text{ th throw is a head}\\ -1 & \text{ if the }j\text{ th throw is a tail.} \end{cases} \]

  1. If \(n=10\,000,\) find an approximate value for the probability that \(S_{n}>100.\)
  2. Find an approximate value for the least \(n\) for which \(\mathrm{P}(S_{n}>0.01n)<0,01.\)
Suppose that instead no points are scored for the first throw, but that on each successive throw, 2 points are scored if both it and the first throw are heads, two points are deducted if both are tails, and no points are scored or lost if the throws differ. Let \(Y_{k}\) be the score on the \(k\)th throw, where \(2\leqslant k\leqslant n.\) Show that \(Y_{k}=X_{1}+X_{k}.\) Calculate the mean and variance of each \(Y_{k}\) and determine whether it is true that \[ \mathrm{P}(Y_{2}+Y_{3}+\cdots+Y_{n}>0.01(n-1))\rightarrow0\quad\mbox{ as }n\rightarrow\infty. \]

Solution: Notice that \(\mathbb{E}(X_i) = 0, \mathbb{E}(X_i^2) = 1\) and so \(\mathbb{E}(S_n) =0, \textrm{Var}(S_n) = n\).

  1. Then by the central limit theorem (or alternatively the normal approximation to the binomial), \begin{align*} && \mathbb{P}(S_n > 100) &\underbrace{\approx}_{\text{CLT}} \mathbb{P} \left (Z > \frac{100}{\sqrt{10\, 000}} \right) \\ &&&= \mathbb{P}(Z > 1) \\ &&&= 1-\Phi(1) \\ &&&\approx 15.9\% \end{align*}
  2. \begin{align*} &&\mathbb{P}(S_n > 0.01n) &\approx \mathbb{P} \left (Z > \frac{0.01n}{\sqrt{n}} \right) \\ &&&= \mathbb{P}(Z > 0.01 \sqrt{n}) \\ &&&= 1-\Phi(0.01\sqrt{n}) \\ &&&< 0.01 \\ && \Phi^{-1}(0.01) &= -2.3263\ldots \\ \Rightarrow && 0.01 \sqrt{n} &= 2.3263\ldots \\ \Rightarrow && n &\approx 233^2 \end{align*}
\begin{array}{cc|cc} 1\text{st throw}& k\text{th throw} & X_1 + X_k & Y_k \\ \hline \text{head} & \text{head} & 1 + 1 & 2 \\ \text{head} & \text{tail} & 1 - 1 & 0 \\ \text{tail} & \text{head} & -1 + 1 & 0 \\ \text{tail} & \text{tail} & -1- 1 & -2 \\ \end{array} Across all possible cases \(Y_k = X_1 + X_k\) so therefore these random variables are equal. \begin{align*} \mathbb{E}(Y_k) &= \mathbb{E}(X_1) + \mathbb{E}(Y_k) \\ &= 0 + 0 = 0 \\ \\ \textrm{Var}(Y_k) &= \textrm{Var}(X_1)+\textrm{Var}(X_k) \\ &= 2 \\ \\ \mathbb{E}\left (\sum_{k=2}^n Y_k \right) &= 0 \\ \textrm{Var}\left (\sum_{k=2}^n Y_k \right) &= 2(n-1) \end{align*} Therefore approximately \(\displaystyle \sum_{k=2}^n Y_k \approx N(0, 2(n-1))\) \begin{align*} \mathbb{P} \left (\sum_{k=2}^n Y_k > 0.01(n-1) \right) &\approx \mathbb{P} \left (Z > \frac{0.01(n-1)}{\sqrt{2(n-1)}} \right) \\ &= \mathbb{P} \left (Z > c \sqrt{n-1} \right) \\ &\to 0 \text{ as } n \to \infty \end{align*}

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