Computing lower expectations with respect to total variation distance and chi-squared divergence balls

Jasper De Bock · 2026

Read Computing lower expectations with respect to total variation distance and chi-squared divergence balls by Jasper De Bock (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30091.txt.

Introduction

Jasper De Bock derives closed-form expressions for lower expectations under two balls around a probability distribution over a finite set. One ball gathers distributions close in total variation distance, a measure of how much two distributions differ. The other gathers distributions close in chi-squared divergence, another score of disagreement between distributions. A lower expectation reports the most pessimistic average a quantity can take across the ball, a useful guard when the true distribution is only roughly known. The paper's formulas give those worst-case averages directly.

Catalog record

CREATORJasper De Bock
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32418
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30091

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computing lower expectations with respect to total variation distance and chi-squared divergence balls Jasper De Bock Abstract We derive closed form expressions for the lower expectations that correspond to total variation distance and chi-squared divergence balls around a probability mass function over a finite set. 1 Introduction In the context of our work on robustness quantification for probabilistic classifiers [ 1 ] , we had to evaluate the lower expectations that correspond to total variation distance [ 2 ] and chi-squared divergence [ 2 ] balls around a categorical/multinomial distribution. To our surprise, while it seems to us that this is a task that is essentially well understood from Distributionally Robust Optimization (DRO), we were unable to find closed form expressions for these lower expectations in the literature. This note aims to remedy this situation. 2 General setting Let \mathcal{X} be a finite non-empty set, with |\mathcal{X}|=n , let \Sigma_{\mathcal{X}} be the set of all probability mass functions over \mathcal{X} , and let \mathbb{R}^{\mathcal{X}} be the set of all real-valued functions on \mathcal{X} . For any f\in\mathbb{R}^{\mathcal{X}} and any p\in\Sigma_{\mathcal{X}} , we write E_{p}(f) for the expectation of f with respect to p , which is defined as E_{p}(f):=\sum_{x\in\mathcal{X}}p(x)f(x). For any non-empty set \mathcal{M}\subseteq\Sigma_{\mathcal{X}} , we write \underline{E}_{\mathcal{M}}(f) for the lower expectation of f with respect to \mathcal{M} , which is defined as \underline{E}_{\mathcal{M}}(f):=\inf_{p\in\mathcal{M}}E_{p}(f). Concretely, we are interested in computing \underline{E}_{\mathcal{M}}(f) for sets \mathcal{M} of the form B_{d}(p,\delta)=\{q\in\Sigma_{\mathcal{X}}:d(q,p)\leq\delta\}, where p\in\Sigma_{\mathcal{X}} is a given probability mass function, d:\Sigma_{\mathcal{X}}\times\Sigma_{\mathcal{X}}\to\mathbb{R}_{\geq 0} is a given distance/divergence, and \delta\in\mathbb{R}_{\geq 0} is a given radius. More specifically, we focus on the cases where d is the total variation distance or the \chi^{2} -divergence. 3 Total variation balls The first case that we consider is when d is the total variation distance, which is defined for all q\in\Sigma_{\mathcal{X}} by d_{\mathrm{TV}}(q,p):=\frac{1}{2}\sum_{x\in\mathcal{X}}|q(x)-p(x)|. In this case, for any \delta\in[0,1] , we write B_{\mathrm{TV}}(p,\delta) instead of B_{d_{\mathrm{TV}}}(p,\delta) . For any given f\in\mathbb{R}^{\mathcal{X}} , our aim is to compute \underline{E}_{B_{\mathrm{TV}}(p,\delta)}(f) , which we will henceforth denote by \underline{E}^{\mathrm{TV}}_{p,\delta}(f) for the sake of brevity. The first step in computing \underline{E}^{\mathrm{TV}}_{p,\delta}(f) is to sort the elements of \mathcal{X}=\{x_{1},\ldots,x_{n}\} in such a way that f(x_{1})\leq f(x_{2})\leq\cdots\leq f(x_{n}) . We will henceforth assume that \mathcal{X} is ordered in this way. Now let r\in\{1,\ldots,n\} be the smallest index such that \delta\geq\sum_{i=r+1}^{n}p(x_{i}) . Note that such an index must exist, since \sum_{i=n+1}^{n}p(x_{i})=0 and \delta\in[0,1] . The following result then provides the desired closed form expression. Theorem 1 . Let r be defined as above. Then \underline{E}^{\mathrm{TV}}_{p,\delta}(f)=E_{q_{\mathrm{TV}}}(f) where, if r>1 , q_{\mathrm{TV}}\in\Sigma_{\mathcal{X}} is given by q_{\mathrm{TV}}(x_{i}):=\begin{cases}p(x_{1})+\delta&\text{if }i=1,\\ p(x_{i})&\text{if }i\in\{2,\ldots,r-1\},\\ \sum_{i=r}^{n}p(x_{i})-\delta&\text{if }i=r,\\ 0&\text{if }i\in\{r+1,\ldots,n\}.\end{cases} and, if r=1 , q_{\mathrm{TV}}\in\Sigma_{\mathcal{X}} is given by q_{\mathrm{TV}}(x_{i}):=\begin{cases}1&\text{if }i=1,\\ 0&\text{if }i\in\{2,\ldots,n\}.\end{cases} Intuitively, this corresponds to constructing q_{\mathrm{TV}} starting from p , by moving as much mass as possible from the elements of \mathcal{X} with the highest f -values to the element of \mathcal{X} with the lowest f -value, until we have moved a total mass of \delta or, if r=1 , have moved all available mass. 4 chi-squared divergence balls The second case that we consider is when d is the chi-squared divergence, often denoted as \chi^{2} -divergence, which, if p(x_{i})>0 for all i\in\{1,\ldots,n\} , is defined for all q\in\mathbb{R}^{\mathcal{X}} by d_{\chi^{2}}(q,p):=\sum_{x\in\mathcal{X}}\frac{(q(x)-p(x))^{2}}{p(x)}=\sum_{x\in\mathcal{X}}p(x)\left(\frac{q(x)}{p(x)}-1\right)^{2}. In this case, for any \delta\geq 0 , we write B_{\chi^{2}}(p,\delta) instead of B_{d_{\chi^{2}}}(p,\delta) . For any given f\in\mathbb{R}^{\mathcal{X}} , our aim is to compute \smash{\underline{E}_{B_{\chi^{2}}(p,\delta)}(f)} , which we will henceforth denote by \underline{E}^{\chi^{2}}_{p,\delta}(f) for the sake of brevity. The first step is again to sort the elements of \mathcal{X}=\{x_{1},\ldots,x_{n}\} in such a way that f(x_{1})\leq f(x_{2})\leq\cdots\leq f(x_{n}) . Let \ell be the largest index such that f(x_{\ell})=f(x_{1}) . Next, for any k\in\{\ell,\ldots,n\} , we define m_{k}:=\sum_{i=1}^{k}p(x_{i}),~~\mu_{k}:=\frac{1}{m_{k}}\sum_{i=1}^{k}p(x_{i})f(x_{i})\text{ and }\sigma_{k}^{2}:=\frac{1}{m_{k}}\sum_{i=1}^{k}p(x_{i})(f(x_{i})-\mu_{k})^{2} We also let \delta_{\ell}:=+\infty and, for any k\in\{\ell+1,\ldots,n\} , let \delta_{k}:=\frac{1}{m_{k}}\left(\frac{\sigma_{k}^{2}}{(f(x_{k})-\mu_{k})^{2}}+1-m_{k}\right). These \delta_{k} are the critical values of \delta at which the lower expectation \underline{E}^{\chi^{2}}_{p,\delta}(f) changes its form, as we will see below. We start out by showing that they are nicely ordered. Proposition 1 . The \delta_{k} are well-defined, positive and non-increasing in k : +\infty=\delta_{\ell}>\delta_{\ell+1}\geq\cdots\geq\delta_{n-1}\geq\delta_{n}>0. Now let r\in\{\ell,\ldots,n\} be the largest index such that \delta_{r}>\delta . Due to the previous proposition, this means that r is the unique value in \{\ell,\ldots,n\} such that \delta_{\ell}\geq\cdots\geq\delta_{r}>\delta\geq\delta_{r+1}\geq\cdots\geq\delta_{n}\geq 0 The following theorem then gives us the desired closed form expression for the lower expectation that we are after. Theorem 2 . With r\in\{\ell,\ldots,n\} defined as above, we have that \underline{E}^{\chi^{2}}_{p,\delta}(f)=\begin{cases}\mu_{r}-\sigma_{r}\sqrt{m_{r}\delta-(1-m_{r})}&\text{if }r>\ell,\\ f(x_{1})&\text{if }r=\ell.\end{cases} (1) If |\mathcal{X}|=3 , Equation ( 1 ) for example results in the following case distinction: \underline{E}^{\chi^{2}}_{p,\delta}(f)=\begin{cases}\mu_{3}-\sigma_{3}\sqrt{\delta}&\text{if }\delta<\delta_{3},\\ \mu_{2}-\sigma_{2}\sqrt{m_{2}\delta-(1-m_{2})}&\text{if }\delta_{3}\leq\delta<\delta_{2},\\ f(x_{1})&\text{if }\delta\geq\delta_{2}.\end{cases} (2) If |\mathcal{X}|=2 , the resulting case distinction can be simplified even further, resulting in the following simple expression: \underline{E}^{\chi^{2}}_{p,\delta}(f)=\begin{cases}\displaystyle\sum_{i=1}^{2}p(x_{i})f(x_{i})-\sqrt{\delta p(x_{1})p(x_{2})}|f(x_{2})-f(x_{1})|&\text{if }\delta<\frac{p(x_{2})}{p(x_{1})},\\ f(x_{1})&\text{if }\delta\geq\frac{p(x_{2})}{p(x_{1})}.\end{cases} (3) Appendix A Proofs for the results in Section 3 Proof of Theorem 1 . If r=1 , then \delta\geq\sum_{i=2}^{n}p(x_{i}) , which implies that \displaystyle d_{\mathrm{TV}}(q_{\mathrm{TV}},p) \displaystyle=\frac{1}{2}\sum_{i=1}^{n}|q_{\mathrm{TV}}(x_{i})-p(x_{i})| \displaystyle=\frac{1}{2}\left(1-p(x_{1})+\sum_{i=2}^{n}p(x_{i})\right)=\sum_{i=2}^{n}p(x_{i})\leq\delta. The result then follows because \min f\leq\underline{E}^{\mathrm{TV}}_{p,\delta}(f)\leq E_{q_{\mathrm{TV}}}(f)=f(x_{1})=\min f . So we can now assume that r>1 , which implies that \sum_{i=r+1}^{n}p(x_{i})\leq\delta<\sum_{i=r}^{n}p(x_{i})\leq\sum_{i=2}^{n}p(x_{i})=1-p(x_{1}). Since B_{\mathrm{TV}}(p,\delta) is a non-empty closed subset of \Sigma_{\mathcal{X}} , the minimum \underline{E}^{\mathrm{TV}}_{p,\delta}(f) is well-defined and there is at least one q\in B_{\mathrm{TV}}(p,\delta) such that \underline{E}^{\mathrm{TV}}_{p,\delta}(f)=E_{q}(f) . Since the set of all q that attain this minimum is also closed, we can choose q^{*} to be one among them that maximizes q(x_{1}) . We first show that q^{*}(x_{1})\geq p(x_{1}) . Assume ex absurdo that q^{*}(x_{1})<p(x_{1}) . Since q^{*} and p are both probability mass functions, this implies that there is some i\in\{2,\ldots,n\} such that q^{*}(x_{i})>p(x_{i}) . Consider any such index. Then we can construct a new probability mass function q^{\prime} by mass \alpha=\min\{p(x_{1})-q^{*}(x_{1}),q^{*}(x_{i})-p(x_{i})\}>0 from x_{i} to x_{1} . This mass transfer does not alter the total variation distance to p , since we are moving the same mass \alpha in opposite directions, and the expectation of f does not increase since f(x_{1})\leq f(x_{i}) . This contradicts the definition of q^{*} , which was chosen to have the highest value of q(x_{1}) among all q such that \underline{E}^{\mathrm{TV}}_{p,\delta}(f)=E_{q}(f) . So we must have that q^{*}(x_{1})\geq p(x_{1}) , as claimed. Next, we show that q^{*}(x_{i})\leq p(x_{i}) for all i\in\{2,\ldots,n\} . Assume ex absurdo that there is some i\in\{2,\ldots,n\} such that q^{*}(x_{i})>p(x_{i}) . Consider any such index. Then we can construct a new probability mass function q^{\prime} by moving mass \alpha=q^{*}(x_{i})-p(x_{i})>0 from x_{i} to x_{1} . This mass transfer does not alter the total variation distance to p , since we are moving the same mass \alpha in opposite directions, and the expectation of f does not increase since f(x_{1})\leq f(x_{i}) . This contradicts the definition of q^{*} , which was chosen to have the highest value of q(x_{1}) among all q such that \underline{E}^{\mathrm{TV}}_{p,\delta}(f)=E_{q}(f) . So we must have that q^{*}(x_{i})\leq p(x_{i}) for all i\in\{2,\ldots,n\} , as claimed. As a next step, we show that q^{*}(x_{1})=p(x_{1})+\delta . Assume ex absurdo that p(x_{1})\leq q^{*}(x_{1})<p(x_{1})+\delta . Since \delta<1-p(x_{1}) , this implies that q^{*}(x_{1})<1 . So there is some i\in\{2,\ldots,n\} such that 0<q^{*}(x_{i})\leq p(x_{i}) . Consider any such i . Then we can construct a new probability mass function q^{\prime} by moving mass \alpha=q^{*}(x_{i})>0 from x_{i} to x_{1} . This mass transfer again does not alter the total variation distance to p

Read the complete text