1 Testing, Estimation, Risk

In the estimation problem, we are given a family of measures and we want to estimate an unknown parameter for the measure from which we observe samples. Let $X$ be the measurable space on which the measures are defined. The measure family is described by a kernel $P : Θ ⇝ X$ . We write $P_{θ}$ for $P (θ)$ . In parametric problems, $Θ$ is a low-dimensional space. In nonparametric problems $Θ$ is large, for example $Θ = M (X)$ or $Θ = P (X)$ .

The goal of the estimation task is to find, given the observation of samples of $P_{θ}$ for an unknown $θ$ , the value of a function $y : Θ \to Y$ , which maps the parameter $θ$ to the quantity we are interested in. For example, $y (θ)$ might be the expected value of the distribution $P_{θ}$ .

An estimator is a Markov kernel $\hat{y} : X ⇝ Z$ , where most often $Z = Y$ . Note that, while $y$ is a function of a parameter in $Θ$ , $\hat{y}$ has domain $X$ as the estimation is done based on a sample of the measure, while the measure itself and its parameter remain unknown. In general this is a randomized estimator, but often deterministic estimators (corresponding to deterministic kernels) are enough to attain optimal performance. The quality of the estimation is quantified by a loss $ℓ^{'} : Y \times Z \to R_{+, \infty}$ . We write $ℓ$ for a loss on $Y \times Y$ and $ℓ^{'}$ in the heterogeneous case.

