Optimal Resource Allocation: With Practical Statistical Applications and Theory

CHAPTER 6

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.

6.1 Generating Function

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:

(6.1)

where p_k is the probability that discrete random variable X takes value k and G_k is the distribution function domain. In optimal redundancy problems, in principle, G_k = [0, ∞), though any practical task has its own limitations on the largest value of k.

Consider two non-negative discrete random values X₁ and X₂ with distributions

and

correspondingly, where n₁ and n₂ are numbers of discrete values of each type. For finding probability of random variable X = X⁽¹⁾ + X⁽²⁾, one should enumerate all possible pairs of X⁽¹⁾ and X⁽²⁾ that give in sum value k and add corresponding ...