Thread: Probabilities between two ordered sets of exponentially distributes samples

1. Probabilities between two ordered sets of exponentially distributes samples

Let <d1,d2,d3...dN> be an odered set of samples from an exponential
random variable with parameter lambda.
Let <l1,l2,l3,...,lM> the same.

Let Z = min<d1,d2,...,dN> --> Z is exp with parameter lambda*N
Let U = min<l1,l2,...,lM> --> U is exp with parameter lambda*M

My question is:
Since we can write that:
p(Z > U) = M/(N+M), which is in fact, p(d1 > l1)= p(Z > l1)

How can I compute the following probability:

p(Z > l2), p(Z > l3),...,p(Z > lN).

Is it possible?? Thanks a lot in advance!

Until now I am "approximating" this probability by assuming that:

p(Z > l2) = (M-1)/((M-1)+N) and succesively, but I know it is wrong....

2. Originally Posted by oscaralive
Let <d1,d2,d3...dN> be an odered set of samples from an exponential
random variable with parameter lambda.
Let <l1,l2,l3,...,lM> the same.

Let Z = min<d1,d2,...,dN> --> Z is exp with parameter lambda*N
Let U = min<l1,l2,...,lM> --> U is exp with parameter lambda*M

My question is:
Since we can write that:
p(Z > U) = M/(N+M), which is in fact, p(d1 > l1)= p(Z > l1)

How can I compute the following probability:

p(Z > l2), p(Z > l3),...,p(Z > lN).

Is it possible?? Thanks a lot in advance!

Until now I am "approximating" this probability by assuming that:

p(Z > l2) = (M-1)/((M-1)+N) and succesively, but I know it is wrong....
I don't know if there is a simple formula. Here is what I get.

Suppose we are starting from $(Y_1,\ldots,Y_M)$ as an (unordered) set of exponential random variables with parameter $\lambda$; if you order them, you get $(I_1,\ldots,I_M)$.

Notice what we want is $P(Z>I_k)=P(Z\mbox{ is greater than at least k values from }Y_1,\ldots,Y_n)$.

Let us cut according to the number $l$ of values below $Z$. Note that, by symmetry, the ${M\choose l}$ ways to choose which variables among $\{Y_1,\ldots,Y_M\}$ are smaller than $Z$ are equally likely. Therefore, we get:

