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

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?

Share Improve this question edited Feb 27, 2014 at 21:37 Xotic750 23.5k8 gold badges59 silver badges81 bronze badges asked Feb 27, 2014 at 3:05 Wasabi Fan 1,8633 gold badges24 silver badges39 bronze badges

Here's the first relevant search query I could think of (athough there may be others): google./#q=smooth+random+walk+algorithm – Anderson Green Commented Feb 27, 2014 at 3:11
1 Is this what you are looking for? It's the best that I could work out from looking at the link to the blog that you posted. It's the first graph on the blog, 10 plots of 100 steps. – Xotic750 Commented Feb 27, 2014 at 10:18
@Xotic750 Holy crap; That works pretty well! Can you explain a bit how it works, so I can modify it if need be? For example, how can I make it spread more, or how can I limit it's values? – Wasabi Fan Commented Feb 27, 2014 at 17:09
Added as an answer, improved the functions to give you a little more control. You can choose the number of steps in the randomWalk to control spread. To limit the values create a function that modifies the boxMullerRandom values and feed that function to the randomWalk. The graph is just for prettiness to show it working, use whatever grapher or the data as you wish. – Xotic750 Commented Feb 27, 2014 at 21:24

Add a ment |

1 Answer 1

Sorted by: Reset to default 16

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

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始

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

1 Answer 1

与本文相关的文章

评论列表(0)