IEEE Transactions on Information Theory, VOL. 46, NO. 7, NOVEMBER 2000

The Ballot Theorem Strikes Again:
Packet Loss Process Distribution

Omer Gurewitz, Moshe Sidi and Israel Cidon
Electrical Engineering Department Technion, Haifa 32000, Israel

The probability distribution of the number of lost packets within a block of consecutive packet arrivals into a finite buffer is an important quantity in various networking problems. In a recent paper, Cidon, Khamisy, and Sidi introduced a recursive scheme to derive this distribution. In this paper, we derive explicit expressions for this distribution using various versions of the powerful Ballot Theorem. The expressions are derived for a single source M/M/1/K queue.