# Deciding whether or not an exponentially distributed random variable exists in a set via the use of a “black box” function

I have some set of known size but with unknown elements, $(x_1, ..., x_N) \in X$, where the elements of $X$ are exponentially distributed random variables with unknown rate parameters, $(\lambda_1, ..., \lambda_N) \in R$. I also have a "black box" function $f$ that samples an element from $X$ with uniform probability, and then returns a randomly sampled value from the chosen element's exponential distribution (corresponding, perhaps, to the time until the first instance of an event governed by the chosen variable).

I'm looking to use $f$ to discern whether or not an exponentially distributed random variable, $x_q$, with known rate parameter, $\lambda_q$, exists in the set $X$. I also know that $\lambda_q$ is smaller then all other rate parameters in the set $X$ by at least a multiplicative factor $w$. Said another way, $\lambda_q \leq Min[(R-\lambda_q)]*w$, where $w < 1$.

Provided $w$, how many times must I use $f$ to sample from $X$ to decide whether $x_q \in X$ with some threshold confidence?

Note - If this problem is too open ended as things stand, please feel free to suggest additional restrictions or clarifications!

Note 2 - We can specify that $N \leq 100$, where $N$ is a positive integer, and that $w \leq \frac{1}{2}$, though we cannot say that $w << 1$.

-
Surely you have to know something about $N$ also in order for this to have any hope? Maybe you want a bound in terms of $N$? –  Anthony Quas Nov 17 '12 at 21:16
@Anthony Quas Fair point. I am looking for a bound in terms of $N$, and I have changed the question to specify that we know $N$. –  user28187 Nov 18 '12 at 7:20
What are typical values of $N$ and $w$? And what is $R$ in $R-\lambda_q$? –  fedja Nov 19 '12 at 1:51
@fedja I have added some specifications for $N$ and $w$ in Note 2. I can tighten them as needed. $R - \lambda_q$ is meant to be the set $R$ without the element $\lambda_q$ (perhaps this notation is incorrect?) –  user28187 Nov 19 '12 at 1:56
@fedja Ah, $R$ is defined earlier as the set of rate parameters associated with the exponentially distributed random variables in $X$. –  user28187 Nov 19 '12 at 2:00

OK, here is what I have. I'll skip some derivations (I'll provide them later if you are interested) and just describe the conclusions. The final tables apply if you have noiseless data. Any noticeable amount of noise will cost you quite a bit here.

The problem of how to distinguish between two fixed densities $p(x)$ and $q(x)$ is classical. Suppose that we want to bound the combined probability of error by some small $\theta>0$. This means that if we are allowed to take $n$ samples, we have to find some set $E\subset\mathbb R^n$ such that $\int_E P+\int_{E^c}Q\le\theta$ where $P(x_1,\dots,x_n)=p(x_1)\dots p(x_n)$ and similarly for $Q$. Here $E$ is the set where we declare $q$ to be actual density. Note that in no way can this sum be better than $\int\min(P,Q)$ and we can achieve that by the standard maximal likelihood decision: we declare the density $Q$ if $P(X_1,\dots,X_n)<Q(X_1,\dots,X_n)$ and $P$ otherwise. We also can get a fairly clear idea of the necessary sampling size. In fact, we can tell it almost up to a factor of $2$. Note that $\min(P,Q)\le\sqrt{PQ}$, so $$\int\min(P,Q)\le \left(\int \sqrt{pq}\right)^n$$. On the other hand, $$\left(\int \sqrt{pq}\right)^{2n}=\left(\int \sqrt{PQ}\right)^{2}\le \left(\int\min(P,Q)\right)\left(\int\max(P,Q)\right)\le 2\int\min(P,Q)$$ Thus, if $\int\sqrt{pq}=e^{-H}$, then to reach the level $\theta$ of combined error, we need at least $\frac 12 H^{-1}\log\frac 1{2\theta}$ and $H^{-1}\log\frac 1\theta$ samples will suffice.

The problem with your case is that we test not two densities but two families of densities against each other. However, if my computations are correct, we are lucky and the likelihood test that distinguishes the worst pair is actually universal enough to achieve the level of confidence given by the above $\sqrt{pq}$ estimate. So assuming that $\lambda_q=w$ (so every other $\lambda$ is $\ge 1$), we can define $p_L(x)=\frac{N-1}N Le^{-Lx}+\frac 1Nwe^{-wx}$, $q(x)=e^{-x}$ where $L=L(N,w)$ is determined from the maximization problem $\int\sqrt{p_Lq}\to\max$ (which in practice is better to pose as $H=\frac 12\int(\sqrt{p_L}-\sqrt q)^2\to\min$), then the corresponding maximal likelihood text works fine and gives a guaranteed bound $\theta$ for each one-sided error whenever the $\sqrt{pq}$ estimate yields the combined error of $\theta$.

