Euler and Milstein Schemes Compared: One Extra Term

A discretisation scheme turns a continuous equation into a rule for taking finite steps. The Euler scheme takes the drift and the randomness at the start of each step and applies both across it. The Milstein scheme adds one further term, built from the square of that step's randomness, and that single addition is the entire difference between them.

One extra term is the whole comparison. The extra term improves the rate at which the error shrinks as the steps are made shorter, and it makes no claim whatever about any particular path at any particular number of steps. A better rate and silence about single paths are not in tension. On the one path worked through below, the better scheme is beaten at the finest partition it is tested on, and holding both claims at once is the only way to read that table without drawing the wrong conclusion from it.

The one term that separates the two schemes is set out below, symbol by symbol, and then both schemes are run along a single path that can be checked by hand, at six different step counts.

What does a discretisation scheme actually do?

A continuous equation describes what happens over an interval of no length at all. A machine cannot take a step of no length. Something has to bridge the two, and a discretisation schemeA rule turning a continuous equation into finite steps a machine can take. is that bridge: a rule saying what to do over a step of real, positive length, given what was known when the step began.

Here is the everyday version. A weighing scale that reports once a second cannot say what a moving object weighed at every instant between readings. The scale gives a reading, and then a rule fills in the gap: hold the last reading until the next one arrives, draw a straight line between them, or something cleverer. Each of those fill-in rules is a discretisation scheme, and they differ only in what they assume happened between the readings. The scale is the same scale in every case. Only the rule changes.

The choices compared here are exactly of that kind. Both schemes read the process at the start of a step. Both apply something across the step. The two schemes differ only in what they apply.

The horizon here is one year, and the partitionThe set of times at which an interval is cut into steps, and the lengths those cuts produce. divides it into a whole number of equal steps. Twelve divides by one, two, three, four and six. So the step counts used here are one, two, three, four, six and twelve, and the same underlying path can be read at every one of those coarsenesses without the path itself being changed.

What is the Euler scheme, in one line?

The Euler schemeTaking the drift and the randomness at the start of each step and applying both across the whole of it. reads the drift and the volatility at the moment the step begins, treats both as fixed for the length of the step, and pushes the process forward by the drift multiplied by the step length plus the volatility multiplied by the step's random increment. Nothing is re-read part way through. Whatever the process did inside the step is invisible to the rule.

The standard process, an invented single traded quantity used throughout this subject area, starts at Rs 100/- with a drift of 8 per cent and a volatility of 20 per cent over one year. Written for that process, the rule is one line.

That one line is the whole scheme. The rule carries the name of Euler from the deterministic case and of Maruyama from its stochastic form. It is nothing more than reading the equation literally and replacing the infinitesimals with finite quantities, so it is the rule that any first attempt at stepping an equation forward lands on unaided.

The assumption inside it is that the coefficients do not move within a step, and that assumption is exactly what the error will be made of. Over a step of one year the process moves a very long way, so the coefficients read at the start are badly out of date by the end. Over a step of one month they are only slightly out of date. Staleness of the coefficients is the intuition for why shortening the steps helps, and for what a better scheme has to correct.

What one term does the Milstein scheme add?

The Milstein schemeThe Euler scheme with one further term added, built from the square of the step's randomness less the step length., published by Milstein in 1975, keeps every part of the line above and adds one more. The extra termHalf the volatility squared, multiplied by the square of the step's random increment less the length of the step. is half the volatility squared, multiplied by the square of the step's random increment less the step length.

The bracket is the whole of the difference, and it repays slow reading. The square of the random increment is a number that is never negative. The step length is subtracted from it. So the added quantity is positive when the step's randomness came out larger than typical for a step of that length, and negative when it came out smaller. The added quantity is not a correction for the direction the process moved; it is a correction for how much the process moved, whichever way it went.

The added term exists to close a gap in the plain rule. The plain rule assumes the volatility contribution scales with the increment alone. The contribution does not scale that way. Over a step of real length the squared increment carries an effect of its own, and a rule ignoring that effect is systematically mis-stating every step. The added term is the leading part of what was being ignored.

What does the extra term buy?

Two things are true of the added bracket at once. The first is that the bracket averages to exactly nothing. The square of a random increment over a step has an average equal to the length of that step, so subtracting the step length centres the whole quantity on zero. Over many steps and many paths it adds nothing at all to the answer.

The second is that it is not nothing on any actual step. Averaging to zero and being zero are different properties, and confusing them is the commonest way to misread this term. Think of a queue at a counter where the average wait is four minutes. Subtract four minutes from every wait and the adjusted figures average to zero. A zero average does not mean nobody waited. The average wait is unchanged by the adjustment, and an unchanged average is a far weaker claim than no waiting.

The locked path used here divides the year into twelve steps with twelve driving values whose squares sum to exactly twelve. Squares summing to exactly twelve are what make the bracket sum to exactly zero across the year, so the claim can be shown rather than asserted.

So what is bought is not a shift in the answer but a reduction in the spread of the answer around the truth. On steps where the randomness came out unusually large or unusually small, the plain rule is most wrong and the term is largest. Where the plain rule was nearly right, the term is near zero. A correction that averages to nothing but tracks the error it is correcting reduces error without introducing a bias, and that is the entire case for carrying the extra term.

Stated formally, what improves is the order of convergenceThe power of the step length at which the error shrinks as the steps are made shorter. in the strong convergenceConvergence of the approximate path itself toward the true path, rather than convergence of an average taken over many paths. sense. Strong convergence is convergence of the path itself rather than of an average over paths.

