I'm wrestling with this formula, formally a function of the vector $\pmb{F}$: $$\begin{aligned} S(\pmb{F}) &:=\sum_{a=0}^A (-1)^{A-a}\,\binom{A}{a}\, \Biggl[\sum_{b=0}^{A} F_b \, \binom{a}{b}\Big/\binom{K}{b}\Biggr]^B \\&\equiv \sum_{a=0}^A (-1)^{a}\,\binom{A}{a}\, \Biggl[\sum_{b=0}^{A} F_b \, \binom{A-a}{b}\Big/\binom{K}{b}\Biggr]^B \end{aligned} $$ (the sums in brackets actually end at $a$ and $A-a$, remaining terms being zero).

The coefficients are all integers and can have these orders of magnitude:

  • $A\sim \text{10 to 1000}$
  • $B\sim \text{10 to 300}$
  • $K \sim \text{50000 to 100000}$

and the argument satisfies $0\le F_b<1$ and $\sum_b F_b <1$, which implies that $S(\pmb{F})\ge0$.

Unfortunately the terms of this sum (in $a$) easily assume extremely similar but opposite values, leading to catastrophic cancellation in numerical computations. For example one can get meaningless results with negative sign.

Taking $b$-independent terms out of the brackets doesn't help, because it doesn't change the relative precision of the mutually almost-cancelling terms. I've also tried grouping together the terms with $\tbinom{A}{a}$ and $\tbinom{A}{A-a}$, but catastrophic cancellation occurs (especially if $A$ is even) even across such groups.

Since I'm numerically dealing with this formula in R, I've tried using the Rmpf package for arbitrary-precision computation. It manages to get the correct result (which I can compute with Mathematica) in some cases, as opposed to machine-precision computation, but it still fails in some situations. And it makes the computation much slower.

Does anyone have some clever ideas of how to transform this formula to avoid the catastrophic cancellation? I'd be really grateful for your help.


This formula arises in network theory, in the problem of guessing the number of connections from a set of nodes to another, disjoint set of nodes.

The first set has $K$ nodes, the second can be assumed to have infinite nodes. We know that exactly $A$ nodes of the first set connect to exactly $B$ nodes of the second, but we don't know which node connects to which. Each of the $A$ nodes must connect to at least one of the $B$ nodes; but not all $B$ nodes need to be receiving a connection. $F_b$ represents the fraction (relative frequency) of nodes in the second set that receive $b$ connections from the first set.

The formula, derivable with some combinatorics, gives the probability (except for a factor independent of $\pmb{F}$) for a particular frequency distribution $\pmb{F}$. The alternating sum appears from the probability-sum rule with more than two terms. Roughly speaking, we're calculating $1$ minus the probability that at least one node from the first set has no connections, or at least two nodes from the first set have no connections, and so on.

Ultimately I'd be interested in the logarithm of $S(\pmb{F})$.

From this context, I'd be happy to hear suggestions for slight variations or limits that may lead to a more manageable formula.




You must log in to answer this question.

Browse other questions tagged .