bucketed-bootstrap.js

/*
 * Build a sample from the given values array with replacement.
 */
function sample(values) {
  var sampleValues = [];
  for (let i = 0; i < values.length; i++) {
    sampleValues.push(values[Math.floor(Math.random() * values.length)]);
  }
  return sampleValues;
}

/*
 * Run the normal bootstrap, with the given eval function, iterations, and
 * desired confidence interval (e.g. 0.1 for 5%-95% bounds).
 */
function bootstrap(values, eval, iterations, ci) {
  var evals = [];
  for (let i = 0; i < iterations; i++) {
    var sampleValues = sample(values);
    evals.push(eval(sampleValues));
  }
  evals.sort();
  return {
    lower: evals[Math.floor(ci / 2.0 * iterations)],
    upper: evals[Math.floor((1 - ci / 2.0) * iterations)]
  };
}

/*
 * Run the bucketed bootstrap, with the given eval function, iterations, and
 * desired confidence interval (e.g. 0.1 for 5%-95% bounds).
 */
function bootstrapBuckets(values, evalBuckets, iterations, ci) {
  var buckets = [];
  for (let i = 0; i < 100; i++) {
    buckets.push([]);
  }
  for (let i = 0; i < values.length; i++) {
    buckets[Math.floor(Math.random() * 100)].push(values[i]);
  }
  var evals = [];
  for (let i = 0; i < iterations; i++) {
    var sampleBuckets = sample(buckets);
    evals.push(evalBuckets(sampleBuckets));
  }
  evals.sort();
  return {
    lower: evals[Math.floor(ci / 2.0 * iterations)],
    upper: evals[Math.floor((1 - ci / 2.0) * iterations)]
  };
}

/*
 * Generates a unform distribution.
 */
function generateUniform(size) {
  var values = [];
  for (let i = 0; i < size; i++) {
    values.push(Math.random() * 100);
  }
  return values;
}

/*
 * Returns the average of an array of values.
 */
function evalAverage(values) {
  return values.reduce((a, b) => a + b) / values.length;
}

/*
 * Returns the average of an array of arrays of values.
 */
function evalAverageBuckets(buckets) {
  var sum = 0;
  var count = 0;
  for (let i = 0; i < buckets.length; i++) {
    sum += buckets[i].reduce((a, b) => a + b);
    count += buckets[i].length;
  }
  return sum / count;
}

var resultsCsv = "";
resultsCsv += "index,lower,bucket_lower,upper,bucket_upper\n";
for (let i = 0; i < 1000; i++) {
  var uniformDistribution = generateUniform(10000);
  var interval = bootstrap(uniformDistribution, evalAverage, 1000, 0.1);
  var bucketInterval = bootstrapBuckets(uniformDistribution, evalAverageBuckets, 1000, 0.1);
  resultsCsv += `${i},${interval.lower},${bucketInterval.lower},${interval.upper},${bucketInterval.upper}\n`;
}

var fs = require("fs");
fs.writeFile("results.csv", resultsCsv, err => {
  if (err) console.log(err);
});