2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "Now, we choose n variables among the N variables" Is this done randomly. If so, in what way? $\endgroup$ Sep 23, 2021 at 0:21

1 Answer 1

1
$\begingroup$

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$).

computation with approximation

##### 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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.