Solutions to infra-exercises I

These are S’s solutions for the first set of infra-Bayesian exercises. Spoilers, of course!

I decree this a Moore method problem set! That means you’re allowed to be as pedantic about definitions as you like, and I commit to addressing your pedantry. Please shoot me an email if there’s a way I can improve this document’s rigor and/or clarity!

Notes

When the document says monotone, it means what most analysis textbooks call increasing. A better term in the context of posets, where the document defines monotonicity, would be order-preserving.

I shall use the terminology 0-nonnegative rather than 0-increasing for a functional \(f : V \to \mathbb R\) with \(f(\mathbf 0) \geq 0,\) since I find the latter misleading. I also like the terminology non-expansive for 1-Lipschitzness, since it describes the geometric intuition rather than being named after a dude, but won’t use it here for clarity.

I use the variable \(t\) for mixture coefficients out of habit.It’s typically used in topology, for instance when defining homotopy.

Problem 1

Let \(V\) be a real vector space. Show that a function \(g : V \to \mathbb R\) is affine iff \(g(x) = f(x) + c,\) where \(f(x) : V \to W\) is linear and \(c \in \mathbb R.\)

Solution

If: Let \(g(x)\) be as given. For any \(v_1, v_2 \in V\) and \(t \in [0, 1],\) we have \[\begin{align*} g(tv_1 + (1 - t)v_2) &= f(tv_1 + (1 - t)v_2) + c \newline &= tf(v_1) + (1 - t)f(v_2) + c \newline &= t(f(v_1) + c) + (1 - t)(f(v_2) + c) \newline &= t\cdot g(v_1) + (1 - t)\cdot g(v_2). \end{align*}\]

Only if: Let \(g(x)\) be affine. Define \(f(x) = g(x) - g(\mathbf 0).\) We must show that \(f(x)\) is linear; i.e., homogeneous and additive.

To show homogeneity, we have for any \(c \in [0, 1]\) \[\begin{align*} f(cx) &= f(cx + (1 - c)\mathbf 0) \newline &= g(cx + (1 - c)\mathbf 0) - g(\mathbf 0) \newline &= c\cdot g(x) + (1 - c)\cdot g(\mathbf 0) - g(\mathbf 0) \newline &= c\cdot g(x) - g(\mathbf 0) = c \cdot f(x). \end{align*}\]

For \(c > 1\) we have \(c^{-1} \in (0, 1).\) Therefore \[ \begin{align*} f(cx) &= f(c^2x/c) = \dfrac1c f(c^2 x). \end{align*}\]

Rewriting, we have \(cf(cx) = f(c^2x).\) Setting \(y = cx,\) we obtain the desired. It remains to show that \(f\) is homogeneous for a negative constant. We have \[\begin{align*} f(-x) &= g(-x) - g(\mathbf 0) \newline &= g(-x) - g\left(\dfrac12 x + \dfrac12 (-x)\right) \newline &= g(-x) - \dfrac12 g(x) - \dfrac12 g(-x) \newline &= \dfrac12 g(-x) - \dfrac12g(x) \newline &= \dfrac12 f(-x) - \dfrac12f(x), \end{align*}\] which implies \(f(-x) = -f(x).\)

To show additivity, we have for any \(v_1, v_2 \in V\) \[\begin{align*} f(v_1 + v_2) &= 2f\left(\dfrac12 v_1 + \dfrac12 v_2\right) \newline &= 2g\left(\dfrac12 v_1 + \dfrac12 v_2 \right) - 2g(\mathbf 0) \newline &= g(v_1) + g(v_2) - 2g(\mathbf 0) = f(v_1) + f(v_2). \end{align*}\]

This completes the proof.

Problem 2

Let \(f : \mathbb R \to \mathbb R\) be continuous and concave. Let \(T\) be the set of all affine functions \(\phi : \mathbb R \to \mathbb R\) such that \(\phi(x) \geq f(x)\) for all \(x.\) Show that \(f(x) = \inf T(x).\)

Solution

Fix an \(a \in \mathbb R.\) Assume \(f(a)\) is defined. \(f(a)\) is a lower bound for \(T(a)\) by construction.

