Submitted to the Annals of Statistics
arXiv: arXiv:1610.03944

RANK VERIFICATION FOR EXPONENTIAL FAMILIES
By Kenneth Hung and William Fithian

arXiv:1610.03944v2 [stat.ME] 3 Jul 2017

University of California, Berkeley
Many statistical experiments involve comparing multiple population groups. For example, a public opinion poll may ask which of
several political candidates commands the most support; a social scientific survey may report the most common of several responses to
a question; or, a clinical trial may compare binary patient outcomes
under several treatment conditions to determine the most effective
treatment. Having observed the “winner” (largest observed response)
in a noisy experiment, it is natural to ask whether that candidate,
survey response, or treatment is actually the “best” (stochastically
largest response). This article concerns the problem of rank verification — post hoc significance tests of whether the orderings discovered
in the data reflect the population ranks. For exponential family models, we show under mild conditions that an unadjusted two-tailed
pairwise test comparing the first two order statistics (i.e., comparing
the “winner” to the “runner-up”) is a valid test of whether the winner
is truly the best. We extend our analysis to provide equally simple
procedures to obtain lower confidence bounds on the gap between the
winning population and the others, and to verify ranks beyond the
first.

1. Introduction.
1.1. Motivating Example: Iowa Republican Caucus Poll. Table 1 shows the result of a Quinnipiac University poll asking 890 Iowa Republicans their preferred candidate for the Republican
presidential nomination (Quinnipiac University Poll Institute, 2016). Donald Trump led with
31% of the vote, Ted Cruz came second with 24%, Marco Rubio third with 17%, and ten other
candidates including “Don’t know” trailed behind.
Rank
1*
2*
3*
4*
5
6
7
..
.

Candidate
Result
Votes
Trump
31%
276
Cruz
24%
214
Rubio
17%
151
Carson
8%
71
Paul
4%
36
Bush
4%
36
Huckabee
3%
27
..
..
..
.
.
.
Table 1
Results from a February 1, 2016 Quinnipiac University poll of 890 Iowa Republicans. To compute the last
column (Votes), we make the simplifying assumption that the reported percentages in the third column (Result)
are raw vote shares among survey respondents. The asterisks indicate that the rank is verified at level 0.05 by a
stepwise procedure.
MSC 2010 subject classifications: Primary 62F07; secondary 62F03
Keywords and phrases: ranking, selective inference, exponential family

1
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

2

K. HUNG AND W. FITHIAN

Seeing that Trump leads this poll, several salient questions may occur to us: Is Trump really
winning, and if so by how much? Furthermore, is Cruz really in second, is Rubio really in third,
and so on? Note that there is implicitly a problem of multiple comparisons here, because if
Cruz had led the poll instead, we would be asking a different set of questions (“Is Cruz really
winning,” etc.). Indeed, the selection issue appears especially pernicious due to the so-called
“winner’s curse”: given that Trump leads the poll, it more likely than not overestimates his
support.
Nevertheless, if we blithely ignore the selection issue, we might carry out the following
analyses to answer the questions we posed before at significance level α = 0.05. We assume
for simplicity that the poll represents a simple random sample of Iowa Republicans; i.e., that
the data are a multinomial sample of size 890 and underlying probabilities (πTrump , πCruz , . . .).
(The reality is a bit more complicated: before releasing the data, Quinnipiac has post-processed
it to make the reported result more representative of likely caucus-goers. The raw data is
proprietary.)
1. Is Trump really winning? If Trump and Cruz were in fact tied, then Trump’s share of their
combined 490 votes would be distributed as Binomial (490, 0.5). Because the (two-tailed)
p-value for this pairwise test is p = 0.006, we reject the null and conclude that Trump is
really winning.
2. By how much? Using an exact 95% interval for the same binomial model, we conclude
Trump has at least 7.5% more support than Cruz (i.e., πTrump ≥ 1.075 πCruz ) and also
leads the other candidates by at least as much.
3. Is Cruz in second, Rubio in third, etc.? We can next compare Cruz to Rubio just as we
compared Trump to Cruz (again rejecting because 214 is significantly more than half of
365), then Rubio to Carson, and so on, continuing until we fail to reject. The first four
comparisons are all significant at level 0.05, but Paul and Bush are tied so we stop.
Perhaps surprisingly, all of the three procedures described above are statistically valid despite
their ostensibly ignoring the implicit multiple-comparisons issue. In other words, Procedures 1
and 2 control the Type I error rate at level α and Procedure 3 controls the familywise error
rate (FWER) at level α. The remainder of this article is devoted to justifying these procedures
for the multinomial family, and extending to analogous procedures in other exponential family
settings. While methods analogous to Procedures 1 and 2 have been justified previously for
balanced independent samples from log-concave location families (Gutmann and Maymin, 1987;
Stefansson, Kim and Hsu, 1988), they have not been justified in exponential families before
now.
1.2. Generic Problem Setting and Main Result. Generically, we will consider data drawn
from an exponential family model with density

(1)
X ∼ exp θ0 x − ψ (θ) g (x) ,
with respect to either the Lebesgue measure on Rn or counting measure on Zn . We assume further that g (x) is symmetric with respect to permutation, and Schur concave, a mild technical
condition defined in Section 2. In addition to the multinomial family, model (1) also encompasses settings such as comparing independent binomial treatment outcomes in a clinical trial,
competing sports teams under a Bradley–Terry model, entries of a Dirichlet distribution, and
many more; see Section 2 for these and other examples.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

3

We will generically use the term population to refer to the treatment group, sports team,
political candidate, etc. represented by a given random variable Xj . As we will see, θj ≥ θk if
and only if Xj is stochastically larger than Xk ; thus, there is a well-defined stochastic ordering
of the populations that matches the ordering of the entries of θ. We will refer to the population
with maximal θj as the best, the population with second largest θj as the second best, the one
with maximal Xj as the winner, and the one with the second-largest Xj as the runner-up,
where ties between observations are broken randomly to obtain a full ordering. Following the
convention in the ranking and selection literature, we assume that if there are multiple largest
θj , then one is arbitrarily marked as the best. Note that in cases where it is more interesting to
ask which is the smallest population (for example, if Xj is the number of patients on treatment j
who suffer a heart attack during a trial) we can change the variables to −X and the parameters
to −θ; this does not affect the Schur concavity assumption.
Write the order statistics of X as
X[1] ≥ X[2] ≥ · · · ≥ X[n] ,
where [j] will denote the random index for the j-th order statistic. Thus, θ[j] is the entry of θ
corresponding to the j-th order statistic of X (so θ[1] might not equal maxj θj , for example).
In each of the above examples, there is a natural exact test we could apply to test θj = θk
for any two fixed populations j and k. In the multinomial case, we would apply the conditional
binomial test based on the combined total Xj + Xk as discussed in the previous section. For
the case of independent binomials we would apply Fisher’s exact test, again conditioning on
Xj + Xk . These are both examples of a generic UMPU pairwise test in which we condition on
the other n − 2 indices (notated X\{j,k} ) and Xj + Xk , and reject the null if Xj is outside the
α/2 and 1 − α/2 quantiles of the conditional law Lθj =θk (Xj | Xj + Xk , X\{j,k} ). Crucially, this
null distribution does not depend on the value of θ provided that θj = θk . We call this test
the (two-tailed) unadjusted pairwise test since it makes no explicit adjustment for selection.
Similarly, inverting this test for other values of θj − θk yields an unadjusted pairwise confidence
interval. (To avoid trivialities in the discrete case, we assume these procedures are appropriately
randomized at the rejection thresholds to give exact level-α control.)
Generalizing the procedures described in Section 1.1 we obtain the following:
1. Is the winner really the best? To test the hypothesis H : θ[1] ≤ maxj6=[1] θj : Carry out
the unadjusted pairwise test comparing the winner to the runner-up. If the test rejects
at level α, reject H and declare that the winner is really the best.
2. By how much? To construct a lower confidence bound for θ[1] − maxj6=[1] θj : Construct
the unadjusted pairwise confidence interval comparing the winner to the runner-up, and
report the lower confidence bound obtained for θ[1] − θ[2] if it is nonnegative, report −∞
otherwise.
3. Is the runner-up really the second best, etc.? Continue by comparing the runner-up to
the second runner-up, again using the unadjusted pairwise test, and so on down the list
comparing adjacent values. Stop the first time the test does not reject; if there are j
rejections, declare that
θ[1] > θ[2] > · · · > θ[j] > max θ[j]
k>j

