Calculating Markov chain probabilities with values too large to exponentiate

Question

I use the formula exp(X) as the rate for a markov chain. So the ratio of selecting one link over another is exp(X1)/exp(X2). My problem is that sometimes X is very large, so exp(X) will exceed the range of double.

Alternatively: Given an array of X[i], with some X[i] so large that exp(X[i]) overflows the range of double, calculate, for each i, exp(X[i]) / S, where S is the sum of all the exp(X[i]).

Daughterinlaw

I made edits to clarify your question and my answer. You may revert them if I erred. – Bathyal

Answer 1

This pseudo-code should work:

Let M = the largest X[i].

For each i:
    Subtract M from X[i].

Let S = the sum of exp(X[i]) for all i.

For each i:
    The probability for this i is exp(X[i]) / S.

If M is large, then, after the subtraction step, some X[i] will be so small (have large negative values) that their exp(X[i]) will evaluate to zero in double precision. However, the actual probability of these items is so minuscule that there is no practical difference between their actual probability and zero, so it is okay that exp(X[i]) underflows to zero.

Aside from underflow and rounding errors, the probabilities should be the same after the subtraction transformation, because:

• exp(x-M) = exp(x)/exp(M).
• This division affects both the numerator and the denominator of the probability the same way, so the ratio remains the same.

Bathyal

I see, but I want to run the markov chain. I must select a link with probability exp(X1)/sum(exp(Xi)). Instead I create a cumulative array of exp(Xi)s. And generate a number between 0 to exp(Xn). So I don't need the ratio. I need the actual numbers – Daughterinlaw

What is too large to represent as a double, X or exp(X)? (You wrote “it will get out of double range” when “X” was the nearest preceding noun.) If X is too big, you have to solve that problem before worrying about exp(X). If exp(X) is too big, then normalize your Xi by subtracting the largest Xi from all of them (making the largest of them 0 and the rest of them non-positive). This should leave all the significant exp(Xi) within range of a double without altering the probabilities. (Any Xi that become large negative values will have miniscule probabilities, so it is okay if exp(Xi) is zero.) – Bathyal