In short, an estimation problem is specified by the data $(P, y, ℓ^{'})$ .

Example: simple binary hypothesis testing (SBHT)

We say that an estimation problem is a testing problem if $Y = Z$ is discrete and the loss takes values in ${0, 1}$ . A test is said to be binary if $Y$ has two elements. A test is simple if ${θ ∣ y (θ) = y_{0}}$ is a singleton for all $y_{0} \in Y$ , i.e. $y$ is bijective.

In summary, in simple binary hypothesis testing, $Θ = Y = Z = {0, 1}$ , $y (0) = 0$ , $y (1) = 1$ (that is, $y$ is the identity). For $y_{0}, z \in {0, 1}$ , $ℓ (y_{0}, z) = I {y_{0} \neq z}$ .

1.1 Risk

Let ${\hat{μ}}_{θ}$ be the law of $\hat{y} (θ)$ . That is, $\hat{μ} : Θ ⇝ X$ is the kernel $\hat{y} \circ P$ .

Definition 1 Risk

✓

The risk of an estimator $\hat{y}$ on the estimation problem $(P, y, ℓ^{'})$ at $θ \in Θ$ is $r_{θ}^{P} (\hat{y}) = (\hat{y} \circ P) (θ) [z \mapsto ℓ^{'} (y (θ), z)]$ .

Example (SBHT): $r_{θ}^{P} (\hat{y}) = {\hat{μ}}_{θ} (\hat{y} (θ) \neq y (θ))$ .

Definition 2 Bayesian risk

✓

The Bayesian risk of an estimator $\hat{y}$ on $(P, y, ℓ^{'})$ for a prior $π \in M (Θ)$ is $R_{π}^{P} (\hat{y}) = π [θ \mapsto r_{θ}^{P} (\hat{y})]$ . It can also be expanded as $R_{π}^{P} (\hat{y}) = (π \otimes (\hat{y} \circ P)) [(θ, z) \mapsto ℓ^{'} (y (θ), z)]$ .

If we write $ℓ^{'}$ and $y$ for their deterministic kernels, the Bayesian risk of $\hat{y}$ is the mean of the measure $ℓ^{'} \circ (y ∥ \hat{y}) \circ (π \otimes P)$ .

Definition 3 Bayes risk

✓

The Bayes risk of $(P, y, ℓ^{'})$ for prior $π \in M (Θ)$ is $R_{π}^{P} = inf_{\hat{y} : X ⇝ Z} R_{π}^{P} (\hat{y})$ , where the infimum is over Markov kernels.

The Bayes risk of $(P, y, ℓ^{'})$ is $R_{B}^{*} = sup_{π \in P (Θ)} R_{π}^{P} .$

Example (SBHT): $R_{B}^{*} = sup_{γ \in [0, 1]} inf_{\hat{y}} (γ {\hat{μ}}_{0} (\hat{y} \neq 0) + (1 - γ) {\hat{μ}}_{1} (\hat{y} \neq 1))$ .

Definition 4 Bayes estimator

✓

An estimator $\hat{y}$ is said to be a Bayes estimator for a prior $π \in P (Θ)$ if $R_{π}^{P} (\hat{y}) = R_{π}^{P}$ .

Definition 5 Minimax risk

✓

The minimax risk of $(P, y, ℓ^{'})$ is $R^{*} = inf_{\hat{y} : X ⇝ Z} sup_{θ \in Θ} r_{θ}^{P} (\hat{y})$ .

Example (SBHT): $R^{*} = inf_{\hat{y}} max {{\hat{μ}}_{0} (\hat{y} \neq 0), {\hat{μ}}_{1} (\hat{y} \neq 1)}$ .

Lemma 1.1.1

✓

$R_{B}^{*} \leq R^{*}$ .

Proof ▶

For any $π \in P (X)$ and any estimator, $π [{\hat{μ}}_{θ} [ℓ^{'} (y (θ), \hat{y} (θ))]] \leq sup_{θ \in Θ} {\hat{μ}}_{θ} [ℓ^{'} (y (θ), \hat{y} (θ))]$ .

TODO: “often”, $R_{B}^{*} = R^{*}$ .

1.1.1 Properties of the Bayes risk of a prior

Lemma 1.1.2

✓

The Bayes risk of a prior $π \in M (Θ)$ on $(P, y, ℓ^{'})$ with $P$ a Markov kernel satisfies

\begin{array}{r} R_{π}^{P} \leq inf_{z \in Z} π [θ \mapsto ℓ^{'} (y (θ), z)] . \end{array}

Proof ▶

The infimum over all Markov kernels in the definition of the Bayes risk of $π$ is bounded from above by the infimum restricted to constant, deterministic Markov kernels.

Lemma 1.1.3

The Bayes risk of a prior $π \in M (Θ)$ on $(P, y, ℓ^{'})$ with $P$ a constant Markov kernel is

\begin{array}{r} R_{π}^{P} = inf_{z \in Z} π [θ \mapsto ℓ^{'} (y (θ), z)] . \end{array}

In particular, it does not depend on $P$ .

Proof ▶

Let $ξ$ be the measure such that $P (θ) = ξ$ for all $θ$ .

\begin{aligned} R_{π}^{P} & = inf_{\hat{y}} (π \times (\hat{y} \circ ξ)) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ = inf_{μ \in P (X)} (π \times μ) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ = inf_{μ \in P (X)} μ [z \mapsto π [θ \mapsto ℓ^{'} (y (θ), z)]] \\ = inf_{z \in Z} π [θ \mapsto ℓ^{'} (y (θ), z)] . \end{aligned}

Data-processing inequality and consequences

Theorem 1.1.4 Data-processing inequality

✓

For $P : Θ ⇝ X$ and $κ : X ⇝ X^{'}$ a Markov kernel, $R_{π}^{κ \circ P} \geq R_{π}^{P}$ (where the estimation problems differ only in the kernel).

Proof ▶

The risk $R_{π}^{κ \circ P}$ is

\begin{aligned} R_{π}^{κ \circ P} & = inf_{\hat{y} : X^{'} ⇝ Z} (π \otimes (\hat{y} \circ κ \circ P)) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ \geq inf_{\hat{y} : X ⇝ Z} (π \otimes (\hat{y} \circ P)) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ = R_{π}^{P} . \end{aligned}

The inequality is due to taking an infimum over a larger set: ${\hat{y} \circ κ ∣ \hat{y} : X^{'} ⇝ Z Markov} \subseteq {{\hat{y}}^{'} : X ⇝ Z ∣ \hat{y} Markov}$ .

Lemma 1.1.5

✓

For $P : Θ ⇝ X$ and $κ : Θ \times X ⇝ X^{'}$ a Markov kernel, $R_{π}^{P \otimes κ} \leq R_{π}^{P}$ .

Proof ▶

Use Theorem 1.1.4: $P$ is the composition of $P \otimes κ$ and the deterministic kernel $X \times X^{'} ⇝ X$ that forgets the second value.

Lemma 1.1.6

For $P : Θ ⇝ X$ and $κ : Θ \times X ⇝ X^{'}$ a Markov kernel, $R_{π}^{P \otimes κ} \leq R_{π}^{(P \otimes κ)_{X^{'}}}$ , in which $(P \otimes κ)_{X^{'}} : Θ ⇝ X^{'}$ is the kernel obtained by marginalizing over $X$ in the output of $P \otimes κ$ .

Proof ▶

Use Theorem 1.1.4: $(P \otimes κ)_{X^{'}}$ is the composition of $P \otimes κ$ and the deterministic kernel $X \times X^{'} ⇝ X^{'}$ that forgets the first value.

Lemma 1.1.7

The Bayes risk $R_{π}^{P}$ is concave in $P : Θ ⇝ X$ .

Proof ▶

The infimum of a sum is larger than the sum of the infimums:

\begin{aligned} R_{π}^{λ P_{1} + (1 - λ) P_{2}} & = inf_{\hat{y} : X ⇝ Z} (π \otimes (\hat{y} \circ (λ P_{1} + (1 - λ) P_{2}))) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ = inf_{\hat{y} : X ⇝ Z} (λ (π \otimes (\hat{y} \circ P_{1})) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ + (1 - λ) (π \otimes (\hat{y} \circ P_{2})) [(θ, z) \mapsto ℓ^{'} (y (θ), z)]) \\ \geq λ inf_{\hat{y} : X ⇝ Z} (π \otimes (\hat{y} \circ P_{1})) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ + (1 - λ) inf_{\hat{y} : X ⇝ Z} (π \otimes (\hat{y} \circ P_{2})) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ = λ R_{π}^{P_{1}} + (1 - λ) R_{π}^{P_{2}} . \end{aligned}

TODO: can we build kernels such that this lemma is a consequence of one of the lemmas above?

Generalized Bayes estimator

Lemma 1.1.8

✓

The Bayesian risk of a Markov kernel $\hat{y} : X ⇝ Z$ with respect to a prior $π \in M (Θ)$ on $(P, y, ℓ^{'})$ satisfies

\begin{array}{r} R_{π}^{P} (\hat{y}) = ((P_{π}^{†} \times \hat{y}) \circ P \circ π) [(θ, z) \mapsto ℓ^{'} (y (θ), z)], \end{array}

whenever the Bayesian inverse $P_{π}^{†}$ of $P$ with respect to $π$ exists (Definition 48).

Proof ▶

Use the main property of the Bayesian inverse.

\begin{aligned} (P_{π}^{†} \times \hat{y}) \circ P \circ π & = (id ∥ \hat{y}) \circ (P_{π}^{†} \times id) \circ (P \circ π) \\ = (id ∥ \hat{y}) \circ (id \times P) \circ π \\ = (id \times (\hat{y} \circ P)) \circ π \\ = π \otimes (\hat{y} \circ P) . \end{aligned}

Lemma 1.1.9

✓

The Bayesian risk of a Markov kernel $\hat{y} : X ⇝ Z$ with respect to a prior $π \in M (Θ)$ on $(P, y, ℓ^{'})$ satisfies

\begin{array}{r} R_{π}^{P} (\hat{y}) \geq (P \circ π) [x \mapsto inf_{z \in Z} P_{π}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)]] . \end{array}

Proof ▶

Starting from the equality of Lemma 1.1.8, we get

\begin{aligned} R_{π}^{P} (\hat{y}) & = ((P_{π}^{†} \times \hat{y}) \circ P \circ π) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] \\ = (P \circ π) [x \mapsto (P_{π}^{†} (x) \times \hat{y} (x)) [(θ, z) \mapsto ℓ^{'} (y (θ), z)]] \\ = (P \circ π) [x \mapsto \hat{y} (x) [z \mapsto P_{π}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)]]] \\ \geq (P \circ π) [x \mapsto inf_{z \in Z} P_{π}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)]] . \end{aligned}

Definition 6 Generalized Bayes estimator

✓

The generalized Bayes estimator for prior $π \in P (Θ)$ on $(P, y, ℓ^{'})$ is the deterministic estimator $X \to Z$ given by

\begin{array}{r} x \mapsto \arg min_{z} P_{π}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)], \end{array}

if there exists such a measurable argmin.

Lemma 1.1.10

✓

The Bayesian risk of the generalized Bayes estimator ${\hat{y}}_{B}$ is

\begin{array}{r} R_{π}^{P} ({\hat{y}}_{B}) = (P \circ π) [x \mapsto inf_{z \in Z} P_{π}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)]] . \end{array}

Proof ▶

Theorem 1.1.11

✓

When the generalized Bayes estimator is well defined, it is a Bayes estimator. The value of the Bayes risk with respect to the prior $π \in M (Θ)$ is then

\begin{array}{r} R_{π}^{P} = (P \circ π) [x \mapsto inf_{z \in Z} P_{π}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)]] . \end{array}

Proof ▶

Lemma 1.1.12

When the generalized Bayes estimator is well defined, the Bayes risk with respect to the prior $π \in M (Θ)$ is

\begin{array}{r} R_{π}^{P} = (P \circ π) [x \mapsto inf_{z \in Z} π [θ \mapsto \frac{d P_{θ}}{d (P \circ π)} (x) ℓ^{'} (y (θ), z)]] . \end{array}

Proof ▶

Lemma 1.1.13

When the generalized Bayes estimator is well defined, the Bayes risk with respect to the prior $π \in M (Θ)$ for $Y = Z = Θ$ , $y = id$ and $ℓ^{'} = I {θ \neq z}$ is

\begin{array}{r} R_{π}^{P} = (P \circ π) [1] - (P \circ π) [x \mapsto sup_{z \in Z} P_{π}^{†} (x) {z}] . \end{array}

Proof ▶

Lemma 1.1.14

When the generalized Bayes estimator is well defined, the Bayes risk with respect to the prior $π \in M (Θ)$ for $Y = Z = Θ$ , $y = id$ and $ℓ^{'} = I {θ \neq z}$ is

\begin{array}{r} R_{π}^{P} = (P \circ π) [1] - (P \circ π) [x \mapsto sup_{z \in Z} \frac{d P_{z}}{d (P \circ π)} (x) π {z}] . \end{array}

When $π$ is a probability measure and $P$ is a Markov kernel, $(P \circ π) [1] = 1$ .

Proof ▶

Lemma 1.1.15

The generalized Bayes estimator for prior $π \in P (Θ)$ on the estimation problem defined by $Y = Z = Θ$ , $y = id$ and $ℓ^{'} = I {θ \neq z}$ is

\begin{array}{r} x \mapsto \arg max_{z} (π {z} \frac{d P_{z}}{d (P \circ π)} (x)) . \end{array}

Proof ▶

Lemma 1.1.16

Suppose that $Θ$ is finite and let $ξ \in P (Θ)$ . The Bayes risk with respect to the prior $π \in P (Θ)$ for $Y = Z = Θ$ , $y = id$ , $P$ a Markov kernel and $ℓ^{'} = I {θ \neq z}$ satisfies

\begin{array}{r} R_{π}^{P} \leq 1 - (\prod_{θ \in Θ} π_{θ}^{ξ_{θ}}) (P \circ π) [x \mapsto \prod_{θ \in Θ} {(\frac{d P_{θ}}{d (P \circ π)} (x))}^{ξ_{θ}}] . \end{array}

Proof ▶

1.1.2 Bayes risk increase

TODO: remove this section? It’s not used for anything now.

The following is a new definition, which is a natural generalization of the DeGroot statistical information.

Definition 7

✓

The Bayes risk increase $I_{π}^{P} (κ)$ of a kernel $κ : X ⇝ X^{'}$ with respect to the estimation problem $(P, y, ℓ^{'})$ and the prior $π \in M (Θ)$ is the difference of the Bayes risk of $(κ \circ P, y, ℓ^{'})$ and that of $(P, y, ℓ^{'})$ . That is,

\begin{aligned} I_{π}^{P} (κ) & = R_{π}^{κ \circ P} - R_{π}^{P} \\ = inf_{\hat{y} : X^{'} ⇝ Z} (π \otimes (\hat{y} \circ κ \circ P)) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] - inf_{\hat{y} : X ⇝ Z} (π \otimes (\hat{y} \circ P)) [(θ, z) \mapsto ℓ^{'} (y (θ), z)] . \end{aligned}

In particular, if we take $κ : X ⇝ *$ equal to the Markov kernel to the point space (denoted by $d_{X}$ , for “discard” kernel), we get $I_{π}^{P} (d_{X}) = R_{π}^{d_{X} \circ P} - R_{π}^{P}$ , where $d_{X} \circ P = d_{Θ}$ if $P$ is a Markov kernel. We recover a difference between the risk of the best constant kernel and the Bayes estimator, as in the DeGroot statistical information.

The risk increase quantifies how much risk we accrue by forgetting information due to the composition with $κ$ .

Lemma 1.1.17

For $κ$ a Markov kernel, $I_{π}^{P} (κ) \geq 0$ .

Proof ▶

Lemma 1.1.18

✓

For $κ : X ⇝ X^{'}$ and $η : X^{'} ⇝ X^{″}$ two Markov kernels, $I_{π}^{P} (η \circ κ) = I_{π}^{P} (κ) + I_{π}^{κ \circ P} (η)$ .

Proof ▶

\begin{aligned} I_{π}^{P} (κ) + I_{π}^{κ \circ P} (η) & = R_{π}^{κ \circ P} - R_{π}^{P} + R_{π}^{η \circ κ \circ P} - R_{π}^{κ \circ P} \\ = R_{π}^{η \circ κ \circ P} - R_{π}^{P} \\ = I_{π}^{P} (η \circ κ) . \end{aligned}

Lemma 1.1.19 Data-processing inequality

✓

For any measurable space $X$ , let $d_{X} : X ⇝ *$ be the Markov kernel to the point space. For all Markov kernels $κ : X ⇝ X^{'}$ ,

\begin{array}{r} I_{π}^{P} (d_{X}) \geq I_{π}^{κ \circ P} (d_{X^{'}}) . \end{array}

Proof ▶

By Lemma 1.1.18, then Lemma 1.1.17,

\begin{array}{r} I_{π}^{P} (d_{X^{'}} \circ κ) = I_{π}^{P} (κ) + I_{π}^{κ \circ P} (d_{X^{'}}) \geq I_{π}^{κ \circ P} (d_{X^{'}}) . \end{array}

Finally, $d_{X^{'}} \circ κ = d_{X}$ since $κ$ is a Markov kernel.

1.2 Simple binary hypothesis testing

In this section, for a measure $ξ$ on ${0, 1}$ , we write $ξ_{0}$ for $ξ ({0})$ and $ξ_{1}$ for $ξ ({1})$ . We sometimes write $(a, b)$ for the measure $ξ$ on ${0, 1}$ with $ξ_{0} = a$ and $ξ_{1} = b$ .

Lemma 1.2.1

✓

The Bayesian inverse of a kernel $P : {0, 1} ⇝ X$ with respect to a prior $ξ \in M ({0, 1})$ is $P_{ξ}^{†} (x) = (ξ_{0} \frac{d P (0)}{d (P \circ ξ)} (x), ξ_{1} \frac{d P (1)}{d (P \circ ξ)} (x))$ (almost surely w.r.t. $P \circ ξ = ξ_{0} P (0) + ξ_{1} P (1)$ ).

Proof ▶

Lemma 1.2.2

✓

For $Θ = {0, 1}$ , the Bayes risk of a prior $ξ \in M ({0, 1})$ is

\begin{array}{r} R_{ξ}^{P} = (P \circ ξ) [x \mapsto inf_{z \in Z} (ξ_{0} \frac{d P (0)}{d (P \circ ξ)} (x) ℓ^{'} (y (0), z) + ξ_{1} \frac{d P (1)}{d (P \circ ξ)} (x) ℓ^{'} (y (1), z))] . \end{array}

Proof ▶

Use Theorem 1.1.11, with the value of $P_{ξ}^{†}$ given by Lemma 1.2.1.

1.2.1 Bayes risk of a prior

Definition 8

✓

The Bayes binary risk between measures $μ$ and $ν$ with respect to prior $ξ \in M ({0, 1})$ , denoted by $B_{ξ} (μ, ν)$ , is the Bayes risk $R_{ξ}^{P}$ for $Θ = Y = Z = {0, 1}$ , $ℓ (y, z) = I {y \neq z}$ , $P$ the kernel sending 0 to $μ$ and 1 to $ν$ and prior $ξ$ . That is,

\begin{array}{r} B_{ξ} (μ, ν) = inf_{\hat{y} : X ⇝ {0, 1}} (ξ_{0} (\hat{y} \circ μ) ({1}) + ξ_{1} (\hat{y} \circ ν) ({0})), \end{array}

in which the infimum is over Markov kernels.

If the prior is a probability measure with weights $(π, 1 - π)$ , we write $B_{π} (μ, ν) = B_{(π, 1 - π)} (μ, ν)$ .

Thanks to the following lemma, we can prove properties of the Bayes binary risk for non-zero finite measures by considering only probability measures.

Lemma 1.2.3

✓

For all $a, b > 0$ , $B_{ξ} (μ, ν) = B_{(a ξ_{0}, b ξ_{1})} (a^{- 1} μ, b^{- 1} ν)$ .

Proof ▶

Alternatively, we can reduce the study of the Bayes binary risk for any prior to the study of the prior $(1, 1)$ , for which that risk is related to the total variation distance (defined later).

Lemma 1.2.4

✓

$B_{ξ} (μ, ν) = B_{(1, 1)} (ξ_{0} μ, ξ_{1} ν)$ .

Proof ▶

Theorem 1.2.5 Data-processing inequality

✓

For $μ, ν \in M (X)$ and $κ : X ⇝ Y$ a Markov kernel, $B_{ξ} (κ \circ μ, κ \circ ν) \geq B_{ξ} (μ, ν)$ .

Proof ▶

Lemma 1.2.6

✓

For $μ \in M (X)$ , $B_{ξ} (μ, μ) = min {ξ_{0}, ξ_{1}} μ (X)$ .

Proof ▶

Lemma 1.2.7

For all measures $μ, ν$ , $B_{ξ} (μ, ν) \geq 0$ .

Proof ▶

Lemma 1.2.8

✓

For all measures $μ, ν$ , $B_{ξ} (μ, ν) \leq min {ξ_{0} μ (X), ξ_{1} ν (X)}$ .

Proof ▶

Let $d_{X} : X ⇝ *$ be the discard kernel and $δ_{*}$ be the only probability measure over $*$ , that is a Dirac delta. Then applying the DPI (Theorem 1.2.5), followed by Lemma 1.2.3 and Lemma 1.2.6, we obtain:

\begin{aligned} B_{ξ} (μ, ν) & \leq B_{ξ} (d_{X} \circ μ, d_{X} \circ ν) \\ = B_{ξ} (μ (X) δ_{*}, ν (X) δ_{*}) \\ = B_{(μ (X) ξ_{0}, ν (X) ξ_{1})} (δ_{*}, δ_{*}) \\ = min {μ (X) ξ_{0}, ν (X) ξ_{1}} δ_{*} (X) \\ = min {μ (X) ξ_{0}, ν (X) ξ_{1}} . \end{aligned}

Lemma 1.2.9

✓

For $μ, ν \in M (X)$ and $ξ \in M ({0, 1})$ , $B_{ξ} (μ, ν) = B_{ξ_{\leftrightarrow}} (ν, μ)$ where $ξ_{\leftrightarrow} \in M ({0, 1})$ is such that $ξ_{\leftrightarrow} ({0}) = ξ_{1}$ and $ξ_{\leftrightarrow} ({1}) = ξ_{0}$ . For $π \in [0, 1]$ , $B_{π} (μ, ν) = B_{1 - π} (ν, μ)$ .

Proof ▶

Lemma 1.2.10

✓

The generalized Bayes estimator for the Bayes binary risk with prior $ξ \in M ({0, 1})$ is $x \mapsto if ξ_{1} \frac{d ν}{d (P \circ ξ)} (x) \leq ξ_{0} \frac{d μ}{d (P \circ ξ)} (x) then 0 else 1$ , i.e. it is equal to $I_{E}$ for $E = {x ∣ ξ_{1} \frac{d ν}{d (P \circ ξ)} (x) > ξ_{0} \frac{d μ}{d (P \circ ξ)} (x)}$ .

Proof ▶

The generalized Bayes estimator is defined by

\begin{array}{r} x \mapsto \arg min_{z} P_{ξ}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)] . \end{array}

For the simple binary hypothesis testing problem,

\begin{aligned} P_{ξ}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)] & = P_{ξ}^{†} (x) (θ \neq z) . \end{aligned}

For $z = 0$ , this is $P_{ξ}^{†} (x) ({1})$ and for $z = 1$ , this is $P_{ξ}^{†} (x) ({0})$ . The generalized Bayes estimator is $x \mapsto if P_{ξ}^{†} (x) ({1}) \leq P_{ξ}^{†} (x) ({0}) then 0 else 1$ .

The expression of the lemma statement is obtained by replacing $P_{ξ}^{†}$ by its value (Lemma 1.2.1).

Lemma 1.2.11

✓

\begin{array}{r} B_{ξ} (μ, ν) = inf_{E event} (ξ_{0} μ (E) + ξ_{1} ν (E^{c})) . \end{array}

Proof ▶

By definition,

\begin{array}{r} B_{ξ} (μ, ν) = inf_{\hat{y} : X ⇝ {0, 1}} (ξ_{0} (\hat{y} \circ μ) ({1}) + ξ_{1} (\hat{y} \circ ν) ({0})) . \end{array}

If we restrict the infimum to deterministic kernels corresponding to functions of the form $x \mapsto I {x \in E}$ , we get that $B_{ξ} (μ, ν)$ is bounded from above by the expression for which we want to show equality.

Since the Bayes estimator has that shape (Lemma 1.2.10), $B_{ξ} (μ, ν)$ is also greater than the infimum and we have equality.

Theorem 1.2.12

✓

The Bayes risk of simple binary hypothesis testing for prior $ξ \in M ({0, 1})$ is

\begin{array}{r} B_{ξ} (μ, ν) = (P \circ ξ) [x \mapsto min {ξ_{0} \frac{d μ}{d (P \circ ξ)} (x), ξ_{1} \frac{d ν}{d (P \circ ξ)} (x)}] . \end{array}

Proof ▶

By Theorem 1.1.11, the generalized Bayes estimator is a Bayes estimator, hence it suffices to compute its Bayesian risk. By Lemma 1.1.10,

\begin{aligned} R_{ξ} ({\hat{y}}_{B}) & = (P \circ ξ) [x \mapsto inf_{z \in Z} P_{ξ}^{†} (x) [θ \mapsto ℓ^{'} (y (θ), z)]] \\ = (P \circ ξ) [x \mapsto min {P_{ξ}^{†} (x) ({0}), P_{ξ}^{†} (x) ({1})}] \\ = (P \circ ξ) [x \mapsto min {ξ_{0} \frac{d μ}{d (P \circ ξ)} (x), ξ_{1} \frac{d ν}{d (P \circ ξ)} (x)}] . \end{aligned}

The last line is obtained by replacing $P_{ξ}^{†}$ by its value (Lemma 1.2.1).

Corollary 1.2.13

✓

\begin{array}{r} B_{ξ} (μ, ν) = \frac{1}{2} ((P \circ ξ) (X) - (P \circ ξ) [x \mapsto | ξ_{0} \frac{d μ}{d (P \circ ξ)} (x) - ξ_{1} \frac{d ν}{d (P \circ ξ)} (x) |]) . \end{array}

Proof ▶

Use Theorem 1.2.12 and the equality $min {a, b} = \frac{1}{2} (a + b - | a - b |)$ .

Lemma 1.2.14

Let ${\hat{y}}_{B}$ be the generalized Bayes estimator for simple binary hypothesis testing. The distribution $ℓ \circ (id ∥ {\hat{y}}_{B}) \circ (π \otimes P)$ (in which $ℓ$ stands for the associated deterministic kernel) is a Bernoulli with mean $B_{π} (μ, ν)$ .

Proof ▶

$ℓ$ takes values in ${0, 1}$ so the law has to be Bernoulli. It has mean $B_{π} (μ, ν)$ because the expected risk of the generalized Bayes estimator is $B_{π} (μ, ν)$ .

TODO: find a way to hide the following dummy lemma

Lemma 1.2.15 Dummy lemma: bayesBinaryRisk properties

✓

Dummy node to summarize properties of the Bayes binary risk.

Proof ▶

1.3 Reduction to testing

TODO: lower bounds on estimation by reduction to testing problems.

1.4 Sample complexity

TODO: we could generalize this to a sequence of kernels instead of iid observations.

An estimation problem of the shape $(P^{\otimes n}, y, ℓ^{'})$ corresponds to estimating from $n \in N$ i.i.d. samples of the distribution. From the data-processing inequality, we get that the risk (Bayes risk, minimax risk...) decreases with the number of samples (Lemma 1.4.1 for example). Intuitively, having more information allows for better estimation.

In a sequence of estimation tasks $(P^{\otimes n}, y, ℓ^{'})$ for $n \in N$ , the sample complexity is the minimal $n$ such that the risk is less than a desired value.

Lemma 1.4.1

If $n \leq m$ then $R_{π}^{P^{\otimes n}} \geq R_{π}^{P^{\otimes m}}$ .

Proof ▶

Use the data-processing inequality, Theorem 1.1.4, for the deterministic kernel that projects on the first $n$ coordinates. □

Definition 9

The sample complexity of Bayesian estimation with respect to a prior $π \in M (Θ)$ at risk level $δ \in R_{+, \infty}$ is

\begin{array}{r} n_{π}^{P} (δ) = min {n \in N ∣ R_{π}^{P^{\otimes n}} \leq δ} . \end{array}