Procedures 2 and 3 are conservative stand-ins for exact, but slightly more involved, conditional
inference procedures. In particular, as we will see, reporting −∞ in Procedure 2 is typically
much more conservative than is necessary.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

4

K. HUNG AND W. FITHIAN

We now state our main theorem: under a mild technical assumption, Procedures 1–3 described above are statistically valid, even accounting for the selection.
Theorem 1.

Assume the model (1) holds and g (x) is a Schur-concave function. Then:

1. Procedure
lation not
2. Procedure
3. Procedure

1 has exact level α conditional on H being true (conditional on the best popuwinning), and marginally has level α · P(H is true) ≤ α 1 − n1 .
2 gives a conservative 1 − α lower confidence bound for θ[1] − maxj6=[1] θj .
3 is a conservative stepwise procedure with FWER no larger than α.

n
Note that Theorem 1 implies that we could actually replace α with n−1
α to obtain a more
powerful version of Procedure 1 when n is not too large.
We define Schur-concavity and discuss its properties in Section 2. Because any log-concave
and symmetric function is Schur-concave, Theorem 1 applies to all of the cases discussed above.
The proof combines the conditional selective-inference framework of Fithian, Sun and Taylor
(2014) with classical multiple-testing methods, as well as new technical tools involving majorization and Schur-concavity.
Note that these procedures make an implicit adjustment for selection because they use twotailed, rather than one-tailed, unadjusted tests. If we instead based our tests on an independent
realization X ∗ = (X1∗ , . . . , Xn∗ ) then, for example, Procedure 1 could use a right-tailed version
of the unadjusted pairwise test. In the case n = 2, Procedure 1 amounts to a simple two-tailed
test of the null hypothesis θ1 = θ2 , and it is intuitively clear that a one-tailed test would be too
liberal. More surprising is that, no matter how large n is, Procedures 1–3 require no further
adjustment beyond what is required when n = 2.

1.3. Related work. Rank verification has been studied extensively in the ranking and selection literature. See Gupta and Panchapakesan (1971, 1985) for surveys of the subset selection
literature. The two main formulations of ranking and selection are closely related to procedures for multiple comparisons with the best treatment (Edwards and Hsu, 1983; Hsu, 1984),
but more powerful methods are available in some cases for procedures involving only the first
sample rank, the problem of comparisons with the sample best; see Hsu (1996) for an overview
and discussion of the relationships between these problems.
Comparisons with the sample best have been especially well-studied and the validity of Procedures 1 and 2 have been established in a different setting: balanced independent samples from
log-concave location families. Gutmann and Maymin (1987) prove the validity of Procedure 1
in this setting, and Bofinger (1991); Maymin and Gutmann (1992); Karnnan and Panchapakesan (2009) give similar results for other models including scale and location-scale families.
Stefansson, Kim and Hsu (1988) provide an alternative proof for the validity of Procedure 1
in the same setting, leading to a lower confidence bound analogous to that of Procedure 2;
interestingly, the proof involves a very early application of the partitioning principle, later developed into fundamental technique in multiple comparisons (Finner and Strassburger, 2002).
These results use very different technical tools than the ones we use here, require independence
between the different groups (ruling out, for example, the multinomial family), and do not
address the exponential family case. Because most exponential families are not location-scale
families (the Gaussian being a notable exception), and because our results involve more general
dependence structures, both our proof techniques and our technical results are complementary
to the techniques and results in the above works.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

5

For the multinomial case, Gupta and Nagel (1967), discussed in Section 3.1, remain the state
of the art in finite-sample tests; Gupta and Wong (1976) discuss related approaches for Poisson
models. Berger (1980) mentions an alternative, simpler rule which performs a binomial test
on each population, but its power does not necessarily increase as the size m of observations
increases in cases like Multinomial(m; 2/3, 1/3, 0, . . . , 0). Nettleton (2009) proves validity for an
asymptotic version of the winner-versus-runner-up test, and Gupta and Liang (1989) consider
an empirical Bayes approach for selecting the best binomial population wherein a parametric
prior distribution is assumed for the success probabilities for the different populations. Ng and
Panchapakesan (2007) discuss an exact test for a modified problem in which the maximum
count is fixed instead of the total count; that is, we sample until the leading candidate has
at least m votes. As Section 3.1 shows, our test can be much more powerful than the one in
Gupta and Nagel (1967), especially if there are many candidates, because of the way our critical
rejection threshold for X[1] − X[2] adapts to the data. Thus, our work closes a significant gap
in the ranking and selection literature, extending the result of Gutmann and Maymin (1987)
and others to new families like the multinomial, independent binomials, and many others.
1.4. Outline. Section 2 defines Schur concavity, and gives several examples satisfying this
condition. Section 3 justifies Procedure 1 and compares its power to that of Gupta and Nagel
(1967). Sections 4 and 5 justify Procedures 2 and 3 respectively, and Section 6 concludes.
2. Majorization and Schur concavity.
2.1. Definitions and basic properties. We start by reviewing the notion of majorization,
defined on both Rn and Zn .
Definition 1. For two vectors a and b in Rn (or Zn ), suppose sorting the two vectors in
descending order gives a(1) ≥ · · · ≥ a(n) and b(1) ≥ · · · ≥ b(n) . We say that a  b (a majorizes
b) if for 1 ≤ i < n,
a(1) + · · · + a(i) ≥ b(1) + · · · + b(i) ,

and

a(1) + · · · + a(n) = b(1) + · · · + b(n) .
This forms a partial order in Rn (or Zn ).
Intuitively, majorization is a partial order that monitors the evenness of a vector: the more
even a vector is, the “smaller” it is. There are two properties of majorization that we will use
in the proofs.
Lemma 2.
1. Suppose (x1 , x2 , x3 , . . .) and (x1 , y2 , y3 , . . .) are two vectors in Rn . Then
(x1 , x2 , x3 , . . .)  (x1 , y2 , y3 , . . .) if and only if (x2 , x3 , . . .)  (y2 , y3 , . . .) .
2. (Principle of transfer) If x1 > x2 and t ≥ 0, then
(x1 + t, x2 , x3 , . . .)  (x1 , x2 + t, x3 , . . .) .
If t ≤ 0, the majorization is reversed.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

