Separation Proof for Finite Decision Problems

Why Separation Produces a Prior

In a finite-state decision problem, each rule has a finite risk vector: one coordinate for each possible state of nature. A rule is admissible if no other available rule has risk no greater in every state and strictly smaller in at least one. The geometry of these vectors makes it possible to ask a useful question: can an admissible rule be recognized as minimizing an average of its statewise risks?

The answer follows from convex separation. Randomization makes the attainable risks convex, while the set of vectors strictly smaller than a given risk vector in every coordinate is an open convex orthant. If the given rule is admissible, these sets do not meet. A separating hyperplane then supplies nonnegative coefficients; after normalization, those coefficients are a prior distribution.

Finite Risk Sets and the Separation Result

For the finite result below, assume there are finitely many deterministic rules and that randomized mixtures of those rules are allowed. A mixture selects one of the rules using a randomization independent of the state and data. Its risk vector is the corresponding convex combination of their risk vectors. Thus the attainable risk set \(C\) is the convex hull of finitely many vectors; in particular, it is compact and convex. Admissibility here is assessed among these randomized rules.

For \(r\in C\), write \(O_r=\{x\in\mathbb{R}^m:x_i<r_i\text{ for every }i\}\). This is the open orthant of risks strictly below \(r\) in every state. If \(r\) is admissible, then \(C\cap O_r=\varnothing\): any vector in that intersection would dominate \(r\), with strict improvement in every coordinate.

Proof. The set \(C\) is convex, and \(O_r\) is open and convex. They are disjoint by admissibility. The finite-dimensional separating-hyperplane theorem for a convex set and a disjoint open convex set gives a nonzero vector \(w\) such that \(w\cdot c\ge w\cdot o\) for every \(c\in C\) and \(o\in O_r\).

Each coordinate of \(w\) must be nonnegative. If, for example, \(w_j<0\), we could keep all coordinates of \(o\) except \(o_j\) fixed and let \(o_j\) tend to \(-\infty\). Since \(o\in O_r\), this is permitted, and \(w\cdot o\) would tend to \(+\infty\). That contradicts \(w\cdot c\ge w\cdot o\) for a fixed \(c\in C\). Therefore \(w_i\ge0\) for every \(i\).

For such a nonzero \(w\), the supremum of \(w\cdot o\) over \(o\in O_r\) is \(w\cdot r\). Indeed, \(o_i<r_i\) and \(w_i\ge0\) imply \(w\cdot o\le w\cdot r\); taking \(o=r-\varepsilon(1,\ldots,1)\) and letting \(\varepsilon\) decrease to zero gives values tending to \(w\cdot r\). The separating inequality therefore implies \(w\cdot c\ge w\cdot r\) for every \(c\in C\). Because \(w\ne0\) and \(w_i\ge0\), \(\sum_i w_i>0\). Dividing by this sum gives prior probabilities. The inequality says exactly that \(r\) minimizes the prior-weighted risk over \(C\). \(\square\)

Worked Risk-Vector Calculations

From the Theorem to a Complete-Class Statement

The theorem gives a useful finite complete-class conclusion. Let \(C\) be the attainable randomized risk set. Every admissible risk vector in \(C\) is Bayes for at least one prior, possibly one that assigns zero probability to some states. Also, every risk vector in \(C\) is weakly dominated by an admissible vector in \(C\).

To see the second claim, fix \(r\in C\) and consider \(K=\{c\in C:c_i\le r_i\text{ for all }i\}\). This set is nonempty because it contains \(r\), and it is compact because it is a closed subset of the compact set \(C\). Choose \(q\in K\) minimizing the coordinate sum \(\sum_i q_i\). If some \(t\in C\) weakly dominated \(q\) with at least one strict improvement, then \(t_i\le q_i\le r_i\) for every \(i\), so \(t\in K\), while \(\sum_i t_i<\sum_i q_i\). This contradicts the choice of \(q\). Therefore \(q\) is admissible and weakly dominates \(r\). The admissible rules consequently form a complete class in the sense that each attainable risk vector is weakly dominated by one in that class.

These two claims fit together: admissible vectors are Bayes for some prior, and every vector can be replaced by an admissible one without increasing any coordinate. They do not say that every Bayes rule for every prior is admissible. The zero-probability example shows why that stronger assertion would be false.

Common Pitfall: Confusing Supporting Weights with Strict Positivity

A separation argument guarantees coefficients that are nonnegative and not all zero. It does not, by itself, guarantee that every coefficient is positive. After normalization, the result is a prior that may put zero mass on some states. This distinction matters: a zero-weight state does not affect the weighted-risk comparison, so improvements confined to that state can go undetected.

A related mistake is to infer admissibility from the fact that a rule is Bayes for an arbitrary prior. The correct implication in this finite setting is that a rule Bayes for a prior with strictly positive probabilities is admissible. For a prior with zero probabilities, Bayes optimality alone is not enough; the rule must be checked for domination on all states.