The Viterbi algorithm first sets up a probability matrix, with one column for each observation $o_t$ and one row for each state in the state graph. Each column thus has a cell for each state $q_i$ in the single combined automaton. Each cell of the matrix is given by: $v_t(j) = \max_{q_1, ..., q_{t-1}} P(q_1...q{t-1}, o_1, ..., o_t, q_t = j|\lambda)$

For a given state $q_j$ at time $t$, we compute the value $v_t(j)$ as: $v_t(j) = \max_{i=1}^N v_{t-1}(i)a_{ij}b_j(o_t)$ where:

• $v_{t-1}(i)$ is the previous Viterbi path probability from the previous time step
• $a_{ij}$ is transition probability from previous state $q_i$ to current state $q_j$
• $b_j(o_t)$ is the state observation likelihood of the observation symbol $o_t$ given the current state $j$