B2.13

Applied Probability
Part II, 2002

Two enthusiastic probability students, Ros and Guil, sit an examination which starts at time 0 and ends at time TT; they both decide to use the time to attempt a proof of a difficult theorem which carries a lot of extra marks.

Ros' strategy is to write the proof continuously at a constant speed λ\lambda lines per unit time. In a time interval of length δt\delta t he has a probability μδt+o(δt)\mu \delta t+o(\delta t) of realising he has made a mistake. If that happens he instantly panics, erases everything he has written and starts all over again.

Guil, on the other hand, keeps cool and thinks carefully about what he is doing. In a time interval of length δt\delta t, he has a probability λδt+o(δt)\lambda \delta t+o(\delta t) of writing the next line of proof and for each line he has written a probability μδt+o(δt)\mu \delta t+o(\delta t) of finding a mistake in that line, independently of all other lines he has written. When a mistake is found, he erases that line and carries on as usual, hoping for the best.

Both Ros and Guil realise that, even if they manage to finish the proof, they will not recognise that they have done so and will carry on writing as much as they can.

(a) Calculate pl(t)p_{l}(t), the probability that, for Ros, the length of his completed proof at time tl/λt \geqslant l / \lambda is at least ll.

(b) Let qn(t)q_{n}(t) be the probability that Guil has nn lines of proof at time t>0t>0. Show that

Qt=(s1)(λQμQs)\frac{\partial Q}{\partial t}=(s-1)\left(\lambda Q-\mu \frac{\partial Q}{\partial s}\right)

where Q(s,t)=n=0snqn(t)Q(s, t)=\sum_{n=0}^{\infty} s^{n} q_{n}(t).

(c) Suppose now that every time Ros starts all over again, the time until the next mistake has distribution FF, independently of the past history. Write down a renewal-type integral equation satisfied by l(t)l(t), the expected length of Ros' proof at time tt. What is the expected length of proof produced by him at the end of the examination if FF is the exponential distribution with mean 1/μ1 / \mu ?

(d) What is the expected length of proof produced by Guil at the end of the examination if each line that he writes survives for a length of time with distribution FF, independently of all other lines?