I ran a small program to see what sampling sizes it gives for reasonable $w$ and $N$. The table for the sacramental $\theta=0.05$ is below. The lines are $N,L,n$. \phantom{+} is the artifact of the automatic LaTeX style formatting that I was too lazy to disable. As you can see, with your $10^5$ samples you are just on the edge of "theoretically feasible" for $w=0.5,N=100$ but if you can drop either number, everything gets fairly nice (if no noise is present, of course).

I suggest you run a few simulations and see whether it works for you (the "general theory" should be OK, but I could make some stupid mistakes somewhere). Normally, you are getting something like $$n=8N^{\frac 1{1-w}}\log\frac {1}{\theta}$$ as a rule of thumb for choosing the sample size. This is all "the best performance in the worst case" approach. If you actually have more information than you put in the post, that may help push the numbers down a bit :).

Feel free to ask questions but do not expect a quick answer: life is crazy at this end...

w=0.5
100  \phantom{+} 1.009397  186378
90  \phantom{+} 1.010406  155814
80  \phantom{+} 1.011662  127611
70  \phantom{+} 1.013269  101830
60  \phantom{+} 1.015398   78546
50  \phantom{+} 1.018358   57847
40  \phantom{+} 1.022762   39849
30  \phantom{+} 1.030037   24705
20  \phantom{+} 1.044454   12637
w=0.45
100  \phantom{+} 1.010954   89813
90  \phantom{+} 1.012108   75790
80  \phantom{+} 1.013540   62719
70  \phantom{+} 1.015367   50637
60  \phantom{+} 1.017779   39584
50  \phantom{+} 1.021120   29613
40  \phantom{+} 1.026065   20790
30  \phantom{+} 1.034179   13204
20  \phantom{+} 1.050103    6985
w=0.4
100  \phantom{+} 1.012550   45454
90  \phantom{+} 1.013842   38711
80  \phantom{+} 1.015442   32363
70  \phantom{+} 1.017476   26429
60  \phantom{+} 1.020152   20932
50  \phantom{+} 1.023843   15900
40  \phantom{+} 1.029277   11371
30  \phantom{+} 1.038131    7392
20  \phantom{+} 1.055337    4039
w=0.35
100  \phantom{+} 1.014103   24058
90  \phantom{+} 1.015519   20670
80  \phantom{+} 1.017266   17449
70  \phantom{+} 1.019481   14406
60  \phantom{+} 1.022385   11553
50  \phantom{+} 1.026372    8904
40  \phantom{+} 1.032211    6480
30  \phantom{+} 1.041659    4307
20  \phantom{+} 1.059842    2427
w=0.3
100  \phantom{+} 1.015495   13254
90  \phantom{+} 1.017009   11481
80  \phantom{+} 1.018872    9781
70  \phantom{+} 1.021226    8158
60  \phantom{+} 1.024301    6619
50  \phantom{+} 1.028504    5172
40  \phantom{+} 1.034628    3826
30  \phantom{+} 1.044470    2597
20  \phantom{+} 1.063235    1506
w=0.25
100  \phantom{+} 1.016562    7561
90  \phantom{+} 1.018136    6600
80  \phantom{+} 1.020067    5670
70  \phantom{+} 1.022499    4775
60  \phantom{+} 1.025664    3917
50  \phantom{+} 1.029973    3099
40  \phantom{+} 1.036219    2328
30  \phantom{+} 1.046192    1611
20  \phantom{+} 1.065043     960
w=0.2
100  \phantom{+} 1.017079    4443
90  \phantom{+} 1.018656    3906
80  \phantom{+} 1.020587    3382
70  \phantom{+} 1.023011    2873
60  \phantom{+} 1.026156    2380
50  \phantom{+} 1.030419    1906
40  \phantom{+} 1.036571    1453
30  \phantom{+} 1.046335    1024
20  \phantom{+} 1.064644     625
w=0.15
100  \phantom{+} 1.016716    2675
90  \phantom{+} 1.018218    2367
80  \phantom{+} 1.020052    2064
70  \phantom{+} 1.022349    1768
60  \phantom{+} 1.025319    1478
50  \phantom{+} 1.029333    1197
40  \phantom{+} 1.035099     924
30  \phantom{+} 1.044204     662
20  \phantom{+} 1.061157     414
w=0.1
100  \phantom{+} 1.014952    1647
90  \phantom{+} 1.016263    1466
80  \phantom{+} 1.017861    1287
70  \phantom{+} 1.019857    1111
60  \phantom{+} 1.022433     937
50  \phantom{+} 1.025903     766
40  \phantom{+} 1.030871     599
30  \phantom{+} 1.038684     436
20  \phantom{+} 1.053150     278
w=0.05
100  \phantom{+} 1.010786    1099
90  \phantom{+} 1.011716     983
80  \phantom{+} 1.012849     868
70  \phantom{+} 1.014262     754
60  \phantom{+} 1.016083     641
50  \phantom{+} 1.018533     528
40  \phantom{+} 1.022034     417
30  \phantom{+} 1.027529     308
20  \phantom{+} 1.037677     200

-