Randomized Rules and Convexified Risk Sets

Why Randomization Changes the Risk Set

A decision rule need not always choose an action with certainty. It can assign probabilities to possible actions, conditional on the observed data. There is also a second way to randomize: select one of two complete rules using an independent coin, then apply the selected rule. Either mechanism can enlarge the set of attainable risk functions. The key fact is that expected loss is linear in the probabilities used to mix rules.

This linearity matters for complete classes. A rule may not be dominated by any one deterministic rule, yet a randomized combination of rules may dominate it. To make such comparisons correctly, we need to identify the risks attainable after randomization and keep track of the class of competitors being used.

Randomized Rules and Their Risks

Definition: A randomized decision rule $q$ is a measurable probability kernel from the observation space to the action space. Thus, for observed data $x$, $q(\,\cdot\mid x)$ is a probability distribution over actions. Given a parameter $\theta$, its risk under loss $L(\theta,a)$ is $$ R(\theta,q)=E_\theta\left[\int L(\theta,a)\,q(da\mid X)\right]. $$ Assume the loss is measurable and that this expectation is well-defined and finite for every parameter and rule under discussion. For a discrete action space, the integral is the sum $\sum_a L(\theta,a)q(a\mid X)$.

A nonrandomized rule is included as a special case: its kernel puts probability one on the action the rule selects. A mixture of two rules can be implemented by first drawing an independent coin $Z$, with $P(Z=1)=\lambda$, and then using $q_1$ if $Z=1$ and $q_2$ otherwise. The resulting rule has conditional action distribution

q_\lambda(\,\cdot\mid x) =\lambda q_1(\,\cdot\mid x)+(1-\lambda)q_2(\,\cdot\mid x), \qquad 0\leq\lambda\leq 1.

This rule can also be defined directly by the displayed kernel; an external coin is one way to interpret it. The mixing probability is chosen without knowing the true parameter. In particular, $\lambda$ is the same for every $\theta$.

Theorem: For any two randomized rules $q_1,q_2$ with finite risks and any $0\leq\lambda\leq1$, their mixture satisfies $$ R(\theta,q_\lambda) =\lambda R(\theta,q_1)+(1-\lambda)R(\theta,q_2) \quad\text{for every }\theta. $$

Proof. By the definition of $q_\lambda$, conditional expected loss at $X=x$ is

\int L(\theta,a)\,q_\lambda(da\mid x) =\lambda\int L(\theta,a)\,q_1(da\mid x) +(1-\lambda)\int L(\theta,a)\,q_2(da\mid x).

Taking expectation under the same sampling distribution $P_\theta$ on both sides and using linearity of expectation gives

R(\theta,q_\lambda) =\lambda E_\theta\left[\int L(\theta,a)q_1(da\mid X)\right] +(1-\lambda)E_\theta\left[\int L(\theta,a)q_2(da\mid X)\right].

The two expectations are the risks of $q_1$ and $q_2$, respectively. Their assumed finiteness justifies the calculation. Therefore the stated identity holds for every $\theta$. $\square$

The proof uses only linearity of expected loss: the observation distribution and the loss stay fixed while the action distribution is averaged. For nonnegative losses, the expectations can also be handled as nonnegative integrals; in either case, the risks must be defined for the rules being compared.

Convexified Risk Sets

For a parameter space with finitely many values $\theta_1,\ldots,\theta_m$, represent a rule by its risk vector $r(q)=(R(\theta_1,q),\ldots,R(\theta_m,q))$. For a general parameter space, represent it by the whole function $\theta\mapsto R(\theta,q)$. The theorem says that a mixture produces the corresponding coordinatewise, or pointwise, convex combination.

Result: The risk set of a class of rules is convex if it contains every finite mixture of its rules. In particular, the set of risks attainable by allowing all finite mixtures of a given collection of rules contains every finite convex combination of their risk vectors or risk functions.

For two rules this follows directly from the theorem. For $k$ rules $q_1,\ldots,q_k$, choose nonnegative weights $w_1,\ldots,w_k$ summing to one and define the mixture kernel $q=\sum_{j=1}^k w_jq_j$. Applying the same linearity calculation gives

