Start with 36 cells, not 160 billion: the case for a coarse first-order Markov chain

A dev.to walkthrough of clickstream sequence modelling makes a deliberately unfashionable recommendation: begin next-action prediction with a first-order Markov chain over coarse page types, on the grounds that it takes about ten lines to fit, every parameter is readable, and its failures are informative about what a bigger model would need to do ^[1]. That matters because the two decisions that determine whether the work is usable are both taken before any model is fitted: where a session ends, and how many states you allow. The input is sessions, and according to the write-up the boundary rule is a modelling choice rather than a preprocessing detail: a longer inactivity timeout stitches a return visit onto the previous session and creates transitions that no single sitting contained ^[2]. Those transitions are not observations. Anyone tuning the timeout to tidy the data is editing the transition counts. Then the alphabet. Modelling transitions between individual URLs on a site with 400,000 pages gives 1.6 x 10^11 possible transitions and essentially no data per cell ^[3]. Collapsing to home, search, product, cart, checkout and exit gives a matrix you can read and estimate reliably ^[4]: 36 cells, roughly 4.4 billion times fewer than the URL-level version of 160 billion ^[1]. The stated rule is to start coarse, because if the coarse model predicts well a finer alphabet may add resolution, and if it predicts badly a finer one only adds noise ^[5]. The worked example is five sessions over H, S, P, C and X ^[6], with row totals of 5, 6, 6 and 3 out of H, S, P and C, or 20 transitions in all ^[7][2]. Maximum likelihood is the count of a transition divided by the total out of that state, so every row sums to one by construction ^[8]. The matrix gives P(S|H) = 0.800, P(P|S) = 0.833, P(C|P) = 0.500 and P(X|C) = 1.000 ^[9], which makes the sequence H S P C X 0.333 ^[10] against 0.067 for H P X ^[11], about five times as likely ^[3]. Two readings come free: the product row has users going to cart half the time and leaving a third of the time, so P is where the leak is ^[12], and the cart row makes checkout entry certain, which on three observations means nothing and is exactly the overconfidence smoothing exists to correct ^[13]. The zeros are the trap. A zero is a strong claim of impossibility, so any sequence containing that transition has probability exactly zero ^[15], and a user arriving at a saved cart directly from the homepage, which the author says happens constantly in real traffic, is scored at zero by a model estimated from five sessions that did not contain it ^[16]. Additive smoothing pretends each transition was seen alpha extra times: at alpha = 1 over five states the H row goes from [0, 4, 1, 0, 0] to [1, 5, 2, 1, 1] and P(S|H) falls to 0.500 while P(C|H) rises to 0.100 ^[17]. With a row total of 5 and an alphabet of 5, the prior is half the posterior ^[18], a 37.5 per cent relative cut to the leading estimate, against 6.9 per cent at alpha = 0.1, which still gives H to C a non-zero 0.018 ^[19][4]. Across the full matrix, add-one injects 25 pseudo-counts against 20 real ones ^[5]. The alternative offered is back-off, mixing the row-specific distribution with the marginal distribution of next states weighted by how much data the row has, which beats a flat prior because some destinations are popular from everywhere ^[20]. The honest limit is the assumption itself. A product-page visitor who arrived from search has different intent from one who arrived from a marketing email, and the model cannot tell them apart because both are in state P ^[21].