#!/usr/bin/env node
// ─────────────────────────────────────────────────────────────────────────────
// The Arcsine Law of a Fair Coin — offline verifier
//
// P7 (playable STEM) / P2 (small true things).  Every number that the immersive
// page displays is recomputed here from first principles, and — where the object
// is small enough — checked by BRUTE-FORCE ENUMERATION of all 2^(2m) paths, with
// exact integer arithmetic (BigInt).  The house rule: nothing is asserted on the
// page that does not PASS below.
//
// The surprise being verified: for a fair ±1 coin-toss walk of 2m steps,
//   • the number of steps the walker spends on the WINNING side is NOT bunched
//     near half — its distribution is U-shaped (arcsine).  The single most likely
//     outcome is spending ALL of the time on one side.
//   • lead changes (returns to a tie) are rare: their count grows like √(2N/π).
//   • the same U-shaped law governs THREE different quantities at once:
//       (a) time in the lead,  (b) the last tie,  (c) the position of the peak.
//
// What we prove, in order:
//   A. Central-binomial convolution identity  Σ_k C(2k,k)C(2m-2k,m-k) = 4^m.
//   B. Chung–Feller, exact.   #paths of length 2m with exactly 2k positive
//                             segments  ==  C(2k,k)·C(2m-2k,m-k).   (Enumerated.)
//   C. Last-tie law, exact.   #paths whose LAST return to 0 is at step 2k  ==
//                             C(2k,k)·C(2m-2k,m-k).   Same law.   (Enumerated.)
//   D. Peak-position law.     The position of the first maximum obeys the same
//                             arcsine limit (enumerated CDF → (2/π)arcsin√x).
//   E. U-shape.               α_{2k,2m} is minimised at the middle and maximised
//                             at BOTH ends (0 and 2m) — "ahead the whole time" is
//                             the single most probable outcome.
//   F. Continuous limit.      The enumerated CDF converges to (2/π)arcsin√x; the
//                             max deviation shrinks as m grows.
//   G. The headline numbers.  P(balanced, 45–55% ahead) ≈ 0.064;
//                             P(lopsided, ≥90% or ≤10% ahead) ≈ 0.410.
//   H. Ties are rare.         E[# returns to 0 in N=2m steps] → √(2N/π).
//   I. Drift breaks it.       A biased coin is NOT arcsine — the law is a fact
//                             about the DRIFTLESS symmetric walk, and we show the
//                             U-shape collapse under bias so the page can't overclaim.
//   J. Monte-Carlo bridge.    The sampling the browser does (finite batches of
//                             random walks) converges to the exact law within the
//                             expected statistical error — the live histogram is honest.
//
// Run:  node research/arcsine-law/verify.mjs
// ─────────────────────────────────────────────────────────────────────────────

let pass = 0, fail = 0;
const fails = [];
function check(name, cond, got, want) {
  if (cond) { pass++; console.log(`  PASS  ${name}`); }
  else { fail++; fails.push(name); console.log(`  FAIL  ${name}${got !== undefined ? `   got ${got}, want ${want}` : ''}`); }
}
const close = (a, b, tol) => Math.abs(a - b) <= tol;

// ── exact combinatorics (BigInt, any n) ─────────────────────────────────────
function C(n, k) {            // exact binomial for arbitrary n,k
  n = BigInt(n); k = BigInt(k);
  if (k < 0n || k > n) return 0n;
  if (k > n - k) k = n - k;
  let num = 1n, den = 1n;
  for (let i = 0n; i < k; i++) { num *= (n - i); den *= (i + 1n); }
  return num / den;
}
const alphaExact = (k, m) => C(2 * k, k) * C(2 * m - 2 * k, m - k); // integer count, = 4^m·α_{2k,2m}

