A first-order Markov chain over page types is the model most next-action work should start with. It takes ten lines to fit, you can read every parameter, and its failures are informative about what a bigger model would need to do.
From sessions to transitions
The input is sessions, produced by the boundary rule described in session reconstruction, and that rule is a modelling choice rather than a preprocessing detail: a longer timeout stitches a return visit onto the previous session and creates transitions that no single sitting contained.
The second choice is the state alphabet. Modelling transitions between individual URLs on a site with 400,000 pages gives 1.6 × 1011 possible transitions and essentially no data per cell. Modelling transitions between page types — home, search, product, cart, checkout, exit — gives a matrix you can read and estimate reliably. Start coarse. If the coarse model predicts well, a finer alphabet may add resolution; if it predicts badly, a finer one will only add noise.
Take five sessions over the alphabet H (home), S (search), P (product), C (cart), X (exit).
s1 H S P C X
s2 H S P S P C X
s3 H P X
s4 H S S P X
s5 H S P C X
transition counts (from -> to)
H S P C X total
H 0 4 1 0 0 5
S 0 1 5 0 0 6
P 0 1 0 3 2 6
C 0 0 0 0 3 3
Estimating the matrix
The maximum-likelihood estimate of a transition probability is simply the count of that transition divided by the total count of transitions out of that state. Every row sums to 1 by construction.
P(next | current)
H S P C X
H 0.000 0.800 0.200 0.000 0.000
S 0.000 0.167 0.833 0.000 0.000
P 0.000 0.167 0.000 0.500 0.333
C 0.000 0.000 0.000 0.000 1.000
probability of the sequence H S P C X under this model
= P(S|H) x P(P|S) x P(C|P) x P(X|C)
= 0.800 x 0.833 x 0.500 x 1.000
= 0.333
probability of H P X
= P(P|H) x P(X|P) = 0.200 x 0.333 = 0.067
Two useful things fall straight out of the matrix without any further machinery. The row for P says that a user on a product page goes to cart half the time and leaves a third of the time, so P is where the leak is; the row for C says checkout entry from cart is certain in this corpus, which given three observations means nothing yet and is exactly the sort of overconfidence smoothing exists to correct. Multiplying the matrix by itself gives two-step probabilities, and the stationary distribution of the chain — the eigenvector for eigenvalue 1 — describes long-run occupancy, which is only meaningful if you handle the absorbing exit state deliberately rather than letting all probability mass drain into it.
Zero counts and what smoothing costs
The matrix contains many zeros, and a zero is a strong claim: it says the transition is impossible, so any sequence containing it has probability exactly zero. A user who goes H → C — arriving at a saved cart directly from the homepage, which happens constantly in real traffic — is assigned probability zero by a model estimated from five sessions that did not contain it.
Additive smoothing fixes this by pretending each transition was seen α extra times. With α = 1 (Laplace) over an alphabet of 5 states:
row H, raw counts [0, 4, 1, 0, 0], total 5
add-one [1, 5, 2, 1, 1], total 10
P(H|H) = 0.100 P(S|H) = 0.500 P(P|H) = 0.200
P(C|H) = 0.100 P(X|H) = 0.100
compare with the unsmoothed row
P(S|H) fell from 0.800 to 0.500
P(C|H) rose from 0.000 to 0.100
That is a large distortion, and it is the honest cost of smoothing on small counts: with a row total of 5 and an alphabet of 5, the prior is half the posterior. The correction is to scale α down — α = 0.1 moves P(S|H) to 4.1/5.5 = 0.745 while still giving H → C a non-zero 0.018 — or to back off to a lower-order model, mixing the row-specific distribution with the overall marginal distribution of next states weighted by how much data the row has. Back-off is generally better than a flat prior because it uses the fact that some destinations are popular from everywhere.
Where the memoryless assumption breaks
A first-order chain asserts that the next state depends only on the current one. That is plainly false for browsing: a user on a product page who arrived from a search has different intent from one who arrived from a marketing email, and the model cannot represent the difference because both are in state P.
The direct fix is a higher-order chain, where the state becomes the last k pages. The cost is exponential: with an alphabet of m states, a k-th order chain has mk rows. With 5 page types, second order is 25 rows and fine; with 500 page categories, second order is 250,000 rows and third order is 125 million, against which any realistic traffic volume is sparse. This is the data sparsity wall, and it is the reason variable-order models — extend the context only where the extra history measurably changes the prediction, prune everywhere else — exist.
The other break is duration. A Markov chain models order and ignores the time between steps, yet dwell time is one of the strongest available signals: forty seconds on a product page means something different from two. Semi-Markov models attach a duration distribution to each state, and the cheaper practical alternative is to split states by binned dwell time — Pshort and Plong as distinct states — which multiplies the alphabet but keeps the entire apparatus above unchanged.
When both limits bite, sequence models with learned hidden state — recurrent networks, or self-attention over the session — carry arbitrary history without the exponential state count, at the cost of the interpretability that made the matrix worth reading. Session-based recommendation with recurrent networks is the established line of work here. It is worth keeping the Markov model alongside as a baseline regardless, because a neural model that does not beat it is telling you something about your data rather than about your architecture.
Evaluating a next-action model
Split by session and by time, never by event. Randomly splitting individual clicks puts the same session on both sides and leaks the answer; splitting by session but not by time trains on the future. Hold out whole sessions from a later period.
Report top-k accuracy and mean reciprocal rank rather than exact-match accuracy, because the task is naturally uncertain and being right within three candidates is what a downstream use — prefetching, ranking, a recommendation slot — actually requires. Perplexity over held-out sequences is the right aggregate for comparing model families, and it must be computed with a smoothed model or it is infinite the moment an unseen transition appears.
Compare against two baselines before believing anything. The first is the marginal: always predict the globally most common next state, ignoring the current one. The second is the identity: predict that the user stays on the same page type. On real clickstreams both are stronger than people expect, and a model that does not clearly beat both is not yet a model.
Top comments (0)