## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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 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

and

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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required