most recent 30 from http://mathoverflow.net 2013-05-22T05:31:11Z http://mathoverflow.net/feeds/question/112703 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112703/deciding-whether-or-not-an-exponentially-distributed-random-variable-exists-in-a unknown (yahoo) 2012-11-17T18:47:37Z 2012-12-19T03:22:00Z

<p>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). </p> <p>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 &lt; 1$. </p> <p>Provided $w$, how many times must I use $f$ to sample from $X$ to decide whether $x_q \in X$ with some threshold confidence? </p> <p>Note - If this problem is too open ended as things stand, please feel free to suggest additional restrictions or clarifications!</p> <p>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 &lt;&lt; 1$.</p>

http://mathoverflow.net/questions/112703/deciding-whether-or-not-an-exponentially-distributed-random-variable-exists-in-a/114010#114010 fedja 2012-11-21T01:41:55Z 2012-11-21T01:41:55Z

<p>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.</p> <p>The problem of how to distinguish between <em>two fixed</em> 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 <code>$P(X_1,\dots,X_n)&lt;Q(X_1,\dots,X_n)$</code> 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. </p> <p>The problem with your case is that we test not two densities but two <em>families</em> 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$.</p> <p>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 <em>no noise is present</em>, of course).</p> <p>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 :).</p> <p>Feel free to ask questions but do not expect a quick answer: life is crazy at this end...</p> <pre> 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 </pre>