convergence test for pseudo-stochastic monte carloesque dynamically updated loop exit condition

dynamic-exit-condition-convergence-test.js

// 21 November 2023
// convergence test for pseudo-stochastic monte carloesque dynamically updated
// loop exit condition

// program proof that loops with changing random length converge on square root
// of max length (from a Tweet the other day that jonathan blow responded to).

// T asked why programmers think a loop with length reset to random * 100 will
// average to 50 instead of 10 (well, actually, it will converge on the square
// root of max plus 2, given the first two steps always execute).

// In the random * 100 case, the chances of producing max 10 are 1 in 10, so for
// 10 iterations we are likely to see at least one value of 10, from which we
// also conclude that for random * 64 will converge on 10 (8 plus 2).


function converge(n) {
  var max = +n == n ? +n : 100;
  var counts = [];

  for (var i = 0; i < max; i++) {
    var count = 1;

    // pseudo-stochastic monte carloesque dynamically updated exit condition
    while (count < (Math.random() * max)) {
      count++;
    }

    counts.push(count);
  }

  var avg = counts.reduce((sum, next) => sum + next, 0) / counts.length;

  return +(avg.toFixed(2));
}


/* test it out */


console.group('100');
var v1 = Array.from({length: 1000}).map(_ => converge( '100' ));
console.log(v1);
console.log(v1.reduce((sum, next) => sum + next, 0) / v1.length);
console.groupEnd('100');

console.group('64');
var v2 = Array.from({length: 1000}).map(_ => converge( '64' ));
console.log(v2);
console.log(v2.reduce((sum, next) => sum + next, 0) / v2.length);
console.groupEnd('64');