Discrete Exhaustions for Countable Parameter Spaces

Why Exhaust a Countable Parameter Space?

In admissibility arguments, a parameter space may be countable but infinite. A prior supported on finitely many parameter values makes integrated-risk calculations finite sums; a sequence of such priors can successively include more of the space. The important issue is not just that every parameter eventually appears. The weights and risks must also be controlled so that the part left out at each stage contributes little.

This tutorial develops that construction for countable parameter spaces. The key condition is weighted summability of the risk of a reference rule. It gives an explicit bound on omitted risk, and it ensures that the integrated risks under the finite priors converge to the corresponding full weighted average.

Definition: Let $\Theta=\{\theta_1,\theta_2,\ldots\}$ be a countable parameter space. An increasing finite exhaustion is a sequence $F_1\subseteq F_2\subseteq\cdots$ of finite subsets of $\Theta$ such that $\bigcup_{m=1}^{\infty}F_m=\Theta$. A sequence of finite-support priors has each prior supported on one of these finite sets.

An exhaustion need not add exactly one point at each step, and it need not follow a particular enumeration. It must, however, eventually include every parameter value. In calculations, write $q_j>0$ for the weight assigned to $\theta_j$. If $Q=\sum_{j=1}^{\infty}q_j<\infty$, define $Q_m=\sum_{\theta_j\in F_m}q_j$. Whenever $Q_m>0$, the weights restricted to $F_m$ and divided by $Q_m$ form a proper prior.

Definition: Given positive weights $q_j$ with $0<Q=\sum_j q_j<\infty$ and an increasing finite exhaustion $F_m$, the associated finite prior is $$ \pi_m(\theta_j)= \begin{cases} q_j/Q_m, & \theta_j\in F_m,\\ 0, & \theta_j\notin F_m, \end{cases} \qquad Q_m=\sum_{\theta_j\in F_m}q_j. $$ For this to define a prior at every index $m$, require $Q_m>0$; if necessary, begin the sequence at a set containing at least one point.

Constructing Exhaustions and Prior Sequences

For a countable space, one can enumerate its elements and use initial segments. More generally, a convenient exhaustion may reflect the structure of the parameter. For example, for pairs of nonnegative integers, the sets of pairs whose coordinate sum is at most $m$ are finite, nested, and eventually contain every pair. The weights can be chosen separately from the exhaustion, provided they are positive and have finite total mass.

Worked Example: An Exhaustion of a Countable Product Space

Let $\Theta=\{(i,j):i,j\in\{0,1,2,\ldots\}\}$. For $m=0,1,2,\ldots$, set $F_m=\{(i,j):i+j\leq m\}$. Show that these sets exhaust $\Theta$, and construct finite priors from positive weights.

For each $m$, there are $k+1$ pairs with $i+j=k$, so $F_m$ has $\sum_{k=0}^m(k+1)=(m+1)(m+2)/2$ elements. It is finite. If $(i,j)\in F_m$, then $i+j\leq m+1$, so $F_m\subseteq F_{m+1}$. Given any fixed pair $(i,j)$, it belongs to $F_m$ whenever $m\geq i+j$. Thus the sets are nested and their union is all of $\Theta$.

Assign $q_{ij}=2^{-(i+j+2)}$. These weights are positive and have total mass $$ \sum_{i=0}^{\infty}\sum_{j=0}^{\infty}2^{-(i+j+2)} =\left(\sum_{i=0}^{\infty}2^{-(i+1)}\right)^2 =1. $$ The weight in $F_m$ is $Q_m=\sum_{k=0}^m(k+1)2^{-(k+2)}>0$. Restricting $q_{ij}$ to $F_m$ and dividing by $Q_m$ therefore gives a proper prior for every $m$. Since the total weight is one and $F_m$ increases to $\Theta$, $Q_m$ increases to one.

Weighted Summability Controls the Omitted Risk

For a decision rule $\delta$, let $R(\theta_j,\delta)$ denote its risk at $\theta_j$. Risks are nonnegative, though they may be unbounded as $j$ varies. The relevant condition for controlling an omitted tail is that the reference rule's weighted risks have a finite sum.

Theorem: Let $q_j>0$, $Q=\sum_j q_j<\infty$, and let $F_m$ be an increasing finite exhaustion. Suppose a rule $\delta_0$ satisfies $$ A=\sum_{j=1}^{\infty}q_j R(\theta_j,\delta_0)<\infty. $$ Then the omitted weighted risk $$ T_m=\sum_{\theta_j\notin F_m}q_jR(\theta_j,\delta_0) $$ tends to zero. If another rule $\delta$ is dominated by $\delta_0$, meaning $R(\theta_j,\delta)\leq R(\theta_j,\delta_0)$ for every $j$, then its omitted weighted risk and the omitted weighted risk difference also satisfy $$ \sum_{\theta_j\notin F_m}q_jR(\theta_j,\delta)\leq T_m, \qquad 0\leq\sum_{\theta_j\notin F_m}q_j\bigl(R(\theta_j,\delta_0)-R(\theta_j,\delta)\bigr)\leq T_m. $$