6

K. HUNG AND W. FITHIAN

Proof.
1. The property follows from an equivalent formulation of majorization listed in Marshall,
Olkin and Arnold (2010), where x  y if and only if
n
X
j=1

xn =

n
X

yn

n
X

and

j=1

(xj − a)+ ≥

j=1

n
X

(yj − a)+ for all a ∈ R.

j=1

2. Proved in Marshall, Olkin and Arnold (2010).
Definition 2.

A function g is Schur-concave if x  y implies g (x) ≤ g (y).

A Schur-concave function is symmetric by default since a  b and b  a if and only if b is a
permutation of the coordinates of a. Conversely a symmetric and log-concave function is Schurconcave (Marshall, Olkin and Arnold, 2010). Interestingly, Gupta, Huang and Panchapakesan
(1984) also show that, in the context of independent location families, Schur concavity of the
probability density is equivalent to monotone likelihood ratio.
2.2. Examples. Many common exponential family models have Schur-concave carrier densities. Below we give a few examples:
Example 1 (Independent binomial treatment outcomes in a clinical trial). If each of n
different treatments are applied to m patients independently, the number of positive outcomes
Xj for treatment j is Binomial (m, pj ). The best treatment would be the treatment with the
highest success probability pj . The joint distribution of X is given by


X
pj 
1
p (x) ∝ exp 
xj log
1 − pj x1 ! (m − x1 )! · · · xn ! (m − xn )!
j

The carrier measure above is Schur-concave. The unadjusted pairwise test in this family is
Fisher’s exact test.
Example 2 (Competitive sports under the Bradley–Terry model). Suppose n players compete in a round robin tournament, where player j has ability θj , and the probability of player
j winning against player k is
eθj −θk
e(θj −θk )/2
= (θ −θ )/2
.
θ
−θ
1+e j k
e j k + e(θk −θj )/2
Let Yjk be an indicator for the match between player j and k, where we take Yjk = 1 if
j beats k and Yjk = 0 if k beats j. For symmetry, we will also adopt the convention that
Yjk + Ykj = 1. Thus the joint distribution of Y = (Yjk )j6=k is


X
X

p (y) ∝ exp 
2θj
yjk  = exp 2θ0 x ,
j

k6=j

P

where xj =
k6=j yjk . In other words, if Xj is the number of wins by player j, then X =
(X1 , . . . , Xn ) is a sufficient statistic with distribution

p (x) = exp 2θ0 x g (x) ,
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

7

where g (x) is a function that counts the number of possible tournament results giving the net
win vector x. A bijection proof shows that x is indeed Schur-concave. Therefore, we can use
Procedures 1–3 to compare player qualities.
After conditioning on U (X) = (X1 + X2 , X3 , . . . , Xn ), and under the assumption θ1 = θ2 ,
every feasible configuration of Y is equally likely. If n is not too large (say, no more than 40
players), we can find the conditional distribution of X1 by enumerating over the configurations;
for larger n, computation might pose a more serious problem, requiring us for example to
compute the p-value using Markov Chain Monte Carlo techniques (Besag and Clifford, 1989).
Example 3 (Comparing the variances of different normal populations). Suppose there
are n normal populations with laws N (µj , σj2 ) and m independent observations from each of
them. The sample variance for population j can be denoted as Rj . By Cochran’s theorem,
(m − 1) Rj ∼ σj2 χ2m−1 , and thus the joint distribution of R is
!(m−3)/2
2
(m − 1) rj
r∼
e−(m−1)rj /2σj 1{rj >0}
2
σj
j=1

Y
n
m−1
m−1
(m−3)/2
∝ exp −
r
−
·
·
·
−
r
rj
1{r>0} .
1
n
2σn2
2σ12
j=1
n
Y

Q
(m−3)/2
1{r>0} , which is Schur-concave. Thus, we can use ProceThe carrier measure is nj=1 rj
dures 1–3 to find populations with the smallest or largest variances. In this example, the distribution of X1 /(X1 + X2 ) conditional on (X1 + X2 , X3 , . . . , X4 ) is distributed as Beta(m/2, m/2)
under the null, or equivalently X1 /X2 is conditionally distributed as Fm,m ; hence a (two-tailed)
F -test is valid for comparing the top two populations.
3. Verifying the Winner: Is the Winner Really the Best?. First, we justify the
notion that the population with largest θj is also the largest population in stochastic order:
Theorem 3. For a multivariate exponential family with a symmetric carrier distribution,
X1 ≥ X2 in stochastic order if and only if θ1 ≥ θ2 .
Proof. It suffices to prove the “if” part, as the “only if” part can be follows from swapping
the role of θ1 and θ2 . For any fixed a, and x1 ≥ a and x2 < a, we have x1 > x2 and
exp (θ1 x1 + θ2 x2 + · · · + θn xn − ψ (θ)) g (x) ≥ exp (θ1 x2 + θ2 x1 + · · · + θn xn − ψ (θ)) g (x) .
Integrating both sides over the region {x : x1 ≥ a, x2 < a} gives
P [X1 ≥ a, X2 < a] ≥ P [X1 < a, X2 ≥ a] .
Now adding P [X1 ≥ a, X2 ≥ a] to both probabilities gives
P [X1 ≥ a] ≥ P [X2 ≥ a] ,
meaning that X1 is greater than X2 in stochastic order.
Before proving our main result for Procedure 1, we give the following lemmas, the first of
which clarifies a key idea in the proof, and the second is needed for a sharper bound in (2).
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

8

K. HUNG AND W. FITHIAN

Lemma 4 (Berger, 1982). If pj are valid p-values for testing null hypothesis H0j
S, then
p∗ = maxj pj is a valid p-value for the union null (i.e. disjunction null) hypothesis H0 = j H0j .
Proof. Under H0 , one of the H0j is true; without loss of generality assume it is H01 . Then,
P [p∗ ≤ α] ≤ P [p1 ≤ α] ≤ α.
Therefore p∗ is a valid p-value for the union null hypothesis.
Lemma 5.

If θ1 ≥ maxj6=1 θj , then P [1 wins] ≥ n1 .

Proof. We can prove so with a coupling argument: for any sequence x1 , x2 , . . . , xn , define
τ (x) = {τ (xj )}j=1,...,n , obtained by swapping x1 with the largest value in the sequence x.
Hence
exp (θ1 τ (x1 ) + · · · + θn τ (xn ) − ψ (θ)) g (X) ≥ exp (θ1 x1 + · · · + θn xn − ψ (θ)) g (X) .
If we integrating both sides over Rn (or Zn in the case of counting measure), the right hand
side gives 1. Since τ is an n-to-1 mapping, the left hand side is n times the integral over
{x1 ≥ maxj>1 xj }. In other words,
nP [1 wins] ≥ 1
as desired.
In the case of counting measure, the above argument follows if a subscript is attached to
identical observations uniformly to ensure strict ordering.
We are now ready to prove our result for Procedure 1, restated here for reference.
Part 1 of Theorem 1. Assume the model (1) holds and g (x) is a Schur-concave function.
Procedure 1 (the unadjusted pairwise test) has level α conditional on the best population not
winning.
Proof. Let j ∗ denote the (fixed) index of the best population, so θj ∗ ≥ maxj6=j ∗ θj . The
type I error — the probability of incorrectly declaring any other j to be the best — is


