Repository: statsmodels/statsmodels (Python)

Issue:
BUG: statsmodels.stats.multitest.fdrcorrection_twostage sometimes returns values in wrong order and gives values above 1
test case:
```
>>> import statsmodels.stats.multitest
>>> import numpy as np
>>> test=np.array([0.2, 0.8, 0.3, 0.5, 1])
>>> statsmodels.stats.multitest.fdrcorrection_twostage(test, alpha=0.05, method='bky')[1]
array([0.7875, 0.7875, 0.875 , 1.05  , 1.05  ])
>>> statsmodels.stats.multitest.multipletests(test, alpha=0.05, method='fdr_tsbky')[1]
array([0.7875, 1.    , 0.7875, 0.875 , 1.    ])
```
There are two issues with `fdrcorrection_twostage`
1. it sometimes but not always returns results in sorted order, which does not mach input order. The behavior is inconsistent and depends on values in the input array
2. it returns values above 1

results from `fdrcorrection_twostage` and `multipletests` should match but only results from `multipletests` seems to be correct compared to results from Prism


Hints:
Thanks for reporting.

Looks like a bug, but it's not clear to me yet why. It has the same rearranging code like fdrcorrection and multipletests.

if there is one rejection, then it seems to work

```
test=np.array([0.2, 0.8, 0.3, 0.5, 0.9, 1e-3])
res1 = statsmodels.stats.multitest.fdrcorrection_twostage(test, alpha=0.05, method='bky')[1]
print(test)
res2 = statsmodels.stats.multitest.multipletests(test, alpha=0.05, method='fdr_tsbky')[1]
res1, res2
[0.2   0.8   0.3   0.5   0.9   0.001]
(array([0.525  , 0.7875 , 0.525  , 0.65625, 0.7875 , 0.00525]),
 array([0.525  , 0.7875 , 0.525  , 0.65625, 0.7875 , 0.00525]))
```

found it:

if no rejection, then there is an early return that doesn't reorder the result

```
    r1 = rej.sum()
    if (r1 == 0) or (r1 == ntests):
        return rej, pvalscorr * fact, ntests - r1, alpha_stages
```

Also it looks like `multipletests` does not support `iter` keyword for fdr twostage.

aside: both fdrcorrection method always reorder if not is_sorted, no option for turning it off as in multipletest function.



@nevubm 

Can you check some additional results with Prism, if you have that?

a current unit test uses the following uncorrected pvalues
pvals = [
        0.0001, 0.0004, 0.0019, 0.0095, 0.0201, 0.0278, 0.0298, 0.0344, 0.0459,
        0.3240, 0.4262, 0.5719, 0.6528, 0.7590, 1.000]

When I wrote this function, there were no corrected p-values for the two-stage fdr available in other packages or reference articles. The original paper only had the rejection decision and I derived the computation for corrected p-values myself.

fdr_tsbh has unit tests for corrected pvalues in TestMultiTests3 and TestMultiTests4
fdr_tsbky only has unit test for rejection count and for alpha-star (in test_fdr_bky )

possible fixes

- make large if else block, i.e. iterate in else block, or
- keep early return and write helper function for reordering of return arrays

the first is cleaner if we want to change the return, e.g. to HolderTuple, but maybe we only change the return of `multipletests`.

other possible changes
- `iter` is reserved word, rename to `iterate`
- add `fdrts_iterate` (or similar name) keyword to `multipletests` and forward to fdr two-stage
- privatize the two fdr functions, I guess not


> Can you check some additional results with Prism, if you have that?
> 
> a current unit test uses the following uncorrected pvalues pvals = [ 0.0001, 0.0004, 0.0019, 0.0095, 0.0201, 0.0278, 0.0298, 0.0344, 0.0459, 0.3240, 0.4262, 0.5719, 0.6528, 0.7590, 1.000]

This is the output from Prism 9.4.1, using two stage BKY
P value | q value
-- | --
0.0001 | 0.0012
0.0004 | 0.0023
0.0019 | 0.0073
0.0095 | 0.0274
0.0201 | 0.0464
0.0278 | 0.0492
0.0298 | 0.0492
0.0344 | 0.0497
0.0459 | 0.0589
0.3240 | 0.3742
0.4262 | 0.4475
0.5719 | 0.5505
0.6528 | 0.5800
0.7590 | 0.6262
1.0000 | 0.7700