Proof. The series defining $A$ is a convergent series of nonnegative terms. Since every $\theta_j$ eventually belongs to $F_m$, its complementary tail decreases to the empty set in the sense that each fixed term is eventually removed. To verify that $T_m\to0$, let $\varepsilon>0$. Convergence of the series gives an $N$ such that $\sum_{j>N}q_jR(\theta_j,\delta_0)<\varepsilon$. Because $F_m$ is increasing and contains every one of $\theta_1,\ldots,\theta_N$ for all sufficiently large $m$, its complement then contains none of these first $N$ points. For those $m$, $0\leq T_m\leq\sum_{j>N}q_jR(\theta_j,\delta_0)<\varepsilon$. Hence $T_m\to0$. The domination inequalities hold term by term on the complement of $F_m$; summing them proves both bounds. $\square$

This result controls a tail in the unnormalized weighted sum. The finite prior is normalized, so it is also useful to state what happens to normalized integrated risks. Write $A_m=\sum_{\theta_j\in F_m}q_jR(\theta_j,\delta_0)$. Its risk under $\pi_m$ is $A_m/Q_m$, while the full normalized weighted risk is $A/Q$.

Result: Under the theorem's assumptions, $Q_m\to Q$, $A_m\to A$, and therefore $$ \sum_{\theta_j\in F_m}\pi_m(\theta_j)R(\theta_j,\delta_0) =\frac{A_m}{Q_m} \longrightarrow \frac{A}{Q}. $$ For every $m$ with $Q_m>0$, the difference is bounded by $$ \left|\frac{A}{Q}-\frac{A_m}{Q_m}\right| \leq \frac{T_m}{Q}+\frac{A_m(Q-Q_m)}{QQ_m}. $$

Proof. Since $q_j$ has finite sum and the exhaustion eventually includes each point, the same finite-head and small-tail argument gives $Q_m\to Q$. Likewise, the theorem's assumption gives $A_m\to A$, with $A-A_m=T_m$. As $Q>0$, these limits imply $A_m/Q_m\to A/Q$. For the stated bound, use $A=A_m+T_m$ and $Q=Q_m+(Q-Q_m)$ to write $$ \frac{A}{Q}-\frac{A_m}{Q_m} =\frac{T_m}{Q}-\frac{A_m(Q-Q_m)}{QQ_m}. $$ Taking absolute values and applying the triangle inequality gives the result. $\square$

If $\delta$ is dominated by $\delta_0$, weighted summability for $\delta_0$ also ensures that $\sum_jq_jR(\theta_j,\delta)$ is finite. Thus the same convergence result applies to its integrated risk. Moreover, if the domination is strict at some $\theta_k$, the finite-prior risk difference has a positive lower bound once $\theta_k$ is included: $$ \sum_{\theta_j\in F_m}\pi_m(\theta_j) \bigl(R(\theta_j,\delta_0)-R(\theta_j,\delta)\bigr) \geq \frac{q_k\bigl(R(\theta_k,\delta_0)-R(\theta_k,\delta)\bigr)}{Q_m}. $$ The right side tends to a strictly positive number. This observation concerns finite-prior integrated comparisons; it does not by itself establish that a particular rule is Bayes or admissible.

Worked Risk Calculations

Worked Example: A Geometric Prior Sequence With an Explicit Risk Tail

Consider an experiment with a single possible observation, so the data contain no information about $\theta$. Let $\Theta=\{1,2,\ldots\}$, the action space be the real line, and the loss be $L(\theta,a)=(a-\theta)^2$. Compare the rules $\delta_0$, which always chooses $0$, and $\delta_1$, which always chooses $1$. Use weights $q_j=2^{-j}$ and $F_m=\{1,\ldots,m\}$.

Because the observation is constant, the risks are their losses: $$ R(j,\delta_0)=j^2,\qquad R(j,\delta_1)=(j-1)^2. $$ Thus $\delta_1$ dominates $\delta_0$, since $j^2-(j-1)^2=2j-1>0$ for every $j\geq1$. The total prior weight is $\sum_{j=1}^{\infty}2^{-j}=1$, and the finite prior has normalizing constant $Q_m=1-2^{-m}$.

The reference rule's full weighted risk is $\sum_{j=1}^{\infty}j^2 2^{-j}=6$. To check the omitted risk directly, for $n=m+1$ the geometric-series identities give $$ \sum_{j=n}^{\infty}\frac{j^2}{2^j} =2^{1-n}(n^2+2n+3). $$ Substituting $n=m+1$ yields $T_m=2^{-m}(m^2+4m+6)$, which tends to zero. For example, at $m=3$, $T_3=(9+12+6)/8=27/8$; the included weighted risk is $6-27/8=21/8$. The normalized integrated risk under $\pi_3$ is therefore $(21/8)/(7/8)=3$.

