Bounding a Probability Measure Over a Polymatroid with an Application to Transportation Problems

For M = {1, …, m} and a supermodular set function f: 2^M → ℛ, define the polymatroid P(M, f) = {x: ∑_j∈Ax_j ≥ f(A), A ⊆ M; x ∈ ℛ^m}. We develop a bound for the probability P{X ∈ P(M, f)}, where X is a random m-vector. In particular we show that if X, X₁, …, X_m, are independent and identically distributed nonnegative random variables with new better than used (NBU) distribution function, then P{X ∈ P(M, f)} ≥ P{X ≥ f(M̂)}, where M̂ = arg max {f(A): A ⊆ M}. We apply this result to transportation problems with random supply and/or demand. Suppose we have a set K = {1, …, k} of k supply nodes with a random supply S_i, i ∈ K and a set N = {1, …, n} of n demand nodes with a random demand D_j, j ∈ N. Let β be the probability that the random demand can be met by the random supply. If the demand and supply are mutually independent, D₁, …, D_n, are independent, and S₁, …, S_k, are independent and have NBU distribution function, then β ≤ ∏_j=1ⁿP{Z_j ≥ D_j}, where Z_j = ∑_i∈KS_ir_ij, j∈N and r_ij takes the value one if node i can supply the demand node j and zero otherwise (i ∈ K and j ∈ N).