Suppose \(k > f(a).\) We will show that there is a \(\phi \in T\) with \(k > \phi(a).\)

We claim the set \(C = \{(x, y) \in \mathbb R^2 \mid y \leq f(x)\}\) is convex and closed:

• Convex: Follows directly from concavity of \(f.\)
• Closed: We show that the complement of \(C\) \[C' = \{(x, y) \in \mathbb R^2 \mid y > f(x)\}\] is open under the \(\infty\)-norm. Let \(p = (x, y) \in C'.\) Let \(\varepsilon_1 = (y - f(x))/2 > 0.\) By continuity of \(f\) there is a \(\delta > 0\) such that \[|x_1 - x_2| < \delta \implies |f(x_1) - f(x_2)| < \varepsilon_1.\] Let \(\varepsilon = \min \{\varepsilon_1, \delta\}.\) Then whenever \(|x - x_1| < \varepsilon\) and \(|y - y_1| < \varepsilon,\) we have \[ \begin{align*} y_1 - f(x_1) &= (y_1 - y) + \left(y - f(x)\right) + \left(f(x) - f(x_1)\right) \newline &> -\varepsilon + 2\varepsilon_1 - \varepsilon_1 = \varepsilon_1 - \varepsilon \geq 0. \end{align*}\]

Since \(v = (a, k) \in \mathbb R^2 \setminus C,\) the Hahn-Banach separation theorem furnishes a linear, continuous \(F : \mathbb R^2 \to \mathbb R\) and \(s \in \mathbb R\) such that \(F(c) \leq s < F(v)\) for any \(c \in C.\) In particular, there are constants \(m, n \in \mathbb R\) such that \(F((x, y)) = mx + ny.\) The Hahn-Banach condition then says \[mx + n \cdot f(x) \leq s < ma + nk.\]

If \(n = 0,\) we have \(mx < ma\) for all \((x, y) \in C,\) which is absurd, since \((a, f(a)) \in C.\) Thus we may define \(\phi(x) = (s - mx)/n\). Then we have that \(\phi\) is affine, \(\phi(x) \geq f(x),\) and \(\phi(a) < k.\)

This completes the proof.

Problem 3a

Let \(f: \mathbb R \to \mathbb R\) be concave, monotone, 0-nonnegative, and 1-Lipschitz. Let \(T\) be the set of all affine functions \(\phi : \mathbb R \to \mathbb R\) satisfying the latter three properties and \(\phi(x) \geq f(x).\) Show that \(f(x) = \inf T(x).\)

Solution

Construct \(\phi\) as in the previous solution. We must show that \(\phi\) is monotone, 0-nonnegative, and 1-Lipschitz.

• Monotonicity: Suppose contrariwise that \(x_1 < x_2\) but \(\phi(x_1) > \phi(x_2).\) Since \(\phi\) is affine, there is some \(x_3 > x_1\) with \(\phi(x_3) < f(x_1) < f(x_3),\) a contradiction.
• 1-Lipschitz: Suppose contrariwise there are \(x_1, x_2 \in \mathbb R\) and \(\varepsilon > 0\) such that \[\frac{\phi(x_2) - \phi(x_1)}{x_2 - x_1} = 1 + \varepsilon.\] Since \(\phi\) is affine, \(\phi(x) = (1 + \varepsilon)x + \phi(0).\) Let \[c < \frac{f(0) - \phi(0)}{\varepsilon} < 0.\] Then we have \(f(c) \geq f(0) + c > \phi(0) + (1 + \varepsilon)c = \phi(c),\) a contradiction.
• 0-nonnegativity: \(\phi(0) \geq f(0) \geq 0.\)

This completes the proof.

Problem 3b

Let \(\Phi = \{\phi_i\}_{i \in I}\) be a collection of affine functions mapping \(\mathbb R \to \mathbb R\) that are each monotone, 1-Lipschitz, and 0-nonnegative. Show that \(f(x) = \inf \Phi(x)\) is continuous, concave, monotone, 1-Lipschitz, and 0-nonnegative.

Solution