Read the exponents rather than the constant. Halving the step length cuts the Euler bound by a factor of about 1.41 and the Milstein bound by a factor of 2. The gap compounds: dividing the step length by a hundred cuts one bound by ten and the other by a hundred. Every word of that sentence carries an average over paths inside it, and none of it is a statement about any single path that might be run.

What do the two schemes give on a path that can be checked?

Everything above is a claim about averages. Here is one path, worked all the way through, so the claim can be tested against something concrete rather than accepted.

The path is the locked twelve step path, an invented construction, used throughout this subject area. The path divides the year into twelve equal steps and carries twelve driving values that sum to exactly zero and whose squares sum to exactly twelve. Because the driving values sum to zero, the Brownian path returns to where it began at the horizon. The exact answer at the horizon is therefore the starting value of Rs 100/- multiplied by e to the 0.06, or Rs 106.183655/- exactly, and every error below is measured against that one number.

Both schemes are run along that identical path at six different step counts. Nothing about the path changes between rows. The only thing that changes is how many steps the year is cut into and which rule is applied across each step.

Start at the top row, the crudest thing anybody could do: cut the year into a single step and take it whole. With a Brownian increment of zero over the whole year the only thing left is the drift, so the plain rule gives Rs 108.000000/-, one hundred multiplied by one plus 0.08 being one hundred and eight. The corrected rule subtracts half the variance rate, 0.02, from that same bracket, giving exactly Rs 106.000000/- and landing within Rs 0.183655/- of the truth on a single step.

The two error columns settle the rest. The corrected scheme is closer at one step, at two, at three, at four and at six, and the margin is not small: a factor of 9.89, then 18.60, then 31.80, then 9.88, then 14.02. Five rows, five wins, and by an order of magnitude or better in every one of them. Then look at the last row, where the corrected scheme has an error of minus Rs 0.005872/- against the plain scheme's plus Rs 0.000836/-, and loses by a factor of seven.

What does the extra term not promise?

The extra term does not promise to win. Not on any particular path, not at any particular step count, not on any single run made to check it. The term promises a rate, and a rate is a statement about a limit taken over an average across many paths. One path is not an average, and six readings of one path are still not an average.

Look at what the two error columns actually do as the steps shorten. The plain scheme starts too high, stays too high, goes higher still at three steps, crosses to too low at four, stays too low at six, and crosses back to too high at twelve. The plain scheme's error makes a sign changeThe point at which an error crosses zero, from too high to too low or the other way round. twice over. The corrected scheme starts too low, stays too low, stays too low again, crosses to too high at four, and crosses back to too low at six. Also twice.

Neither sequence declines cleanly either. The plain scheme's error grows from 1.413012 at two steps to 1.967130 at three, so a refinement of the grid made the answer worse. The corrected scheme's error grows from 0.061859 at three steps to 0.089567 at four, and again from 0.003684 at six steps to 0.005872 at twelve. Refining a partition on a single path is not obliged to help, and on this path it repeatedly does not.

When is the extra term worth its cost?

The added term costs one squaring and one subtraction per step. One squaring and one subtraction are close to free on any machine built in the last forty years, so the cost question is rarely about arithmetic time. The cost question is about whether the thing being improved is the thing being measured.

The added term improves how faithfully the whole approximated path tracks the true path. So the test is simple: does the quantity being computed read the whole path, or only where the path finished?

If the quantity reads the whole path, a better path approximation feeds straight through, and the correction earns its keep. A scheme can wander badly in the middle and still arrive close to the right place, so if the quantity reads only the endpoint, the improvement in path fidelity may buy very little. There is a separate notion of convergence covering exactly that case, and it treats the two schemes far more evenly than the path-fidelity notion does.

How does somebody checking a computation rather than building one use this?

Most people who meet these two schemes are not writing them. The reader is instead handed a number somebody else produced, and has to decide how much of it to believe. Three questions get most of the way, and none of them needs the code.

The first is which rule was used and at what step length. A figure quoted without its step length is not a figure; it is one of a range of figures, and the range here runs from Rs 105.299068/- to Rs 108.150785/- for the plain rule on one path. The step length is part of the answer, not a footnote to it.

The second is what convergence evidence exists. A single run at a single step length is a number. A run repeated at halving step lengths, with the errors shrinking at roughly the promised power, is evidence. The promised power is a statement about an average, and an average needs many paths before it means anything. Ask for the repeated run, and ask how many paths went into it.

The third is whether the quantity being computed reads the whole path or only the finish. The whole-path question decides whether the corrected scheme was worth carrying, and somebody who cannot answer it about their own computation has not yet decided what they are measuring.

A household example makes the shape of it plain. A bill added up once, giving a total that looks fine, is one run at one setting. Adding it up a second time, a different way, and getting the same total is not proof either. The second reading is evidence about the method rather than about the arithmetic, so the two readings together are worth much more than twice one of them. Convergence evidence is exactly that second reading, done systematically.

Does any of this depend on jurisdiction?

No. There is no regulator of discretisation, no jurisdiction in which the squared increment behaves differently, and no local convention that changes the strong order of either scheme. Milstein published in 1975 and the result has held everywhere since. The strong order is a statement about the mathematics, not about any market, any exchange or any set of conduct rules.

Permission to use a number produced this way does vary by place, and permission belongs to conduct and disclosure rules rather than to numerical analysis.