$P(Z>I_k)=\sum_{l=k}^M {M\choose l}P(Z>Y_1,\ldots,Z>Y_l, Z $=\sum_{l=k}^M {M\choose l} \int_0^\infty (1-e^{-\lambda z})^l (e^{-\lambda z})^{M-l} \lambda N e^{-\lambda N z} dz$.

If $k=1$ you can recover $\frac{M}{M+N}$ using the binomial formula. In the general case, I guess there is not a significant simplification, but I may be wrong. Are you expecting a more satisfying answer?

3. my approach

First of all, thank you!
But, I think your solution is not appropiated for my problem since I need to model this proabilities such that they are easily computable.

recovering:
Let <d1,d2,d3...dN> be an odered set of samples from an exponential
random variable with parameter lambda.
Let <l1,l2,l3,...,lM> the same.

and

Let Z = min<d1,d2,...,dN> --> Z is exp with parameter lambda*N
Let U = min<l1,l2,...,lM> --> U is exp with parameter lambda*M

Then my approach is:

p(Z > U)=p(Z > l1) = M/(N+M)--ok

now p(Z > l2) = p(Z >(l2-l1) + U| Z> U), since Z is exponentially distributed I try to solve the following:

p(Z >(l2-l1))*p(Z > U) = p(Z >(l2-l1))*(M/(N+M))

and I also try to generalise it for all l's by doing:

p(Z > R*(l2-l1)) = p(Z/R + l1 > l2) where R = 1,2,3...

Let X = Z/R + l1, where Z/R is exp(lambda*N*R) and l1,l2 of param lambda.

I compute fx(x) = (lamda*N*R/N*R-1)*(exp(-lambda*x) - exp(-lambda*N*R*x)) by convolution of both pdf's

and then I compute the double integral for p(X > l2), and i found that:

p(Z > l1) = M/(N+M)

and

p(Z > l2) = 0.5*(K+2/K+1)*p(Z > l1)

p(Z > l3) = 0.5*(K*2 + 2/K*2 + 1)*p(Z > l1)

generalising:

p(Z > lR) = 0.5*(K*R+2/K*R+1)*p(Z > l1)

However, I'm not sure at all this is right, may be i'm wrong in the integrals.... what do you think?

4. I have just computed that the random variables $I_1$, $I_2-I_1$,..., $I_M-I_{M-1}$ are independent, and $I_k-I_{k-1}$ is an exponential r.v. of parameter $\lambda(M-(k-1))$. In particular, $I_k-I_{k-1}$ is independent of $(I_1,\ldots,I_{k-1})$. I didn't know that (did you?), and that helps much.

We have $P(Z>I_k)=P(Z>I_{k-1}+(I_k-I_{k-1}))=P(Z>I_{k-1})P(Z>I_k-I_{k-1})$ (using the above independence, and the memoryless property of $Z$), hence $P(Z>I_k)=P(Z>I_{k-1})\frac{M-(k-1)}{M-(k-1)+N}$.

Inductively, we deduce $P(Z>I_k)=\frac{M(M-1)\cdots(M-k+1)}{(M+N)(M+N-1)\cdots(M+N-k+1)}$ $= \frac{{M\choose k}}{{M+N\choose k}}$.

I didn't really understand what you wrote, but it seemed to relate to this solution. It is somewhat simpler, indeed...

5. Thank you again, Laurent.

Finally I decided to proceed with the following approach:

p(Z > k(l2-l1)) = p(Z/k > l2-l1), then Z becomes exponential of param lambda*N*k; where k means how many times should be Z larger than the interval between two samples of the ordered set.

I have computed the joint density of W = l2-l1, and then the probability p(Z/k > W) and I get: 1/2 *(1/NK+1). Note that in computing the pdf of W we have the constraint that l2>l1.

Thus, for computing the probability that Z is higher than the third element in the ordered set we have:

M/(N+M) * 1/2 *(1/N*2+1).

This study is being used to model analytically a single output port in one router under a novel architecture. I have also tried your last formula with the combinatorial; however the results are matched with my last approach in all cases and after several comparisons against rigorous simulations.

Maybe in your approach you are omitting something...don't know, but anyway thank you very much!!

6. After reading your last post I tried checking my formula with simulations myself (Scilab code below), and it happens to match pretty well... So maybe we're not dealing with exactly the same problem. Here is the problem that I answered:

Let $Y_1,\ldots,Y_M$ be independent exponential variables of parameter $\lambda$, and $Z$ be an exponential variable of parameter $\lambda N$ independent of the previous ones. We denote by $(I_1,\ldots,I_M)$ the ordered sample $(Y_1,\ldots,Y_M)$, i.e. $I_1 and $\{I_1,\ldots,I_M\}=\{Y_1,\ldots,Y_M\}$. Then, for $k=1,\ldots,M$, $P(Z>I_k)=\frac{M(M-1)\cdots(M-k+1)}{(M+N)(M+N-1)\cdots(M+N-k+1)}$.

Code:
M=20;
N=8;
lambda=10;

// Simulation

S=zeros(M,1); // S(k) will contain the empirical P(Z>I_k)

nb=50000; // nb of simulations (probability is an average over nb simulations)

for i=1:nb,
Z=-log(rand())/(N*lambda);
Y=-log(rand(M,1))/lambda;

Y=gsort(Y,'g','i'); // ordering of the sample
I=find(Z>Y); // vector I contains the indices i such that Z>Y(i)
for j=I,
S(j)=S(j)+1;
end;
end;

S=S/nb;
clf;plot(1:M,S,'bx'); // Simulated plot in blue

// Theoretical computation

T=zeros(M,1); // T(k) will contain theoretical P(Z>I_k)
u=M; v=N+M;
T(1)=u/v;
for i=2:M,
u=u-1;
v=v-1;
T(i)=T(i-1)*u/v;
end;
plot(1:M,T,'rx');  // Theoretical plot in red