STEP III 2007 question 13 solution

Register

About Us | Help | Sign in

Create New Article | Editing Help

Advanced Search

Edit \| Hide
Welcome \| Study Help \| A Levels \| Applications, UCAS etc. \| University Discussion \| Careers \| General Discussion \| Have Your Say \| Health & Relationships \| Debate & Discussion \| Technology \| Sport \| Entertainment \| Chat \| Ask A Moderator

STEP III 2007 question 13 solution

From The Student Room

Jump to:navigation, search

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 |