A Dynamic Program for Computing the Joint Cumulative Distribution Function of Order Statistics
Rigel Galgana, Cengke Shi, Amy Greenwald, Takehiro Oyakawa · Society for Industrial and Applied Mathematics eBooks · 2021
We consider the problem of computing the joint cumulative distribution function of d ∊ ℕ select order statistics of n ≥ d independent random variables representing m ≤ n distinct populations. We present an efficient dynamic programming algorithm for this problem that is polynomial in both d and n, though exponential in m, hence most practical when m ≪ n. Previously, the fastest known algorithms were exponential in d, and either exponential in m or exponential in n, as well. Like others before us, we reduce the problem to a combinatorial one of tossing balls into bins, and then we calculate the probability of satisfying various bin conditions: i.e., of sufficiently many balls landing in bins. The key observation that leads to such a significant speedup is that one need not keep track of the exact configurations of balls in bins to determine if the requisite bin conditions are satisfied. Instead, the relevant information can be compressed by merging configurations that satisfy the same bin conditions.