Bapat–Beg theorem

In probability theory, the Bapat–Beg theorem R. B. Bapat and M. I. Beg. Order statistics for nonidentically distributed variables and permanents. "Sankhyā Ser. A", 51(1):79–93, 1989. [http://www.ams.org/mathscinet-getitem?mr=1065561 MR1065561] ] gives the joint cumulative distribution function of order statistics of independent but not necessarily identically distributed random variables in terms of the cumulative distribution functions of the random variables. Simpler proof of this can be found in Sayaji Hande. A note on order statistics for nonidentically distributed variables "Sankhyā Ser. A", 56(2):365–368, 1994. [http://www.ams.org/mathscinet-getitem?mr=1664921 MR1664921] ]

This result describes the order statistics when each element of the sample is obtained from a possibly different population with a different probability distribution. Ordinarily, all elements of the sample are obtained from the same population and thus have the same probability distribution.

The theorem

Let $extstyle\; X\_\{i\}$, $extstyle\; i=1,ldots,m$ be independent real valued random variables with cumulative distribution functions $extstyle\; F\_\{i\}left(\; x\; ight)$. Denote the order statistics by $extstyle\; Y\_\{1\},Y\_\{2\},ldots,Y\_\{m\}$, with $extstyle\; Y\_\{1\}leq\; Y\_\{2\}leqcdotsleq\; Y\_\{m\}$. Further let $extstyle\; y\_\{0\}=-infty,$ $extstyle\; y\_\{k+1\}=+infty$, and

:$i\_\{0\}=0,quad\; i\_\{k+1\}=m,quad\; F\_\{i\}left(\; y\_\{0\}\; ight)\; =0,quad\; F\_\{i\}left(\; y\_\{k+1\}\; ight)\; =1$

for all $extstyle\; i.$ For and $extstyle\; y\_\{1\}leq\; y\_\{2\}leqcdotsleq\; y\_\{k\}$, the joint cumulative distribution function of the subset $extstyle\; Y\_\{n\_\{1,ldots\; Y\_\{n\_\{k$ of the order statistics satisfies

:

where

:

is the permanent of a block matrix with the subscript $extstyle\; left(\; i\_\{j\}-i\_\{j-1\}\; ight)\; imes1$ denoting the dimension of a block obtained by repeating the same entry, and the block row index $extstyle\; j$ and block column index $extstyle\; i$.

The independent identically distributed case

In the case when the variables $extstyle\; X\_\{1\}$, $extstyle\; X\_\{2\},ldots,X\_\{m\}$ are independent and identically distributed with cumulative probability distribution function $extstyle\; F\_\{i\}=F$ for all $extstyle\; i$, the Bapat–Beg theorem reduces to Deborah H. Glueck, Anis Karimpour-Fard, Jan Mandel, Larry Hunter, Keith E. Muller. "Fast computation by block permanents of cumulative distribution functions of order statistics from several populations," [http://arxiv.org/abs/0705.3851 arXiv:0705.3851] , 2007]

:

where again

:$i\_\{0\}=0,quad\; i\_\{k+1\}=m,quad\; Fleft(\; y\_\{0\}\; ight)\; =0,quad\; Fleft(\; y\_\{k+1\}\; ight)\; =1.$

Remarks

* No assumption of continuity of the cumulative distribution functions is needed.

* The theorem is formulated for the joint cumulative probability distribution function in terms of a subset of the order statistics and ordered arguments. If the inequalities $extstyle\; y\_\{1\}leq\; y\_\{2\}leqcdotsleq\; y\_\{k\}$ are not imposed, some of the inequalities $extstyle\; Y\_\{n\_\{jleq\; y\_\{j\}$ may be redundant (because always $extstyle\; Y\_\{1\}leq\; Y\_\{2\}leqcdotsleq\; Y\_\{m\})$ and the argument list needs to be first reduced by dropping all $extstyle\; y\_\{j\}$ such that $extstyle\; y\_\{i\}>y\_\{j\}$ for some $extstyle\; i$.

Complexity

The Bapat–Beg formula involves exponentially many permanents, and the complexity of the computation of the permanent itself is at least exponential. Thus, in the general case, the formula is not practical. However, when the random variables have only two possible distributions, the complexity can be reduced to $O(m^\{2k\})$ Deborah H. Glueck, Anis Karimpour-Fard, Jan Mandel, Larry Hunter, Keith E. Muller. "Fast computation by block permanents of cumulative distribution functions of order statistics from several populations," [http://arxiv.org/abs/0705.3851 arXiv:0705.3851] , 2007] . Thus, in the case of two populations, the complexity is polynomial in "m" for any fixed number of statistics "k".

ee also

*For standard results for the distribution of order statistics for independent and identically-distributed random variables see, for example, N. Balakrishnan and C. R. Rao. Order statistics: an introduction. In "Order statistics: theory & methods", volume 16 of "Handbook of Statist.", pages 3–24. North-Holland, Amsterdam, 1998.

]
*permanent
*independent and identically-distributed random variables

References