R(\theta,q)=\sum_{j=1}^k w_jR(\theta,q_j) \quad\text{for every }\theta.

Thus the risk set of the randomized class is the convex hull of the original risk set when all such finite mixtures are allowed. This statement concerns attainable risks; it does not say that every point in a closure or limit of that set is attained.

Worked Example: Checking a Binary-Decision Mixture

Let $\theta\in\{0,1\}$, let $X\in\{0,1\}$, and suppose $P_0(X=1)=0.2$ and $P_1(X=1)=0.8$. Actions are 0 and 1, with loss 1 for an incorrect action and 0 for a correct one. Rule $q_A$ chooses action 1 with probabilities 0.9 at $X=1$ and 0.1 at $X=0$. Rule $q_B$ chooses action 1 with probabilities 0.3 at $X=1$ and 0.7 at $X=0$. Find the risks of each rule and of the mixture $q=0.25q_A+0.75q_B$.

At $\theta=0$, action 1 is an error. Therefore $R(0,q_A)=0.2(0.9)+0.8(0.1)=0.26$, while $R(0,q_B)=0.2(0.3)+0.8(0.7)=0.62$. At $\theta=1$, action 0 is an error. Thus $R(1,q_A)=0.8(0.1)+0.2(0.9)=0.26$, and $R(1,q_B)=0.8(0.7)+0.2(0.3)=0.62$. The conditional error at $X=0$ for $q_A$ under $\theta=1$ is 0.9, not 0.1: the probability 0.1 is the chance that $q_A$ chooses the correct action 1 there.

The mixture chooses action 1 with probability $0.25(0.9)+0.75(0.3)=0.45$ at $X=1$, and with probability $0.25(0.1)+0.75(0.7)=0.55$ at $X=0$. Hence $R(0,q)=0.2(0.45)+0.8(0.55)=0.53$. For $\theta=1$, the conditional error probabilities are $1-0.45=0.55$ at $X=1$ and $1-0.55=0.45$ at $X=0$. So $R(1,q)=0.8(0.55)+0.2(0.45)=0.53$.

The result also follows by mixing the risk vectors: $0.25(0.26,0.26)+0.75(0.62,0.62)=(0.53,0.53)$. Both calculations agree. The reversal from action probabilities to error probabilities at $\theta=1$ is essential.

Pointwise Domination with Randomized Competitors

Risk comparisons are pointwise in the parameter. A rule $q$ weakly dominates a rule $d$ if $R(\theta,q)\leq R(\theta,d)$ for every $\theta$; it strictly dominates $d$ if, in addition, the inequality is strict for at least one parameter. Whether such a comparison exists can depend on the allowed class of competitors.

For clarity, call a class complete under weak pointwise replacement, relative to an ambient class, if every rule in the ambient class has some rule in the proposed class with no greater risk at any parameter. This replacement convention makes the role of randomization explicit: changing the ambient class from deterministic to randomized rules changes which risks must be replaced. Other formulations of completeness may additionally distinguish strict improvement from equality of risks.

Worked Example: A Mixture Dominates a Rule Neither Component Dominates

Consider a finite decision problem with two parameter values and three deterministic rules whose risk vectors are $r_A=(0,1)$, $r_B=(1,0)$, and $r_C=(0.6,0.6)$. Compare rule $C$ with $A$ and $B$, then allow a randomized mixture of $A$ and $B$.

Rule $A$ does not dominate $C$, because its second risk is $1>0.6$. Rule $B$ does not dominate $C$, because its first risk is $1>0.6$. Thus neither deterministic rule $A$ nor deterministic rule $B$ weakly dominates $C$.

Now choose $A$ and $B$ with equal probability, independently of the data. The mixed risk vector is $\tfrac12(0,1)+\tfrac12(1,0)=(0.5,0.5)$. Since $0.5<0.6$ in both coordinates, this mixture strictly dominates $C$. The calculation shows why checking only individual deterministic competitors can miss a pointwise improvement available to the randomized class.

