Parallel random-walk simulation

What is this about?

This example simulates particles taking a random walk from the origin. A particle moves one unit at a time and stops when it reaches the specified radius or its step limit.

Every trial can take a different number of steps. That variation makes this a useful example of chunking and load balancing.

How it works

1. The host divides the requested trials into batches.
2. Each worker runs its batch with a deterministic random seed.
3. A worker returns only summary values: escaped count, step totals, and squared step totals.
4. The host combines the summaries into escape probability, mean escape time, and standard deviation.

The task payload is a small tuple, while the simulation loop stays entirely in the worker.

Run

Bun

bun.sh

bun src/walks_runs.ts --threads 4 --runs 50000 --batch 2500 --steps 3000 --radius 40

Deno

deno.sh

deno run -A src/walks_runs.ts --threads 4 --runs 50000 --batch 2500 --steps 3000 --radius 40

Node

node.sh

npx tsx src/walks_runs.ts --threads 4 --runs 50000 --batch 2500 --steps 3000 --radius 40

Expected output:

threads:           4
runs:              50,000
batches:           20
radius:            40
max steps:         3,000
escape probability: 0.8896
mean escape steps:  1,308.8
stdev steps:       668.3
elapsed:           2,000 ms

The random seed is fixed, so the statistical values are reproducible. Elapsed time depends on your runtime, CPU, and worker count.

Why this pattern works

• The worker does one thing: run independent random walks.
• The host owns scheduling and combines compact summaries.
• No individual path crosses the worker boundary.
• Smaller batches smooth out differences between short and long walks.

Unlike Monte Carlo pi, this simulation does not do the same amount of work for every trial. Particles that reach the boundary early finish cheaply; particles that wander longer keep a worker busy.

Code

walks_runs.ts

walks_runs.ts

import { createPool, isMain } from "knitting";
import { walkChunk } from "./walk2d.ts";

type Options = {
  threads: number;
  runs: number;
  batch: number;
  maxSteps: number;
  radius: number;
};

type WalkResult = {
  escaped: number;
  totalRuns: number;
  sumSteps: number;
  sumSteps2: number;
};

function positiveIntArg(name: string, fallback: number): number {
  const index = process.argv.indexOf(`--${name}`);
  const value = index === -1 ? undefined : Number(process.argv[index + 1]);
  return Number.isInteger(value) && value > 0 ? value : fallback;
}

function readOptions(): Options {
  return {
    threads: positiveIntArg("threads", 4),
    runs: positiveIntArg("runs", 50_000),
    batch: positiveIntArg("batch", 2_500),
    maxSteps: positiveIntArg("steps", 3_000),
    radius: positiveIntArg("radius", 40),
  };
}

async function main() {
  const options = readOptions();
  const jobCount = Math.ceil(options.runs / options.batch);
  const seed = 0x1234_5678;

  using pool = createPool({ threads: options.threads })({ walkChunk });

  const started = performance.now();
  const jobs: Promise<WalkResult>[] = [];

  for (let job = 0; job < jobCount; job++) {
    const offset = job * options.batch;
    const runs = Math.min(options.batch, options.runs - offset);
    const jobSeed = (seed + job * 0x6d2b_79f5) | 0;

    jobs.push(
      pool.call.walkChunk([
        jobSeed,
        runs,
        options.maxSteps,
        options.radius,
      ]),
    );
  }

  const results = await Promise.all(jobs);
  const total = results.reduce(
    (summary, result) => ({
      escaped: summary.escaped + result.escaped,
      totalRuns: summary.totalRuns + result.totalRuns,
      sumSteps: summary.sumSteps + result.sumSteps,
      sumSteps2: summary.sumSteps2 + result.sumSteps2,
    }),
    { escaped: 0, totalRuns: 0, sumSteps: 0, sumSteps2: 0 },
  );

  const escapeProbability = total.escaped / total.totalRuns;
  const meanSteps = total.escaped ? total.sumSteps / total.escaped : 0;
  const meanStepsSquared = total.escaped
    ? total.sumSteps2 / total.escaped
    : 0;
  const standardDeviation = Math.sqrt(
    Math.max(0, meanStepsSquared - meanSteps * meanSteps),
  );
  const elapsed = performance.now() - started;

  console.log(`threads:           ${options.threads}`);
  console.log(`runs:              ${total.totalRuns.toLocaleString()}`);
  console.log(`batches:           ${jobCount.toLocaleString()}`);
  console.log(`radius:            ${options.radius}`);
  console.log(`max steps:         ${options.maxSteps.toLocaleString()}`);
  console.log(`escape probability: ${escapeProbability.toFixed(4)}`);
  console.log(`mean escape steps:  ${meanSteps.toFixed(1)}`);
  console.log(`stdev steps:       ${standardDeviation.toFixed(1)}`);
  console.log(`elapsed:           ${elapsed.toFixed(0)} ms`);
}

if (isMain) {
  await main();
}

walk2d.ts

walk2d.ts

import { task } from "knitting";

type WalkJob = readonly [
  seed: number,
  runs: number,
  maxSteps: number,
  radius: number,
];

type WalkResult = {
  escaped: number;
  totalRuns: number;
  sumSteps: number;
  sumSteps2: number;
};

function xorshift32(state: number): number {
  state |= 0;
  state ^= state << 13;
  state ^= state >>> 17;
  state ^= state << 5;
  return state | 0;
}

export const walkChunk = task<WalkJob, WalkResult>({
  f: ([seed, runs, maxSteps, radius]) => {
    let state = seed | 0;
    let escaped = 0;
    let sumSteps = 0;
    let sumSteps2 = 0;
    const radiusSquared = radius * radius;

    for (let run = 0; run < runs; run++) {
      let x = 0;
      let y = 0;

      for (let step = 1; step <= maxSteps; step++) {
        state = xorshift32(state);

        switch (state & 3) {
          case 0:
            x++;
            break;
          case 1:
            x--;
            break;
          case 2:
            y++;
            break;
          default:
            y--;
        }

        if (x * x + y * y >= radiusSquared) {
          escaped++;
          sumSteps += step;
          sumSteps2 += step * step;
          break;
        }
      }
    }

    return { escaped, totalRuns: runs, sumSteps, sumSteps2 };
  },
});

The math

The escape probability is the fraction of particles that reach the boundary:

$$\hat{p} = \frac{\text{escaped particles}}{\text{total particles}}$$

The mean escape time averages the number of steps for escaped particles. This is a discrete approximation of Brownian motion and diffusion, and the same pattern applies to transport, agent simulations, and hitting-time problems.

CLI knobs

• --runs — total number of particles.
• --batch — particles per worker task; smaller batches improve load balancing.
• --steps — maximum steps for one particle.
• --radius — distance from the origin that ends a walk.
• --threads — number of workers in the pool.

Things to try

1. Increase --radius to make walks last longer and lower the escape probability.
2. Lower --steps to see more particles hit the step limit.
3. Compare --batch 500 with --batch 20000 and watch the scheduling trade-off.
4. Change the four-direction step to include a drift term or diagonal moves.