Simulating Pedestrian Movement with First-Order Markov Models

When a memoryless transition matrix built from sparse pedestrian telemetry produces walks that dead-end, loop in a disconnected pocket, or wander outside walkable space, the fix is a smoothed, row-stochastic matrix over a validated walkable grid sampled with a propagated seed.

Part of Markov Chain Routing Models: that page covers network-constrained routing in general; this page drills into the specific case of pedestrian walks on a tessellated walkable surface, where the failure modes are dead-ends from sparse counts, traps inside disconnected subgraphs, and boundary leakage — none of which a naive count-to-probability conversion catches.

Root Cause: Why the Memoryless Property Breaks on Sparse Pedestrian Grids

A first-order Markov walk chooses the next spatial state using only the current state: $P(s_{t+1} \mid s_t, s_{t-1}, \dots) = P(s_{t+1} \mid s_t)$. That memoryless property is exactly why these models are attractive for synthetic pedestrian data — they cannot memorize an individual’s long-range movement signature, so a sampled walk reproduces aggregate route-choice structure without replaying a real journey. It is also the source of three deterministic failure modes that all trace back to how the transition matrix $\mathbf{P} \in \mathbb{R}^{N \times N}$ is built.

First, zero-sum rows from sparse counts. Raw pedestrian telemetry rarely visits every walkable cell. A cell observed once, or never, produces a matrix row that sums to zero. Inverse-transform sampling on a zero row has no valid next state, so the walk silently truncates the instant it reaches that cell — and because truncation looks like a “short trip,” it corrupts the path-length distribution rather than raising an error.

Second, absorbing-state traps and disconnected pockets. An un-validated grid contains cells whose only outgoing edge points back to themselves ($P_{ii}=1$), and clusters of cells that form a strongly connected component with no exit. A walk that enters either one loops forever or terminates against an unmodeled wall. Real absorbing states exist — a building entrance is a legitimate sink — but they must be whitelisted, not discovered by a stuck simulation.

Third, boundary leakage. With a rectangular lattice, a cell on the tessellation edge has fewer neighbours than an interior cell, and an un-guarded next-hop draw can index a cell outside the valid domain. The walk escapes onto non-walkable space, and downstream consumers that join it against the point process simulation models feeding density layers inherit the corruption.

The reason a hexagonal index such as Uber’s H3 is preferred over a square grid is that every interior cell has exactly six neighbours, so adjacency counts are uniform and the directional bias that warps square-lattice walks disappears. Stabilizing the grid and smoothing the matrix — not making sampling faster — is what removes all three failures.

Prerequisite Check: Confirm the Matrix Is Broken

Before fixing anything, confirm the two conditions that silently corrupt walks: rows that do not sum to one, and absorbing/dead-end states. Pin the toolchain so node ordering and RNG streams are identical across machines.

pythonCopy
# requirements.txt — pin majors; let patch releases float
numpy==1.26.*
scipy==1.11.*        # CSR sparse transition matrix
h3==3.7.*            # hexagonal spatial index, uniform 6-neighbour adjacency

pythonCopy
import numpy as np
from scipy import sparse

def audit_matrix(P: sparse.csr_matrix) -> dict:
    """Surface the failure modes a naive count->probability build leaves behind."""
    row_sums = np.asarray(P.sum(axis=1)).ravel()
    dead_ends = np.flatnonzero(row_sums == 0.0)            # zero-sum -> truncation
    diag = P.diagonal()
    absorbing = np.flatnonzero((diag == 1.0) & (row_sums == 1.0))  # P_ii == 1
    drift = np.abs(1.0 - row_sums[row_sums > 0]).max(initial=0.0)
    return {"dead_ends": dead_ends.size,
            "absorbing": absorbing.size,
            "max_rowsum_drift": float(drift)}

# A matrix built straight from raw adjacency counts fails all three checks:
# {'dead_ends': 318, 'absorbing': 12, 'max_rowsum_drift': 0.0}  # rows don't even sum to 1

Any non-zero dead_ends, any non-whitelisted absorbing, or a max_rowsum_drift above floating-point noise means the matrix is not safe to sample.

