Why applying the same test to several hypotheses reduces its rejection power?

Question

UPDATE: after more study on the subject, I noticed that I didn't have a good grasp on the difference between $p$-value and significance. In particular in the last portion of the question I use the term $p$-value instead of significance. I'll leave the question as is for future reference, just keep in mind that it is a bit imprecise :)

Reading "Kernel Methods for Pattern Analysis", by John Shawe-Taylor, I've got stuck into this sentence:

[...] if we applied the same test for $n$ hypotheses $P_1, \dots, P_n$, and found that for one of the hypotheses, say $P^*$, a significance of $p$ is measured, we can only assert the hypothesis with significance $np$. This is because the data could have misled us about any one of the hypotheses, so that even if none were true there is still a probability $p$ for each hypothesis that it could have appeared significant, giving in the worst case a probability $np$ that one of the hypotheses appears significant at level $p$.

This sentence doesn't make any sense to me, since each test is independent of the other $n-1$. Can you provide me with a clear example of the contrary? Can you provide me a mathematical proof, or at least an insight?

EDIT: Thanks for the link in the comment (for future reference: xkcd: Significant). Let me elaborate further.

Let's suppose I have a training algorithm $f(\alpha)$, that is, a function $f$ that returns the parameters of a classifier. $\alpha$ is a custom parameter that can be set by the experimenter. If I vary $\alpha$, let's say, between $0$ and $1$ with step $0.1$, I'll get $11$ different results for the classifier parameters. Let's suppose that only in one case this trained classifier (e.g., for $\alpha = 0.6$) is better than a "reference", with $p$-value $0.01$. I still have to say that the overall $p$-value for the null hypothesis is $11 \times 0.11 = 0.121$?

Answer 1

The p-value adjustment you describe is known as the Bonferroni correction.

Regarding your follow-up question about picking the best classifier: in that case you might also be concerned about overfitting to the evaluation set. There are a couple recent papers dealing with this problem that might interest you:

http://jmlr.org/proceedings/papers/v37/blum15.html http://www.sciencemag.org/content/349/6248/636.full

Answer 2

Look at this from a different perspective with just P1 and P2. lets say you're looking for p significance level, that is, the chance to regect P1 if P1 is true is less or equal to p.

lets assume that P1 and P2 are indepentent.

what is the chance to not reject P1 and P2 if both are true: (1-p)^2. so the chance to reject atleast one: 1-(1-p)^2 = 2*p - p^2 --> 2*p for small p. The same methodology applies for n>2. When we use instead of P, P/n than we will have the desired significance level of p that atleast one of the hypothesis will be rejected when all the null are trues.