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(st+1∣st,st−1,… )=P(st+1∣st)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 P∈RN×N\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.

Cumulative observation share against cumulative cell share for a pedestrian network Cells are ranked from busiest to quietest along the horizontal axis, expressed as a cumulative percentage of all cells; the vertical axis is the cumulative percentage of all observations they account for. A dashed diagonal shows what perfectly even coverage would look like. The measured curve bows far above it: a small fraction of cells accounts for half of all observations, and the long tail of cells contributes almost nothing. Two markers on the horizontal axis show the share of cells with fewer than five observations, and the share with none at all. The consequence for a first-order Markov model is stated underneath: the aggregate corpus size is irrelevant, because the rows that matter for realistic movement are exactly the quiet ones in the tail, and those rows are estimated from a handful of samples or from none. Any model fitted here is a well-estimated model of the busiest corridors and a smoothing prior everywhere else, which is why a coverage histogram belongs in the validation report alongside the transition matrix. The corpus is large in aggregate and empty where it matters 0% 25% 50% 75% 100% 0% 25% 50% 75% 100% cells, ranked busiest first (cumulative %) observations accounted for (cumulative %) perfectly even coverage 10% of cells carry half the observations 23% of cells: < 5 observations 3% of cells: no observations at all 90,000 observations over 2,600 cells, log-normal traffic weights, fixed seed. Aggregate corpus size is the wrong number: the rows that carry realistic movement are the quiet ones, and they are estimated from a handful of samples or none — so ship a coverage histogram beside the matrix.
Aggregate corpus size is the wrong number — the rows that carry realistic movement are the quiet ones in the tail.

Second, absorbing-state traps and disconnected pockets. An un-validated grid contains cells whose only outgoing edge points back to themselves (Pii=1P_{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.

First-order Markov pedestrian walk on a walkable H3 patch with a guard ring, a dead-end cell, and a whitelisted absorbing entrance Left: a honeycomb patch of seven walkable H3 cells (A, B, C, D, E, F, G) surrounded by a dashed guard ring of hexes each carrying probability zero so no draw can leave the domain. Directed primary-coloured arrows route the walk between walkable cells; two accent arrows lead into cell B, a dead-end whose transition row sums to zero so the walk truncates the instant it arrives. Cell D is drawn with a heavier stroke and a self-loop labelled probability one — a whitelisted absorbing building entrance. Right: the outgoing transition row of the central hub cell C is shown as six horizontal bars to neighbours A, F, G, E, D and B with Laplace-smoothed probabilities 0.21, 0.19, 0.18, 0.16, 0.14 and 0.12 that sum to 1.00, while a separate strip shows the dead-end cell B whose row sums to zero and a note that cell D self-absorbs with probability one. Walkable H3 patch + guard ring Smoothed transition row, hub cell C 000 00 00 00 000 A E F G C hub B dead-end Σ = 0 D entrance A 0.21 F 0.19 G 0.18 E 0.16 D 0.14 B 0.12 Σ = 1.00 · Laplace-smoothed, no zero rows B → Σ = 0 → walk truncates D → Pᵢᵢ = 1 · whitelisted absorbing sink

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.

python
# 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

python
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.

Four repairs to a raw pedestrian transition matrix, in order, with their assertions The repairs run in sequence and each one depends on the previous. First, mask to the walkable network: drop any transition whose destination is not a walkable cell, which removes the observations that were map-matching noise rather than movement; the assertion is that every remaining destination is in the walkable set. Second, restrict to the largest strongly connected component: drop cells from which the rest of the network cannot be reached, or which cannot be reached from it, because a walk that enters them can never leave; the assertion is that the component count is one. Third, apply a smoothing floor and row-normalise: give every remaining reachable successor a small positive probability so no row is absorbing, then scale each row to sum to one; the assertions are that every row sums to one within tolerance and that no row has a zero maximum. Fourth, assert the result as a whole: the matrix is row-stochastic, irreducible, and hashes to a value recorded in the manifest, so the walks that follow are attributable to a specific operator. A footer records why the order is forced: masking after the component restriction can disconnect the graph again, and normalising before the floor leaves rows that sum to one and still trap a walk. Four repairs, and an order that is forced rather than chosen 1 · mask to walkable drop destinations off the walkable network REMOVES removes map-matching noise ASSERT every destination ∈ walkable set 2 · largest SCC drop cells the network cannot reach, or reach from REMOVES removes one-way traps ASSERT component count == 1 3 · floor, then normalise a positive floor on every reachable successor REMOVES removes absorbing rows ASSERT Σ row == 1 ± tol; max(row) > 0 4 · assert and stamp row-stochastic, irreducible, hashed REMOVES makes the operator attributable ASSERT matrix hash recorded in the manifest The order is forced: masking after the component restriction can disconnect the graph again, and normalising before the floor leaves rows that sum to one and still trap a walk. Both mistakes produce a matrix that passes a row-sum check and truncates trajectories in production.
The order is forced: both plausible rearrangements produce a matrix that passes a row-sum check and truncates trajectories in production.

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.

python
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.

python
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.

python
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.

python
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

Why a first-order chain instead of a higher-order or memory-augmented model?
First-order chains are memoryless by construction, which is precisely what makes them privacy-safe: they cannot reproduce an individual's long-range movement signature, only aggregate route-choice structure. A second-order model conditions on the previous two states and begins to encode recognizable habits, raising re-identification risk. Use first-order when the goal is reproducible, deidentified path diversity at scale; reach for higher order only when a validated fidelity metric proves the first-order walk underfits the turn-correlation in your source.
How should I choose the Laplace smoothing constant alpha?
Pick the smallest alpha that eliminates zero-sum rows without flattening the observed structure — typically 0.01 to 0.05. Too small leaves sparsely observed cells effectively dead; too large washes out the real transition preferences and pushes every walk toward a uniform random walk. Validate the choice against the path-length distribution: over-smoothing shows up as walks that are too diffuse and too long relative to the source telemetry.
Why keep destination bias out of the transition matrix?
A first-order matrix encodes only local, current-state-conditioned transitions. Folding a global attraction toward a destination into those probabilities makes the next-hop depend on where the walk is ultimately headed, which is path information the current state does not carry — it violates the Markov property and breaks byte-for-byte replay. Keep destination weighting as a separate overlay applied after sampling, so the base chain stays ergodic and reproducible.
The walk truncates after a few steps even though the matrix passes the row-sum gate. What now?
A passing row-sum gate rules out zero-sum dead-ends, so the remaining cause is an absorbing state the walk reaches early. Run the absorbing-state audit: if the cell is a legitimate sink (a building entrance), whitelist it; if it is not, it is topology leakage from an un-mapped barrier and the cell should be merged with its walkable neighbours before the matrix is rebuilt.