Fix: Validated Walkable Grid, Smoothed Row-Stochastic Matrix, Seeded Walk

The fix has three parts: build adjacency over a connected walkable H3 grid, Laplace-smooth the counts into a strictly row-stochastic matrix with no zero rows, then sample with a propagated seed and a boundary guard.

Step 1 — Connected walkable adjacency

Resolve walkable cells at an H3 resolution matched to pedestrian kinematics (resolution 11 ≈ 25 m edge; tune to your 1.5–5 m target by going finer), then keep only the largest connected component so no walk can be born inside a trap. This mirrors the seeding contract used by the Markov Chain Routing Models parent so the same grid reproduces across runs.

pythonCopy
import h3
import networkx as nx

def walkable_graph(walkable_cells: set[str]) -> tuple[nx.DiGraph, list[str]]:
    """Directed adjacency over the LARGEST connected walkable component only."""
    g = nx.DiGraph()
    for cell in walkable_cells:
        for nbr in h3.k_ring(cell, 1) - {cell}:           # 6 uniform neighbours
            if nbr in walkable_cells:                     # skip non-walkable
                g.add_edge(cell, nbr)
    # Drop disconnected pockets that would trap a walk forever.
    largest = max(nx.weakly_connected_components(g), key=len)
    g = g.subgraph(largest).copy()
    nodes = sorted(g.nodes)                               # fixed order -> reproducible index
    return g, nodes

Step 2 — Laplace-smoothed, strictly row-stochastic matrix

Normalize observed transition counts with a small additive constant $\alpha$ so every in-component edge has non-zero probability and no row can sum to zero. Keep destination bias out of this matrix — conflating a global attraction term with local transition probability breaks the Markov property and the replay determinism the scoping rules and data contracts require of every generated artifact.

pythonCopy
import numpy as np
from scipy import sparse

def build_transition_matrix(g, nodes, counts, alpha: float = 0.02) -> sparse.csr_matrix:
    """Row-stochastic P with Laplace smoothing -> no zero rows, no dead-ends."""
    index = {c: i for i, c in enumerate(nodes)}
    n = len(nodes)
    rows, cols, vals = [], [], []
    for cell, i in index.items():
        nbrs = list(g.successors(cell))
        denom = sum(counts.get((cell, nb), 0) for nb in nbrs) + alpha * len(nbrs)
        for nb in nbrs:                                   # alpha lifts every edge off zero
            rows.append(i); cols.append(index[nb])
            vals.append((counts.get((cell, nb), 0) + alpha) / denom)
    P = sparse.csr_matrix((vals, (rows, cols)), shape=(n, n))
    return P

Step 3 — Seeded sampling with a boundary guard

Draw next states by inverse-transform sampling on each row’s cumulative distribution. The seed is a first-class, versioned artifact: derive a per-walk stream from a SHA-256-truncated base seed so every node reproduces the same trace bitwise. Decouple the step index from wall-clock time — variable walking speed and pauses belong to the temporal synchronization for moving objects stage, not the chain.

pythonCopy
import hashlib
import numpy as np

def _stream(base_seed: int, walk_id: int) -> np.random.Generator:
    digest = hashlib.sha256(f"{base_seed}:{walk_id}".encode()).digest()
    return np.random.default_rng(int.from_bytes(digest[:8], "big"))

def sample_walk(P, nodes, start: int, walk_id: int, *,
                base_seed: int, max_steps: int, absorbing: set[int]) -> list[str]:
    """One reproducible walk; stops only at a WHITELISTED absorbing state."""
    rng = _stream(base_seed, walk_id)
    indptr, indices, data = P.indptr, P.indices, P.data
    state, path = start, [nodes[start]]
    for _ in range(max_steps):
        if state in absorbing:                            # legitimate sink only
            break
        lo, hi = indptr[state], indptr[state + 1]
        probs = data[lo:hi]                               # smoothing guarantees non-empty
        nxt = indices[lo + np.searchsorted(np.cumsum(probs), rng.random())]
        state = nxt                                       # guard: nxt is in-component by construction
        path.append(nodes[state])
    return path