For the unit tests, it would be a good idea to shuffle the input order a couple times instead of feeding it in sorted order, to check the output order.

Also, are the values above 1 related to the sorting or is that a different issue?
Since you're already thinking about this, I have a question. Having separate `fdrcorrection_twostage`, `fdrcorrection`, and `multipletests` that do a lot of the same thing was always a bit confusing for me. Is not the main difference that `fdrcorrection_twostage` can do more than 2 stages with `iter`? And `fdrcorrection` seems fully redundant with `multipletests`. Would it be possible to combine these functions into a single function in a way that makes sense?
Thanks for the reference numbers

I have not yet checked why pvalue can be >1
The `fdrcorrection` function uses `pvals_corrected[pvals_corrected>1] = 1` but I don't see yet why pvalues can still be >1

```
test=np.array([0.2, 0.8, 0.3, 0.5, 0.9999999])
res1 = statsmodels.stats.multitest.fdrcorrection_twostage(test, alpha=0.05, method='bky')[1]
print(test)
res2 = statsmodels.stats.multitest.multipletests(test, alpha=0.05, method='fdr_tsbky')[1]
res1, res2
[0.2       0.8       0.3       0.5       0.9999999]
(array([0.7875   , 0.7875   , 0.875    , 1.0499999, 1.0499999]),
 array([0.7875, 1.    , 0.7875, 0.875 , 1.    ]))
```

**update**

the call to fdrcorrection if the two-stage function return <=1, however two-stage still has a multiplicative `fact` > 1 in return
```
if (r1 == 0) or (r1 == ntests):
        return rej, pvalscorr * fact, ntests - r1, alpha_stages
```

There is also factor in the final return if only some tests are rejected, so there should be cases with pvalue > 1 also in that path

```
    if method == 'bky':
        pvalscorr *= (1. + alpha)
```

`multipletests` function has `pvals_corrected[pvals_corrected>1] = 1` for all methods and will never return pvalue > 1, it's only the two-stage fdr function than can have it.
> Having separate fdrcorrection_twostage, fdrcorrection, and multipletests that do a lot of the same thing

`multipletests` delegates to the two fdrcorrection functions. I split those out because those computation are much longer than the non-fdr methods.
Essentially, `multipletests` is supposed to be the main public function, the fdrcorrection functions are implementation details.
But because those are not private (no leading underscore), we ended up adding the supporting code like sorting, reordering and pvalue>1 checks to all three functions (and need to finish that for the two-stage fdr).

The multiple testing functions are pretty old. Because this bug hasn't been reported yet, I guess that most users use `multipletests` which does not have the bugs.

After we add the `iter` option for two-stage fdr to multipletests, then there is no reason anymore to use the fdrcorrection functions directly.
 
Aside:
if `is_sorted=True`, then most of the extra code like sorting and reordering is not used. So internally we don't duplicate those computations when multipletests calls an fdrcorrection function.


**update**
We should add a comment to the docstring of the fdrcorrection functions to indicate that the main function is `multipletests` and check we have the `See Also`.
Similar problem for rates etest https://www.statsmodels.org/dev/generated/statsmodels.stats.rates.etest_poisson_2indep.html
In that case, the main function `test_poisson_2indep` uses `etest_kwds=None` so users have no reason to call the etest function directly.

related: should we have `maxiter` (int or boolean) instead of `iter` (boolean)?

Current `iter` is binary, either no iteration or iterate to convergence. Loop has at most ntests iterations, AFAICS, possible ri=0,...,ntests.
It would be possible to allow just one or two iterations using maxiter.
e.g. 
If maxiter is in {True, False}, then current no are complete iteration
If maxiter is int or not boolean, then stop at maxiter unless already converged before maxiter (as in optimization loops)

`maxiter` seems more complete and flexible, and you can have `maxiter=-1` for no limit/until convergence, `0` for no iteration (default), and any other integer specifies number of iterations
another problem that currently the twostage fdrcorrection function is not redundant:
multipletest does not return 2 extra returns from fdrcorrection: m0 estimated number of true hypotheses and alphastages.
m0 can be inferred from other returns, but not alphastages

