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
Traw log Plog-domainscaledraw path = log path
50-105.41-105.41-105.411.000
200-410.93-410.93-410.931.000
400-inf(0.0)-818.24-818.240.943
600-inf(0.0)-1228.56-1228.560.632
1000-inf(0.0)-2042.15-2042.150.408
2000-inf(0.0)-4042.20-4042.200.255
log-probability per click: -2.021 nats
raw products die near T = 368 clicks

Key formula

\[\delta_t(j) = \max_i \left[ \delta_{t-1}(i)\, a_{ij} \right] b_j(o_t),\]
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