Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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