The weighted risk difference over the full space is $$ \sum_{j=1}^{\infty}2^{-j}(2j-1) =2\sum_{j=1}^{\infty}\frac{j}{2^j}-\sum_{j=1}^{\infty}\frac{1}{2^j} =2(2)-1=3. $$ The omitted weighted difference after $m$ is $2^{-m}(2m+3)$, which tends to zero. At $m=3$, it is $9/8$; the included weighted difference is $3-9/8=15/8$, and its finite-prior average is $(15/8)/(7/8)=15/7$. This illustrates how both the risk tail and the prior-mass normalization enter finite integrated comparisons.

Worked Example: Strict Improvement Appears in Every Sufficiently Large Exhaustion

Keep the same parameter space, experiment, loss, and rules, but suppose only that the exhaustion is any increasing sequence of finite sets whose union is $\{1,2,\ldots\}$. Use the same weights $q_j=2^{-j}$. Verify a lower bound on the finite-prior improvement once parameter $1$ is included.

At $j=1$, the risks are $R(1,\delta_0)=1$ and $R(1,\delta_1)=0$, so the improvement is one. Since the exhaustion covers the parameter space, there is an index $m_0$ such that $1\in F_m$ for every $m\geq m_0$. For each such $m$, the unnormalized improvement on $F_m$ is at least the contribution from $j=1$, namely $2^{-1}$. Also $Q_m\leq1$. Therefore $$ \sum_{j\in F_m}\pi_m(j) \bigl(R(j,\delta_0)-R(j,\delta_1)\bigr) \geq \frac{2^{-1}}{Q_m}\geq \frac12. $$ Every sufficiently large finite prior consequently registers a positive average improvement, irrespective of how the remaining points are ordered in the exhaustion. This bound uses nonnegative contributions from all included points; if risk differences could have either sign, the same lower-bound argument would not apply.

When the Tail Condition Fails

Worked Example: Finite Priors Do Not Guarantee Bounded Integrated Risk

Again let $\Theta=\{1,2,\ldots\}$, let the observation be constant, and use squared-error loss $L(\theta,a)=(a-\theta)^2$. Consider $\delta_0$, which always chooses $0$, with $F_m=\{1,\ldots,m\}$ and weights $q_j=1/j^2$. Each finite prior is well-defined because $Q_m=\sum_{j=1}^m1/j^2$ is positive and finite. But the weighted risk numerator is $$ \sum_{j=1}^m q_jR(j,\delta_0) =\sum_{j=1}^m\frac{j^2}{j^2}=m. $$ Since $Q_m\leq 1+\int_1^\infty x^{-2}\,dx=2$, the finite-prior integrated risk satisfies $m/Q_m\geq m/2$ and diverges to infinity. The omitted unnormalized risk is $\sum_{j>m}1$, which is infinite for every $m$. Thus positive weights and proper finite priors alone do not yield a vanishing risk tail.

Common Pitfall and Practical Use

A common mistake is to argue that the omitted contribution is negligible merely because each fixed parameter is eventually included. That fact controls the omission of any fixed finite collection of terms, but it says nothing about the total contribution of infinitely many remaining terms. In the preceding example, every fixed $j$ eventually enters $F_m$, yet the omitted weighted risk is infinite at every stage.

The correction is to check a tail condition on the actual quantity being controlled. For nonnegative risk, $\sum_jq_jR(\theta_j,\delta_0)<\infty$ is a direct sufficient condition. It provides a vanishing bound for the reference risk, and, under domination, also for the competitor's risk and the risk difference. When this condition is unavailable, one needs a different argument that controls the relevant tails; simply choosing larger finite sets is not enough.

Key takeaway: An exhaustion determines which parameter values are included; summability determines whether the omitted risk becomes small. For a finite-prior sequence to support a reliable integrated-risk limit, establish both coverage of the parameter space and quantitative control of the weighted tail.

Check Your Understanding

Answer each question using the definitions and bounds developed above.

Why does an increasing sequence of finite sets need to have union equal to the entire parameter space?
State a sufficient condition that guarantees the omitted weighted risk of a reference rule tends to zero.
If a rule is dominated by a reference rule satisfying the weighted summability condition, what bound controls the competitor's omitted weighted risk?
In the geometric-weight example, calculate the omitted weighted risk at $m=2$ using $T_m=2^{-m}(m^2+4m+6)$.
Why do the weights $q_j=1/j^2$ fail to control the omitted risk for the zero-action rule under squared-error loss with $\theta=j$?