Enumeration of k-Exceedance Lattice Paths with an Application to Comparing Chains of Order Statistics

Abstract

We enumerate the number of monotonic lattice paths starting at $(0,0)$ and terminating at $(m,n)$ in which $l$ of the first $k$ steps lie below the line $y=x(0\le k\le m\le n)$. These closed formulas consist of terms which are a product Catalan numbers, ballot numbers and binomial coefficients. We then apply the combinatorial formulas to failure analysis by deriving a probability distribution that compares the performance of a $k$-out-of-$m$ system to a $k$-out-of-$n$ system of continuous, independent, and identically distributed random variables. Lastly, we provide asymptotics in a few special cases of $k,m,n$ and leave others as conjecture.

10 pages, 2 figures