A Generalization of the Ballot Problem and its Application in the Theory of Queues

Abstract

The following generalization of the classical ballot theorem is given: Suppose that an urn contains n cards marked with nonnegative integers whose sum is k ≦ n. All the n cards are drawn without replacement from the urn. The probability that for r = 1, 2, ···, n the sum of the first r numbers drawn is less than r is 1 —k/n. By using the ballot theorem and its generalization the author finds G _n (x) the probability that a busy period consists of serving n customers and its length is ≦x for single-server queues when either the inter-arrival times or the service times have an exponential distribution. Finally, the author gives the general solution of the classical ballot problem as well as an application of it in the theory of Bernoulli trials.