// u_{2k} = P(S_{2k}=0) = C(2k,k)/4^k, built by the exact stable recurrence
//   u_0 = 1,  u_{2k} = u_{2k-2}·(2k-1)/(2k).   Float, valid to any k.
function uTable(kmax) {
  const t = new Float64Array(kmax + 1); t[0] = 1;
  for (let k = 1; k <= kmax; k++) t[k] = t[k - 1] * (2 * k - 1) / (2 * k);
  return t;
}
const u2 = (k) => uTable(k)[k];                                 // convenience for small k

// ── A. the convolution identity Σ_k C(2k,k)C(2m-2k,m-k) = 4^m ────────────────
console.log('\nA. Central-binomial convolution identity  Σ_k C(2k,k)C(2m-2k,m-k) = 4^m');
for (const m of [1, 3, 5, 8, 12, 20]) {
  let s = 0n;
  for (let k = 0; k <= m; k++) s += alphaExact(k, m);
  check(`Σ = 4^${m}  (m=${m})`, s === 4n ** BigInt(m), s.toString(), (4n ** BigInt(m)).toString());
}

// ── brute-force enumeration of all 2^(2m) sign sequences ────────────────────
// For each path of length 2m:
//   segAbove : # of segments i∈[1,2m] with S_{i-1}+S_i>0  (a "positive segment";
//              since consecutive sums differ by 1 the sum is odd, never 0, so
//              every segment is strictly above or strictly below — no ties to fudge).
//   lastZero : the largest i∈[0,2m] with S_i=0  (S_0=0, so always defined; even).
//   firstMax : the first i∈[0,2m] attaining max_i S_i.
//   returns  : # of i∈[1,2m] with S_i=0  (ties / lead-restarts).
function enumerate(m) {
  const n = 2 * m;
  const cntSeg = new Array(m + 1).fill(0);   // indexed by k where segAbove=2k
  const cntLast = new Array(m + 1).fill(0);  // indexed by k where lastZero=2k
  const cntMax = new Array(n + 1).fill(0);   // indexed by firstMax position 0..n
  const cntPos = new Array(n + 1).fill(0);   // indexed by #{i: S_i>0}  (0..n)
  let sumReturns = 0;
  const total = 1 << n;
  for (let mask = 0; mask < total; mask++) {
    let S = 0, seg = 0, last = 0, maxV = 0, maxAt = 0, ret = 0, pos = 0;
    for (let i = 0; i < n; i++) {
      const prev = S;
      S += (mask >> i) & 1 ? 1 : -1;
      if (prev + S > 0) seg++;               // positive segment
      if (S > 0) pos++;                       // moment strictly ahead
      if (S === 0) { last = i + 1; ret++; }
      if (S > maxV) { maxV = S; maxAt = i + 1; }
    }
    cntSeg[seg / 2]++;
    cntLast[last / 2]++;
    cntMax[maxAt]++;
    cntPos[pos]++;
    sumReturns += ret;
  }
  return { n, total, cntSeg, cntLast, cntMax, cntPos, sumReturns };
}

// ── B & C. Chung–Feller and the last-tie law, exact by enumeration ──────────
console.log('\nB. Chung–Feller (time-in-lead), exact:  #paths(2k positive segments) = C(2k,k)C(2m-2k,m-k)');
console.log('C. Last-tie law, exact:                 #paths(last tie at 2k)      = C(2k,k)C(2m-2k,m-k)');
const enums = {};
for (const m of [2, 3, 4, 5, 6, 8, 10, 11]) {
  const e = enumerate(m);
  enums[m] = e;
  let okSeg = true, okLast = true;
  for (let k = 0; k <= m; k++) {
    if (BigInt(e.cntSeg[k]) !== alphaExact(k, m)) okSeg = false;
    if (BigInt(e.cntLast[k]) !== alphaExact(k, m)) okLast = false;
  }
  check(`time-in-lead distribution exact  (m=${m}, ${e.total} paths)`, okSeg);
  check(`last-tie distribution exact      (m=${m}, ${e.total} paths)`, okLast);
}

