How to calculate confidence intervals for future values of a random walk in Javascript?

Question

I have a random-number-generator hooked up to a simple "random walk" experiment. It looks something like this:

let valueAtStepX = [];
let lastValue = 0;
for (let i = 0; i < 1000; i++) {
    let randomDeviationThisStep = Math.floor(Math.random() * 201) - 100;
    lastValue += randomDeviationThisStep;
    valueAtStepX[i] = lastValue;
}

I now want to be able to calculate the "confidence interval" for the value X steps in the future. That is, I want to know what range I can be 95% sure that the value X steps in the future will be within.

I believe I've found a function to forecast this confidence-interval, however it's in another language (R): https://github.com/robjhyndman/forecast/blob/master/R/naive.R

Does anyone know of a Javascript function to perform this calculation? In the mean-time, I will try converting the R function above into Javascript.

Answer 1

Okay, I think I've managed to convert the R function above into Typescript/Javascript. (although I've removed some of the parameters and such since I didn't have a use for those other options)

export function GetUpperAndLowerBoundForRandomWalkOfXSteps(maxDeviationPerStep: number, stepsAhead: number, confidenceLevel = .95) {
    let standardDeviationOfStep = Math.sqrt(maxDeviationPerStep / 2);
    let standardDeviationOfStepX = Math.sqrt((maxDeviationPerStep / 2) * stepsAhead);

    let z = InverseCumulativeProbability(confidenceLevel, standardDeviationOfStep);
    let upperBound = z * standardDeviationOfStepX;
    //let lowerBound = -upperBound;
    return upperBound;
}

const Sqrt2 = 1.4142135623730950488016887;
function InverseCumulativeProbability(probability: number, standardDeviationOfStep: number) {
    var Z = Sqrt2 * InverseErrorFunc(probability);
    return Z * standardDeviationOfStep;
}
function InverseErrorFunc(x: number){
    if (x == 0) return 0;
    var a = 0.147;

    var the_sign_of_x =
        x > 0 ? 1 :
        x < 0 ? -1 :
        0;

    var ln_1minus_x_sqrd = Math.log(1 - x * x);
    var ln_1minusxx_by_a = ln_1minus_x_sqrd / a;
    var ln_1minusxx_by_2 = ln_1minus_x_sqrd / 2;
    var ln_etc_by2_plus2 = ln_1minusxx_by_2 + (2 / (Math.PI * a));
    var first_sqrt = Math.sqrt((ln_etc_by2_plus2 * ln_etc_by2_plus2) - ln_1minusxx_by_a);
    var second_sqrt = Math.sqrt(first_sqrt - ln_etc_by2_plus2);
    let z = second_sqrt * the_sign_of_x;
    return z;
}

Here is a screenshot of it used in a graph, with the gray lines marking the 95% confidence intervals:

NOTE: After further reading on the topic, I believe the solution above is not quite correct. It appears to give a similar result to the "correct" algorithm, but is off some because the R functions were meant to work on actual "sampled" data, whereas my use case is trying to calculate the theoretical confidence-intervals based on known generation probabilities.

I've since brought together a set of functions that I think are correct, but it makes use of some code from another Github repo (https://github.com/RajahBimmy/Sungear/tree/master/public/javascripts/hyperGeo/distribution), so is not practical to lay out in full here.

Nonetheless, I'll include the part I put together on top of that base:

/**
 * Finds the standard-deviation for a Binomial distribution with the given parameters. (a Binomial distribution consists of a series of yes/no trials, where each trial is independent of the previous one)
 * For a Binomial distribution, the theoretical/expected variance is: yesNoTrialCount * yesProbability * (1 - yesProbability) [https://en.wikipedia.org/wiki/Binomial_distribution#Variance]
 * To then get the standard-deviation, just calculate the square-root of that variance.
 */
export function GetStandardDeviationForBinomialDistribution(yesNoTrialCount: number, yesProbability: number) {
    let variance = yesNoTrialCount * yesProbability * (1 - yesProbability);
    return Math.sqrt(variance);
}

let binomialDistributionToRange_cache = {};

/**
 * @param yesNoTrialCount The total number of yes/no trials (eg. 0 or 1 bits) that went into creating the data set.
 * @param yesProbability The probability each trial had of yielding a "1" bit. (assumes a binomial distribution, ie. that each trial is independent of the previous one)
 * @param confidenceInterval The certainty level, ie. how "wide" of a confidence interval we want to calculate. Range: 0-1 (eg: 0.95 means 95%)
 * @returns The smallest distance from the theoretical mean, within which we're X% (confidenceInterval) sure that the terminal-value/end-point of a random walk with these parameters will be found.
 */
export function GetRangeHavingXPercentCertaintyOfContainingRandomWalkEndPoint_Binomial(yesNoTrialCount: number, yesProbability: number, confidenceInterval = .95, minLower?: number, maxUpper?: number) {
    if (yesNoTrialCount == 0) return 0;

    let key_part1 = `${yesProbability}|${confidenceInterval}`;
    let key_part2 = yesNoTrialCount;

    binomialDistributionToRange_cache[key_part1] = binomialDistributionToRange_cache[key_part1] || {};
    let highestKeyPart2UnderCurrent = binomialDistributionToRange_cache[key_part1].VKeys().map(ToInt).filter(a=>a <= key_part2).OrderBy(a=>a).LastOrX();

    if (highestKeyPart2UnderCurrent != key_part2) {
        // works I think, but doesn't seem to be needed
        /*if (highestKeyPart2UnderCurrent != null) {
            let highestKeyPart2UnderCurrent_result = binomialDistributionToRange_cache[key_part1][highestKeyPart2UnderCurrent];
            minLower = (minLower != null ? minLower : 0).KeepAtLeast(highestKeyPart2UnderCurrent_result);
        }*/

        let binomialDistribution = new BinonomialDistribution(yesNoTrialCount, yesProbability);
        let result = binomialDistribution.inverseCumulativeProbability(confidenceInterval, minLower, maxUpper).Distance(binomialDistribution.getNumericalMean());
        binomialDistributionToRange_cache[key_part1][key_part2] = result;
    }
    return binomialDistributionToRange_cache[key_part1][key_part2];
}

Answer 2

There is no built-in function in Javascript equivalent to what you found in R. While R is a tool built specifically for data science, Javascript is designed for web usage; statistics methods are not among web development's concerns. So you either need a Javascript library, or do the work yourself.

Best match for your problem might be jStat.js.