In a finite parameter problem, this geometry can be read directly from the risk vectors: a randomized rule is a convex combination, and domination is coordinatewise comparison. In an infinite parameter problem the same reasoning applies to risk functions, with the inequality required at every parameter, not merely at selected values or on average.

Worked Example: Mixing Data-Dependent Rules Under Unequal Loss

Let $\theta\in\{0,1\}$, $X\in\{u,v\}$, with $P_0(X=u)=0.75$ and $P_1(X=u)=0.25$. There are actions $a,b$, with losses $L(0,a)=0$, $L(0,b)=2$, $L(1,a)=3$, and $L(1,b)=0$. Rule $q_A$ chooses $b$ with probabilities 0.2 at $u$ and 0.6 at $v$. Rule $q_B$ chooses $b$ with probabilities 0.8 at $u$ and 0.2 at $v$. Calculate the risks of $q_A,q_B$, and $q=0.25q_A+0.75q_B$.

At $\theta=0$, only action $b$ incurs loss, equal to 2. Therefore $R(0,q_A)=0.75(0.2)(2)+0.25(0.6)(2)=0.30+0.30=0.60$, and $R(0,q_B)=0.75(0.8)(2)+0.25(0.2)(2)=1.20+0.10=1.30$.

At $\theta=1$, only action $a$ incurs loss, equal to 3. Hence $R(1,q_A)=0.25(1-0.2)(3)+0.75(1-0.6)(3)=0.60+0.90=1.50$, and $R(1,q_B)=0.25(1-0.8)(3)+0.75(1-0.2)(3)=0.15+1.80=1.95$.

The mixed rule chooses $b$ with probability $0.25(0.2)+0.75(0.8)=0.65$ at $u$, and $0.25(0.6)+0.75(0.2)=0.30$ at $v$. Its risks are $R(0,q)=0.75(0.65)(2)+0.25(0.30)(2)=0.975+0.15=1.125$ and $R(1,q)=0.25(1-0.65)(3)+0.75(1-0.30)(3)=0.2625+1.575=1.8375$. These equal the risk mixtures $0.25(0.60)+0.75(1.30)=1.125$ and $0.25(1.50)+0.75(1.95)=1.8375$, respectively. The check uses the loss under each parameter; action probabilities alone are not risks.

Common Pitfall and Practical Use

Reversing the error probability. Under zero-one loss, the probability of choosing action 1 is an error probability at $\theta=0$, but the probability of choosing action 0 is the error probability at $\theta=1$. Calculate errors from the loss and the true parameter, not from the action probability alone.
Mixing risks with the wrong weights. If the rule uses $q_1$ with probability $\lambda$, its risk is $\lambda R(\theta,q_1)+(1-\lambda)R(\theta,q_2)$, with those same weights at every parameter.
Confusing an average over parameters with pointwise domination. A small weighted average risk does not establish that one rule has no greater risk at every parameter. Check every coordinate, or every value of the risk function.
Assuming deterministic completeness settles randomized comparisons. A class that replaces all deterministic rules may fail to replace every randomized rule. The relevant ambient class must be stated whenever completeness is claimed.

Convexification is useful because it turns randomization into a geometric operation on risks: mixtures fill line segments and, more generally, finite convex combinations. For complete-class analysis, this lets us identify when an available randomized competitor supplies a pointwise replacement that individual rules do not. It does not by itself establish that a particular risk is attainable by a deterministic rule, nor that a limiting risk is attained.

Check Your Understanding

Use the definitions and calculations above to answer the following.

State the risk of a mixture of two rules with mixing probability $\lambda$, and explain why the same $\lambda$ is used at every parameter.
For the binary zero-one loss example, why is the error probability at $X=0$ under $\theta=1$ the probability of choosing action 1?
If two rules have risk vectors $(2,5)$ and $(6,1)$, what risk vector results from choosing each with probability one half?
In what sense can a mixture dominate a rule even when neither component dominates it?
Why must a claim of completeness specify whether randomized rules belong to the ambient class?