An Iterative Scheme to Compute Size Probabilities in Random Graphs and Branching Processes

Abstract EN

We deal with a functional equation that plays an important role in random graphs and in branching processes.

In branching processes, the functional equation relates offspring probabilities to population size probabilities, while in random graph it relates degree probabilities to small component size probabilities.

We present an iterative scheme that allows computing the size probabilities numerically.

It is also theoretically possible to invert the iteration, although this inverse iteration is numerically unstable.