Chapter 173Optional

Computable Conditioning and Its Limits

Prerequisites. Direct starred prerequisites: none. No later core chapter depends on this route.

A disease affects one person in a thousand. A test reports positive on $99 / 100$ of the affected and on $1 / 50$ of the unaffected. Given a positive report, the posterior probability of the disease is a quotient of two exact rationals: $\begin{aligned} Pr [D ∣ T] \\ = \frac{Pr [D \land T]}{Pr [T]} \\ = \frac{\frac{1}{1000} \cdot \frac{99}{100}}{\frac{1}{1000} \cdot \frac{99}{100} + \frac{999}{1000} \cdot \frac{1}{50}} \\ = \frac{99 / 100000}{99 / 100000 + 1998 / 100000} \\ = \frac{99}{2097} = \frac{33}{699} = \frac{11}{233} . \end{aligned}$ Every step is a finite computation on reduced fractions, and a program that performs it needs nothing but integer arithmetic and a check that the denominator is nonzero.

Replace the test report by a real-valued measurement. The event ${X = x}$ then has probability zero, the quotient has the form $0 / 0$ , and the object to be computed — a family of measures indexed by $x$ — is determined only up to a set of $x$ of measure zero. Two questions arise at once, and this chapter answers both. Which family is meant? And, once the family is pinned down, is it computable from a program that samples the joint distribution?

The answer to the second question is negative in a strong and precise sense, and the mechanism is already visible in the first: a family determined only almost everywhere cannot be recovered from finitely much information about the joint distribution, because a perturbation of arbitrarily small size can install an arbitrary answer at the point of interest. That perturbation argument is proved here in full. The chapter’s positive results identify the hypotheses — a discrete observation, or a positive bounded computable conditional density — that defeat it.

Conditioning on a null event

Definition 173.1 — Elementary conditioning ¶

Let $P$ be a probability measure on a measurable space and let $C$ be an event with $P (C) > 0$ . For every event $A$ , $P (A ∣ C) = P (A \cap C) / P (C)$ .

Referenced from 4 locations

Computable Conditioning and Its Limits

The hypothesis $P (C) > 0$ is not a technicality that a limit can remove, and the following calculation shows what fails. It is the standard reason why “the conditional distribution given $Y = 0$ ” is not a well-posed request.

Example 173.2 — Two shrinking families, two answers ¶

Let $(X, Y)$ be uniformly distributed on the closed unit disc, with density $1 / π$ . Condition on two families of events, both shrinking to ${Y = 0}$ .

Strips. Let $C_{ε} = {| Y | \leq ε}$ . For $| x | \leq \sqrt{1 - ε^{2}}$ the section ${y ∣ (x, y) \in C_{ε}}$ is the full interval $[- ε, ε]$ , so the density of $X$ restricted to $C_{ε}$ is the constant $2 ε / π$ there. Hence the conditional law of $X$ given $C_{ε}$ is uniform on $[- \sqrt{1 - ε^{2}}, \sqrt{1 - ε^{2}}]$ , and as $ε \to 0$ it converges weakly to the uniform law on $[- 1, 1]$ .

Wedges. Write $(X, Y) = (R \cos Θ, R \sin Θ)$ and let $D_{ε} = {| Θ | \leq ε} \cup {| Θ - π | \leq ε}$ , also shrinking to ${Y = 0}$ . In polar coordinates the density is $r / π$ , so given $D_{ε}$ the radius $R$ has density $2 r$ on $[0, 1]$ , independently of $Θ$ . As $ε \to 0$ the law of $X = R \cos Θ$ converges weakly to the law with density $| x |$ on $[- 1, 1]$ .

The two limits are different measures; at $x = 0$ the first has density $1 / 2$ and the second density $0$ . The event ${Y = 0}$ is common to both families, so the phrase “condition on $Y = 0$ ” does not name a measure. What does name one is a family indexed by all values of $Y$ , constrained by an integral equation, and determined only up to a null set of indices.

Referenced from 4 locations

Computable Conditioning and Its Limits

Definition 173.3 — Conditional distribution ¶

