Minimax Interchange for Finite Parameter Sets

Why a Finite Parameter Set Simplifies Minimax Problems

When the parameter can take only finitely many values, each decision rule has a finite list of risks: one risk for each parameter value. This turns a statistical minimax problem into a geometric problem about a set of vectors in finite-dimensional space. Under suitable compactness and convexity conditions, the largest risk that a rule can have equals the best worst-case Bayes risk achievable by putting a prior distribution on the parameter set.

The interchange is useful because it gives two complementary ways to study the same value. One minimizes the largest coordinate of a risk vector; the other chooses a prior to make the smallest prior-weighted risk as large as possible. The assumptions matter: a finite parameter set alone does not guarantee the equality.

Risk Vectors and the Minimax Value

A prior on this finite parameter set is a vector \(\pi=(\pi_1,\ldots,\pi_m)\) in the probability simplex \(\Delta_m=\{\pi\in\mathbb R^m:\pi_i\ge 0,\ \sum_i\pi_i=1\}\). The prior-weighted risk of \(\delta\) is \(\sum_i\pi_iR(\theta_i,\delta)\). Its infimum over rules is the Bayes risk for \(\pi\), whether or not a minimizing rule exists.

For the finite-dimensional interchange below, assume that \(C\) is nonempty, compact, and convex. Compactness ensures finite risks and attainment of the minimum of any continuous function on \(C\). Convexity is naturally supplied by randomization: choosing between two rules using an independent random device produces the corresponding convex combination of their risk vectors. The assumption is on the attainable risk set; it need not mean that the original collection of nonrandomized rules is convex.

The Finite-Parameter Minimax Interchange

Here is a finite-dimensional separation proof. Let \(t_*=\min_{r\in C}\max_i r_i\). This minimum exists because \(C\) is compact and \(r\mapsto\max_i r_i\) is continuous. Let \(Q=\{q\in\mathbb R^m:q_i<t_*\text{ for every }i\}\). This is an open convex set disjoint from \(C\): if \(r\) were in both, then \(\max_i r_i<t_*\), contradicting the definition of \(t_*\).

By the separating-hyperplane theorem for disjoint convex sets when one set is open, there are a nonzero vector \(a\in\mathbb R^m\) and a real number \(\alpha\) such that \(a\cdot r\ge\alpha\ge a\cdot q\) for every \(r\in C\) and \(q\in Q\). Each coordinate \(a_i\) must be nonnegative. Indeed, if \(a_j<0\), taking \(q_j\) arbitrarily far below \(t_*\), while holding the other coordinates below \(t_*\), would make \(a\cdot q\) arbitrarily large, contradicting \(a\cdot q\le\alpha\). Thus \(\sum_i a_i>0\). The supremum of \(a\cdot q\) over \(Q\) is \(t_*\sum_i a_i\): all coordinates of \(q\) are below \(t_*\), and they can approach \(t_*\) from below. It follows that \[ a\cdot r\ge\alpha\ge t_*\sum_i a_i\qquad(r\in C). \] Define \(\pi_i=a_i/\sum_j a_j\). Then \(\pi\in\Delta_m\), and \(\sum_i\pi_i r_i\ge t_*\) for every \(r\in C\). Consequently, \(\min_{r\in C}\sum_i\pi_i r_i\ge t_*\).

For the reverse inequality, choose \(r_*\in C\) with \(\max_i(r_*)_i=t_*\). For every \(\pi\in\Delta_m\), \(\min_{r\in C}\sum_i\pi_i r_i\le\sum_i\pi_i(r_*)_i\le t_*\), since a weighted average of the coordinates of \(r_*\) cannot exceed their maximum. Taking the maximum over \(\pi\), together with the prior constructed by separation, proves equality.

The maximum over priors is attained as well. To see this directly, compactness of \(C\) gives a finite \(M\) such that \(|r_i|\le M\) for all \(r\in C\) and all \(i\). For any \(\pi,\pi'\in\Delta_m\), \[ |b(\pi)-b(\pi')|\le \sup_{r\in C}|(\pi-\pi')\cdot r| \le M\sum_i|\pi_i-\pi_i'|. \] Thus \(b\) is continuous. The simplex is compact, so \(b\) attains its maximum. This completes the attainment claims. \(\square\)

The proof also explains the role of the prior: the separating vector, normalized to sum to one, weights the parameter-specific risks so that every attainable risk vector has at least the minimax value under those weights.

Worked Examples

What the Interchange Does—and Does Not—Say

The theorem is a statement about values: the best worst-case risk equals the largest Bayes risk. It does not say that every prior yields the same Bayes risk, or that every Bayes rule is minimax. In the first example, most priors have Bayes risk below \(2\). The prior must maximize Bayes risk to identify the minimax value.

Nor does the theorem follow just from having finitely many parameter values. The proof used a compact, convex attainable risk set. Without convexity, the separating argument cannot be applied to the original set in this form; randomization often supplies the needed convexity. Without compactness, minima or maxima may fail to be attained, and the asserted equality with attained optimizers requires additional care.

• Common mistake: “There are finitely many parameters, so minimax equals maximum Bayes risk automatically.” Finiteness makes the risk vector finite-dimensional, but does not ensure the required compactness or convexity.
• Correction: Identify the attainable risk set and verify that it is nonempty, compact, and convex before applying the theorem. If randomization is what makes it convex, include randomized rules in the decision class.
• Common mistake: Treating a prior-weighted risk as the worst-case risk. A weighted average is generally no larger than the largest coordinate; maximizing the Bayes risk over priors is the step that recovers the minimax value under the theorem’s assumptions.