• 0-nonnegativity: \(f(0) = \inf \Phi(0) = C.\) Suppose \(C < 0.\) Then there would exist \(\phi \in \Phi\) with \(\phi(0) = C/2 < 0,\) a contradiction.

• Monotonicity: Suppose contrariwise that \(x < y\) but \(f(x) > f(y).\) Then, for any \(\varepsilon > 0,\) there is a \(\phi \in \Phi\) with \(f(y) = \phi(y) + \varepsilon.\) We have \[\begin{align*} f(x) - \phi(x) &> f(y) - \phi(x) \newline &\geq f(y) - [\phi(y) - (y - x)] \newline &= \varepsilon + (y - x) > 0, \end{align*}\] a contradiction.

• 1-Lipschitz: Suppose towards a contradiction that \(f\) is not 1-Lipschitz. Then there exist \(x, y \in \mathbb R\) with \[\frac{|f(y) - f(x)|}{|y - x|} = L > 1.\] Suppose without loss of generality that \(x < y.\) Let \(\varepsilon > 0,\) choosing \(\varepsilon < (L - 1)|y - x|.\) Since \(f(x) = \inf \Phi(x),\) there is a \(\phi_i \in \Phi\) such that \(\phi_i(x) = f(x) + \varepsilon.\) Then we have \[ \begin{align*} f(y) - \phi_i(y) &\geq f(y) - \left(\phi_i(x) + |y - x|\right) \newline &= f(y) - \left(f(x) + \varepsilon + |y - x|\right) \newline &= [f(y) - f(x)] - \varepsilon - |y - x| \newline &= L|y - x| - \varepsilon - |y - x| \newline &= (L - 1)|y - x| - \varepsilon > 0, \end{align*}\] a contradiction.

• Continuity: Follows immediately.

• Concavity: Suppose contrariwise that \(f\) is not concave. Then there exist \(x, y \in \mathbb R\) and \(t \in (0, 1)\) such thatThe variable names here are for “line” and “curve." \[L = t\cdot f(x) + (1 - t)f(y) > f(tx + (1 - t)y) = C.\]

  By assumption, there is a function \(\phi \in \Phi\) such that \(\phi(tx + (1-t)y) = (L + C)/2.\) We must have \(\phi(x) \geq f(x)\) and \(\phi(y) \geq f(y).\) But since \(\phi\) is affine, we must have \(\phi(tx + (1-t)y) \geq L,\) a contradiction.

Problem 4a

Let \(\psi : C(X) \to \mathbb R\) be concave, monotone, 1-Lipschitz, and 0-nonnegative. Let \(\Phi\) be the set of all affine, monotone, 1-Lipschitz, and 0-nonnegative functions \(\phi : C(X) \to \mathbb R\) such that \(\phi \geq \psi.\) Show that \(\psi = \inf \Phi.\)

Solution

\(\psi\) is a lower bound for \(\Phi\) by construction. Fix \(f \in C(X)\) and suppose that \(k > \psi(f).\) We shall produce a \(\phi \in \Phi\) such that \(\psi(f) \leq \phi(f) < k.\)

We claim that the set \(S = \bigcup_{g \in C(X)} \left(g \times (-\infty, \psi(g)]\right) \subset C(X) \times \mathbb R\) is closed and convex:

