[math-fun] The chance that N statistical tests fail simultaneously
The chance that N statistical tests fail simultaneously =========Warren D. Smith====Nov 2014======== Suppose you perform N statistical tests. One fails with p-level a. Another fails with p-level b. ... Another fails with p-level z. What is the p-level for this combined event? Call the answer F_N(a,b,c,...,z). We may assume wlog that 0<a<b<c<...<z<1. F_1(a)=a, of course. It is NOT the case that F_2(a,b)=ab. Actually, F_2(a,b) = 2ab-aa = a(2b-a). Because that is the chance that if x and y are independent uniform01 randoms, then either x<a and y<b, or x<b and y<a. What about F_3(a,b,c), F_4(a,b,c,d), and so on? It is possible to determine these by working out certain N-dimensional volumes via something like an inclusion-exclusion argument. But it gets more and more painful. As an easy upper bound, F_N(a,b,c,...,z) < N! abc...z. But this bound can be pretty weak. For example it is easy to exactly work out the special case F_N(x,x,x,...,x) = x^N. I would like the exact answer in general. The following recurrence F_{N+1}(a,b,c,...z) = (N+1) * integral(from x=0..a) F_N( (b-x)/(1-x), (c-x)/(1-x), ..., (z-x)/(1-x) ) * (1-x)^N dx seems an easier way to get the answer. From this I compute: F_3(a,b,c) = [3b(2c-b)+a(a-3c)]a F_4(a,b,c,d) = [4(b-3d)b^2+6c(4bd+(a-2b)c-2da)+(4d-a)a^2]a F_5(a,b,c,d,e) = [20bc^3-5b^4+30b^2d^2-60bcd^2+20b^3e-60bc^2e-60b^2de+120bcde-10c^3a+30cd^2a+30c^2ea-60cdea-10d^2a^2+20dea^2-5ea^3+a^4]a. These keep getting messier. But there might be some simple general form for the answer (e.g. if we go back to the original inclusion-exclusion idea and do not get confused), and/or there might be some algorithm for computing answer whose runtime grows only polynomially with N. Can you find them? At present, the best algorithm I thought of runs in time exponential in N, roughly like 4^N in fact.
On Mon, Nov 10, 2014 at 11:38 AM, Warren D Smith <warren.wds@gmail.com> wrote:
The chance that N statistical tests fail simultaneously =========Warren D. Smith====Nov 2014========
Suppose you perform N statistical tests. One fails with p-level a. Another fails with p-level b.
What is the p-level for this combined event?
Presumably the answer should not depend on what event we call "one event" and what event we call "another event". So the answer should be symmetric in the two arguments, that is, F_2(a, b) = F_(b,a)
It is NOT the case that F_2(a,b)=ab. Actually, F_2(a,b) = 2ab-aa = a(2b-a).
This is not symmetric. How do we tell whether the correct answer is 2ab - aa or 2ab - bb? Which event should we call "one event" and which should we call "another event" to obtain the correct answer? Andy -- Andy.Latto@pobox.com
On 11/10/2014 8:38 AM, Warren D Smith wrote:
The chance that N statistical tests fail simultaneously =========Warren D. Smith====Nov 2014========
Suppose you perform N statistical tests. One fails with p-level a. Another fails with p-level b. ... Another fails with p-level z.
What is the p-level for this combined event? Call the answer F_N(a,b,c,...,z). We may assume wlog that 0<a<b<c<...<z<1.
F_1(a)=a, of course.
It is NOT the case that F_2(a,b)=ab. Actually, F_2(a,b) = 2ab-aa = a(2b-a).
Because that is the chance that if x and y are independent uniform01 randoms, then either x<a and y<b, or x<b and y<a.
Are you assuming the statistical tests are independent? That's not usually a good assumption, particularly if the tests are trying to measure the same or similar things. Brent
What about F_3(a,b,c), F_4(a,b,c,d), and so on? It is possible to determine these by working out certain N-dimensional volumes via something like an inclusion-exclusion argument. But it gets more and more painful. As an easy upper bound,
F_N(a,b,c,...,z) < N! abc...z.
But this bound can be pretty weak. For example it is easy to exactly work out the special case F_N(x,x,x,...,x) = x^N.
I would like the exact answer in general. The following recurrence
F_{N+1}(a,b,c,...z) = (N+1) * integral(from x=0..a) F_N( (b-x)/(1-x), (c-x)/(1-x), ..., (z-x)/(1-x) ) * (1-x)^N dx
seems an easier way to get the answer. From this I compute:
F_3(a,b,c) = [3b(2c-b)+a(a-3c)]a
F_4(a,b,c,d) = [4(b-3d)b^2+6c(4bd+(a-2b)c-2da)+(4d-a)a^2]a
F_5(a,b,c,d,e) = [20bc^3-5b^4+30b^2d^2-60bcd^2+20b^3e-60bc^2e-60b^2de+120bcde-10c^3a+30cd^2a+30c^2ea-60cdea-10d^2a^2+20dea^2-5ea^3+a^4]a.
These keep getting messier. But there might be some simple general form for the answer (e.g. if we go back to the original inclusion-exclusion idea and do not get confused), and/or there might be some algorithm for computing answer whose runtime grows only polynomially with N. Can you find them?
At present, the best algorithm I thought of runs in time exponential in N, roughly like 4^N in fact.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--to answer Meeker, Yes, I assume all the N tests independent. --to answer Andy Latto, F_N(a,b,c,...) is NOT symmetric in its arguments because as I said we assume 0<a<b<c<...<z<1, or anyhow I made that assumption before writing the formulas. However, without that assumption, then it would be symmetric, in the sense that the correct formula would be got by 1. sort the N arguments into increasing order 2. apply my formula. This 2-step process of course produces a result which is a symmetric function. It is a piecewise polynomial function, and it is continuous, but the pieces are not symmetric polynomials. --to eyeball my F5 formula F_5(a,b,c,d,e) = [20bc^3-5b^4+30b^2d^2-60bcd^2+20b^3e-60bc^2e-60b^2de+120bcde-10c^3a+30cd^2a+30c^2ea-60cdea-10d^2a^2+20dea^2-5ea^3+a^4]a. one does observe interesting things such as all coefficients divide 120... I think one could prove that in the FN formula, all coefficients divide N!, the coefficient of a^N is +1, and the coefficient of abcd...z is +N!. Which is a long way short of complete understanding, but it is something.
As Brent said, statistical tests are usually not independent, and properly calculating the p-level of a combined set of tests is complicated. That being said, if test i has a probability p_i of failing, and the tests are independent, isn't the probability that they all fail equal to the product of the p_i ? and the probability that at least one of them fails is 1-\prod (1-p_i) ? And somewhat on-topic, an amusing demonstration of non-independent tests: https://macartan.shinyapps.io/fish/ On 10 November 2014 17:38, Warren D Smith <warren.wds@gmail.com> wrote:
The chance that N statistical tests fail simultaneously =========Warren D. Smith====Nov 2014========
Suppose you perform N statistical tests. One fails with p-level a. Another fails with p-level b. ... Another fails with p-level z.
What is the p-level for this combined event? Call the answer F_N(a,b,c,...,z). We may assume wlog that 0<a<b<c<...<z<1.
F_1(a)=a, of course.
It is NOT the case that F_2(a,b)=ab. Actually, F_2(a,b) = 2ab-aa = a(2b-a).
Because that is the chance that if x and y are independent uniform01 randoms, then either x<a and y<b, or x<b and y<a.
What about F_3(a,b,c), F_4(a,b,c,d), and so on? It is possible to determine these by working out certain N-dimensional volumes via something like an inclusion-exclusion argument. But it gets more and more painful. As an easy upper bound,
F_N(a,b,c,...,z) < N! abc...z.
But this bound can be pretty weak. For example it is easy to exactly work out the special case F_N(x,x,x,...,x) = x^N.
I would like the exact answer in general. The following recurrence
F_{N+1}(a,b,c,...z) = (N+1) * integral(from x=0..a) F_N( (b-x)/(1-x), (c-x)/(1-x), ..., (z-x)/(1-x) ) * (1-x)^N dx
seems an easier way to get the answer. From this I compute:
F_3(a,b,c) = [3b(2c-b)+a(a-3c)]a
F_4(a,b,c,d) = [4(b-3d)b^2+6c(4bd+(a-2b)c-2da)+(4d-a)a^2]a
F_5(a,b,c,d,e) =
[20bc^3-5b^4+30b^2d^2-60bcd^2+20b^3e-60bc^2e-60b^2de+120bcde-10c^3a+30cd^2a+30c^2ea-60cdea-10d^2a^2+20dea^2-5ea^3+a^4]a.
These keep getting messier. But there might be some simple general form for the answer (e.g. if we go back to the original inclusion-exclusion idea and do not get confused), and/or there might be some algorithm for computing answer whose runtime grows only polynomially with N. Can you find them?
At present, the best algorithm I thought of runs in time exponential in N, roughly like 4^N in fact.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It should be mentioned that p-levels are not really probabilities. --Dan On Nov 11, 2014, at 6:48 AM, Seb Perez-D <sbprzd+mathfun@gmail.com> wrote:
As Brent said, statistical tests are usually not independent, and properly calculating the p-level of a combined set of tests is complicated.
That being said, if test i has a probability p_i of failing, and the tests are independent, isn't the probability that they all fail equal to the product of the p_i ? and the probability that at least one of them fails is 1-\prod (1-p_i) ?
And somewhat on-topic, an amusing demonstration of non-independent tests: https://macartan.shinyapps.io/fish/
participants (5)
-
Andy Latto -
Dan Asimov -
meekerdb -
Seb Perez-D -
Warren D Smith