# Help understanding successive maximization in step-down maxT algorithm

I am currently trying to better understand different permutation-based procedures for controlling FWER. Specifically, the minP/maxT procedures that are commonly used. One of the problems I am running into is the differences in the way the same procedures are described by different sources. Currently, I am reading the otherwise excellent paper by Ge, Dudoit, and Speed (citation and link at end of post).

On page 16, box 2 describes the permutation algorithm for calculating step-down maxT adjusted p-values, based on algorithm 4.1 in Westfall & Young (1993). Specifically, I am having some trouble understanding the purpose of step 3, in which the successive maxima of the test statistics are calculated. So, the notation of Ge, Dudoit, and Speed,

Let $t_i$ denote the $i^{th}$ test statistic for $i=1,\ldots,m$. Then, let $|t_{s_i}|$ denote the absolute value of the $i^{th}$ ORDERED test statistic.

For each permutation $b$, after computing the test statistics $t_{i,b}$ ($i\in{1,\ldots,m}$) on the permuted data, the successive maxima are then calculated as:

$u_{m,b}=|t_{s_m,b}|$ $\leftarrow$ i.e. the absolute value of the largest test statistic for permutation $b$

$u_{i,b}=$ max$(u_{i+1,b},|t_{s_i,b}|)$ for $i=m-1,\ldots,1$

That is, for the second largest test statistic, you assign to $u_{m-1,b}$ the value of whichever is larger: $u_{m,b}$ or $|t_{s_{m-1},b}|$. However, since these are the ordered test statistics, by definition $|t_{s_{m},b}|>|t_{s_{m-1},b}|$ . So each successive maxima will ALWAYS be assigned the value of the previous maxima, so that $u_{i,b}=u_{m,b}$ for all $i$.

What, then, is the purpose of this successive maximization? If the same maximum is going to be assigned regardless (by the definition of order statistics), then why waste any time calculating them successively?

Ge, Y., Dudoit, S., and Speed, T.P. "Resampling-based multiple testing for microarray data analysis." Test 12, 1-77 (2003). Available online: here

Westfall PH, Young SS. Resampling-Based Multiple Testing: Examples and Methods for p-Value Adjustment. Wiley; New York: 1993.

I guess I shouldn't ask for help here, but after doing some research I can answer the question. The OP is simply misunderstanding some notation. Here is the paper in question, box 2.

Basically:

$u_{m,b}= |t_{sm,b}|$ ← i.e. the absolute value of the largest test statistic for permutation b

Simply not the case if you look at the paper. In step 3:

They compute the statistic $t$ in step 2 for all the permuted columns. Then in step 3 they are ensuring through successive maximization that $|t_{sm,b}|$ is the minimum, so it can be compared to the minimum of the original statistics calculated from unpermutated data .

So nowhere does it say:

$u_{m,b}= |t_{sm,b}|$ ← i.e. the absolute value of the largest test statistic for permutation b

They then successively define $u_{i,b}$ for all successive $i$ so it is ordered can be directly compared to the unpermutated statistics, which are ordered already, which you can then can a p-value from.

I'm pretty sure I'm right on this, but any criticism would be greatly appreciated as this is my first real post here.

side note: @whuber whats the best way to revive a dead question? Should I just post the question again if no one has answered it?

• Thank you for your response. I'm just so used to seeing that notation used to represent absolute value. To be honest, though, I don't see how this actually answers the question. Whether or not that denotes absolute value, my question still stands as to what is the purpose of the successive maximization? If the statistics have already been ordered, then by definition t1 is larger than t2, etc. It just seems computationally wasteful to then go through this successive maximization process if you will always choose the same largest test statistic as if you didn't go through that process. Commented Dec 18, 2015 at 15:00
• So the original statistics $t_s1 ... t_sm$ have already been ordered, which is correct. But when you permute the columns and calculate the statistics, $t_{s1,b}...t_{sm,b}$, the statistics from the permuted columns are unordered, so you order them through successive maximization. You order them so they can be meaningfully compared to the original statistics (i.e. the unpermuted ones). Because you perform a permutation the statistics become unordered. At least, this is my understanding. I'm new to this stuff Commented Dec 18, 2015 at 15:02