Weighting Transitions by Time of Day

The routing model produces the same flow pattern at 08:00 and at 23:00. Real networks reverse direction across the morning peak, empty out overnight, and route around congestion that only exists for two hours a day — none of which a single transition matrix can express.

Part of Markov Chain Routing Models: a stationary chain is stationary by definition, so the fix is not a better chain but a family of them, and the interesting question is how many.

Root Cause: One Matrix Encodes One Regime

A transition matrix fitted across a full day is an average over regimes that differ sharply. The average is not a compromise between them; it is a distribution that matches none of them and that generates traces belonging to no real period.

The consequence is concentrated in exactly the periods people care about. Off-peak flows are close to the daily mean and come out approximately right, so the model looks reasonable in aggregate. Peak flows are furthest from the mean and come out worst, and peak behaviour is what almost every downstream consumer is analysing.

There is also a directional signature that makes the defect easy to confirm. In the morning peak, flow on a commuter corridor is strongly asymmetric — heavy inbound, light outbound — and it reverses in the evening. A single matrix averages the two into a symmetric flow that appears at every hour, including 03:00.

Corridor flow through the day against a single averaged matrix The horizontal axis is the hour of day from midnight to midnight. The vertical axis is flow along one commuter corridor in vehicles per minute. Two solid curves show the observed flow in each direction. The inbound curve has a sharp peak just after eight in the morning, more than three times its overnight level, and a smaller secondary rise in the evening. The outbound curve is the mirror image: modest in the morning and sharply peaked around half past five. Two flat dashed lines show what a transition matrix fitted across the whole day produces — one constant value per direction, identical at every hour, and nearly identical to each other because averaging the two directions over a full day removes almost all of the asymmetry. At three in the morning the averaged model produces peak-hour-adjacent flow in both directions; at the morning peak it produces less than half the real inbound flow. The note underneath points out where the error concentrates: off-peak hours sit near the daily mean and come out roughly right, so the model looks reasonable in aggregate, while the peaks — the hours consumers actually analyse — are where it is worst. The average matches the quiet hours and misses every peak 00:00 06:00 12:00 18:00 23:00 0 40 80 120 hour of day corridor flow (veh/min) observed inbound observed outbound single averaged matrix — both directions, every hour inbound outbound The error is not spread evenly. Off-peak hours sit close to the daily mean and come out approximately right, which is why an averaged model looks reasonable in aggregate. The peaks are furthest from the mean and come out worst — and peak behaviour is what almost every downstream consumer is analysing.
Inbound and outbound corridor flow through the day: observed reversal against what a single averaged matrix produces at every hour.

Prerequisite Check: How Many Periods Can the Data Support?

More periods always fit the training data better and eventually fit nothing else. The binding constraint is transitions per state per period, and it is worth computing before choosing a scheme.

python
def period_adequacy(observations, period_of, states, min_per_state: int = 30) -> dict:
    """Transitions available per state in each period."""
    counts: dict = {}
    for prev, nxt, ts in observations:
        counts.setdefault(period_of(ts), {}).setdefault(prev, 0)
        counts[period_of(ts)][prev] += 1
    report = {}
    for period, per_state in counts.items():
        thin = [s for s in states if per_state.get(s, 0) < min_per_state]
        report[period] = {
            "median_per_state": median([per_state.get(s, 0) for s in states]),
            "states_below_floor": len(thin),
            "usable": len(thin) / len(states) < 0.15,
        }
    return report

The floor of thirty is not arbitrary: below roughly that, a row of the transition matrix is dominated by which handful of transitions happened to be observed, and the resulting routes inherit that accident as though it were structure. When a period fails the check the answer is to merge it with an adjacent one, not to fit it anyway and smooth afterwards.

Fix: A Small Number of Regimes, Fitted Independently, Smoothed at the Edges

1 — Choose periods from the data, not from the clock

python
def discover_regimes(hourly_matrices, max_regimes: int = 6) -> list:
    """Merge adjacent hours whose transition distributions are close."""
    groups = [[h] for h in range(24)]
    while len(groups) > max_regimes:
        best, where = None, None
        for i in range(len(groups) - 1):
            d = jensen_shannon(pooled(hourly_matrices, groups[i]),
                               pooled(hourly_matrices, groups[i + 1]))
            if best is None or d < best:
                best, where = d, i
        groups[where:where + 2] = [groups[where] + groups[where + 1]]
    return groups