// ── D. peak position — the exact Sparre Andersen equivalence ─────────────────
// The index of the first maximum and the number of strictly-positive partial
// sums are EQUIDISTRIBUTED (Sparre Andersen 1954).  This is an exact identity,
// not an asymptotic — so we check the two enumerated histograms are identical.
// Both, in turn, tend to the arcsine law; the position of the peak is arcsine
// for the same reason the time-in-lead is.
const arcCDF = (x) => (2 / Math.PI) * Math.asin(Math.sqrt(Math.max(0, Math.min(1, x))));
console.log('\nD. Peak position — exact Sparre Andersen equivalence  (argmax index =d #{S_i>0})');
for (const m of [4, 6, 8, 10, 11]) {
  const e = enums[m];
  let identical = true;
  for (let j = 0; j <= e.n; j++) if (e.cntMax[j] !== e.cntPos[j]) identical = false;
  check(`argmax-index and #positive-sums equidistributed (m=${m})`, identical);
}

// ── E. U-shape: ends dominate, middle is the trough ─────────────────────────
console.log('\nE. U-shape: α_{0,2m} = α_{2m,2m} are the maxima; the middle is the minimum');
for (const m of [6, 10, 20]) {
  const a = (k) => alphaExact(k, m);
  const ends = a(0);                            // = a(m) by symmetry
  const mid = a(Math.floor(m / 2));
  let endsAreMax = true, midIsMin = true;
  for (let k = 0; k <= m; k++) {
    if (a(k) > ends) endsAreMax = false;
    if (a(k) < mid) midIsMin = false;
  }
  check(`ends maximal (m=${m})`, endsAreMax && a(0) === a(m));
  check(`middle minimal (m=${m})`, midIsMin);
}

// ── F. continuous limit: exact discrete CDF → (2/π)arcsin√x, error shrinks ───
// Using the EXACT discrete arcsine pmf  p_k = u_{2k}·u_{2m-2k}  (float recurrence,
// valid to any m) so we can push m far past what enumeration allows.  The
// convergence is genuinely slow near the endpoints (the atom at k=0 is ~1/√(πm)),
// which is itself part of the story — so we verify it shrinks like 1/√m.
console.log('\nF. Continuous limit: max deviation of the EXACT discrete CDF from (2/π)arcsin√x shrinks ~1/√m');
{
  const devs = [];
  for (const m of [11, 50, 200, 1000, 5000]) {
    const U = uTable(m);
    const pmf = new Float64Array(m + 1);
    for (let k = 0; k <= m; k++) pmf[k] = U[k] * U[m - k];
    let maxDev = 0;
    for (const x of [0.02, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.98]) {
      let c = 0;
      for (let k = 0; k <= m; k++) if (k / m < x) c += pmf[k];
      maxDev = Math.max(maxDev, Math.abs(c - arcCDF(x)));
    }
    devs.push({ m, maxDev });
  }
  console.log('   deviations:', devs.map(d => `m=${d.m}:${d.maxDev.toFixed(4)}`).join('  '));
  const shrinking = devs.every((d, i) => i === 0 || d.maxDev <= devs[i - 1].maxDev + 1e-9);
  check('deviation strictly shrinks with m', shrinking);
  check('deviation < 0.01 by m=5000', devs[devs.length - 1].maxDev < 0.01, devs[devs.length - 1].maxDev.toFixed(4), '<0.01');
  // the single largest atom sits at the endpoint and its height is exactly u_{2m} ~ 1/√(πm):
  const m = 1000, atom = uTable(m)[0] * uTable(m)[m];
  check('endpoint atom height = u_{2m} ≈ 1/√(πm)  (m=1000)', close(atom, 1 / Math.sqrt(Math.PI * m), 5e-4), atom.toFixed(4), (1 / Math.sqrt(Math.PI * m)).toFixed(4));
}

