Introduction

Imagine flipping a fair coin for money. Heads you gain $1, tails you lose $1. Your fortune wanders — sometimes up, sometimes down — but on average, it never drifts. No matter how many flips have happened, the best guess for your fortune after the next flip is exactly your fortune right now.

That property — expected future value equals present value — is the definition of a martingale. The name comes from a 18th-century betting strategy, but the mathematics, formalized by Joseph Doob in the 1940s, runs far deeper than any casino.

Martingales are the mathematical language of fairness. Wherever a system must obey some conservation law on average — prices, algorithms, random walks — martingales are usually hiding behind the scenes. Understanding them is the first step to understanding Bayesian inference, concentration inequalities, and the theory of optimal stopping.

See the Fair Walk

Below is a symmetric random walk: at each step, your fortune goes up $1 or down $1 with equal probability. Run as many independent walks as you like and watch the sample average (blue line) hover around zero — while individual paths (grey) scatter wildly.

<!-- Martingale demo: controls, canvas, status line, and action buttons. -->
<p class="hint">Each grey line is an independent fair random walk (+1 or -1 at every step). The blue line is the <b>sample average</b> across all walks — it stays near zero, illustrating the martingale property. Use <em>Stop early</em> to check optional stopping.</p>
<div class="controls">
  <label>Walks: <input id="numWalks" type="number" min="1" max="50" value="10"></label>
  <label>Steps: <input id="numSteps" type="number" min="10" max="200" value="50"></label>
  <label>Stop at step: <input id="stopAt" type="number" min="1" max="200" value="25"></label>
</div>
<canvas id="canvas" width="460" height="260"></canvas>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btnRun" type="button">Run walks</button>
  <button id="btnStop" type="button">Stop early</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

