# What's the standard name for sets of a given size with maximal probability (or a given probability and minimal size)?

The definition I'm going to give isn't quite the concept I really want, but it's a good approximation. I don't want to make the definition too technical and specific because if there's a standard name for a slightly different definition, then I want to know about it.

Let $(X,\mu)$ be a measure space, and let $\rho$ be a probability measure on $X$. I call a subset $A$ of $X$ special if for all measurable $B\subseteq X$,

1. $\mu(B)\leq\mu(A)$ implies $\rho(B)\leq\rho(A)$, and
2. $\mu(B)=\mu(A)$ and $\rho(B)=\rho(A)$ implies $B=A$ up to measure zero (with respect to both $\mu$ and $\rho$).

What is the standard name for my "special" sets? Equivalently, one could stipulate $\mu(A)\leq\beta$ and call $A$ "special" if it is essentially the unique maximizer of $\rho(A)$ given that constraint.

Also equivalently, we could stipulate a particular $\rho$-measure and consider sets achieving that $\rho$-measure having the smallest possible $\mu$-measure. That's probably the most intuitive way to think about this: we're looking for sets that contain a certain (heuristically: large) fraction of of the mass of $\rho$ but are as small as possible (with respect to $\mu$). That seems like a completely natural and obvious concept, which is why I think it should have a standard name. But I have almost no training in statistics, so I don't know what the name is.