Merging only adjacent hours keeps the periods contiguous, which matters because a trip crosses period boundaries and a non-contiguous scheme makes those crossings incoherent. What usually emerges is four to six regimes — an overnight period, a morning peak, an interpeak, an evening peak, and an evening — which is both what the data supports and what practitioners would have guessed, and it is worth confirming rather than assuming.

2 — Fit each regime with shrinkage toward the pooled matrix

python
def fit_regime(counts, pooled_matrix, alpha: float = 12.0) -> dict:
    """Regime-specific rows shrunk toward the all-day matrix by their own sample size."""
    out = {}
    for state, row in counts.items():
        total = sum(row.values())
        w = total / (total + alpha)            # more data → less shrinkage
        out[state] = {
            nxt: w * (c / total) + (1 - w) * pooled_matrix[state].get(nxt, 0.0)
            for nxt, c in row.items()
        }
    return out

This is what makes a six-regime model safe on thin states. A well-observed state uses its own regime’s data almost entirely; a rarely visited one falls back to the pooled behaviour rather than to whatever two transitions happened to be recorded at 04:00.

3 — Interpolate across boundaries so trips do not teleport between regimes

python
def transition_row(state, t_minutes: float, regimes, blend_minutes: float = 30.0):
    """Blend linearly across a regime boundary instead of switching at a point."""
    cur, nxt, frac = regime_position(t_minutes, regimes, blend_minutes)
    if frac is None:
        return regimes[cur][state]
    a, b = regimes[cur][state], regimes[nxt][state]
    keys = set(a) | set(b)
    return {k: (1 - frac) * a.get(k, 0.0) + frac * b.get(k, 0.0) for k in keys}

Without the blend, an agent mid-trip at the regime boundary changes its routing distribution discontinuously, which shows up as an implausible spike in turn rates at exactly 07:00 and 10:00 in the generated data — a signature that is easy to spot once you know to look for it and mystifying otherwise.

Where the natural time-of-day regime boundaries fall The horizontal axis is the hour of day. Each bar sits between two consecutive hours and its height is the Jensen-Shannon distance between their transition distributions — a measure of how differently the network routes in those two hours. Most bars are short: adjacent hours in the middle of the night, or in the middle of the afternoon, route almost identically. A handful are much taller, and they fall at the shoulders of the peaks — the transition into the morning peak, out of it into the interpeak, into the evening peak, out of it into the evening, and the settle into overnight. Those five tall bars are marked as the boundaries a merging procedure selects when it repeatedly joins the closest pair of adjacent hours. What emerges is five or six contiguous regimes rather than twenty-four hourly matrices. The note underneath makes the point that this is worth computing rather than assuming: the boundaries usually land where a practitioner would guess, and the check costs one pass over the data and occasionally disagrees. Merge adjacent hours until only the real boundaries survive 00:00 06:00 12:00 18:00 23:00 0.00 0.05 0.10 hour of day distance to the next hour 06:00 10:00 15:00 19:00 22:00 selected regime boundary merged away Merging only adjacent hours keeps the regimes contiguous, which matters because a trip crosses boundaries and a non-contiguous scheme makes those crossings incoherent. What emerges here is five regimes — overnight, morning peak, interpeak, evening peak, evening — which is what a practitioner would have guessed. It is worth computing anyway: the check is one pass, and it occasionally disagrees.
Hour-to-hour transition distance and the merge sequence: where the natural regime boundaries actually fall.

Verification Step: Hold Out Hours, Not Rows

python
def test_period_model_beats_pooled(train, holdout_hours, states):
    """Held-out log-likelihood, the only comparison that means anything here."""
    pooled = fit_pooled(train)
    periods = fit_periods(train)
    ll_pooled = loglik(pooled, holdout_hours)
    ll_periods = loglik(periods, holdout_hours)
    assert ll_periods > ll_pooled, "the period model does not generalise; use fewer regimes"


def test_peak_asymmetry_is_reproduced(generated, observed, tol=0.12):
    for hour in (8, 17):
        got = directional_ratio(generated, hour)
        want = directional_ratio(observed, hour)
        assert abs(got - want) / want < tol, f"hour {hour}: {got:.2f} vs {want:.2f}"


