Universal Generating Functions
The Method of Universal Generating Functions (U-functions), introduced by Ushakov (1986), actually represents a generalization of Kettelle's Algorithm. This method suggests a transparent and convenient method of computerized solutions of various enumeration problems, in particular, the optimal redundancy problem.
First, let us refresh our memory concerning generating functions. This is a very convenient tool widely used in probability theory for finding joint distributions of several discrete random variables. Generating function is defined as:
where pk is the probability that discrete random variable X takes value k and Gk is the distribution function domain. In optimal redundancy problems, in principle, Gk = [0, ∞), though any practical task has its own limitations on the largest value of k.
Consider two non-negative discrete random values X1 and X2 with distributions
correspondingly, where n1 and n2 are numbers of discrete values of each type. For finding probability of random variable X = X(1) + X(2), one should enumerate all possible pairs of X(1) and X(2) that give in sum value k and add corresponding ...