What is the probability that every variable of combination of random variables is greater than a specific value?

Question

Suppose there are $N$ positive random variables. Each variable follows an exponential distribution with parameter $\lambda_i$. Now, we choose $n$ variables among the $N$ variables. What is the probability that, among the $n$ variables chosen, there are at least $k$ ($n \geq k$) variables that has a value greater than a certain constant $C$?

For example, we have $N=5$ variables $X_1, \ldots, X_5$, each follows an exponential distribution with parameter $\lambda_1, \ldots, \lambda_5$. Now, I want that among the $n$ variables I choose, there will be at least $k=2$ variables that has $X_i>C$. Let $P_i=P(X_i>C)$. Note that since $\lambda_i$ are differrent, $P_i$ are also different for each $i$. If I choose the $n=2$ variables, then the probability that both $X_i>C$ is $P=P_1P_2$. If I choose the $n=3$ variables then $P=P_1P_2+P_1P_3+P_2P_3+P_1P_2P_3$.

This will be much longer as $n$ increases. Thus, I want to ask if there is any approach to calculate this probability more efficiently? Is there any feasible/elegant bounds? Thank you.

Answer 1

The number of variables $K$ among the $N$ variables that surpass the critical value $C$ follows a Poisson binomial distribution.

For a given number $K$ you can compute the probability to select at least $k$ from them when you draw $n$ from the $N$. The number $k$ follows a hypergeometric distribution (conditional on $K$).

If $n$ is not too large you can compute the combination of these two.

• For each $K$ compute the probability that you get it from the Poisson binomial distribution (which might be approximated with a Gaussian distribution)
• For each $K$ compute the probability to get $k$ that are above your threshold $C$.
• Multiply the previous two figures for each $K$ and sum them to get the total probability.

---

Below is an example to compute it with R-code.

The graph shows the probability for the amount of $k$ variables that are above $C$ among the $n$ selected variables. (So it is a probability mass function, you can convert it to 'at least ... variables' by summing the probabilities of the function).

Interesting is the little approximation added at the end of the code. It is based on a Gaussian distribution with mean $\frac{n}{N} \sum p_i$ and the variance is the variance of the Poisson binomial distribution and the variance of the hypergeometric distribution added to each other (where we use the variance of the hypergeometric at the mean value of $K$).

##### Begin Problem settings ##########

N = 200   # number of total variables
n= 100    # number of picked variables
Cv = 1/100  # critical level to be passed

lambda = c(1:200) ### some array of values for lamba_i; 
                 ### this can be changed depending on the problem

##### Emd Problem settings ##############


### probabilites for each x_i ~ exp(lambda_i) to be above C
p = 1-pexp(Cv,lambda)

### computing Poisson Binomial distribution for each K
K = 0:N  
pK = PoissonBinomial::dgpbinom(K, p, 
                               val_p = rep(1,N),
                               val_q = rep(0,N))

### computing alternative approximation to Poisson Binomial distribution for each K
### This can be done for larger $n$ when the Poisson Binomial is too slow
mu = sum(p)
vr = sum(p*(1-p))
pK_alt = dnorm(K, mu, sqrt(vr))

### this plot shows whether the approximation is reasonable
plot(pK)
lines(pK_alt)

### computing Geometric distribution for each K
x = 0:N
s = sapply(K, function(y) dhyper(x, y, N-y, n)) ### this returns a matrix with each column relating to a K

### combining the two

probs = s %*% pK ### multiplying and summing the two probabilites using a matrix equation

### the resulting distribution for k
plot(K,probs, xlab = "k", ylab = "probability")

### using an estimation
xs = seq(0,N,0.1)
vr2 = (n/N) * mu * ((N-mu)/(N)) * ((N-n)/(N-1))  ### variance for hypergeometric at the average K
est = dnorm(xs, mu*n/N, sqrt(vr*(n/N)^2+vr2))    ### normal distribution estimate 
                                                 ### with variance of hypergeometric and Poisson binomial combined
lines(xs,est)