  This paper studies the fundamental limits of availability and throughput for
independent and heterogeneous demands of a limited resource. Availability is
the probability that the demands are below the capacity of the resource.
Throughput is the expected fraction of the resource that is utilized by the
demands. We offer a concentration inequality generator that gives lower bounds
on feasible availability and throughput pairs with a given capacity and
independent but not necessarily identical distributions of up-to-unit demands.
We show that availability and throughput cannot both be poor. These bounds are
analogous to tail inequalities on sums of independent random variables, but
hold throughout the support of the demand distribution. This analysis gives
analytically tractable bounds supporting the unit-demand characterization of
Chawla, Devanur, and Lykouris (2023) and generalizes to up-to-unit demands. Our
bounds also provide an approach towards improved multi-unit prophet
inequalities (Hajiaghayi, Kleinberg, and Sandholm, 2007). They have
applications to transaction fee mechanism design (for blockchains) where high
availability limits the probability of profitable user-miner coalitions (Chung
and Shi, 2023).
