The negative binomial distribution captures the probability of having S-1 successes and F failures in F+S-1 trials and then a success on the (F+S)th trial[1] where the probability of success at any trial is P. Let this function be called NBpdf(F,S,P).

If a N-state, left-right markov model is constructed such that the probability of transition to the next state is P and the probability of a self-transition is (1-P), then the probability of visiting x states (and generating an observation sequence of length x) in a state machine of length n is given by NBpdf(x-N,N,P).