Because Step 1 kept only the connected component and Step 2 smoothed every row off zero, there is no out-of-bounds index to draw and no dead-end to fall into — the boundary guard is structural rather than a runtime clamp.

Verification Step: Gate the Matrix and the Walks

Wire the invariants as CI assertions so a regression cannot reach a training pipeline. The path-length and coverage checks lean on the same statistics the realism metrics evaluation stage uses to score synthetic against source.

pythonCopy
import numpy as np

def test_pedestrian_chain_is_safe_and_reproducible(P, nodes, starts, absorbing):
    # 1. Strict row-stochasticity within floating-point tolerance.
    row_sums = np.asarray(P.sum(axis=1)).ravel()
    assert np.abs(1.0 - row_sums).max() < 1e-9, "rows not normalized"

    # 2. No dead-ends and no NON-whitelisted absorbing states.
    assert (row_sums > 0).all(), "zero-sum row -> silent truncation"
    diag = P.diagonal()
    leaked = set(np.flatnonzero(diag == 1.0)) - set(absorbing)
    assert not leaked, f"unmodeled absorbing states: {leaked}"

    # 3. Byte-identical reproducibility from the same seed.
    a = sample_walk(P, nodes, starts[0], 0, base_seed=42, max_steps=500, absorbing=absorbing)
    b = sample_walk(P, nodes, starts[0], 0, base_seed=42, max_steps=500, absorbing=absorbing)
    assert a == b, "non-deterministic walk for fixed seed"

    # 4. Kinematic sanity: no step exceeds a plausible pedestrian hop.
    coords = [np.array(__import__("h3").h3_to_geo(c)) for c in a]
    steps_m = [np.linalg.norm(p - q) * 111_000 for p, q in zip(coords, coords[1:])]
    assert max(steps_m, default=0) < 3.0 * 1.0, "step implies speed > 3 m/s"  # per 1 s tick

The row-stochastic and dead-end gates are the non-negotiable pair: each catches a distinct corruption the other passes straight through. Floating-point accumulation during sparse assembly routinely violates the 1e-9 bound even when the build logic is correct, so the tolerance gate is load-bearing.

Edge Cases & Gotchas

Disconnected walkable pockets that survive masking. A pedestrian plaza separated from the street grid by an un-mapped barrier forms its own strongly connected component. Keeping only the largest weakly connected component (Step 1) silently drops it — usually correct, but if that pocket is a genuine destination you have erased it. Assert the retained component covers an expected fraction of total walkable area, and log dropped components so a real plaza is not quietly deleted by an upstream masking error.

Antimeridian-spanning walkable extents. An H3 grid that crosses ±180° longitude produces cells whose h3_to_geo coordinates wrap, and the naive great-circle step distance in the kinematic gate folds across the seam, reporting an impossible multi-thousand-metre hop between adjacent cells. Detect longitude sign flips between consecutive states and unwrap before computing step distance, or shift the extent into a local projected CRS whose central meridian sits inside the region.

Floating-point drift in row normalization. Summing many smoothed probabilities in CSR order accumulates rounding error, so a row that should sum to exactly 1.0 lands at 1.0 ± 1e-12. Inverse-transform sampling with searchsorted against a cumulative sum that stops just below 1.0 can, on the rare draw of rng.random() near 1.0, index past the last neighbour. Clamp the final cumulative value to 1.0 (or draw from a half-open interval) so the last neighbour always absorbs the tail.

Frequently Asked Questions

Related

• Markov Chain Routing Models — the parent workflow this page specializes, from transition-matrix calibration through statistical and privacy gates.
• Noise Injection & Stochastic Drift — add realistic GNSS error to the clean walks this page produces before they reach a training set.
• Temporal Synchronization for Moving Objects — attach variable walking speeds and pauses to the step sequence without altering the chain.
• Privacy-Preserving Generation Frameworks — the budgeted mechanisms that pair with the chain’s inherent re-identification resistance.
• Realism Metrics Evaluation — score the synthetic path-length and coverage distributions against the source telemetry.