Join TSR
 
 About Us | FAQs | Sign in
 
HomeForumsArticlesRevision NotesPersonal StatementsUniversity GuidesHealth & RelationshipsPostgraduate StudyCareers
Join the UK's largest student community  
Advanced
Search

Join The Student Room Today

Be part of the UK's largest and fastest growing student community.

It's free to join and a lot of fun - Get inspired, express your ideas, interact and share

Join The Student Room Today

STEP III 2007 question 13 solution

From The Student Room

TSR Wiki > Study Help > Subjects and Revision > Mathematics > STEP > STEP III 2007 question 13 solution

(i) We can think of p_n(j) as the probability that the frog travels less than [i]n[/i] meters by jump j-1 and at least [i]n[/i] meters by jump [i]j[/i]. So p_2(2) is probability that the frog travels < 2 m on its first jump and at least 2m by the 2nd jump. So the first jump must have been 1m (with prob p), and then any jump on the 2nd jump is sufficient. So p_2(2) = p.

(ii) Starting 1-\frac{1}{2}m from the pond, any jump will land in the pond, so u_1 = 1.

Starting 2-\frac{1}{2}m from the pond, the chance of splashing in one jump is q, and the chance of splashing in two jumps is p. So u_2 = q+2p = 2-q.

Starting 3-\frac{1}{2}m from the pond, getting to the pond in 1 jump is impossible (so p_3(1) = 0). 3 jumps are required if and only if the first 2 jumps are small (so p_3(3) = p^2). So p(2) = 1 - p_3(1)-p_3(2)= 1-p^2.

So u_3 = 2(1-p^2)+3p^2 = 2+p^2 = 3-2q+q^2.

(iii)u_1 = A+B+C = 1,\,u_2 = -qA+B+2C=2-q,\,u_3=q^2A+B+3C=3-2q+q^2.

So u_1-u_2 = (1+q)A-C = q-1, u_3-u_2 = q(1+q)A+C=1-q+q^2.

Adding these two gives (1+q)^2A=q^2 \implies A=\frac{q^2}{(1+q)^2}.

Then C = 1-q+(1+q)A = 1-q+\frac{q^2}{1+q} = \frac{(1-q)(1+q)+q^2}{1+q} = \frac{1}{1+q}.

Finally B = 1-A-C = \frac{(1+q)^2-q^2-(1+q)}{(1+q)^2}=\frac{q}{(1+q)^2}

For large n, the term in C dominates and so u_n \approx \frac{n}{1+q} = \frac{n}{p+2q}.

This is to be expected because the expected distance travelled per jump is p+2q, so if d_n is the distance travelled in n jumps then E(d_n) = n(p+2q). Moreover, by the central limit theorem, d_n \approx N(n(p+2q), \sqrt{npq}). This tells us that 99% of d_n lies within n(p+2q)\pm 3\sqrt{npq}, or more relevantly, for any \epsilon > 0, P(|d_n-n(p+2q)| < \epsilon n) \to 1 as n\to \infty. So after 'n' jumps we are almost certain to have travelled a distance n(p+2q)\pm\epsilon n. It follows that it is almost certain to require \frac{n}{p+2q}\pm \epsilon n to travel a distance 'n', and so |E(j_n) - \frac{n}{p+2q}| < \epsilon n. Thus j_n \approx \frac{n}{p+2q}.

Comment: I found it quite hard to know what they were expecting for the last bit. Intuitively, the expected distance travelled is n(p+2q), and the CLT (or Chebychev's inequality) says this is a good enough estimate that we can invert it to say the expected number of jumps is to travel a distance n is n/(p+2q). But I don't really see a way of making this argument 'rigourous' that's not a lot more work than the actual question.

On a slightly different note: If we set u_0=u_{-1} = 0 then it's fairly obvious that u_n = p u_{n-1}+q u_{n-2}+1, so u_n-pu_{n-1}-qu_{n-2} = 1. The aux equation is x^2-px-q = 0, or (x+q)(x-1)=0. Set u_n = Cn for the P.I. and find Cn-p(Cn-1)-q(Cn-2) = 1, so (p+2q)C = 1, or C=(1+q)^{-1} for a general solution u_n = A(-q)^n + B +n(1+q)^{-1}. Then u_0 = 0 gives A+B=0 \implies B=-A, while u_{-1} = 0 gives 0 = -A/q + B -1/(1+q), so -A/q -A = 1/(1+q) \implies A = -q/(1+q)^2. This is the same solution as that found in the question (only we have derived the formula for u_n rather than being given it).

Solution by DFranklin.

Retrieved from "http://thestudentroom.co.uk/wiki/STEP_III_2007_question_13_solution"
Article Tools:  Create New Article  |  Report This Article  |  This Article's History  |