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.

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

Consider two non-negative discrete random values *X*_{1} and *X*_{2} with distributions

and

correspondingly, where *n*_{1} and *n*_{2} 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 ...

Start Free Trial

No credit card required