path_dependence: Per-Context Path Dependence at Order k

In Nestimate: Network Estimation, Bootstrap, and Higher-Order Analysis

Per-Context Path Dependence at Order k

Description

Diagnoses where a chain's order-1 Markov assumption fails by comparing, for each order-k context (s_1, \ldots, s_{k-1}), the empirical next-state distribution P(s_k \mid s_1, \ldots, s_{k-1}) against the order-1 prediction P(s_k \mid s_{k-1}) that uses only the most recent state. Returns a tidy per-context table sorted by Kullback-Leibler divergence so the analyst can see exactly which histories carry extra predictive information.

Usage

path_dependence(x, order = 2L, min_count = 5L, base = 2)

Arguments

x	A wide sequence data.frame / matrix (rows = actors, columns = time-steps), or a netobject that carries the source data.
order	Integer. Order of the conditioning context. order = 2 (default) compares 2-step memory against 1-step; order = 3 compares 3-step memory; etc. Must be a whole number; a non-integer value is an error rather than being silently truncated.
min_count	Integer. Drop contexts seen fewer than this many times. Default 5. Very small samples produce noisy KL estimates.
base	Numeric. Logarithm base for entropy and KL. Default 2 (bits).

Details

For each context c = (s_1, \ldots, s_{k-1}) occurring at least min_count times, the function computes:

• the empirical conditional P_k(\cdot \mid c) from k-gram counts;

• the order-1 prediction P_1(\cdot \mid s_{k-1}) from the most recent state alone (the bigram-marginal estimator);

• the entropy drop H(P_1) - H(P_k) - bits of uncertainty removed by extending memory by one step in this specific context;

• the Kullback-Leibler divergence D_{KL}(P_k \,\|\, P_1) - bits of "surprise" if you used the order-1 model when the order-k model is true.

KL = 0 means longer history adds no information for that context. H_drop > 0 means longer history sharpens the prediction; H_drop < 0 indicates the order-k context happens to spread probability across more outcomes than order-1 alone (small-sample noise or genuine context-induced uncertainty - inspect n).

Contexts where flips = TRUE are the substantively interesting ones: the longer history changes the modal prediction, not just its confidence.

Pair this with markov_order_test (which decides whether order-k is needed globally) to see the chain-level decision broken down per context.

Value

An object of class "net_path_dependence" with

contexts

tidy data.frame, one row per order-k context, sorted by KL descending. Columns: context (e.g. "A -> B"), n (count), H_order1 (entropy of P(\cdot \mid s_{k-1})), H_orderk (entropy of P(\cdot \mid \mathrm{context})), H_drop (= H_order1 - H_orderk), KL (= D_{KL}(P_k \| P_1)), top_o1 (most likely next state under order-1), top_ok (most likely next state under order-k), flips (logical: did the most likely next state change?).

chain

list with chain-level summaries: KL_weighted (count-weighted mean KL across contexts), H_drop_weighted (count-weighted mean entropy drop), n_contexts, n_flips (contexts where the most-likely next state changed).

order

integer

base

numeric

min_count

integer

states

character vector

References

Cover, T.M. & Thomas, J.A. (2006). Elements of Information Theory, 2nd ed., chapters 2 and 4. Wiley. (KL divergence and conditional entropy.)

See Also

markov_order_test, transition_entropy, build_mogen

Examples

data(trajectories, package = "Nestimate")
pd <- path_dependence(as.data.frame(trajectories), order = 2)
print(pd)
summary(pd)
plot(pd)

Nestimate documentation built on July 11, 2026, 1:09 a.m.