need holdertuple to allow for extra returns
for more iteration, then twostage, the number of iterations can be inferred from len(alphastages).
Given that we only have a finite number of possible iteration, a `converged` indicator is not needed because we always converge (endless loops are ruled out by code, number of rejections can only increase, raises exception if it decreases)

If we switch to holdertuple also in fdrcorrection_twostage, then we could also return `ri` list, i.e. stages of number of rejections in iterations.



Patch:
diff --git a/statsmodels/stats/multitest.py b/statsmodels/stats/multitest.py
--- a/statsmodels/stats/multitest.py
+++ b/statsmodels/stats/multitest.py
@@ -60,7 +60,9 @@ def _ecdf(x):
     for a in m[1:]:
         multitest_alias[a] = m[0]
 
-def multipletests(pvals, alpha=0.05, method='hs', is_sorted=False,
+def multipletests(pvals, alpha=0.05, method='hs',
+                  maxiter=1,
+                  is_sorted=False,
                   returnsorted=False):
     """
     Test results and p-value correction for multiple tests
@@ -86,6 +88,13 @@ def multipletests(pvals, alpha=0.05, method='hs', is_sorted=False,
         - `fdr_tsbh` : two stage fdr correction (non-negative)
         - `fdr_tsbky` : two stage fdr correction (non-negative)
 
+    maxiter : int or bool
+        Maximum number of iterations for two-stage fdr, `fdr_tsbh` and
+        `fdr_tsbky`. It is ignored by all other methods.
+        maxiter=1 (default) corresponds to the two stage method.
+        maxiter=-1 corresponds to full iterations which is maxiter=len(pvals).
+        maxiter=0 uses only a single stage fdr correction using a 'bh' or 'bky'
+        prior fraction of assumed true hypotheses.
     is_sorted : bool
         If False (default), the p_values will be sorted, but the corrected
         pvalues are in the original order. If True, then it assumed that the
@@ -228,11 +237,13 @@ def multipletests(pvals, alpha=0.05, method='hs', is_sorted=False,
         # delegate, call with sorted pvals
         reject, pvals_corrected = fdrcorrection_twostage(pvals, alpha=alpha,
                                                          method='bky',
+                                                         maxiter=maxiter,
                                                          is_sorted=True)[:2]
     elif method.lower() in ['fdr_tsbh', 'fdr_2sbh']:
         # delegate, call with sorted pvals
         reject, pvals_corrected = fdrcorrection_twostage(pvals, alpha=alpha,
                                                          method='bh',
+                                                         maxiter=maxiter,
                                                          is_sorted=True)[:2]
 
     elif method.lower() in ['fdr_gbs']:
@@ -356,7 +367,9 @@ def fdrcorrection(pvals, alpha=0.05, method='indep', is_sorted=False):
         return reject, pvals_corrected
 
 
-def fdrcorrection_twostage(pvals, alpha=0.05, method='bky', iter=False,
+def fdrcorrection_twostage(pvals, alpha=0.05, method='bky',
+                           maxiter=1,
+                           iter=None,
                            is_sorted=False):
     '''(iterated) two stage linear step-up procedure with estimation of number of true
     hypotheses
@@ -376,7 +389,23 @@ def fdrcorrection_twostage(pvals, alpha=0.05, method='bky', iter=False,
            and Yekuteli 2006
         * 'bh' - the two stage method of Benjamini and Hochberg
 
+    maxiter : int or bool
+        Maximum number of iterations.
+        maxiter=1 (default) corresponds to the two stage method.
+        maxiter=-1 corresponds to full iterations which is maxiter=len(pvals).
+        maxiter=0 uses only a single stage fdr correction using a 'bh' or 'bky'
+        prior fraction of assumed true hypotheses.
+        Boolean maxiter is allowed for backwards compatibility with the
+        deprecated ``iter`` keyword.
+        maxiter=False is two-stage fdr (maxiter=1)
+        maxiter=True is full iteration (maxiter=-1 or maxiter=len(pvals))
+
     iter : bool
+        ``iter`` is deprecated use ``maxiter`` instead.
+        If iter is True, then only one iteration step is used, this is the
+        two-step method.
+        If iter is False, then iterations are stopped at convergence which
+        occurs in a finite number of steps (at most len(pvals) steps).
 
     Returns
     -------
@@ -385,7 +414,7 @@ def fdrcorrection_twostage(pvals, alpha=0.05, method='bky', iter=False,
     pvalue-corrected : ndarray
         pvalues adjusted for multiple hypotheses testing to limit FDR
     m0 : int
-        ntest - rej, estimated number of true hypotheses
+        ntest - rej, estimated number of true (not rejected) hypotheses
     alpha_stages : list of floats
         A list of alphas that have been used at each stage
 
@@ -411,6 +440,18 @@ def fdrcorrection_twostage(pvals, alpha=0.05, method='bky', iter=False,
     '''
     pvals = np.asarray(pvals)
 
+    if iter is not None:
+        import warnings
+        msg = "iter keyword is deprecated, use maxiter keyword instead."
+        warnings.warn(msg, FutureWarning)
+
+    if iter is False:
+        maxiter = 1
+    elif iter is True or maxiter in [-1, None] :
+        maxiter = len(pvals)
+    # otherwise we use maxiter
+
+
     if not is_sorted:
         pvals_sortind = np.argsort(pvals)
         pvals = np.take(pvals, pvals_sortind)
@@ -430,30 +471,36 @@ def fdrcorrection_twostage(pvals, alpha=0.05, method='bky', iter=False,
                                    is_sorted=True)
     r1 = rej.sum()
     if (r1 == 0) or (r1 == ntests):
-        return rej, pvalscorr * fact, ntests - r1, alpha_stages
-    ri_old = r1
-
-    while True:
-        ntests0 = 1.0 * ntests - ri_old
-        alpha_star = alpha_prime * ntests / ntests0
-        alpha_stages.append(alpha_star)
-        #print ntests0, alpha_star
-        rej, pvalscorr = fdrcorrection(pvals, alpha=alpha_star, method='indep',
-                                       is_sorted=True)
-        ri = rej.sum()
-        if (not iter) or ri == ri_old:
-            break
-        elif ri < ri_old:
-            # prevent cycles and endless loops
-            raise RuntimeError(" oops - should not be here")
-        ri_old = ri
-
-    # make adjustment to pvalscorr to reflect estimated number of Non-Null cases
-    # decision is then pvalscorr < alpha  (or <=)
-    pvalscorr *= ntests0 * 1.0 /  ntests
-    if method == 'bky':
-        pvalscorr *= (1. + alpha)
-
+        # return rej, pvalscorr * fact, ntests - r1, alpha_stages
+        reject = rej
+        pvalscorr *= fact
+        ri = r1
+    else:
+        ri_old = ri = r1
+        ntests0 = ntests # needed if maxiter=0
+        # while True:
+        for it in range(maxiter):
+            ntests0 = 1.0 * ntests - ri_old
+            alpha_star = alpha_prime * ntests / ntests0
+            alpha_stages.append(alpha_star)
+            #print ntests0, alpha_star
+            rej, pvalscorr = fdrcorrection(pvals, alpha=alpha_star, method='indep',
+                                           is_sorted=True)
+            ri = rej.sum()
+            if (it >= maxiter - 1) or ri == ri_old:
+                break
+            elif ri < ri_old:
+                # prevent cycles and endless loops
+                raise RuntimeError(" oops - should not be here")
+            ri_old = ri
+
+        # make adjustment to pvalscorr to reflect estimated number of Non-Null cases
+        # decision is then pvalscorr < alpha  (or <=)
+        pvalscorr *= ntests0 * 1.0 /  ntests
+        if method == 'bky':
+            pvalscorr *= (1. + alpha)
+
+    pvalscorr[pvalscorr>1] = 1
     if not is_sorted:
         pvalscorr_ = np.empty_like(pvalscorr)
         pvalscorr_[pvals_sortind] = pvalscorr


Test patch:
diff --git a/statsmodels/stats/tests/test_multi.py b/statsmodels/stats/tests/test_multi.py
--- a/statsmodels/stats/tests/test_multi.py
+++ b/statsmodels/stats/tests/test_multi.py
@@ -326,6 +326,75 @@ def test_fdr_bky():
     assert_almost_equal([0.047619, 0.0649], res_tst[-1][:2], 3)
     assert_equal(8, res_tst[0].sum())
 
+    # reference number from Prism, see #8619
+    res2 = np.array([
+        0.0012, 0.0023, 0.0073, 0.0274, 0.0464, 0.0492, 0.0492, 0.0497,
+        0.0589, 0.3742, 0.4475, 0.5505, 0.5800, 0.6262, 0.77
+        ])
+    assert_allclose(res_tst[1], res2, atol=6e-5)
+
+    # issue #8619, problems if no or all rejected, ordering
+    pvals = np.array([0.2, 0.8, 0.3, 0.5, 1])
+    res1 = fdrcorrection_twostage(pvals, alpha=0.05, method='bky')
+    res2 = multipletests(pvals, alpha=0.05, method='fdr_tsbky')
+    assert_equal(res1[0], res2[0])
+    assert_allclose(res1[1], res2[1], atol=6e-5)
+    # confirmed with Prism
+    res_pv = np.array([0.7875, 1., 0.7875, 0.875 , 1.])
+    assert_allclose(res1[1], res_pv, atol=6e-5)
+
+
+def test_fdr_twostage():
+    # test for iteration in fdrcorrection_twostage, new maxiter
+    # example from BKY
+    pvals = [
+        0.0001, 0.0004, 0.0019, 0.0095, 0.0201, 0.0278, 0.0298, 0.0344, 0.0459,
+        0.3240, 0.4262, 0.5719, 0.6528, 0.7590, 1.000]
+    n = len(pvals)
+
+    # bh twostage fdr
+    k = 0
+    # same pvalues as one-stage fdr
+    res0 = multipletests(pvals, alpha=0.05, method='fdr_bh')
+    res1 = fdrcorrection_twostage(pvals, alpha=0.05, method='bh', maxiter=k,
+                                  iter=None)
+    res2 = multipletests(pvals, alpha=0.05, method='fdr_tsbh', maxiter=k)
+    assert_allclose(res1[1], res0[1])
+    assert_allclose(res2[1], res1[1])
+
+    k = 1
+    # pvalues corrected by first stage number of rejections
+    res0 = multipletests(pvals, alpha=0.05, method='fdr_bh')
+    res1 = fdrcorrection_twostage(pvals, alpha=0.05, method='bh', maxiter=k,
+                                  iter=None)
+    res2 = multipletests(pvals, alpha=0.05, method='fdr_tsbh', maxiter=k)
+    res3 = multipletests(pvals, alpha=0.05, method='fdr_tsbh')
+    assert_allclose(res1[1], res0[1] * (1 - res0[0].sum() / n))
+    assert_allclose(res2[1], res1[1])
+    assert_allclose(res3[1], res1[1])  # check default maxiter
+
+    # bky has an extra factor 1+alpha in fdr twostage independent of iter
+    fact = 1 + 0.05
+    k = 0
+    # same pvalues as one-stage fdr
+    res0 = multipletests(pvals, alpha=0.05, method='fdr_bh')
+    res1 = fdrcorrection_twostage(pvals, alpha=0.05, method='bky', maxiter=k,
+                                  iter=None)
+    res2 = multipletests(pvals, alpha=0.05, method='fdr_tsbky', maxiter=k)
+    assert_allclose(res1[1], np.clip(res0[1] * fact, 0, 1))
+    assert_allclose(res2[1], res1[1])
+
+    k = 1
+    # pvalues corrected by first stage number of rejections
+    res0 = multipletests(pvals, alpha=0.05, method='fdr_bh')
+    res1 = fdrcorrection_twostage(pvals, alpha=0.05, method='bky', maxiter=k,
+                                  iter=None)
+    res2 = multipletests(pvals, alpha=0.05, method='fdr_tsbky', maxiter=k)
+    res3 = multipletests(pvals, alpha=0.05, method='fdr_tsbky')
+    assert_allclose(res1[1], res0[1] * (1 - res0[0].sum() / n) * fact)
+    assert_allclose(res2[1], res1[1])
+    assert_allclose(res3[1], res1[1])  # check default maxiter
+
 
 @pytest.mark.parametrize('method', sorted(multitest_methods_names))
 def test_issorted(method):