def test_no_turn_rate_spike_at_boundaries(generated, regimes, tol=1.25):
    base = median_turn_rate(generated)
    for boundary in regime_boundaries(regimes):
        assert median_turn_rate(generated, window=boundary) < base * tol, (
            f"turn-rate spike at {boundary} — the blend is missing or too narrow"
        )


def test_overnight_period_is_not_overfitted(periods, pooled, min_shrinkage=0.35):
    """Thin periods should be visibly pulled toward the pooled matrix."""
    assert mean_shrinkage(periods["overnight"], pooled) > min_shrinkage

Holding out whole hours rather than random transitions is the crucial detail. Random held-out transitions come from the same hours as the training data, so a model that has memorised each hour scores well on them, and the test certifies exactly the overfitting it was meant to catch.

Held-out likelihood against time-of-day regime count The horizontal axis is the number of time-of-day regimes fitted, from a single all-day matrix up to one matrix per hour, on a scale that spreads the small values. The vertical axis is average log-likelihood per transition, where higher is better. The training curve rises steadily all the way to twenty-four regimes, which is what it must do — more parameters always fit the data they were fitted to. The held-out curve rises steeply from one to about four regimes, flattens, reaches a maximum, and then falls away as the regimes become too thin to estimate. A marker identifies the peak, which sits at a small number well below the hourly granularity people reach for first. Past that point every additional regime makes the model fit its own training hours better and describe new hours worse. The note underneath states the practical consequence: the number of regimes is set by transitions available per state, not by how finely the day can be divided, and the only way to see the difference is to hold out whole hours rather than random transitions. More regimes always fit better; only held-out hours say whether it helps 1 4 8 12 24 -2.50 -2.35 -2.20 -2.05 time-of-day regimes fitted log-likelihood per transition peak at 6 regimes training likelihood held-out hours training data The regime count is set by transitions available per state, not by how finely the day can be divided. Holding out whole hours rather than random transitions is what makes the difference visible: random held-out transitions come from the same hours as the training data, so a model that memorised each hour scores well on them and the check certifies the overfitting it was meant to catch.
Held-out log-likelihood against regime count: the improvement stops well before the daily-schedule granularity people reach for first.

Edge Cases & Gotchas

Day of week is a second dimension, and usually a bigger one. Saturday differs from Tuesday more than 10:00 differs from 14:00. Fitting time-of-day within a weekday/weekend split before adding regimes is almost always the better use of the same data.

Trips that span several regimes. A ninety-minute trip starting in the morning peak finishes in the interpeak. Using the departure period for the whole trip is wrong in a way that compounds with trip length; evaluating the row at the current simulated time costs nothing and removes the bias.

Absorbing states appear in thin periods. A state with no outbound transitions observed overnight becomes absorbing in that regime, and agents entering it never leave. Shrinkage prevents this as a side effect, which is a good reason to apply it even where the sample size does not demand it.

Holidays and events. These are not time-of-day effects and should not be fitted as regimes. Excluding them from the training window is the standard treatment; modelling them, if needed at all, is a separate model with a separate calendar.

What to Record So the Regimes Survive Contact With Consumers

A time-varying routing model is a more complicated object than a stationary one, and most of the trouble it causes downstream comes from the extra structure not being written down.

The regime boundaries, as data. A consumer aggregating generated traces by hour needs to know that 09:59 and 10:01 come from different regimes, or their hourly summaries will show a discontinuity they cannot explain. Publishing the boundaries alongside the release turns a mystery into a documented property.

Whether the blend was applied, and how wide it is. A thirty-minute blend means the boundary is soft and hourly aggregates near it are mixtures. A consumer computing peak-hour statistics needs that number to decide which hours are clean.

The shrinkage weight per regime. An overnight regime pulled seventy percent toward the pooled matrix is not really an overnight model, and a consumer analysing night-time routing should know that before drawing conclusions from it. This is the same honesty requirement as reporting a degraded accuracy field rather than a nominal one — the release knows something the consumer cannot recover.

Which periods were excluded from fitting. Holidays, incident days, and the weeks around roadworks are usually and correctly dropped, and a release that does not say so invites a consumer to compare its output against a period it was never meant to describe.

The general shape here is the one that recurs across every parameterised generator: the parameters are part of the artifact. A release that ships traces without them is asking every consumer to reverse-engineer the model from its output, and they will each get a slightly different answer.