• Closed: We show that the complement of \(S\) \[ S' = \bigcup_{g \in C(X)} \left(g \times (\psi(g), \infty)\right) \] is open under the \(\infty\)-norm. Let \((g, c) \in S'.\) Let \(\varepsilon = \left(c - \psi(g)\right)/2.\) Then for any \((h, k) \in C(X) \times \mathbb R\) with \(d_\infty(g, h) < \varepsilon\) and \(|c - k| < \varepsilon,\) we have \[ \begin{align*} k - \psi(h) &= (k - c) + \left(c - \psi(g)\right) + \left((\psi(g) - \psi(h)\right) \newline &> -\varepsilon + 2\varepsilon - d_\infty(g, h) \newline &> -\varepsilon + 2\varepsilon - \varepsilon = 0. \end{align*} \]
• Convex: Let \((f_1, c_1), (f_2, c_2) \in S.\) Let \(t \in (0, 1).\) Then \(t \cdot f_1 + (1 - t)f_2 \in C(X),\) and since \(\psi\) is concave, \[ t \cdot \psi(f_1) + (1 - t)\psi(f_2) \leq \psi(t\cdot f_1 + (1-t) f_2). \]

Therefore Hahn-Banach produces a linear functional \(F: C(X) \times \mathbb R \to \mathbb R\) and \(s \in \mathbb R\) such that for any \((g, c) \in S,\) \(F(g, c) \leq s < F(f, k).\) Since \(F\) is (bi)linear, we can write \[F(g, c) = F(g, 0) + F(0, c) = M(g) + nc\] for some linear \(M : C(X) \to \mathbb R\) and \(n \in \mathbb R.\) The Hahn-Banach condition then says

\[M(g) + nc \leq s < M(f) + nk.\]

As before, \(M \equiv 0\) and \(n = 0\) are impossible. If \(M \not \equiv 0\) and \(n = 0,\) the Hahn-Banach condition is \(M(g) < M(f)\) for all \(g \in C(X),\) which is absurd. Thus, we may define \[\phi(f) = \frac{s - M(g)}n.\]

Note that \(\phi\) is affine. Applying the Hahn-Banach condition to \((f, \psi(f))\) gives \(\psi(f) \leq \phi(f) < k,\) as desired.

It remains to show that \(\phi\) is monotone, 1-Lipschitz, and 0-nonnegative.

• 0-nonnegativity: \(\phi(0) \geq \psi(0) \geq 0.\)
• Monotonicity: Suppose contrariwise that \(f < g\) but \(\phi(f) > \phi(g).\) Since \(\phi\) is affine, there is some \(c \in \mathbb R\) and \(h(x) = f(x) + c\) for which \(\phi(h) < \psi(f) < \psi(h),\) a contradiction.
• 1-Lipschitz: This is the hard part.It took me multiple days by itself. Suppose there are \(f, g \in C(X)\) and \(\varepsilon > 0\) for which \[|\phi(f) - \phi(g)| = (1 + \varepsilon) d_\infty(f,g).\] Let \(U = \max\{f,g\}, L = \min\{f,g\}.\) Clearly \(U, L \in C(X).\) Also,\[\begin{align*} \phi(U) - \phi(L) &= \phi\left(\frac{f + g + |f - g|}2\right) - \phi\left(\frac{f + g -|f - g|}2\right) \newline &= M(|f-g|) \newline &\geq \left|M(f-g)\right| \newline &= \left|\phi(f) - \phi(g)\right| \newline &\geq (1 + \varepsilon) d_\infty(f, g) = (1 + \varepsilon) d_\infty(U, L). \end{align*}\] Since \(U > L,\) \(tU + (1-t)L\) is an increasing function of \(t.\) Take \[t < \dfrac{\psi(L) - \phi(L)}{\varepsilon \cdot d_\infty(U,L)}.\] If the right-hand side is positive, \(\phi(L) < \psi(L),\) which is a contradiction. So, \(t < 0,\) and we have \[\begin{align*} \phi(tU + (1-t)L) &= t\phi(U) + (1-t)\phi(L) \newline &= \phi(L) + t\cdot\left(\phi(U) - \phi(L)\right) \newline &\leq \phi(L) + t\cdot (1 + \varepsilon) d_\infty(U, L) \newline &< \phi(L) + \left(\frac{\psi(L) - \phi(L)}{\varepsilon \cdot d_\infty(U, L)}\right)\cdot \varepsilon \cdot d_\infty(U, L) + t\cdot d_\infty(U, L) \newline &= \psi(L) + t \cdot d_\infty(U, L) \newline &= \psi(L) - |t| \cdot d_\infty(U, L) \newline &= \psi(L) - d_\infty(tU, tL) \newline &= \psi(L) - d_\infty(tU + (1 - t)L, L) \newline &\leq \psi(L) - \left(\psi(L) - \psi(tU + (1 - t)L)\right) \newline &= \psi(tU + (1-t)L), \end{align*}\] a contradiction.

This completes the proof.

Problem 4b

Let \(\Phi = \{\phi_i\}_{i\in I}\) be a collection of affine functions mapping \(C(X) \to \mathbb R\) that are monotone, 1-Lipschitz, and 0-nonnegative. Show that \(f = \inf \Phi\) is continuous, concave, monotone, 1-Lipschitz, and 0-nonnegative.

Solution

• 0-nonnegativity: Suppose contrariwise that \(f(0) < 0.\) Then there must be \(\phi_i\) with \(\phi_i(0) = f(0)/2 < 0,\) a contradiction.
• Monotonicity: Suppose contrariwise that there exist \(m, n \in C(X)\) with \(m < n\) and \(f(m) > f(n).\) By assumption, for any \(\varepsilon > 0,\) there is a \(\phi_i\) with \(f(n) = \phi_i(n) + \varepsilon.\) Then we have \[\begin{align*} f(m) - \phi_i(m) &> f(n) - \phi_i(m) \newline &= \phi_i(n) - \phi_i(m) + \varepsilon > 0, \end{align*}\] a contradiction.
• 1-Lipschitz: Suppose there are functions \(m, n \in C(X)\) and \(\delta > 0\) with \[\frac{|f(n) - f(m)|}{d_\infty(m, n)} = 1 + \delta.\] Without loss of generality, assume \(f(n) \geq f(m).\) Let \(0 < \varepsilon < \delta \cdot d_\infty(m, n).\) There is a \(\phi_i\) with \(\phi_i(m) = f(m) + \varepsilon.\) We have \[\begin{align*} f(n) - \phi_i(n) &= f(m) + (1 + \delta) d_\infty(m, n) - \phi_i(n) \newline &\geq f(m) + \delta \cdot d_\infty(m, n) + |\phi_i(n) - \phi_i(m)| - \phi_i(n) \newline &\geq f(m) + \delta \cdot d_\infty(m, n) - \phi_i(m) \newline &= \delta \cdot d_\infty(m, n) - \varepsilon > 0, \end{align*}\] a contradiction.
• Continuity: Follows immediately.
• Concavity: Suppose contrariwise that \(f\) is not concave. Then there exist \(g, h \in C(X)\) and \(t \in (0, 1)\) such that \[L = t \cdot f(g) + (1 - t) f(h) > f(t \cdot g + (1 - t) h) = C.\] By assumption, there is a \(\phi \in \Phi\) with \(\phi(t \cdot g + (1 - t)h) = (L + C)/2,\) \(\phi(g) \geq f(g),\) and \(\phi(h) \geq f(h).\) But since \(\phi\) is affine, we must have \(\phi(t \cdot g + (1 - t)h) \geq L,\) a contradiction.

This completes the proof.

Problem 5b

Let \(m \in \mathcal M^\pm(X).\) Show that \(\phi : C(X) \to \mathbb R\) defined by \(\phi(g) = \int_X g(x) ~\mathrm dm\) is a continuous linear functional.

Solution

Lebesgue integrals are always linear. Let \(\varepsilon > 0.\) We must produce \(\delta > 0\) such that whenever \(d_\infty(f, g) < \delta,\) \[\left| \int_X f ~\mathrm dm - \int_X g ~\mathrm dm \right| < \varepsilon.\] If \(m \) is the zero measure then there is nothing to prove. Suppose \(m\) is nonzero. Let \[\delta = \frac{\varepsilon}{\int_X \mathrm dm^+ + \int_X \mathrm dm^-}.\] Then we have \[\begin{align*} \left| \int_X f ~\mathrm dm - \int_X g ~\mathrm dm \right| &= \left| \int_X (f - g) ~\mathrm dm \right| \newline &= \left| \int_X (f-g) ~\mathrm dm^+ - \int_X (f - g) ~\mathrm dm^- \right| \newline &\leq \left|\int_X (f - g) ~\mathrm dm^+ \right| + \left| \int_X (f - g) ~\mathrm dm^- \right| \newline &\leq \int_X |f - g| ~\mathrm dm^+ + \int_X |f - g| ~\mathrm dm^- \newline &< \int_X \delta ~\mathrm dm^+ + \int_X \delta ~\mathrm dm^- \newline &= \delta \left[\int_X \mathrm dm^+ + \int_X \mathrm dm^- \right] = \varepsilon. \end{align*}\]

Problem 5c

What extra conditions on a continuous linear functional \(F : C(X) \to \mathbb R\) are required so that it corresponds to a positive measure? What about a probability measure?

Solution

Say \(F\) is positive if whenever \(f \geq 0,\) \(F(f) \geq 0.\) By Riesz-Markov-Kakutani, positive functionals correspond to positive measures. Note that this implies monotonicity by the linearity of \(F.\)

To have a probability measure, we need \(F(1) = \int_X \mathbf 1_X ~\mathrm dm = m(X) = 1.\) Note that this implies 1-Lipschitzness: if \(d_\infty(f, g) = \varepsilon\) and \(F\) is positive, then \[\begin{align*} | F(f) - F(g) | = | F(f - g) | \leq F\left( | f-g | \right) \leq F(\varepsilon) = \varepsilon F(1) = \varepsilon. \end{align*}\]

Problem 6

Let \(\phi : C(X) \to \mathbb R\) be affine, monotone, 1-Lipschitz, and 0-nonnegative. Show that \(\phi\) corresponds to an affine measure \((m, b)\) with \(0 \leq m(X) \leq 1.\)

Solution

We have \(\phi(f) = M(f) + \phi(0),\) where \(M\) is linear and monotone, hence corresponds to a positive measure \(m.\) Since \(M\) is 1-Lipschitz, we have \(m(X) = M(1) \in [0, 1].\)

Fundamental Theorem of Inframeasures, forward direction

Let \(\psi : C(X) \to \mathbb R\) be concave, monotone, 1-Lipschitz, and 0-increasing. Let \(T\) be the set of (positive) affine measures above \(\psi\): \[T = \{(m, b): m(g) + b \geq \psi(g) \text{ for all } g \in C(X)\}.\]

Prove that \(\psi(g) = \inf_{(m, b) \in T} (m(g) + b).\)

Solution

We need to show that each \((m, b) \in T\) corresponds to an affine \(\phi : C(X) \to \mathbb R\) such that \(\phi \geq \psi \) and \(\phi\) is 1-Lipschitz, 0-nonnegative, and monotone. Define \(\phi(g) = m(g) + b.\) Then \(\phi\) is affine and above \(\psi\) by definition.

• Monotonicity: Since \(m\) is positive, \(\phi\) is monotone.
• 0-nonnegativity: \(\phi(\mathbf 0) = m(\mathbf 0) + b \geq \phi(\mathbf 0) > 0.\)
• 1-Lipschitz: It suffices to show that \(m(\mathbf 1) \leq 1.\) Suppose contrariwise that \(m(\mathbf 1) = 1 + \varepsilon.\) Let \(a < (\psi(\mathbf 0) - b)/\varepsilon \leq 0.\) Then \[\begin{align*} \phi(a\mathbf 1) &= a \cdot m(\mathbf 1) + b \newline &= a(1 + \varepsilon) + b \newline &< a + \varepsilon\left(\frac{\psi(\mathbf 0) - b}\varepsilon\right) + b \newline &= \psi(\mathbf 0) + a \newline &\leq \psi(a\mathbf 1), \end{align*}\] a contradiction.

This completes the proof.

Fundamental Theorem of Inframeasures, backward direction

For all sets \(\Psi\) of affine measures \(m\) with \(0 \leq m(\mathbf 1) \leq 1,\) show that the functional \(\psi : C(X) \to \mathbb R\) defined by \[\psi(g) = \inf_{(m, b) \in \Psi} (m(g) + b)\] is concave, monotone, 1-Lipschitz, and 0-nonnegative.

Solution

\(\Psi\) corresponds to a set \(\Phi\) of affine, monotone, 1-Lipschitz, 0-nonnegative functionals via \((m, b) \mapsto (g \mapsto m(g) + b).\)