We wish to test null hypotheses indexed by the set . The hypotheses indexed by are truly null with and the remaining hypotheses are non-null. A test in this setting looks at the data and decides to *accept* or *reject* each . While devising such a test, one obviously wants to guard against rejecting too many true null hypotheses. A classical way of ensuring this is to allow only those tests whose Family Wise Error Rate (FWER) is controlled at a predetermined small level. The FWER is defined as

It is very easy to design a test whose FWER is controlled by a predetermined level : reject or accept each hypothesis according to a test whose type I error is atmost . By the union bound, one then has

The above procedure is sometimes called the Bonferroni method. In modern theory of hypothesis testing, control of the FWER is considered too stringent mainly because it leads to tests that fail to reject many non-null hypotheses as well. The modern method is to insist on control of FDR (False Discovery Rate) as opposed to FWER. The FDR of a test is defined as

where

and . The quantity is often called the FDP (False Discovery Proportion). FDR is therefore the expectation of FDP.

How does one design a test whose FDR is controlled at a predetermined level (e.g., ) and which rejects more often that the Bonferroni procedure? This was answered by Benjamini and Hochberg in a famous paper in 1995. Their procedure is described below. For each hypothesis , obtain a -value . For , the -value has the uniform distribution on . For , the -value has some other distribution probably more concentrated near 0. Let the ordered -values be . The BH procedure is the following:

where

In the event that for all , we take . The BH procedure is probably easier to understand via the following sequential description. Start with and keep accepting the hypothesis corresponding to as long as . As soon as , stop and reject all the hypotheses corresponding to for .

It should be clear that the BH procedure rejects hypotheses much more liberally compared to the Bonferroni method (which rejects when ). Indeed any hypothesis rejected by the Bonferroni method will also be rejected by the BH procedure. The famous Benjamini-Hochberg theorem states that the FDR of the BH procedure is exactly equal to under the assumption that the -values are independent:

Theorem 1 (Benjamini-Hochberg)The FDR of the BH procedure is exactly equal to under the assumption that the -values are independent.

There probably exist many proofs of this by-now classical inequality. Based on an understated google search, I was able to find two extremely slick and short proofs which I describe below. Prior to that, let me provide some rudimentary intution for the specific form of the BH procedure. Based on the -values , our goal is to reject or accept each hypothesis . It is obvious that we will have to reject those for which is small but how small is the question. Suppose we decide to reject all hypotheses for which the -value is less than or equal to . For this procedure, the number of rejections and the number of false rejections are given by

respectively. Consequently the FDR of this procedure is . We would ideally like to choose to be the largest subject to the constraint that (*largest* because larger values of lead to more rejections or discoveries). Unfortunately, we do not quite know what is; we do not even know what is (if we did we could have used it as a proxy for ). We do however know what is but requires knowledge of which we do not have. However, the expectation of equals which we know cannot be larger than the known quantity . It is therefore reasonable to choose as

and reject all -values which are less than or equal to . This intuitive procedure is actually exactly the same as the BH procedure and this fact is not very hard to see.

**Proof One**: This proof uses martingales and is due to Storey, Taylor and Siegmund in a paper published in 2004. The explanation above about an alternative formulation of the BH procedure implies that we only need to prove

where and are defined as in (2). The important observation now is that the process is a backward martingale i.e.,

for all . This fact involves only independent uniform random variables and is easy. With defined as in (3), one of Doob’s martingale theorems gives

Now the definition (3) of implies that (this requires an argument!). As a result, we can replace by to obtain (4). This completes the proof.

**Proof Two**: This proof works directly with the original formulation of the BH procedure. I have found this proof in a recent paper by Heesen and Janssen (see page 25 in arxiv:1410.8290). We may assume that is nonempty for otherwise and there will be nothing to prove. Let and let denote the number of rejections made by the BH procedure. From the description, it should be clear that is exactly equal to . We can therefore write the FDP as

We now fix and let i.e., the th -value is replaced by and the rest of the -values are unchanged. Let denote the number of rejections of the BH procedure for . It should be noted that because of the presence of a zero -value in . The key observation now is

To see this, it is enough to note that and that when . It is straightforward to verify these facts from the definition of the BH procedure. Using (5), we can write

The independence assumption of now implies that and are independent. Also because is uniformly distributed on as , we deduce that and this completes the proof.