algorithm - Generating a Smooth Random Trend (Random Walk) in JavaScript

Question

I am looking for a JavaScript implementation of a random walk/random trend algorithm. I need something that will stick with a trend (so, just plain random deltas are out) while still staying within some specified boundaries. I tried writing something off the top of my head by choosing numbers based on a weighted average (the weight was calculated using the Gaussian function) and ended up with a slightly smoother line (not good enough). I then took a less direct approach and tried searching on the internet, and although I found a few outlines, there was nothing specific enough that I understood.

As it turns out (I was not aware of this originally), it seems there is already a family of algorithms that use the Gaussian equation to make a random trend. But, despite hours of searching, I couldn't find much more than abstract equations that were no use to me. The best that I could find was this blog where he shows a picture of random data like I'm looking for. He lists equations, but I have no idea what those actually are supposed to mean (to me, it doesn't seem like it's even a full solution).

What algorithms are already out there (JavaScript or C-like implementations preferably) to generate data like this?

Answer 1

Here is what I came up with from reading the blog that you linked. As far as I can tell, this is what the author did for his first graph.

CSS

#container {
    min-width: 310px;
    height: 400px;
    margin: 0 auto;
}

HTML

<div id="container"></div>

Javascript

Box–Muller transform to generate Gaussian Random Numbers

var boxMullerRandom = (function () {
    var phase = 0,
        RAND_MAX,
        array,
        random,
        x1, x2, w, z;

    if (crypto && typeof crypto.getRandomValues === 'function') {
        RAND_MAX = Math.pow(2, 32) - 1;
        array = new Uint32Array(1);
        random = function () {
            crypto.getRandomValues(array);

            return array[0] / RAND_MAX;
        };
    } else {
        random = Math.random;
    }

    return function () {
        if (!phase) {
            do {
                x1 = 2.0 * random() - 1.0;
                x2 = 2.0 * random() - 1.0;
                w = x1 * x1 + x2 * x2;
            } while (w >= 1.0);

            w = Math.sqrt((-2.0 * Math.log(w)) / w);
            z = x1 * w;
        } else {
            z = x2 * w;
        }

        phase ^= 1;

        return z;
    }
}());

Random Walk generator

function randomWalk(steps, randFunc) {
    steps = steps >>> 0 || 100;
    if (typeof randFunc !== 'function') {
        randFunc = boxMullerRandom;
    }

    var points = [],
        value = 0,
        t;

    for (t = 0; t < steps; t += 1) {
        value += randFunc();
        points.push([t, value]);
    }

    return points;
}

Helper function to get the Y values from the Random Walk points

function getYValues(points) {
    return points.map(function (point) {
        return point[1];
    });
}

Helper function to generate X plots for the graph

function generatePlots(howMany) {
    howMany = howMany >>> 0 || 10;
    var plots = [],
        index;

    for (index = 0; index < howMany; index += 1) {
        plots.push({
            name: 'plot' + index,
            data: getYValues(randomWalk())
        });
    }

    return plots;
}

Graph the results, uses jQuery and highcharts.js

$('#container').highcharts({
    title: {
        text: 'Random Walk',
        x: -20 //center
    },
    subtitle: {
        text: 'Random Walk',
        x: -20
    },
    xAxis: {
        type: 'linear'
    },
    yAxis: {
        title: {
            text: 'Value'
        },
        plotLines: [{
            value: 0,
            width: 1,
            color: '#808080'
        }]
    },
    tooltip: {
        valueSuffix: ' units'
    },
    legend: {
        layout: 'vertical',
        align: 'right',
        verticalAlign: 'middle',
        borderWidth: 0
    },
    series: generatePlots(10)
});

On jsFiddle