[
X
P
declare j best ≤
P [declare j best | j wins] P [j wins] ,
j6=j ∗

j6=j ∗

recalling that ties are broken randomly, so there is only one winner in any realization. Thus,
it is enough to bound Pθ [declare j best | j wins] ≤ α, for each j 6= j ∗ , and for all θ with
j ∗ ∈ arg maxj θj . Then we will have


[
X
n−1
α,
(2)
P
declare j best ≤
α · P [j wins] = αP [j ∗ does not win] ≤
n
∗
∗
j6=j

j6=j

where the last inequality follows from Lemma 5.
We start by assuming that we are working with the Lebesgue measure rather than the
counting measure (eliminating the possibility of ties). The necessary modification of the proof
for the counting measure case is provided at the end of this proof.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

9

To minimize notational clutter, we consider only the case where the winner is 1, i.e. X1 ≥
maxj>1 Xj . Furthermore, we will denote the runner-up with 2. This is not necessarily true,
but we will use it as a shorthand to simplify our notation. For other cases, the following proof
remains valid under relabeling and can thus be applied. In this case, we will test the null
hypothesis H01 : θ1 ≤ maxj>1 θj , which is the union of the null hypotheses H01j : θ1 ≤ θj
for j ≥ 2. For each of these we can construct an exact p-value p1j , which is valid under H01j
conditional on A1 , the event that X1 is the winner. Hence by Lemma 4, a test that rejects when
p1∗ = maxj p1j ≤ α is valid for H01 conditional on A1 . Procedure 1 performs an unadjusted
pairwise test comparing X1 to X2 . Hence it is sufficient to show that p12 = p1∗ and that
rejecting when p12 ≤ α coincides with the unadjusted pairwise test.
Our proof has three main parts: (1) deriving p1j for each j ≥ 2, (2) showing that p12 ≥ p1j
for each j ≥ 2, and (3) showing that p12 is an unadjusted pairwise p-value.
Derivation of p1j . Following the framework in Fithian, Sun and Taylor (2014), we first construct the p-values by conditioning on the selection event where the winner is 1:


A1 = X1 ≥ max Xj .
j>1

For convenience, we let
Djk =

Xj − Xk
2

and

Mjk =

Xj + Xk
.
2

We then re-parametrize to replace X1 and Xj with D1j and M1j . The distribution is now
an exponential family with sufficient statistics D1j , M1j , X\{1,j} and corresponding natural
parameters θ1 − θj , θ1 + θj , θ\{1,j} . We now consider

(3)
Lθ1 −θj =0 D1j M1j , X\{1,j} , A1 .
We can rewrite the selection event in terms of our new parameterization as


A1 = {X1 ≥ Xj } ∩ X1 ≥ max Xk
k6=1,j


= {D1j ≥ 0} ∩ D1j ≥ max Xk − M1j .
k6=1,j

The conditional law of D1j in (3), in particular, is a truncated distribution.

p d1j | M1j , X\{1,j} , A1 ∝ exp ((θ1 − θj ) d1j + θ2 X2 + · · · + (θ1 + θj ) M1j + · · · + θn Xn )
g (M1j + dij , X2 , . . . , Mij − dij , . . . Xn ) 1A1
(a)

∝ g (M1j + d1j , X2 , . . . , M1j − d1j , . . . Xn ) 1A1 ,

where at step (a), conditioning on X\{1,j} and M1j removes dependence on θ\{1,j} and θ1 + θj
respectively, while θ1 − θj is taken to be 0 under our null hypothesis. Note that we consider
this as a one-dimensional distribution of D1j on R, where M1j and X\{1,j} are treated as fixed.
The p-value for H01j is thus
R∞
D1j g (M1j + z, X2 , . . . , M1j − z, . . . , Xn ) dz
(4)
p1j = R ∞
.
max{X2 −M1j ,0} g (M1j + z, X2 , . . . , M1j − z, . . . , Xn ) dz
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

10

K. HUNG AND W. FITHIAN

Finally, by construction, p1j satisfies


PH01j p1j < α M1j , X\{1,j} , A1 ≤ α

a.s.,

Marginalizing over M1j , X\{1,j} ,
PH01j [p1j < α | A1 ] ≤ α.
Therefore these p1j are indeed valid p-values.
Demonstration that p1∗ = p12 . We now proceed to show that p12 , the p-value comparing the
winner to the runner-up, is the largest of all p1j . Without loss of generality, it is sufficient to
show that p12 ≥ p13 .
From the first part of this proof, both p-values are constructed by conditioning on X\{1,2,3} .
Upon conditioning these, (X1 , X2 , X3 ) follows an exponential family distribution, with carrier
distribution
gX4 ,...,Xn (X1 , X2 , X3 ) = g (X1 , . . . , Xn ) ,
here X4 , . . . , Xn are used in the subscript as they are conditioned on and no longer considered
as variables. The first point in Lemma 2 says that the function gX4 ,...,Xn is Schur-concave as
well. We have reduced the problem to the case when n = 3: we can apply the result for n = 3
to gX4 ,...,Xn to yield p12 ≥ p13 for n > 3.
We have reduced to the case when n = 3. The p-values thus are
R∞
g (M12 + z, M12 − z, X3 ) dz
12
p12 = RD∞
,
0 g (M12 + z, M12 − z, X3 ) dz
R∞
g (M13 + z, X2 , M13 − z) dz
p13 = R ∞ D13
max{X2 −M13 ,0} g (M13 + z, X2 , M13 − z) dz
The maximum in the denominator of p13 prompts us to consider two separate cases. First,
we suppose X2 < M13 . Changing variables such that the lower limits of both integrals in the
numerator are 0, we can re-parametrize the integrals above to give
R∞
g (X1 + z, X2 − z, X3 ) dz
p12 = R ∞0
0 g (M12 + z, M12 − z, X3 ) dz
R∞
g (X1 + z, X2 − z, X3 ) dz
= R ∞0
,
−D12 g (X1 + z, X2 − z, X3 ) dz
R∞
g (X1 + z, X2 , X3 − z) dz
p13 = R ∞0
0 g (M13 + z, X2 , M13 − z) dz
R∞
g (X1 + z, X2 , X3 − z) dz
= R ∞0
.
−D13 g (X1 + z, X2 , X3 − z) dz
To help see the re-parametrization, each of these integrals can be thought of in terms of integrals
along segments and rays. For example p12 can be represented in terms of integrals A and B in
Figure 1. Specifically,
B
p12 =
A+B
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

11

RANK VERIFICATION FOR EXP. FAMILIES

(M12 , M12 , X3 )
A
(X1 , X2 , X3 )
+ (0, 1, 0)

X=

X1 +X2 +X3
, X, X
3



B

+ (1, 0, 0)

+ (0, 0, 1)

A1
Fig 1. The p-value p12 can be written in terms of integral A along the segment and B along the ray. The diagram
is drawn a level set of x1 + x2 + x3 . The green region represents the selection event A1 .

Figure 2 has both the p-values shown on the same diagram. Proving p12 ≥ p13 is the same
as proving
B
D
B
D
≥
⇐⇒
≥ .
A+B
C +D
A
C
We will prove so by extending A to include Ã on the diagram. We denote the sum A + Ã as
A0 . Formally,
Z 0
Z 0
0
(5)
A =
g (X1 + z, X2 − z, X3 ) dz ≥
g (X1 + z, X2 − z, X3 ) dz = A.
−D13

−D12

It is thus sufficient to show that B ≥ D and C ≥ A0 .
Indeed from the second point in Lemma 2 we have
(X1 + z, X2 − z, X3 )  (X1 + z, X2 , X3 − z)
for z ≤ 0 and the majorization reversed for z ≥ 0. This majorization relation is indicated as
the dotted line in Figure 2. So Schur-concavity shows that
g (X1 + z, X2 − z, X3 ) ≤ g (X1 + z, X2 , X3 − z)
for z ≤ 0, and the inequality reversed for z ≥ 0. Taking integrals on both sides yields the
desired inequality.
For the second case where X2 ≥ M13 , the segment C will reach the line x1 = x2 first before
it reaches x1 = x3 , ending at (X2 , X2 , X1 − X2 + X3 ) instead. But we can still extend A by
Ã to (X2 , X1 , X3 ). The rest of the proof follows. In either cases, p12 ≥ p13 , or in generality,
p12 ≥ p1j for j > 1. In other words, p12 = p1∗ .
p12 is an unadjusted pairwise p-value. Before conditioning on A1 , the distribution in (3) is
symmetric around 0 under θ1 = θj . Since the denominator of p12 integrates over half of this
symmetric distribution, it is always equal to 1/2. Thus, the one-sided conditional test at level
α is equivalent to the one-sided unadjusted test at level α/2, or equivalently the two-sided
unadjusted pairwise test at level α.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

12

K. HUNG AND W. FITHIAN

(M13 , X2 + D13 , X3 )
(M12 , M12 , X3 )
D

Ã
A

C







(X1 , X2 , X3 )

B

(M13 , X2 , M13 )

A1
Fig 2. The p-value p12 can be written in terms of integral A along the segment and B along the ray; and p13 in
terms of C and D. A0 would refer to the sum of A with the dashed line portion labeled as Ã, formally explained
in Equation (5). The majorization relation is indicated by the dotted line.

Modification for counting measure. Now suppose the exponential family is defined on the
counting measure instead. If ties are broken independently and randomly, the end points on
the rays can be considered as “half an atom” if the coordinates are integers (or a smaller
fraction of an atom in case of a multi-way tie). The number of atoms on each ray is the same
(after the extension Ã) and the atoms on each ray can be paired up in exactly the same way
as illustrated in Figure 2, with the inequalities above still holding for each pair of the atoms.
Summing these inequalities yields our desired result.
3.1. Power Comparison in the Multinomial Case. As the construction of this test follows
Fithian, Sun and Taylor (2014), it uses UMPU selective level-α tests for the pairwise p-values.
This section compares the power of our procedure to the best previously known method for
verifying multinomial ranks, by Gupta and Nagel (1967). They devise a rule to select a subset
that includes the maximum πj . In other words, if the selected subset is J (X), it guarantees
"
#
(6)

P arg max πj ∈ J (X) ≥ 1 − α.
j

This is achieved by finding an integer d, as a function on m, n and α, and selecting the subset


J (X) = j : Xj ≥ max Xk − d .
k

We take d(m, n, α) to be the smallest integer such that (6) holds for any π; Gupta and Nagel
(1967) provide an algorithm for determining d.
Subset selection is closely related to testing whether the winner is the best. In particular,
we can define a test that declares j the best whenever J (X) = {j}. If J (X) satisfies (6), this
test is valid at level α. We next compare the power of the resulting test against the power of
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

13


our Procedure 1 in a multinomial example with π ∝ eδ , 1, . . . , 1 , for several combinations of
m and n.
Figure 3 gives the power curves for Multinomial (m, π) and


π ∝ eδ , 1, . . . , 1 ,
for various combinations of m and n. For their method, we use α = 0.05; but in light of the extra
n
factor of n−1
n in (2), we will apply the selective procedure with n−1 α such that the marginal
type I error rate of both procedures are controlled at α. Their test coincides with our test at
n = 2; however as n grows, the selective test shows significantly more power than Gupta and
Nagel’s test.

Fig 3. Power curves as a function of δ. The plots in the first row all have m = 50 and the second row m = 250.
The solid line and the dashed line are the power for the selective test and Gupta and Nagel’s test, respectively.

To interpret, e.g., the upper right panel of Figure 3, suppose that in a poll of m = 50
respondents, one candidate enjoys 30% support and the other n − 1 = 9 split the remainder
0.3
(δ = log 0.7/9
≈ 1.35). Then our procedure has power approximately 0.3 to detect the best
candidate, while Gupta and Nagel’s procedure has power around 0.1.
To understand why our method is more powerful, note that both procedures operate by
comparing X[1] − X[2] to some threshold, but the two methods differ in how that threshold
is determined. The threshold from Gupta and Nagel (1967) is fixed and depends on m and n
alone, whereas in our procedure the threshold depends on X[1] + X[2] , a data-adaptive choice.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

14

K. HUNG AND W. FITHIAN

The difference between the two methods is amplified when n is large and π(1)  1/2. In
that case, d from Gupta and Nagel is usually computed based on the worst-case scenario
π = 12 , 12 , 0, . . . , 0 ; i.e. d is the upper α quantile of


1
≈ Normal (0, m) .
X1 − X2 ∼ m − 2 · Binomial m,
2
√
Thus d ≈ mzα , where zα is the upper α quantile of a standard Gaussian. On the other hand,
n
our method defines a threshold based on the upper n−1
· α2 quantile of


1
X1 − X2 | X1 + X2 ∼ X1 + X2 − 2 · Binomial X1 + X2 ,
,
2
√
which is approximately X1 + X2 zα/2 . If π(1)  1/2 then with high probability X1 + X2  m,
making our test much more liberal.
4. Confidence Bounds on Differences: By How Much?. By generalizing the above,
we can construct a lower confidence bound for θ[1] − maxj6=[1] θj . Here we provide a more
powerful Procedure 2’ first. We will proceed by inverting a statistical test of the hypothesis
δ
H0[1]
: θ[1] − maxj6=[1] θj ≤ δ, which can be written as a union of null hypotheses:
δ
H0[1]
=

[

H0[1]j : θ[1] − θj ≤ δ.

j6=[1]

By Lemma 4, we can construct selective exact one-tailed p-values pδ[1]j for each of these by
conditioning on A[1] , M[1]j and X\{[1],j} , giving us an exact test for H0[1] by rejecting whenever
maxj6=[1] pδ[1]j < α.
Theorem 6.

The p-values constructed above satisfy pδ[1][2] ≥ pδ[1]j for any j 6= [1].

Proof. Again we start with assuming X1 ≥ X2 ≥ maxj>2 Xj for convenience. The p-values
in question are derived from the conditional law
Lθ1 −θj =δ (D1j | M1j , X2 , . . . , Xn , A) ,
which is the truncated distribution
p (d1j ) ∝ exp ((θ1 − θj ) d1j + θ2 X2 + · · · + (θ1 + θj ) M1j + · · · + θn Xn )
g (M1j + d1j , X2 , . . . , M1j − d1j , . . . Xn ) 1A1
∝ exp (δd1j ) g (M1j + d1j , X2 , . . . , M1j − d1j , . . . Xn ) 1A1 .
The p-values thus are
R∞
pδ1j = R ∞

D1j

exp (δz) g (M1j + z, X2 , . . . , M1j − z, . . . , Xn ) dz

max{X2 −M1j ,0} exp (δz) g (M1j

+ z, X2 , . . . , M1j − z, . . . , Xn ) dz

.

imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

15

As before in Part 1 of Theorem 1, the conditioning reduces to the case where n = 3. Once
again it is sufficient to show that p12 ≥ p13 . We have the same two cases. If X2 < M13 , then
R∞
exp (δ (z + D12 )) g (X1 + z, X2 − z, X3 ) dz
δ
p12 = R ∞0
−D12 exp (δ (z + D12 )) g (X1 + z, X2 − z, X3 ) dz
R∞
exp (δz) g (X1 + z, X2 − z, X3 ) dz
= R ∞0
−D12 exp (δz) g (X1 + z, X2 − z, X3 ) dz
R∞
exp (δ (z + D13 )) g (X1 + z, X2 , X3 − z) dz
δ
p13 = R ∞0
−D13 exp (δ (z + D13 )) g (X1 + z, X2 , X3 − z) dz
R∞
exp (δz) g (X1 + z, X2 , X3 − z) dz
= R ∞0
.
−D13 exp (δz) g (X1 + z, X2 , X3 − z) dz
The same argument in Figure 2 shows that pδ12 ≥ pδ13 . This is again true for the case where
X2 ≥ M13 as well.
In other words, Procedure 2’ can be summarized as: Find the minimum δ such that pδ[1][2] ≤ α.
And by construction, Procedure 2’ gives exact 1 − α confidence bound for θ[1] − maxj6=[1] θj .
Part 2 of Theorem 1. Assume the model (1) holds and g (x) is a Schur-concave function.
Procedure 2 (the lower bound of unadjusted pairwise confidence interval) gives a conservative
1 − α lower confidence bound for θ[1] − maxj6=[1] θj .
Proof. When Procedure 2 reports −∞ as a confidence lower bound, it is definitely valid
and conservative. It remains to show that when Procedure 2 reports a finite confidence lower
bound, it is smaller than the confidence lower bound reported by Procedure 2’.
If Procedure 2 reports a finite confidence lower bound δ ∗ , then δ ∗ ≥ 0. Also
R∞
exp (δ ∗ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
α
(7)
= RD∞12
∗
2
−∞ exp (δ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
as Procedure 2 is constructed from an unadjusted two-tail pairwise confidence interval. However,
as δ ∗ ≥ 0, we have
R0
exp (δ ∗ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
R−∞
≤1
∞
∗
0 exp (δ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
R∞
exp (δ ∗ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
R−∞
≤ 2.
∞
∗
0 exp (δ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
Multiplying this to (7), we have
R∞
exp (δ ∗ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
12
α ≥ RD∞
,
∗
0 exp (δ z) g (M12 + z, X2 , . . . , M12 − z, . . . , Xn ) dz
indicating that δ ∗ is smaller than the confidence bound that Procedure 2’ would report. Hence
δ ∗ is a valid and conservative.
Note that Procedure 2 reporting −∞ in case of δ ∗ ≤ 0 is rather extreme. In reality, we can
always just adopt Procedure 2’ in the case when Procedure 1 rejects. In fact, by Procedure 2’,
the multinomial example for polling in Section 1.1 can give a stronger lower confidence bound,
that πTrump / maxj6=Trump πj ≥ 1.108 (Trump leads the field by at least 10.8%).
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

16

K. HUNG AND W. FITHIAN

5. Verifying Other Ranks: Is the Runner-Up Really the Second Best, etc.?. Often we will be interested in verifying ranks beyond the winner. More generally, we could imagine
declaring that the first j populations are all in the correct order, that is
θ[1] > · · · > θ[j] > max θ[k] .

(8)

k>j

Let j0 denote the largest j for which (8) is true. Note that j0 is both random and unknown,
because it depends on both the data and population ranks. Procedure 3 declares that j0 ≥ j if
the unadjusted pairwise tests between X[k] and X[k+1] , reject at level α for all of k = 1, . . . , j.
In terms of the Iowa polling example of Section 1, we would like to produce a statement of the
form “Trump has the most support, Cruz has the second-most, and Rubio has the third-most.”
Procedure 3 performs unadjusted pairwise tests to ask if Cruz is really the runner-up upon
verifying that Trump is the best, and if Rubio is really the second runner-up upon verifying
that Cruz is the runner-up, etc., until we can no longer infer that a certain population really
holds its rank.
While we aim to declare more populations to be in the correct order, declaring too many
populations, i.e. out-of-place populations, to be in the right order is undesirable. It is possible to
consider false discovery rate (the expected portion of out-of-place populations declared) here,
but we restrict our derivation to FWER (the probability of having any out-of-place populations
declared).
Formally, let ĵ0 denote the number of ranks validated by a procedure (the number of rejections).
h
iThen the FWER of ĵ0 is the probability that too many rejections are made; i.e.
P ĵ0 > j0 . For example, suppose that the top three data ranks and population ranks coincide,
but not the fourth (j0 = 3). Then we will have made a Type I error if we declare that the top
five ranks are correct (ĵ0 = 5), but not if we declare that the top two are correct (ĵ0 = 2). In
other words, ĵ0 is a lower confidence bound for j0 .
To show that Procedure 3 is valid, we will prove the validity of a more liberal Procedure 3’,
described in Algorithm 1. Procedure 3 is equivalent
to Procedure 3’ for the most part, except

that Procedure 3 conditions on a larger event X[j] ≥ maxk>j X[k] in Line 7.
Theorem 7. Procedure 3’ is a stepwise procedure that an estimate ĵ0 of j0 at the FWER
controlled at α, where j0 is given by


j0 = max θ[1] > · · · > θ[j] > max θ[k] .
j

k>j

Proof. We will first show that Procedure 3’ falls into the sequential goodness-of-fit testing
framework proposed by Fithian, Taylor and Tibshirani (2015). We thus analyze Procedure 3’ as
a special case of the BasicStop procedure on random hypothesis, described in the same paper.
This enables us to construct valid selective p-values and derive Procedure 3’.
Application of the sequential goodness-of-fit testing framework.
X[n] , we can set up a sequence of nested models
M1 (X) ⊆ · · · ⊆ Mn (X) ,

Upon observing X[1] ≥ · · · ≥



where Mj (X) = θ : θ[1] > · · · > θ[j] > max θ[k] .
c

k>j

imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

17

Algorithm 1. Procedure 3’, a more liberal version of Procedure 3

1

2
3
4
5
6
7
8

input : X1 , . . . , Xn
output: ĵ0 , an estimate for j0
# Initialization
τj ← [j];
# Consider τj as part of the observation and the fixed realization of the random index [j]
Xτ0 ← ∞;
j ← 0;
rejected ← true;
while rejected do
j ← j + 1;
Dτj ← Xτj − Xτj+1 ;
Set up the distribution of Dτj τj+1 , conditioned on
• the variables Xτ1 , . . . , Xτj−1 , Xτj+2 , . . . , Xτn ] , and

• the event Xτj−1 ≥ Xτj ≥ maxk>j Xτk ) ;
# The distribution of Dτj τj+1 depends only on θτj − θτj+1 now
test H0 : θτj − θτj+1 ≤ 0 against H1 : θτj − θτj+1 > 0 according to the distribution of Dτj τj+1 ;
Set rejected as the output of the test;

9

10
11

end
ĵ0 ← j − 1;

If we define the j-th null hypothesis as
e 0j : θ[j] ≤ max θ[k] ,
H
k>j

e 01 , . . . , H
e 0j are all false if and only if θ ∈
then H
/ Mj (X).
In other words, Mj (X) is a family of distributions that does not have all first j ranks correct.
e 0j , stating that without
As we will see later, each step in Procedure 3’ is similar to testing H
the first j ranks correct, it is hard to explain the observations. Thus, returning ĵ0 = j amounts
e 01 , . . . , H
e 0j , or equivalently determining that the models M1 (X), . . . , Mj (X) do
to rejecting H
not fit the data.
e 0j provided intuition in the setting up the nested models, they
While the null hypotheses H
are rather cumbersome to work with. Inspired by Fithian, Taylor and Tibshirani (2015), we
will instead consider another sequence of random hypothesis that are more closely related to
the nest models,
H0j : θ ∈ Mj (X) ,
or equivalently, that θ[1] , . . . , θ[j] are not the best j parameters
in order. 

Adapting this notation, the FWER can be viewed as P reject H0(j0 +1) .
Special case of the BasicStop procedure. While impractical, Procedure 3’ can be thought of as
performing all n tests first, producing a sequence of p-values pj , and returning
(9)

ĵ0 = min {j : pj > α} − 1.

This is a special case of the BasicStop procedure. Instead of simply checking that Procedure
3’ fits all the requirement for FWER control in BasicStop, we will give the construction of
Procedure 3’, assuming that we are to estimate j0 with BasicStop.

imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

18

K. HUNG AND W. FITHIAN

In general, the FWER for BasicStop can be rewritten as P [pj0 +1 ≤ α]. This is however
difficult to analyze, as j0 itself is random and dependent on X, thus we break the FWER down
as follows:
X
P [pj0 +1 ≤ α] =
P [pj0 +1 ≤ α | j0 = j] P [j0 = j]
j

=

X

=

X

P [pj+1 ≤ α | j0 = j] P [j0 = j]

j

P [pj+1 ≤ α | θ ∈ Mj+1 (X) \ Mj (X)] P [j0 = j] .

j

We emphasize here that θ is not random, but Mj+1 is. Thus it suffices to construct the p-values
such that
(10)

P [pj ≤ α | θ ∈ Mj (X) \ Mj−1 (X)] ≤ α

for all j.

Considerations for conditioning. By smoothing, we are free to condition on additional variables in (10). A logical choice that simplified (10) is conditioning on the variables Mj−1 (X)
and Mj (X). Note that the choice of the model Mj (X), once again, based solely on the random
indices [1], . . . , [j], so conditioning on both Mj−1 (X) and Mj (X) is equivalent to conditioning
on the random indices [1], . . . , [j], which in turns is equivalent to conditioning on the σ-field
generated by the partition of the observation space X



Xτ1 ≥ · · · ≥ Xτj ≥ max Xτk : τ is any permutation of (1, . . . , n) ,
k>j

or colloquially, the set of all possible choices 
of [1], . . . , [j]. Within each set in this partition,
the event {θ ∈ Mj (X) \ Mj−1 (X)} is simply θτ1 > · · · > θτj and θτj ≤ maxk>j θτk , a trivial
event.
As a brief summary, we want to construct p-values pj such that


pj ≤ α Xτ1 ≥ · · · ≥ Xτj ≥ max Xτk .
P θτ1 >···>θτj
θτj ≤maxk>j θτk

k>j

Construction of the p-values. To avoid the clutter in the subscripts, we will drop the τ in the
subscript. Hence our goal is now


P θ1 >···>θj
pj ≤ α X1 ≥ · · · ≥ Xj ≥ max Xk
θj ≤maxk>j θk

k>j

Construction of pj for other permutations τ can be obtained similarly.
There are many valid options for pj (such as constant α). We will follow the idea in the proof
of Part 1 of Theorem 1 here. pj is intended to test H0j : θ ∈ Mj (X), which is equivalent to
the union of the null hypotheses:
1. θk ≤ θk+1 for k = 1, . . . , j − 1, and
e 0j .)
2. θj ≤ θk for k = j + 1, . . . , n. (The union of these null hypotheses is H

imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

19

RANK VERIFICATION FOR EXP. FAMILIES

Since the joint distribution of X, restricted to {X1 ≥ · · · ≥ Xj ≥ maxk>j Xk }, remains in
the exponential family, we can construct the p-values for each of the hypotheses above by
conditioning on the variables corresponding to the nuisance parameters here, similar to the
proof of Part 1 of Theorem 1. Then we can take pj as the maximum of such p-values.
For the hypothesis H0jk : θj ≤ θk , we can construct pjk , by considering the survival function
of the conditional law




X1 ≥ · · · ≥ Xj ≥ max X` , X\{j,k} , Mjk
Lθj =θk Djk
`>j






= Lθj =θk Djk
X
≥ Xj ≥ max X` and Xj ≥ Mjk , X\{j,k} , Mjk 

 j−1
`>j
`6=k

Once again, Xj+1 = max`>j X` is simply shorthand for simplifying our notation. Now the
p-values are similar to the ones in Equation (4), for k > j:
R Xj−1

Djk g (X1 , . . . , Mjk + z, . . . , Mjk − z, . . . , Xn ) dz
pjk = R X
.
j−1
g
(X
,
.
.
.
,
M
+
z,
.
.
.
,
M
−
z,
.
.
.
,
X
)
dz
1
n
jk
jk
max{Xj+1 −Mjk ,0}

We can graphically represent pjk in Figure 4, a diagram analogous to Figure 2.

D

C

B







(Xj , Xj+1 , Xk )

Truncation for Xj ≤ Xj−1

(Mjk , Xj+1 + Djk , Xk )

Mj(j+1) , Mj(j+1) , Xk
Ã
A

(Mjk , Xj+1 , Mjk )

A1
Fig 4. The two p-values constructed corresponds to taking integrals of g along these segments, that lie on a level
set of xj + xj+1 + xk . The dashed line corresponds to extension in (5). The dotted line on the far right is the
truncation that enforces Xj < Xj−1 .

We have pj(j+1) ≥ maxk>j pjk by Section 3: the upper truncation for Xj can be represented
by cropping Figure 2 along a vertical line, shown in Figure 4. Considering pj(j+1) is sufficient in
rejecting all the H0jk . We will take pj∗ = pj(j+1) , noting that this is the p-value that Procedure
3’ would produce. In fact, pj∗ is also the p-value we would have constructed if we were to reject
e 0j .
only H
Upon constructing pj , one should realize that the p-values for testing θk ≤ θk+1 would have
been constructed in earlier iterations of BasicStop, as pk∗ . In other words, pj = maxk≤j pk∗ is
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

20

K. HUNG AND W. FITHIAN

the sequence of p-values that works with BasicStop. However, from (9),


ĵ0 = min j : max pk∗ > α − 1 = min {j : pj∗ > α} − 1,
k≤j

so it is safe to apply BasicStop to pj∗ directly, yielding Procedure 3’.
Part 3 of Theorem 1. Assume the model (1) holds and g (x) is a Schur-concave function.
Procedure 3 is a conservative stepwise procedure with FWER no larger than α.
Proof. The p-values pj(j+1) obtained in Procedure 3’ are always smaller than their counterpart in Procedure 3, as the upper truncation at Xj−1 is on the upper tail. Therefore Procedure
3 is conservative and definitely valid.
6. Discussion. Combining ideas from conditional inference and multiple testing, we have
proven the validity of several very simple and seemingly “naive” procedures for significance
testing of sample ranks. In particular, we have shown that an unadjusted pairwise test comparing the winner with the runner-up is a valid significance test for the first rank. Our result
complements and extends pre-exisiting analogous results for location and location-scale families with independence between observations. Our approach is considerably more powerful than
previously known solutions. We provide similarly straightforward conservative methods for producing a lower confidence bound for the difference between the winner and runner up, and for
verifying ranks beyond the first.
Claims reporting the “winner” are commonly made in the scientific literature, usually with
no significance level reported or an incorrect method applied. For example, Uhls and Greenfield
(2012) asked n = 20 elementary and middle school students which of seven personal values they
most hoped to embody as adults, with “Fame” (8 responses) being the most commonly selected,
with “Benevolence” (5 responses) second. The authors’ main finding — which appeared in the
abstract, the first paragraph of the article, and later a CNN.com headline (Alikhani, 2011) —
was that “Fame” was the most likely response, accompanied by a significance level of 0.006,
which the authors computed by testing whether the probability of selecting “Fame” was larger
than 1/7. The obvious error in the authors’ reasoning could have been avoided if they had
performed an equally straightforward two-tailed binomial test of “Fame” vs. “Benevolence,”
which would have produced a p-value of 0.58.
Reproducibility. A git repository containing with the code generating the image in this
paper is available at https://github.com/kenhungkk/verifying-winner.
References.
Alikhani, L. (2011). Study: Tween TV today is all about fame.
Berger, R. L. (1980). Minimax subset selection for the multinomial distribution. Journal of Statistical Planning
and Inference 4 391–402.
Berger, R. L. (1982). Multiparameter hypothesis testing and acceptance sampling. Technometrics.
Besag, J. and Clifford, P. (1989). Generalized monte carlo significance tests. Biometrika 76 633–642.
Bofinger, E. (1991). Selecting “Demonstrably best” or “Demonstrably worst” exponential population. Australian Journal of Statistics 33 183–190.
Edwards, D. G. and Hsu, J. C. (1983). Multiple comparisons with the best treatment. Journal of the American
Statistical Association 78 965–971.
Finner, H. and Strassburger, K. (2002). The partitioning principle: a powerful tool in multiple decision
theory. The Annals of Statistics 30 1194–1213.
imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

RANK VERIFICATION FOR EXP. FAMILIES

21

Fithian, W., Sun, D. L. and Taylor, J. E. (2014). Optimal Inference After Model Selection. arXiv.org.
Fithian, W., Taylor, J. E. and Tibshirani, R. J. (2015). Selective Sequential Model Selection. arXiv.org.
Gupta, S. S., Huang, D.-Y. and Panchapakesan, S. (1984). On some inequalities and monotonicity results
in selection and ranking theory. In Inequalities in statistics and probability (Lincoln, Neb., 1982) 211–227.
Inst. Math. Statist., Hayward, CA, Hayward, CA.
Gupta, S. S. and Liang, T. (1989). Selecting the best binomial population: parametric empirical Bayes approach. Journal of Statistical Planning and Inference 23 21–31.
Gupta, S. S. and Nagel, K. (1967). On selection and ranking procedures and order statistics from the multinomial distribution. Sankhyā: The Indian Journal of Statistics 29.
Gupta, S. S. and Panchapakesan, S. (1971). On Multiple Decision (Subset Selection) Procedures Technical
Report, Purdue University.
Gupta, S. S. and Panchapakesan, S. (1985). Subset Selection Procedures: Review and Assessment. American
Journal of Mathematical and Management Sciences 5 235–311.
Gupta, S. S. and Wong, W.-Y. (1976). On Subset Selection Procedures for Poisson Processes and Some
Applications to the Binomial and Multinomial Problems Technical Report.
Gutmann, S. and Maymin, Z. (1987). Is the selected population the best? The Annals of Statistics 15 456–461.
Hsu, J. C. (1984). Constrained Simultaneous Confidence Intervals for Multiple Comparisons with the Best. The
Annals of Statistics 12 1136–1144.
Hsu, J. (1996). Multiple comparisons: theory and methods. CRC Press.
Quinnipiac University Poll Institute (2016). First-Timers Put Trump Ahead In Iowa GOP Caucus, Quinnipiac University Poll Finds; Sanders Needs First-Timers To Tie Clinton In Dem Caucus.
Karnnan, N. and Panchapakesan, S. (2009). Does the Selected Normal Population Have the Smallest Variance? American Journal of Mathematical and Management Sciences 29 109–123.
Marshall, A. W., Olkin, I. and Arnold, B. (2010). Inequalities: Theory of Majorization and Its Applications.
Springer Series in Statistics. Springer, New York, NY.
Maymin, Z. and Gutmann, S. (1992). Testing retrospective hypotheses. The Canadian Journal of Statistics.
La Revue Canadienne de Statistique 20 335–345.
Nettleton, D. (2009). Testing for the supremacy of a multinomial cell probability. Journal of the American
Statistical Association 104 1052–1059.
Ng, H. K. T. and Panchapakesan, S. (2007). Is the selected multinomial cell the best? Sequential Analysis
26 415–423.
Stefansson, G., Kim, W.-C. and Hsu, J. C. (1988). On confidence sets in multiple comparisons. In Statistical
Decision Theory and Related Topics IV 89–104. . . . Decision Theory and . . . .
Uhls, Y. T. and Greenfield, P. M. (2012). The value of fame: preadolescent perceptions of popular media
and their relationship to future aspirations. Developmental psychology.
Department of Mathematics
951 Evans Hall, Suite 3840
Berkeley, CA 94720-3840
E-mail: kenhung@berkeley.edu

Department of Statistics
301 Evans Hall
Berkeley, CA 94720
E-mail: wfithian@berkeley.edu

imsart-aos ver. 2014/10/16 file: verifying-winner.tex date: July 4, 2017