// ── G. the headline numbers (continuous arcsine) ────────────────────────────
console.log('\nG. Headline numbers from the continuous arcsine law');
{
  const pBalanced = arcCDF(0.55) - arcCDF(0.45);          // 45–55% of the time ahead
  const pLopsided = arcCDF(0.10) + (1 - arcCDF(0.90));    // ≤10% or ≥90%
  console.log(`   P(45–55% ahead)  = ${pBalanced.toFixed(4)}`);
  console.log(`   P(≤10% or ≥90%)  = ${pLopsided.toFixed(4)}`);
  check('P(balanced 45–55%) ≈ 0.064', close(pBalanced, 0.0640, 0.001), pBalanced.toFixed(4), '0.0640');
  check('P(lopsided ≥90%/≤10%) ≈ 0.410', close(pLopsided, 0.4097, 0.001), pLopsided.toFixed(4), '0.4097');
  check('lopsided is > 6× more likely than balanced', pLopsided / pBalanced > 6);
}

// ── H. ties are rare: E[# returns to 0] → √(2N/π) ───────────────────────────
console.log('\nH. Ties are rare:  E[# returns to 0 in N=2m steps]  →  √(2N/π)');
{
  // exact expectation by linearity: Σ_{j=1}^m P(S_{2j}=0) = Σ u_{2j}
  const Ubig = uTable(5000);
  for (const m of [10, 50, 500, 5000]) {
    let E = 0;
    for (let j = 1; j <= m; j++) E += Ubig[j];
    const N = 2 * m, asymp = Math.sqrt(2 * N / Math.PI);
    const ratio = E / asymp;
    if (m <= 11 && enums[m]) {
      // cross-check the exact expectation against the enumerated mean
      const encMean = enums[m].sumReturns / enums[m].total;
      check(`E[returns] matches enumeration (m=${m})`, close(E, encMean, 1e-9), E.toFixed(6), encMean.toFixed(6));
    }
    if (m === 5000) check(`E[returns]/√(2N/π) → 1 (m=${m})`, close(ratio, 1, 0.02), ratio.toFixed(4), '≈1');
  }
}

// ── I. drift breaks it: a biased coin is NOT arcsine ────────────────────────
console.log('\nI. Scope guard — a biased coin is NOT arcsine (the law needs a fair coin)');
{
  // enumerate with weights p (up), q=1-p; measure P(fraction in lead in [0.45,0.55])
  function biasedBalancedProb(m, p) {
    const n = 2 * m, q = 1 - p, total = 1 << n;
    let probBalanced = 0;
    for (let mask = 0; mask < total; mask++) {
      let S = 0, seg = 0, w = 1;
      for (let i = 0; i < n; i++) {
        const prev = S, up = (mask >> i) & 1;
        S += up ? 1 : -1; w *= up ? p : q;
        if (prev + S > 0) seg++;
      }
      const frac = seg / n;
      if (frac >= 0.45 && frac <= 0.55) probBalanced += w;
    }
    return probBalanced;
  }
  const fair = biasedBalancedProb(10, 0.5);
  const biased = biasedBalancedProb(10, 0.6);
  console.log(`   P(45–55% ahead | fair p=0.5) = ${fair.toFixed(4)}`);
  console.log(`   P(45–55% ahead | biased p=0.6) = ${biased.toFixed(4)}`);
  // Under drift the winner leads essentially the whole time, so "balanced" gets RARER.
  check('bias makes "balanced" even rarer than the (already rare) fair case', biased < fair, biased.toFixed(4), `<${fair.toFixed(4)}`);
}

