计算值太大而无法求幂的马尔可夫链概率 [英] Calculating Markov chain probabilities with values too large to exponentiate

问题描述

我使用公式exp(X)作为马尔可夫链的利率.因此，选择一个链接比另一个链接的比率为exp(X1)/exp(X2).我的问题是，有时X很大，所以exp(X)会超出double的范围.

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.

或者:给定一个X [i]数组，其中有一些X [i]太大，以至于exp(X [i])超出了double的范围，请为每个i计算exp(X [i] )/S，其中S是所有exp(X [i])的和.

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]).

推荐答案

此伪代码应该可以工作:

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.

如果M大，则在减法步骤之后，某些X [i]会很小(具有较大的负值)，以至于它们的exp(X [i])的精度为双精度.但是，这些项目的实际概率是如此之小，以至于它们的实际概率与零之间没有实际差异，因此，exp(X [i])下溢为零是可以的.

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).
• 该除法以相同的方式影响概率的分子和分母，因此比率保持相同.

这篇关于计算值太大而无法求幂的马尔可夫链概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！