/* Layout and styling for the martingale random walk demo. */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem .9rem; margin-bottom: .6rem; align-items: center; }
.controls label { font-size: .85rem; color: #333; display: flex; gap: .3rem; align-items: center; }
.controls input { width: 60px; padding: .2rem .4rem; border: 1px solid #bbb; border-radius: 5px; font-size: .85rem; }
canvas { display: block; border: 1px solid #d0d8e0; border-radius: 8px; background: #f8fafc; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Martingale demo: symmetric random walk visualizer.
// A martingale satisfies E[M_{t+1} | M_0,...,M_t] = M_t for all t.
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const statusEl = document.getElementById('status');

// Shared state: array of walk paths and optional stop line.
let paths = [];
let stopLine = null;

function getParams() {
  // Read input values with safe clamping.
  const n = Math.max(1, Math.min(50,  parseInt(document.getElementById('numWalks').value) || 10));
  const s = Math.max(10, Math.min(200, parseInt(document.getElementById('numSteps').value) || 50));
  const t = Math.max(1, Math.min(s,   parseInt(document.getElementById('stopAt').value)  || 25));
  return { n, s, t };
}

function generateWalks(n, s) {
  // Generate n independent symmetric random walks of length s.
  const result = [];
  for (let i = 0; i < n; i++) {
    const path = [0];
    for (let k = 1; k <= s; k++) {
      // Fair coin: +1 or -1 with equal probability.
      path.push(path[k - 1] + (Math.random() < 0.5 ? 1 : -1));
    }
    result.push(path);
  }
  return result;
}

function averageAtStep(paths, step) {
  // Compute sample average of all walks at a given step index.
  const total = paths.reduce((sum, p) => sum + p[Math.min(step, p.length - 1)], 0);
  return total / paths.length;
}

function draw() {
  const { n, s, t } = getParams();
  const W = canvas.width, H = canvas.height;
  const PAD = { top: 20, bottom: 28, left: 36, right: 16 };
  const plotW = W - PAD.left - PAD.right;
  const plotH = H - PAD.top - PAD.bottom;

  // Compute y-axis scale from max absolute value across all paths.
  let maxAbs = 1;
  for (const p of paths) for (const v of p) if (Math.abs(v) > maxAbs) maxAbs = Math.abs(v);
  maxAbs = Math.ceil(maxAbs * 1.15);

  function xOf(step) { return PAD.left + (step / s) * plotW; }
  function yOf(val)  { return PAD.top  + (1 - (val + maxAbs) / (2 * maxAbs)) * plotH; }

  ctx.clearRect(0, 0, W, H);

  // Draw horizontal grid lines.
  ctx.strokeStyle = '#dde4ec';
  ctx.lineWidth = 1;
  for (let g = -maxAbs; g <= maxAbs; g += Math.ceil(maxAbs / 4)) {
    ctx.beginPath(); ctx.moveTo(PAD.left, yOf(g)); ctx.lineTo(W - PAD.right, yOf(g)); ctx.stroke();
    ctx.fillStyle = '#888'; ctx.font = '11px system-ui';
    ctx.fillText(g, 2, yOf(g) + 4);
  }

  // Draw the zero (mean) axis.
  ctx.strokeStyle = '#b0bec8'; ctx.lineWidth = 1.2;
  ctx.beginPath(); ctx.moveTo(PAD.left, yOf(0)); ctx.lineTo(W - PAD.right, yOf(0)); ctx.stroke();

  // Draw individual walk paths in light grey.
  for (const p of paths) {
    ctx.strokeStyle = 'rgba(160,175,190,0.45)'; ctx.lineWidth = 1;
    ctx.beginPath();
    for (let k = 0; k <= s && k < p.length; k++) {
      k === 0 ? ctx.moveTo(xOf(k), yOf(p[k])) : ctx.lineTo(xOf(k), yOf(p[k]));
    }
    ctx.stroke();
  }

  // Draw sample average path in blue.
  if (paths.length > 0) {
    ctx.strokeStyle = '#2563eb'; ctx.lineWidth = 2.2;
    ctx.beginPath();
    for (let k = 0; k <= s; k++) {
      const avg = averageAtStep(paths, k);
      k === 0 ? ctx.moveTo(xOf(k), yOf(avg)) : ctx.lineTo(xOf(k), yOf(avg));
    }
    ctx.stroke();
  }

  // Draw optional stopping time as a red dashed vertical line.
  if (stopLine !== null) {
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 1.8;
    ctx.setLineDash([5, 4]);
    ctx.beginPath(); ctx.moveTo(xOf(stopLine), PAD.top); ctx.lineTo(xOf(stopLine), H - PAD.bottom); ctx.stroke();
    ctx.setLineDash([]);
    const avgAtStop = averageAtStep(paths, stopLine);
    ctx.fillStyle = '#e63946'; ctx.font = 'bold 11px system-ui';
    ctx.fillText('avg=' + avgAtStop.toFixed(2), xOf(stopLine) + 4, PAD.top + 14);
  }
}

function setStatus(msg, cls) {
  statusEl.textContent = msg; statusEl.className = 'status ' + cls;
}

document.getElementById('btnRun').addEventListener('click', () => {
  // Generate fresh walks and redraw.
  const { n, s } = getParams();
  paths = generateWalks(n, s);
  stopLine = null;
  draw();
  const avg = averageAtStep(paths, s);
  setStatus(fmt('Ran %n% walks of %s% steps. Average at end: %avg% (should be near 0)', { n: n, s: s, avg: avg.toFixed(3) }), 'ok');
  console.log('Generated walks:', n, 'steps', s, '| avg at end:', avg.toFixed(4));
});

document.getElementById('btnStop').addEventListener('click', () => {
  // Apply optional stopping: draw marker and report average.
  if (paths.length === 0) { setStatus('Run some walks first.', 'info'); return; }
  const { t, s } = getParams();
  stopLine = Math.min(t, s);
  draw();
  const avg = averageAtStep(paths, stopLine);
  setStatus(fmt('Stopped at step %stopLine%. Average at stop: %avg% (martingale property holds)', { stopLine: stopLine, avg: avg.toFixed(3) }), 'ok');
});

document.getElementById('btnReset').addEventListener('click', () => {
  // Clear all walks and redraw blank canvas.
  paths = []; stopLine = null;
  draw();
  setStatus('', '');
});

// Initial blank canvas draw.
draw();
Result
Console

Notice the key fact: no matter how far a single path drifts, the average across all walks stays flat. That is the martingale property in action. Press Stop early to apply the optional stopping theorem at a chosen step, and see that the average at that stopping time also stays near zero — confirming that a fair game remains fair no matter when you quit.

The Real Complexity

Two theorems make martingales more than a curiosity.

The Optional Stopping Theorem (Doob, 1940s). Let (Mt)(M_t) be a martingale and τ\tau a stopping time — a rule that says "quit now" based only on what has happened so far, never on the future. Under mild technical conditions (the walk is bounded, or τ\tau has finite expectation), the theorem says:

E[Mτ]=M0\mathbb{E}[M_\tau] = M_0

Your expected fortune when you stop equals your starting fortune. No clever "quit when you are ahead" strategy can profit from a truly fair game. The gambler's intuition that the martingale strategy (doubling bets after each loss) beats the house is flatly contradicted here — the bet sizes can grow without bound, violating the theorem's conditions.

Azuma–Hoeffding Inequality (Azuma, 1967). Now suppose each step of your martingale changes by at most ckc_k in absolute value (a "bounded differences" condition). Then for any ε>0\varepsilon > 0:

Pr⁡ ⁣[Mn−M0≥ε]  ≤  exp⁡ ⁣(−ε22∑k=1nck2)\Pr\!\left[M_n - M_0 \geq \varepsilon\right] \;\leq\; \exp\!\left(-\frac{\varepsilon^2}{2\sum_{k=1}^{n} c_k^2}\right)

This is a concentration inequality: the walk is exponentially unlikely to stray more than ε\varepsilon from its starting value. It is one of the most powerful tools in probabilistic algorithm analysis — anywhere a quantity can be written as a sum of small, conditionally unbiased increments, Azuma applies.

Together these results answer the two most natural questions about a martingale: where will it be when I stop? (Optional stopping: at its start) and how far can it stray? (Azuma: not very far, with high probability).

Where It Matters

"Expected future value equals present value" turns out to describe a remarkable variety of systems:

  • Randomized algorithm analysis: when an algorithm makes random choices, the quantity you care about — cost, number of comparisons, hash-table load — is often a martingale or close to one. Azuma's inequality then gives tight tail bounds almost for free.
  • Finance (Black–Scholes): under the risk-neutral measure, discounted asset prices are martingales. The entire theory of no-arbitrage pricing rests on this property. A random walk model for prices is just a discrete martingale.
  • Online learning and regret: in adversarial online learning, the cumulative regret process is a martingale when the adversary is oblivious. Optional stopping controls when it is safe to switch strategies.
  • Doob's martingale and combinatorics: for any function ff of independent random variables, the sequence of conditional expectations E[f∣X1,…,Xk]\mathbb{E}[f \mid X_1, \dots, X_k] is a martingale (the Doob martingale). Azuma then concentrates ff around its mean — a workhorse technique in probabilistic combinatorics and the Lovász Local Lemma machinery.

Martingales are also the hidden structure in the analysis of many PAC learning algorithms and in the proof that Bayesian inference converges.

Conclusion

A martingale is the simplest possible model of fairness: no information you gather can improve your expected fortune. The optional stopping theorem seals that fairness against any stopping strategy, and Azuma's inequality tells you the walk cannot stray far in one giant leap.

That combination — expectation stays flat, fluctuations are controlled — is why martingales appear wherever randomness must be reasoned about rigorously: in algorithms, finance, machine learning, and combinatorics. The next time a probabilistic argument seems to work by magic, look for the martingale underneath. It is usually there.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/martingales/Content licensed under CC BY-NC 4.0.