This example might be far-fetched, but just to illustrate: suppose the FBI has knowledge that somebody is going to attempt a terrorist attack in a certain huge city at a particular hour. They might not know where, but they might have (some estimate of) a probability distribution for the location of the attack. They want to distribute agents strategically throughout the city, but they probably don't have enough agents to cover the entire city. Let's say every agent can forestall an attack if it occurs within a certain radius of his/her position (which is unrealistic, since the number of nearby agents surely also matters, but ignore that); then, to maximize the probability that the attack will be stopped, to an approximation, they should distribute their agents uniformly over a special subset of the city's area. To approach this from the other perspective, it could be the case that 99% of the mass of their probability distribution is contained in a region with very small area. (The one with the smallest area will be a special set.) Then, to save resources, if they're okay with 99:1 odds (c'est la vie), they might only distribute a relatively small number of agents to that small special region.

If $\rho$ has a density $f$ with respect to $\mu$ (when it makes sense to talk about such), then special sets are closely related to the superlevel sets of $f$, i. e., sets of the form $\{x:f(x)\geq c\}$ for $c\geq 0$. (I think they're basically the same, but specialness of $A$ is unaffected by changing $A$ by a set of measure zero, so a superlevel set actually corresponds to an equivalence class of special sets.) I mention this here because (1) the connection to superlevel sets is one of my reasons for caring about specialness, and (2) "superlevel sets of the density" is not the answer I'm looking for.

Example 1

Here's a very simple example in which special sets can be completely characterized. Let $X=\{x\_1,\ldots,x\_n\}$ be a finite set, and let $\mu$ be counting measure on $X$. Let $\rho$ be any probability distribution on $X$, which necessarily has a density function $f:X\to\mathbb{R}\_+$, so by definition, $f(x\_1) + \ldots + f(x\_n) = 1$ and $\rho(A) = \sum\_{x\in A} f(x)$. Suppose that no two points have the same $f$-value; then, without loss of generality, $f(x\_1) > f(x\_2) > \ldots > f(x\_n)$. It's easy to see that the special sets in this setup are exactly the sets $A\_k = \{x\_1,x\_2,\ldots,x\_k\}$, i. e., which contain the largest $k$ points as measured by $\rho$, for $k=0,\ldots,n$. (Why: if you have some other candidate special set $B$, then $A\_{\\#B}$ has the same $\mu$-measure as $B$ but higher $\rho$-measure, so $B$ can't be special.) It's easy to generalize this example to the case in which $f$ isn't necessarily one-to-one: you have to treat all points with the same $f$-value as a block: either all of them are in the special set, or none of them are. (Otherwise, there's no way to satisfy the "uniqueness" part (point 2) of the definition.)

Example 2

Here's a generalization of the first example that hopefully clarifies what I said above. Let $(X,\mu)$ be some nice measure space on which integration of functions makes sense (like a Riemannian manifold, or just $\mathbb{R}^d$). Let $f:X\to\mathbb{R}\_+$ be a nonnegative integrable function with $\int_X f(x) d\mu = 1$, and let $\rho$ be the probability measure $\rho(Y) = \int_Y f(x) d\mu$, so $f$ is the density of $\rho$ with respect to $\mu$. Fix some $c\geq 0$ and let $A=\{x:f(x)\geq c\}$.

Claim: $A$ is a special set.

Proof: It suffices to show that if $\mu(B) = \mu(A)$, then $\rho(B)\leq \rho(A)$, with equality if and only if $B$ and $A$ differ by a set of measure zero. If $\mu(B) = \mu(A)$, then $\mu(B-A) = \mu(A-B)$. Now we write \begin{align*} \rho(A) - \rho(B) &= \int\_A f(x) d\mu - \int\_B f(x) d\mu \\\\ &= \int\_{A-B} f(x) d\mu - \int\_{B-A} f(x) d\mu \\\\ &= \int\_{A-B} f(x) d\mu - \int\_{A-B}c\\,d\mu - \int\_{B-A} f(x) d\mu + \int\_{B-A}c\\,d\mu\\\\ &= \int\_{A-B} (f(x)-c) d\mu - \int\_{B-A} (f(x)-c) d\mu. \end{align*}

By construction, $f(x) \geq c$ on $A$ and $f(x) < c$ on $B-A$, so the first integral is nonnegative and the second integral is nonpositive, and is in fact negative unless $\mu(B-A)=0$, in which case $\mu(A-B)=0$ as well. Thus, $\rho(A)-\rho(B)\geq 0$, with strict inequality unless $A$ and $B$ differ by measure zero, QED.

-
Can you give an example of a measure space and a special subset of it? – Michael Lugo Dec 5 '09 at 16:39
Is this an example: let $X$ be the reals, $A=[-1,1]$, $\mu$ the normal (0,1) distribution, and $\rho$ and a normal (0,1/2) distribution? – Kevin O'Bryant Dec 5 '09 at 20:00
Michael: sure thing. I've expanded the discussion considerably and included examples. – Darsh Ranjan Dec 5 '09 at 20:24
Kevin: yes, I think so. I think any set $[-a,a]$ is special in your example, with those being essentially all special sets (modulo measure zero). – Darsh Ranjan Dec 5 '09 at 20:27

In statistics, especially Bayesian statistics, what you are looking for is called HPD-region or "highest posterior density region", which is meant to be a set with minimum volume for a given (large) (posterior) probability.

-

A similar (equivalent?) problem in statistic.

I am not sure about the name but it should be something like "critical decision area". This arises naturally in the problem of hypothesis testing of simple hypothesis where the optimization problem is:

$$\sup_{ A \in \mathcal{A}\; \mu(A)\leq \beta } \rho(A)$$

How this problem is solved

A more convenient set for the optimization (than the set of indicator function of set) is : $$\Psi= (\psi: X\rightarrow [0,1]\;\; measurable )$$ (it is more convenient because convex) The problem reformulates as:

$$\sup_{ \psi\in \Psi\; \int_{X} \psi d \mu \leq \beta } \int \psi d\rho=\sup_{\psi\in \Psi}\inf_{t\in [0,\infty]}\mathcal{L}(t,\psi)$$

where $\mathcal{L}(t,\psi)$ is the Lagrangien of the considered optimization problem:

$$\mathcal{L}(t,\psi)=\int\psi d\rho- t\left (\int\psi d\mu-\beta \right )=t\beta-\int \psi (d\rho-td\mu).$$

If you can use a minmax theorem (under some suitable topological assumption, not restrictive) to revert inf and sup, and if $\rho$ is absolutly continuous with respect to $\mu$, the minimizer of the optimization problem is given by the so famous Neymann Pearson test:

$$\psi^*= 1_{\frac{d\rho}{d\mu}\geq t(\beta)}$$

(it remains to find $t(\beta)$...) This is called a test because it can help you to test wether the law of a random variable $X$ is $\mu$ or $\rho$ given an observation of $X$. If $\rho$ is not absolutly continous with respect to $\mu$ you can decompose $\rho$ (by Lebesgue Theorem) and apply the same methodology.

-