This paper proposes the replacement of the ordinary output probability with its expected value if the addition of noise is modeled as a stochastic process, which in turn is merged with the hidden Markov model (HMM) in the Viterbi algorithm. This new output probability is analytically derived for the generic case of a mixture of Gaussians and can be seen as the definition of a stochastic version of the weighted Viterbi algorithm. Moreover, an analytical expression to estimate the uncertainty in noise canceling is also presented. The method is applied in combination with spectral subtraction to improve the robustness to additive noise of a text-dependent speaker verification system. Reductions as high as 30% or 40% in the error rates and improvements of 50% in the stability of the decision thresholds are reported.