// ── J. Monte-Carlo bridge: the browser's sampling is honest ─────────────────
console.log('\nJ. Monte-Carlo bridge — finite batches of random walks match the exact law');
{
  // deterministic PRNG (mulberry32) so the check is reproducible
  function mulberry32(a) { return function () { a |= 0; a = a + 0x6D2B79F5 | 0; let t = Math.imul(a ^ a >>> 15, 1 | a); t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t; return ((t ^ t >>> 14) >>> 0) / 4294967296; }; }
  const rnd = mulberry32(12345);
  const m = 200, n = 2 * m, TRIALS = 40000;
  const bins = 20, hist = new Array(bins).fill(0);
  for (let t = 0; t < TRIALS; t++) {
    let S = 0, seg = 0;
    for (let i = 0; i < n; i++) { const prev = S; S += rnd() < 0.5 ? 1 : -1; if (prev + S > 0) seg++; }
    let b = Math.floor((seg / n) * bins); if (b === bins) b = bins - 1;
    hist[b]++;
  }
  // compare bin frequencies to the arcsine-law probabilities of each bin
  let maxDev = 0;
  for (let b = 0; b < bins; b++) {
    const lo = b / bins, hi = (b + 1) / bins;
    const pExact = arcCDF(hi) - arcCDF(lo);
    const pEmp = hist[b] / TRIALS;
    maxDev = Math.max(maxDev, Math.abs(pEmp - pExact));
  }
  console.log(`   max bin deviation over ${TRIALS} walks = ${maxDev.toFixed(4)}`);
  check('Monte-Carlo histogram within 0.01 of the exact arcsine bins', maxDev < 0.01, maxDev.toFixed(4), '<0.01');
  // and the U-shape is visible: end bins are the tallest
  check('U-shape present: end bins taller than the middle bins', hist[0] > hist[bins / 2] && hist[bins - 1] > hist[bins / 2]);
}

// ── K. exact numbers quoted on the page ─────────────────────────────────────
console.log('\nK. Verified numbers for the page copy (exact discrete arcsine)');
{
  const rows = [];
  for (const N of [20, 100, 1000]) {
    const m = N / 2, U = uTable(m);
    const pmf = (k) => U[k] * U[m - k];
    const pEnds = pmf(0) + pmf(m);                       // ahead the WHOLE game or none of it
    // "balanced" = fraction of segments in [0.45,0.55]  → k in [0.45m, 0.55m]
    let pBal = 0;
    for (let k = 0; k <= m; k++) { const f = k / m; if (f >= 0.45 && f <= 0.55) pBal += pmf(k); }
    // is the endpoint the single most likely lead-count (the mode)?
    let modeAtEnd = true;
    for (let k = 1; k < m; k++) if (pmf(k) > pmf(0) + 1e-15) modeAtEnd = false;
    rows.push({ N, pAllOneSide: pmf(m), pEnds, pBal, modeAtEnd });
    console.log(`   N=${N}:  P(ahead entire game)=${pmf(m).toFixed(4)}   P(all one side)=${pEnds.toFixed(4)}   P(balanced 45–55%)=${pBal.toFixed(4)}`);
  }
  // sanity: at N=20, ahead-whole-game = C(20,10)/4^10
  const exact20 = Number(C(20, 10)) / 4 ** 10;
  check('N=20 P(ahead entire game) = C(20,10)/4^10 ≈ 0.1762', close(rows[0].pAllOneSide, exact20, 1e-9) && close(exact20, 0.1762, 5e-4), exact20.toFixed(4), '0.1762');
  // the honest, scale-free claim: the endpoint lead-count is the single most likely value (the mode) at every N
  check('"ahead the whole game" is the single most likely lead-count (the mode) at every N', rows.every(r => r.modeAtEnd));
  // and at the small N a reader will actually watch, the atom does beat the balanced band
  check('at N=20 (watchable scale) ahead-whole-game (0.176) > balanced band (0.061)', rows[0].pAllOneSide > rows[0].pBal);
}

// ── tally ───────────────────────────────────────────────────────────────────
console.log(`\n${'─'.repeat(60)}`);
console.log(`  ${pass}/${pass + fail} checks passed${fail ? `  —  FAILED: ${fails.join(', ')}` : '  —  all green'}`);
console.log('─'.repeat(60));
process.exit(fail ? 1 : 0);
