What does Hidden Markov Models for Customer Decision Stages conclude, in numbers, about “The Viterbi Trellis: Dynamic Programming in Logarithms, Backtracking and Underflow”?
Answer: Chapter 2 unfolds Viterbi on a trellis, shows direct multiplication underflowing near click 368, and finds that the best path holds only 0.0357 of the total probability.
Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 368
| smallest positive double: 4.941e-324 | ||||
| T | raw log P | log-domain | scaled | raw path = log path |
| 50 | -105.41 | -105.41 | -105.41 | 1.000 |
| 200 | -410.93 | -410.93 | -410.93 | 1.000 |
| 400 | -inf(0.0) | -818.24 | -818.24 | 0.943 |
| 600 | -inf(0.0) | -1228.56 | -1228.56 | 0.632 |
| 1000 | -inf(0.0) | -2042.15 | -2042.15 | 0.408 |
| 2000 | -inf(0.0) | -4042.20 | -4042.20 | 0.255 |
| log-probability per click: -2.021 nats | ||||
| raw products die near T = 368 clicks |
Key formula
Show the full program
# Chapter 2. p22: why decoding must run in logs (or with scaling).
# Model: the four-stage HMM of p11 (illustrative). One long click stream
# is simulated with a fixed seed, as if a member's consented, anonymised
# clicks over many visits were decoded together. At several lengths T
# the program runs the Viterbi recursion three ways: raw products of
# probabilities, natural logs, and per-step rescaling (divide by the
# column maximum and keep the log of the divisor). Raw products sink
# below the smallest double and the decoded path turns to nonsense.
import math
import random
PI = [0.70, 0.20, 0.08, 0.02]
A = [[0.70, 0.22, 0.06, 0.02],
[0.08, 0.64, 0.23, 0.05],
[0.02, 0.10, 0.66, 0.22],
[0.01, 0.03, 0.16, 0.80]]
B = [[0.45, 0.30, 0.08, 0.07, 0.06, 0.04],
[0.15, 0.35, 0.25, 0.12, 0.08, 0.05],
[0.08, 0.22, 0.15, 0.30, 0.17, 0.08],
[0.05, 0.12, 0.08, 0.15, 0.30, 0.30]]
K = 4
def draw(rng, probs):
u, acc = rng.random(), 0.0
for k, p in enumerate(probs):
acc += p # step
if u < acc:
return k
return len(probs) - 1
def decode(obs, mode):
# mode: raw 原始乘积;log 对数域;scale 每步按列最大值缩放
if mode == "log":
d = [math.log(PI[k] * B[k][obs[0]]) for k in range(K)]
else:
d = [PI[k] * B[k][obs[0]] for k in range(K)]
logc = []
back = []
for o in obs[1:]:
if mode == "log":
ptr = [max(range(K), key=lambda i: d[i] + math.log(A[i][j]))
for j in range(K)]
d = [d[ptr[j]] + math.log(A[ptr[j]][j] * B[j][o])
for j in range(K)]
else:
ptr = [max(range(K), key=lambda i: d[i] * A[i][j])
for j in range(K)]
d = [d[ptr[j]] * A[ptr[j]][j] * B[j][o] for j in range(K)]
if mode == "scale":
c = max(d)
logc.append(math.log(c))
d = [x / c for x in d]
back.append(ptr)
best = max(range(K), key=lambda k: d[k])
path = [best]
for ptr in reversed(back):
path.append(ptr[path[-1]])
if mode == "log":
score = d[best]
elif mode == "scale":
score = math.log(d[best]) + math.fsum(logc)
else:
score = math.log(d[best]) if d[best] > 0 else -math.inf
return path[::-1], score
rng = random.Random(20261113)
s = [0]
for _ in range(1999):
s.append(draw(rng, A[s[-1]]))
o = [draw(rng, B[k]) for k in s]
print("smallest positive double: %.3e" % (5e-324))
print(" T raw log P log-domain scaled raw path = log path")
for t_len in (50, 200, 400, 600, 1000, 2000):
obs = o[:t_len]
p_raw, sc_raw = decode(obs, "raw")
p_log, sc_log = decode(obs, "log")
p_sc, sc_sc = decode(obs, "scale")
agree = len([1 for a, b in zip(p_raw, p_log) if a == b]) / t_len
raw_txt = "%10.2f" % sc_raw if sc_raw > -math.inf else " -inf(0.0)"
print("%5d %s %11.2f %8.2f %8.3f%s"
% (t_len, raw_txt, sc_log, sc_sc, agree,
"" if p_sc == p_log else " scaled path differs"))
per_click = sc_log / 2000
print("log-probability per click: %.3f nats" % per_click)
print("raw products die near T = %d clicks"
% int(math.log(5e-324) / per_click))Single source and citation
Fan, Y. (2026). Hidden Markov Models and Viterbi Decoding: Inferring a Customer's Hidden Decision Stage from Click Sequences and Timing the Offer (Version 1.0.0), Chapter 2: The Viterbi Trellis: Dynamic Programming in Logarithms, Backtracking and Underflow. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-300 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026300,
author = {Fan, Yafu},
title = {Hidden Markov Models and Viterbi Decoding: Inferring a Customer's Hidden Decision Stage from Click Sequences and Timing the Offer},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Last-Click Illusion: Whole Sequences against a Single Page
- Chapter 3 · Forward and Backward: Posterior Marginals, the Best Path and "Wait Two More Clicks"
- Chapter 4 · Baum–Welch: Estimating Parameters from Unlabelled Clickstreams
- Chapter 5 · Identifiability and Label Switching: What Clickstreams Cannot Say
- Chapter 6 · Timing the Offer: the Inquiry as Evidence, a Cost Threshold and Calibration
- Chapter 7 · Classical Sources East and West: Markov's Letter Chain in Onegin and the Chuai Chapter of the Guiguzi
- Chapter 8 · Closing the Loop: a Weekly Stage Review, the Customer Stage Decoder and Pre-Registered Tests