A step's volatility, live¶
A random walk's standard deviation over a step dt, from its standard deviation over a period T, σ_dt = σ_T √(dt / T) (lusine.stochastic.step_volatility). Independent steps add their variances, so the variance grows as the time and the spread as its root: n steps of T / n give back the period's variance, σ_T². Below, sixty-four random walks are stepped a period at a time in sixteen steps on your GPU as you read, each step's spread from the library's law and each step a draw uniform on [−√3 σ_dt, √3 σ_dt), whose variance is σ_dt². At each period's end the walks' ends are squared and summed, and their mean is the walks' variance over the period.
This page runs the program on your GPU through WebGPU, so it needs a browser with WebGPU (a recent Chrome, Edge, Safari or Firefox). Without it the program does not run and nothing is drawn below.
What it shows¶
- The strip above the controls is green while every check holds, and turns red for good once one fails.
- The walks: the chart draws the walks' variance over the period so far over the law's, σ_T² = 0.012², a point a step, settling onto 1 as periods end, between the bounds it is held to, 4.5 standard errors either side, which close in as walks end. Below it, the walks ended, their variance, the period's and the spread of a step.
- The sweep: the law's spread over the period's, √(dt / T), for steps from a second to past an hour, up by a quarter a step, against the step in decades, log₁₀(dt / 1 s), on a log scale: a line of slope ½, beside the period's spread scaled linearly, dt / T, a line of slope 1 that meets it only at a step of the period. Below it, the step and the spread over the period's.
- The checks: variances add, the walks' variance within 4.5 standard errors of the law's once four periods (256 walks) have ended; the same walk again, the first period walked again alongside each later one, ending where it ended to the bit; the textbook's case, a spread of 0.01 a minute being 0.01 √60 ≈ 0.0775 over an hour and 0.01 / √60 over a second, within two binary32 epsilons; powers of four, exactly, at 1 to 65536 steps a period, a power of four, the count times the step's spread squared the period's variance bit for bit, since the root is then a power of two; the period, and nothing, a step of the period giving the period's spread bit for bit and a step of nothing none. Each is held at every step.
Every number here is computed by the program on the GPU; the page only reads the values back and draws them. The spread, the period, the steps a period, the seed and the textbook's case are the program's settings, which the host may write; this page offers no control to change them yet.
The program¶
The walks, the powers of four, the sweep and the checks, the panels the page draws, and the one procedure, main, run each step: one step of every walk and of the first period walked again, a period's end summed, the sweep, and the checks.
// The step's volatility's live page: sixty-four random walks stepped a period at a time in sixteen steps, each step's
// spread from the library's law, their ends' variance held to the period's by a bound on the sampling error, the same
// walk walked again to the bit, the law swept over steps from a tenth of a second to an hour, and the law held to the
// textbook's case and its exact limits, with the page's checks computed here on the GPU and shown by the panels the
// program declares.
namespace step_volatility;
lusine.version version = { { number = 1 } };
// The reader's settings: the walks' spread over the period and the period; the steps a period; the seed the walks are
// drawn from; the periods walked before their variance is held to its bound; and the textbook's case, a spread of 0.01
// a minute over an hour and over a second.
host struct {
float spread = 0.012; float<s> period = 60.0 s; integer steps = 16; integer seed = 302; integer settle = 4;
float textbook = 0.01; float<s> minute = 60.0 s; float<s> hour = 3600.0 s; float<s> second = 1.0 s;
} settings;
// Sixty-four walks: where each is in this period, from 0; where it ended the first period; and the first period walked
// again alongside each later one.
struct walk { integer index; float at; float first; float again; bool repeated; };
table<walk> walks(capacity = 64) = {
{ index = 0 }, { index = 1 }, { index = 2 }, { index = 3 }, { index = 4 }, { index = 5 }, { index = 6 },
{ index = 7 }, { index = 8 }, { index = 9 }, { index = 10 }, { index = 11 }, { index = 12 }, { index = 13 },
{ index = 14 }, { index = 15 }, { index = 16 }, { index = 17 }, { index = 18 }, { index = 19 }, { index = 20 },
{ index = 21 }, { index = 22 }, { index = 23 }, { index = 24 }, { index = 25 }, { index = 26 }, { index = 27 },
{ index = 28 }, { index = 29 }, { index = 30 }, { index = 31 }, { index = 32 }, { index = 33 }, { index = 34 },
{ index = 35 }, { index = 36 }, { index = 37 }, { index = 38 }, { index = 39 }, { index = 40 }, { index = 41 },
{ index = 42 }, { index = 43 }, { index = 44 }, { index = 45 }, { index = 46 }, { index = 47 }, { index = 48 },
{ index = 49 }, { index = 50 }, { index = 51 }, { index = 52 }, { index = 53 }, { index = 54 }, { index = 55 },
{ index = 56 }, { index = 57 }, { index = 58 }, { index = 59 }, { index = 60 }, { index = 61 }, { index = 62 },
{ index = 63 },
};
// The steps a power of four, 1 to 65536, each step a period over its count, and each one's variance over the period,
// the count times the step's spread squared.
struct power { integer count; float variance; bool exact; };
table<power> powers(capacity = 9) = {
{ count = 1 }, { count = 4 }, { count = 16 }, { count = 64 }, { count = 256 }, { count = 1024 }, { count = 4096 },
{ count = 16384 }, { count = 65536 },
};
// The walks: the step within the period, the periods ended, the walks ended, their ends' squares summed, the variance
// over the period they give and the law's, the period's spread squared; the step's spread; and, for the chart, the
// walks' variance over the law's, beside 1 and the bounds it is held to.
struct {
integer step; integer periods; integer ended; float squares; float variance; float law; float spread; float ratio;
float fair = 1.0; float low; float high;
} walking;
// The sweep: steps from a second up by a quarter at a time, past an hour and round again; the step in decades,
// log10(dt / 1 s), from the quarters counted; the law's spread over it, over the period's, and the period's spread
// scaled linearly, over the period's, which it is not.
struct { integer quarters = -1; float<s> dt; float decades; float spread; float linear; } sweep;
// The checks: the walks' variance over the period within 4.5 standard errors of the law's, once the settle's periods
// have ended; the first period walked again to the bit; the textbook's case, 0.01 a minute 0.0775 an hour and 0.00129
// a second, each within two binary32 epsilons of 0.01 sqrt(60) and 0.01 / sqrt(60); at every step a power of four the
// count of steps giving back the period's variance bit for bit; a step of the period the period's spread itself, bit
// for bit; and a step of nothing no spread.
struct {
bool variance = true; bool again = true; bool textbook = true; bool powers = true; bool limits = true;
} checks;
// A strip of lamps the page draws, lit green while every check holds and red once one fails.
struct lamp { vector<float, 4> colour; };
lattice<lamp, 2> lamps(spacing = 1 m, boundary = wall);
vector<float, 4> lamp_colour(bool holds)
{
return holds ? vector<float, 4>(0.15, 0.6, 0.3, 1.0) : vector<float, 4>(0.75, 0.15, 0.15, 1.0);
}
// A step of a walk: uniform on [-a, a) with a = sqrt(3) times the step's spread, whose variance is the spread squared.
float stepped(integer seed, integer step, integer index, float spread)
{
let u = lusine.error.uniform(drawn = lusine.error.draw(seed = bits(seed), step = bits(step), key = fnv1a("walk"),
index = bits(index)));
return sqrt(3.0) * spread * (2.0 * u - 1.0);
}
float squares(table<float> at) { return sum(at * at); }
integer repeated(table<bool> repeated) { return count(repeated) where repeated; }
float<s> step_of(float<s> period, integer count) { return period / float(count); }
integer inexact(table<bool> exact) { return count(exact) where !exact; }
bool textbook(float textbook, float<s> minute, float<s> hour, float<s> second)
{
let an_hour = lusine.stochastic.step_volatility(per_period = textbook, period = minute, dt = hour);
let a_second = lusine.stochastic.step_volatility(per_period = textbook, period = minute, dt = second);
return abs <= 2.0 * 0.07745966692414834 / 8388608.0
&& abs <= 2.0 * 0.0012909944487358056 / 8388608.0;
}
bool limits(float spread, float<s> period)
{
return lusine.stochastic.step_volatility(per_period = spread, period, dt = period) == spread
&& lusine.stochastic.step_volatility(per_period = spread, period, dt = 0.0 s) == 0.0;
}
output table<lusine.widget> panels = {
lusine.series { { panel = "the walks", chart = "variance over the law's", quantity = walking.ratio, steps = 400,
label = "the walks'" } },
lusine.series { { panel = "the walks", chart = "variance over the law's", quantity = walking.fair, steps = 400,
label = "the law's" } },
lusine.series { { panel = "the walks", chart = "variance over the law's", quantity = walking.low, steps = 400,
label = "-4.5 se" } },
lusine.series { { panel = "the walks", chart = "variance over the law's", quantity = walking.high, steps = 400,
label = "+4.5 se" } },
lusine.value { { panel = "the walks", quantity = walking.ended, label = "walks ended" } },
lusine.value { { panel = "the walks", quantity = walking.variance, label = "their variance" } },
lusine.value { { panel = "the walks", quantity = walking.law, label = "the period's" } },
lusine.value { { panel = "the walks", quantity = walking.spread, label = "spread a step" } },
lusine.series { { panel = "the sweep", chart = "spread over the period's", quantity = sweep.spread, steps = 38,
against = sweep.decades, log = true, label = "the law" } },
lusine.series { { panel = "the sweep", chart = "spread over the period's", quantity = sweep.linear, steps = 38,
against = sweep.decades, log = true, label = "scaled linearly" } },
lusine.value { { panel = "the sweep", quantity = sweep.dt, label = "step" } },
lusine.value { { panel = "the sweep", quantity = sweep.spread, label = "over the period's" } },
lusine.value { { panel = "the checks", quantity = checks.variance, label = "variances add" } },
lusine.value { { panel = "the checks", quantity = checks.again, label = "the same walk again" } },
lusine.value { { panel = "the checks", quantity = checks.textbook, label = "the textbook's case" } },
lusine.value { { panel = "the checks", quantity = checks.powers, label = "powers of four, exactly" } },
lusine.value { { panel = "the checks", quantity = checks.limits, label = "the period, and nothing" } },
};
void main()
{
// A period's walks start from 0; the first period's ends are kept, and walked again alongside each later period.
walks.at = walking.step == 0 ? 0.0 : walks.at;
walks.again = walking.step == 0 ? 0.0 : walks.again;
walking.spread = lusine.stochastic.step_volatility(per_period = settings.spread, settings.period,
dt = step_of(settings.period, count = settings.steps));
walks.at = walks.at + stepped(settings.seed, step = walking.periods * settings.steps + walking.step, walks.index,
walking.spread);
walks.again = walks.again + stepped(settings.seed, walking.step, walks.index, walking.spread);
walking.step = walking.step + 1;
walks.first = walking.periods == 0 && walking.step == settings.steps ? walks.at : walks.first;
walks.repeated = walks.again == walks.first;
checks.again = checks.again && (walking.step < settings.steps || repeated(walks.repeated) == 64);
walking.squares = walking.step == settings.steps ? walking.squares + squares(walks.at) : walking.squares;
walking.ended = walking.step == settings.steps ? walking.ended + 64 : walking.ended;
walking.periods = walking.step == settings.steps ? walking.periods + 1 : walking.periods;
walking.step = walking.step == settings.steps ? 0 : walking.step;
walking.law = settings.spread * settings.spread;
walking.variance = walking.ended == 0 ? 0.0 : walking.squares / float(walking.ended);
walking.ratio = walking.variance / walking.law;
walking.low = walking.ended == 0 ? 0.0 : 1.0 - 4.5 * sqrt(1.925 / float(walking.ended));
walking.high = walking.ended == 0 ? 2.0 : 1.0 + 4.5 * sqrt(1.925 / float(walking.ended));
// A sum of sixteen uniform steps has the excess kurtosis -1.2 / 16, so the variance of its square is 1.925 times
// the law's squared, and the mean of n squares has that over n.
checks.variance = checks.variance
&& (walking.periods < settings.settle
|| (walking.variance / walking.law - 1.0) * (walking.variance / walking.law - 1.0)
<= 20.25 * 1.925 / float(walking.ended));
powers.variance = float(powers.count) * lusine.stochastic.step_volatility(per_period = settings.spread,
settings.period,
dt = step_of(settings.period,
powers.count))
* lusine.stochastic.step_volatility(per_period = settings.spread, settings.period,
dt = step_of(settings.period, powers.count));
powers.exact = powers.variance == settings.spread * settings.spread;
checks.powers = checks.powers && inexact(powers.exact) == 0;
checks.textbook = checks.textbook && textbook(settings.textbook, settings.minute, settings.hour, settings.second);
checks.limits = checks.limits && limits(settings.spread, settings.period);
sweep.quarters = sweep.quarters >= 37 ? 0 : sweep.quarters + 1;
sweep.dt = sweep.quarters == 0 ? 1.0 s : sweep.dt * 1.25;
sweep.decades = float(sweep.quarters) * 0.09691001300805639;
sweep.spread = lusine.stochastic.step_volatility(per_period = settings.spread, settings.period, sweep.dt)
/ settings.spread;
sweep.linear = sweep.dt / settings.period;
lamps.colour = lamp_colour(holds = checks.variance && checks.again && checks.textbook && checks.powers
&& checks.limits);
}
The law's other proof (the variance over a thousand counts of steps, against a reference in float64) is on its proof page.