Let $X$ and $Y$ be random variables in measurable spaces $S$ and $T$ on a probability space with law $P$ , and let $P_{X} = X_{*} P$ . A conditional distribution of $Y$ given $X$ is a kernel $κ : S ⇝ T$ , in the sense of definition 172.16, such that every $κ (x)$ is a probability measure and $\int_{A} κ (x) (B) d P_{X} (x) = P {X \in A, Y \in B} (A \in Σ_{S}, B \in Σ_{T}) .$ Any such $κ$ is written $P [Y ∣ X = \cdot]$ , and a particular $κ$ satisfying the equation is called a version.

Referenced from 9 locations

Computable Conditioning and Its Limits

Proposition 173.4 — Versions agree almost everywhere ¶

Let $T$ be a measurable space whose $σ$ -algebra is generated by a countable family closed under finite intersection. If $κ$ and $κ^{'}$ are versions of $P [Y ∣ X = \cdot]$ , then there is a set $N \in Σ_{S}$ with $P_{X} (N) = 0$ such that $κ (x) = κ^{'} (x)$ for all $x \notin N$ .

Referenced from 5 locations

Computable Conditioning and Its Limits

Proof of Proposition 173.4 — Versions agree almost everywhere

Proof. Let $G = {B_{1}, B_{2}, \dots}$ be the countable generating family. Fix $B \in G$ . The two functions $x \mapsto κ (x) (B)$ and $x \mapsto κ^{'} (x) (B)$ are measurable and, by definition 173.3, have equal integrals over every $A \in Σ_{S}$ . Taking $A = {x ∣ κ (x) (B) > κ^{'} (x) (B)}$ gives $\int_{A} (κ (\cdot) (B) - κ^{'} (\cdot) (B)) d P_{X} = 0$ with a nonnegative integrand, so $P_{X} (A) = 0$ ; the reverse inequality is the same computation with the roles exchanged. Let $N_{B}$ be the union of the two null sets and $N = ⋃_{B \in G} N_{B}$ , a countable union of null sets, hence null. For $x \notin N$ the measures $κ (x)$ and $κ^{'} (x)$ are probability measures agreeing on $G$ ; since $G$ is closed under finite intersection and generates $Σ_{T}$ , the finite unions of differences of its members form a Boolean algebra on which the two agree, and lemma 172.29 gives $κ (x) = κ^{'} (x)$ . ◻

Convention 173.5 — Imported existence ¶

Existence of a version is imported at the following signature. For random variables $X, Y$ in computable Polish spaces — separable, completely metrizable spaces with the Borel $σ$ -algebra — a conditional distribution $P [Y ∣ X = \cdot]$ exists. Ackerman–Freer–Roy obtain it in their §3 from the Radon–Nikodym theorem, which they state as their Theorem 3.2: for $σ$ -finite measures $μ ≪ ν$ on a measurable space there is a measurable $f \geq 0$ with $μ (A) = \int_{A} f d ν$ , unique up to $ν$ -null sets. What the import supplies is a version to speak about; none of the negative results below depends on which version is chosen, by proposition 173.4.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.1 ¶

★☆☆ Recompute the opening posterior with the false-positive rate changed from $1 / 50$ to $1 / 500$ , as a reduced fraction, and state the exact hypothesis of definition 173.1 that the computation checks.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.2 ¶

★☆☆ Let $X$ be uniform on $[0, 1]$ and $Y = X$ . Exhibit two versions of $P [Y ∣ X = \cdot]$ that differ at the single point $x = 1 / 2$ , and check both against definition 173.3.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.3 ¶

★★☆ In example 173.2, exhibit a third family of events shrinking to ${Y = 0}$ whose conditional laws of $X$ converge to a third measure, and give that measure explicitly.

Referenced from 2 locations

Computable Conditioning and Its Limits

Representations and computability

Computability of a real-valued object is a statement about programs that read and write approximations, so the objects of this chapter must first be given representations.

Convention 173.6 — The Ackerman–Freer–Roy computability card ¶

A real $r$ is computable when some program enumerates a sequence of rationals $q_{n}$ with $| r - q_{n} | \leq 2^{- n}$ , and lower semicomputable when some program enumerates rationals increasing to $r$ . A computable Polish space is a complete separable metric space $(T, d)$ with a distinguished countable dense sequence whose mutual distances are computable uniformly. On $M_{1} (T)$ , the probability measures on $T$ , the Prokhorov metric and the finitely supported rational-mass measures at the distinguished points make $M_{1} (T)$ a computable Polish space; a measure is computable when it is a computable point of it. A random variable $X$ is $P$ -almost computable when it is computable on a set of $P$ -measure one. A set $A$ is $P$ -almost decidable when its indicator is $P$ -almost computable. Finally, every computable map between computable Polish spaces is continuous, and this is the only fact about the computability notions that the negative result of section 173.3 uses.

Referenced from 4 locations

Computable Conditioning and Its Limits

Remark 173.7 — Why continuity is the operative property ¶

A program computing a map $Φ$ must produce each output approximation from finitely many input approximations. Two inputs that agree to that finite precision therefore receive the same output approximation, which is the content of continuity for the Cauchy-sequence representation. The following section shows that no conditioning operator has that property at any point, so the noncomputability below is not an artifact of a particular coding.

Referenced from 2 locations

Computable Conditioning and Its Limits

Conditioning is discontinuous everywhere

Definition 173.8 — Conditioning operator ¶

Let $F \subseteq M_{1} ([0, 1]^{2})$ . A map $Φ : M_{1} ([0, 1]^{2}) \times [0, 1] \to M_{1} ([0, 1])$ is a conditioning operator for $F$ when, for every $μ \in F$ and every pair $(X, Y)$ with joint law $μ$ , the equation $Φ (μ, x) = P [Y ∣ X = x]$ holds for $P_{X}$ -almost all $x$ . It is computable when it is computable on $F \times [0, 1]$ with respect to the representations of convention 173.6.

Referenced from 2 locations

Computable Conditioning and Its Limits

Lemma 173.9 — An arbitrary answer nearby ¶

Let $F \subseteq M_{1} ([0, 1]^{2})$ contain every finitely supported rational-mass measure. Let $ν \in M_{1} ([0, 1]^{2})$ , let $x \in [0, 1]$ , let $α \in M_{1} ([0, 1])$ be finitely supported with rational masses, and let $ε \in (0, 1)$ be rational. Then there is $μ \in M_{1} ([0, 1]^{2})$ with Prokhorov distance $d_{ρ} (μ, ν) < ε$ such that $Φ (μ, x) = α$ for every conditioning operator $Φ$ for $F$ .

Referenced from 9 locations

Computable Conditioning and Its Limits

Proof of Lemma 173.9 — An arbitrary answer nearby

Proof. Choose a finitely supported rational-mass $p^{*} \in M_{1} ([0, 1]^{2})$ with $d_{ρ} (p^{*}, ν) < ε / 2$ and $p^{*} ({x} \times [0, 1]) = 0$ ; this is possible because the finitely supported rational-mass measures are dense and because a support point with first coordinate $x$ may be moved by an arbitrarily small amount. Put $μ = \frac{ε}{2} (δ_{x} \otimes α) + (1 - \frac{ε}{2}) p^{*} .$ Then $μ$ differs from $p^{*}$ by total variation at most $ε / 2$ , hence $d_{ρ} (μ, p^{*}) \leq ε / 2$ and $d_{ρ} (μ, ν) < ε$ .

Let $(X, Y)$ have law $μ$ . Its first marginal gives the point $x$ the mass $μ_{X} ({x}) = ε / 2 > 0$ , because $p^{*}$ contributes nothing there. For $A = {x}$ and any Borel $B$ , definition 173.3 reads $κ (x) (B) μ_{X} ({x}) = μ ({x} \times B) = \frac{ε}{2} α (B),$ so $κ (x) = α$ for every version $κ$ . A conditioning operator must agree with some version $μ_{X}$ -almost everywhere, and ${x}$ has positive $μ_{X}$ -measure, so $Φ (μ, x) = α$ . ◻

Theorem 173.10 — Every conditioning operator is discontinuous everywhere ¶

Let $F \subseteq M_{1} ([0, 1]^{2})$ contain every finitely supported rational-mass measure. Then no conditioning operator for $F$ is continuous at any point of $F \times [0, 1]$ , and hence none is computable.

Referenced from 8 locations

Computable Conditioning and Its Limits

Proof of Theorem 173.10 — Every conditioning operator is discontinuous everywhere

Proof. Give $M_{1} ([0, 1])$ and $M_{1} ([0, 1]^{2})$ the weak topology, which the Prokhorov metric induces. Let $Φ$ be a conditioning operator, let $(ν, x)$ be any point, and let $α, α^{'}$ be two finitely supported rational-mass measures with disjoint supports, so that some weak neighborhood separates them. For every $ε > 0$ , lemma 173.9 provides $μ$ and $μ^{'}$ within Prokhorov distance $ε$ of $ν$ with $Φ (μ, x) = α$ and $Φ (μ^{'}, x) = α^{'}$ . Hence every neighborhood of $(ν, x)$ contains points whose images are separated, so $Φ$ is not continuous at $(ν, x)$ . By convention 173.6 a computable map is continuous, so $Φ$ is not computable. ◻

Remark 173.11 — What the perturbation says ¶

Lemma 173.9 is the precise form of a familiar warning: a finite approximation to a joint distribution determines nothing about the result of conditioning at a particular point. The perturbation is not exotic — it adds an atom of small mass at the query point — and it is available inside every class of distributions containing the finitely supported ones. The theorem therefore rules out a general conditioning algorithm even for inputs restricted to distributions whose conditional distributions are continuous in $x$ , since the restriction does not exclude the perturbed measures.

Referenced from 2 locations

Computable Conditioning and Its Limits

Convention 173.12 — Imported negative theorems ¶

Theorem 173.10 rules out an operator, not a single instance: for each fixed computable joint distribution it leaves open whether its conditional distribution map is computable. The following statements of Ackerman–Freer–Roy close that gap and are imported at exactly these signatures.

Their Theorem 7.6: there are $P$ -almost computable random variables $W$ and $Y$ on $[0, 1]$ such that the conditional distribution map $P [Y ∣ W = \cdot]$ is $P_{W}$ -almost continuous but not $P_{W}$ -almost computable.

Their Corollary 7.7, for the pair $(X, N)$ underlying that construction: if $P [N ∣ X = \cdot]$ is $A$ -computable on a set of $P_{X}$ -measure greater than $5 / 6$ for an oracle $A \subseteq N$ , then $A$ computes the halting set; consequently no version of $P [N ∣ X = \cdot]$ is $P_{X}$ -almost computable.

Their Proposition 7.8: for every $k$ , the map $P [N = k ∣ X = \cdot]$ is not $L^{1} (P_{X})$ -computable, so the failure is not repaired by weakening the demand to an $L^{1}$ approximation.

Their Theorem 6.7: for every conditioning program for a class containing the finitely supported rational-mass measures, and for every code $e$ of a computable distribution and code $j$ of a computable point, one can compute a code $i$ with $μ_{i} = μ_{e}$ on which the program returns no information at all.

What these imports supply is a single computable joint distribution whose conditioning problem encodes the halting set. Their mechanism is a mixture over $n \in N$ of piecewise constant densities whose $n$ -th piece records whether the $n$ -th program halts; the mixture’s value at a point determines, through a base- $5$ expansion with digits confined to ${2, 3, 4}$ , the whole halting sequence, so a semicomputable approximation to the posterior would decide it. Nothing below uses these statements as a premise; they are recorded because theorem 173.10 alone does not establish them.

Referenced from 4 locations

Computable Conditioning and Its Limits

Exercise 173.4 ¶

★☆☆ In lemma 173.9, verify directly from definition 173.3 that a version at a point of positive marginal mass is forced, and state where the proof would fail if $p^{*} ({x} \times [0, 1]) > 0$ were allowed.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.5 ¶

★★☆ Prove that $d_{ρ} (μ, ν) \leq \frac{1}{2} ‖ μ - ν ‖_{TV}$ for probability measures on a metric space, and identify the step of lemma 173.9 that uses it.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.6 ¶

★★☆ Give a class $F \subseteq M_{1} ([0, 1]^{2})$ for which a computable conditioning operator does exist, and explain why it does not contradict theorem 173.10.

Referenced from 2 locations

Computable Conditioning and Its Limits

Where conditioning is computable

The perturbation of lemma 173.9 installs an atom at the query point. Two hypotheses defeat it, and each yields a positive result. The first forbids the query point from being a limit of other query points: the observed variable takes discrete values, each of positive probability. The second forbids atoms altogether by requiring a bounded computable conditional density, so that the answer at $x$ is an integral rather than a quotient of atoms.

Proposition 173.13 — Discrete observations ¶

Let $X$ take values in a countable set $D$ with the discrete $σ$ -algebra, let $Y$ take values in a measurable space $T$ , and suppose that $P {X = d} > 0$ for every $d \in D$ . Then $κ (d) (B) = P {X = d, Y \in B} / P {X = d}$ defines a version of $P [Y ∣ X = \cdot]$ , it is the unique version, and if the reals $P {X = d, Y \in B}$ and $P {X = d}$ are computable uniformly in $d$ and a witness for $B$ , then $κ$ is computable uniformly in the same data.

Referenced from 5 locations

Computable Conditioning and Its Limits

Proof of Proposition 173.13 — Discrete observations

Proof. Each $κ (d)$ is a probability measure, since $B \mapsto P {X = d, Y \in B}$ is a measure of total mass $P {X = d}$ ; measurability in $d$ is automatic on a discrete space. For $A \subseteq D$ , $\begin{aligned} \int_{A} κ (d) (B) d P_{X} (d) \\ = \sum_{d \in A} \frac{P {X = d, Y \in B}}{P {X = d}} P {X = d} \\ = P {X \in A, Y \in B}, \end{aligned}$ which is definition 173.3. Uniqueness holds because every singleton has positive measure, so proposition 173.4 leaves no room for a discrepancy. For computability, the quotient of two computable reals with computable nonzero denominator is computable: from approximations $a_{n} \to a$ and $b_{n} \to b$ with $b > 0$ , and a rational $q$ with $0 < q < b$ obtained from the approximations, the quotient $a_{n} / b_{n}$ approximates $a / b$ with an error bounded by $| a_{n} - a | / q + | a | | b_{n} - b | / q^{2}$ , and both terms are driven below any prescribed $2^{- k}$ by taking $n$ large enough, uniformly in the data. ◻

Example 173.14 — The opening computation, checked against the definition ¶

Take $D = {positive, negative}$ and $T = {ill, well}$ with the joint masses of the opening paragraph. Then $κ (positive) ({ill}) = \frac{99 / 100000}{2097 / 100000} = \frac{11}{233}$ and $κ (positive) ({well}) = \frac{222}{233}$ , a probability measure; the disintegration equation at $A = D$ recovers $P {Y = ill} = 1 / 1000$ . Every number is a reduced rational, and the only side condition checked is the positivity of $P {X = positive}$ .

Referenced from 2 locations

Computable Conditioning and Its Limits

Proposition 173.15 — Bayes' rule under a positive bounded density ¶

Let $X$ and $Y$ take values in measurable spaces $S$ and $T$ , and suppose there is a jointly measurable $p : S \times T \to (0, \infty)$ , bounded, a conditional density of $X$ given $Y$ with respect to a $σ$ -finite measure $λ$ on $S$ : that is, $P {X \in A, Y \in B} = \int_{B} \int_{A} p (x, y) d λ (x) d P_{Y} (y)$ for all measurable $A, B$ . Then $κ (x) (B) = \frac{\int_{B} p (x, y) d P_{Y} (y)}{\int_{T} p (x, y) d P_{Y} (y)}$ is a version of $P [Y ∣ X = \cdot]$ .

Referenced from 7 locations

Computable Conditioning and Its Limits

Proof of Proposition 173.15 — Bayes' rule under a positive bounded density

Proof. The denominator is finite because $p$ is bounded and $P_{Y}$ is a probability measure, and it is positive because $p > 0$ ; so $κ (x)$ is a probability measure for each $x$ , and it is measurable in $x$ by Tonelli’s theorem (convention 172.12) applied to $(x, y) \mapsto p (x, y) 1_{B} (y)$ . Write $m (x) = \int_{T} p (x, y) d P_{Y} (y)$ for the denominator. First, $P_{X} = m λ$ in the sense that $P_{X} (A) = \int_{A} m d λ$ : take $B = T$ in the density hypothesis and exchange the order of integration by Tonelli. Then for measurable $A, B$ , $\begin{aligned} \int_{A} κ (x) (B) d P_{X} (x) \\ \overset{P_{X} = m λ}{=} \int_{A} \frac{\int_{B} p (x, y) d P_{Y} (y)}{m (x)} m (x) d λ (x) \\ \overset{T o n e l l i}{=} \int_{B} \int_{A} p (x, y) d λ (x) d P_{Y} (y) \\ \overset{h y p o t h e s i s}{=} P {X \in A, Y \in B} . \end{aligned}$ The first step uses the change of measure for the nonnegative measurable integrand $x \mapsto κ (x) (B)$ , which is legitimate by the three-stage ascent of theorem 172.14 applied to indicators, simple functions, and monotone limits. ◻

Proposition 173.16 — Computability of Bayes' rule ¶

In the situation of proposition 173.15, suppose in addition that $S, T$ are computable Polish spaces, that $P_{Y}$ is a computable measure, that $p$ is computable on $R \times T$ for some $R \subseteq S$ , and that $p$ is bounded away from $0$ on $R \times T$ . Then $κ$ is computable on $R$ .

Referenced from 5 locations

Computable Conditioning and Its Limits

Proof of Proposition 173.16 — Computability of Bayes' rule

Proof. For a $P_{Y}$ -almost decidable $B$ , the map $x \mapsto \int_{B} p (x, y) d P_{Y} (y)$ is computable on $R$ , uniformly in a witness for $B$ : this is the imported computability of integration against a computable measure for a bounded computable integrand, used by Ackerman–Freer–Roy as their Proposition 2.30. The denominator is the same integral with $B = T$ , and it is bounded below by the assumed positive bound times $P_{Y} (T) = 1$ ; so the quotient is computable by the division argument of proposition 173.13. A measure on a computable Polish space is determined computably by its values on almost decidable sets, so $κ (x)$ is a computable point of $M_{1} (T)$ uniformly in $x \in R$ . ◻

Corollary 173.17 — Observations corrupted by independent noise ¶

Let $U$ be a random variable in $R$ and $V$ a random variable in a computable Polish space, and let $E$ be independent of $(U, V)$ with a bounded computable density $p_{E}$ with respect to Lebesgue measure that is positive everywhere. Put $X = U + E$ . Then $P [(U, V) ∣ X = \cdot]$ is computable.

Referenced from 3 locations

Computable Conditioning and Its Limits

Proof of Corollary 173.17 — Observations corrupted by independent noise

Proof. By independence, the conditional density of $X$ given $(U, V) = (u, v)$ with respect to Lebesgue measure is $p (x, (u, v)) = p_{E} (x - u)$ : for measurable $A \subseteq R$ and $B$ in the range of $(U, V)$ , $P {X \in A, (U, V) \in B} = \int_{B} \int_{A} p_{E} (x - u) d x d P_{(U, V)} (u, v)$ by the independence of $E$ and the translation formula for Lebesgue measure. This $p$ is positive, bounded and computable, so proposition 173.15, proposition 173.16 apply. ◻

Remark 173.18 — The gap between the two regimes ¶

Corollary 173.17 does not make the noise level negotiable. Adding noise $σ Z$ with $Z$ standard Gaussian to the construction of convention 173.12 yields, for every $σ > 0$ , a computable conditional distribution map; as $σ \to 0$ these converge weakly to the noncomputable one. Hence no algorithm computes, from a desired accuracy, a value of $σ$ small enough to guarantee it. The positive results are about the regime, not about approximating the negative one. A fourth positive regime — exchangeable sequences, where a computable de Finetti theorem supplies posteriors of the directing random measure — is due to Freer and Roy and is not reconstructed here.

Referenced from 2 locations

Computable Conditioning and Its Limits

Remark 173.19 — Boundary ¶

This chapter exports its definitions and proposition 173.4, theorem 173.10, proposition 173.13, proposition 173.15 and proposition 173.16. It exports no statement about a programming language: the negative results are about maps between spaces of measures, not about a syntax, and no claim is made here that a particular probabilistic language can or cannot express conditioning. The imported statements of convention 173.12 are not used as premises anywhere in this book.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.7 ¶

★☆☆ Verify proposition 173.15 for $S = T = {0, 1}$ with counting measure $λ$ , and check that it reproduces proposition 173.13.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.8 ¶

★★☆ Give a conditional density that is positive and computable but unbounded, for which the denominator in proposition 173.15 is infinite for some $x$ . State which hypothesis of proposition 173.16 fails.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.9 ¶

★★☆ For $U$ uniform on ${0, 1}$ and $E$ uniform on $[- σ, σ]$ , compute $P [U ∣ X = x]$ for $X = U + E$ explicitly as a function of $x$ and $σ$ , and describe its limit as $σ \to 0$ at $x = 1 / 2$ .

Referenced from 2 locations

Computable Conditioning and Its Limits

Suggested first pass.

None of these problems is a prerequisite for a later chapter. Begin with exercise 173.10, then exercise 173.11, then the practical project exercise 173.14.

Exercise 173.10 ¶

★☆☆ Compute, as reduced rationals, the posterior of a two-state cause given three conditionally independent binary observations with likelihoods $3 / 4$ and $1 / 4$ , and verify the disintegration equation of definition 173.3 for the resulting kernel.

Referenced from 3 locations

Computable Conditioning and Its Limits

Exercise 173.11 ¶

★★☆ Reconstruct lemma 173.9 with $ν$ the uniform measure on $[0, 1]^{2}$ , $x = 1 / 2$ , $α = δ_{1 / 3}$ , and $ε = 1 / 10$ : write $p^{*}$ and $μ$ explicitly and compute $μ_{X} ({1 / 2})$ .

Referenced from 3 locations

Computable Conditioning and Its Limits

Exercise 173.12 ¶

★★☆ In example 173.2, compute for each family the conditional expectation $E [X^{2} ∣ C_{ε}]$ and $E [X^{2} ∣ D_{ε}]$ exactly, and take both limits. State the two limits and the ratio between them.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.13 ¶

★★★ Prove that if a conditioning operator were continuous at one point of $F \times [0, 1]$ , then the perturbation of lemma 173.9 would have to fail at that point, and deduce theorem 173.10 again by contradiction rather than directly. Compare the two arguments and state which hypotheses each uses.

Referenced from 2 locations

Computable Conditioning and Its Limits

Exercise 173.14 ¶

★★★ Practical project.finite-conditioning-checker Build an exact finite conditioner. Its input is a finite joint distribution over pairs $(x, y)$ with reduced rational masses summing to $1$ , together with an observation $x_{0}$ ; its output is either the exact posterior table $y \mapsto κ (x_{0}) ({y})$ or a rejection naming the reason. The program has three parts: a normalizer that checks the input masses sum to $1$ ; the elementary conditioner of definition 173.1 implemented on reduced rationals with integer arithmetic; and a checker that verifies the disintegration equation of definition 173.3 for the computed kernel on every pair $(A, B)$ of subsets of the finite value sets.

The invariant to maintain is that no division is performed before the denominator has been checked nonzero, and that the output table sums to exactly $1$ whenever a table is produced. The concrete result is the posterior for the opening example: with the joint table $\begin{matrix} {(pos, ill) \mapsto 99 / 100000, (pos, well) \mapsto 1998 / 100000, \\ (neg, ill) \mapsto 1 / 100000, (neg, well) \mapsto 97902 / 100000} \end{matrix}$ and the observation $pos$ , the program must print the posterior table ${ill \mapsto 11 / 233$ , $well \mapsto 222 / 233}$ .

The acceptance test is decidable and exact: that table, verbatim; a rejection naming a zero denominator when the observation is a value of probability zero added to the input; a rejection naming a mass defect when the input masses sum to $999 / 1000$ ; and a successful verification of the disintegration equation for all sixteen pairs of subsets in the example. The checker decides the finite case only. It does not bear on theorem 173.10, whose content is that no such program extends to arbitrary computable joint distributions on $[0, 1]^{2}$ .

Referenced from 3 locations