O'Reilly logo

Optimal Resource Allocation: With Practical Statistical Applications and Theory by Igor A. Ushakov

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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) c6-math-0001

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

c6-math-5001

and

c6-math-5002

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.

Start Free Trial

No credit card required