Probability of a random distribution being in a set of distributions

Question

Let $S=\{s_1,\dots,s_k\}$ be some set of size $k$ and let $\mathit{Dist}(S)$ be the set of all probability distributions over $S$ where a probability distribution is simply a function $p \colon S \rightarrow [0,1]$ with $\sum_{s\in S}p(s) = 1$.

We construct a random probability distribution $t$ over $S=\{s_1,\dots,s_k\}$ in the following way:

• generate a multiset $R$ of $k-1$ random variables each sampled uniformly from $[0,1]$
• sort them ascending and label them $n_1$ to $n_k$, i.e., $\hat{\{}n_i\mid i\in \{1,\dots,k-1\}\hat{\}}=R$ and $n_1\leq n_2 \leq \dots \leq n_{k-1}$
• define $n_0=0$ and $n_k=1$
• for each $i$ we define $t(s_i)=n_i-n_{i-1}$

This can be visualised as taking the number line from 0 to 1, split it into $k$ parts by dropping $k-1$ separators randomly and asserting each probability a value that corresponds to the distance between two adjacent separators.

Note that $t$ is indeed a probability distribution since $n_i\geq n_{i-1}$ and $\sum_{s\in S}t(s) = 1$.

Given a set of distributions $T \subseteq Dist(S)$, what is the probability that $t \in T$?

If it helps, we can assume that $T$ gives a dense range of possible values for the probability of each element of $S$, i.e., for each $i \in \{1,\dots,k\}$ there are some $\underline{p_i},\overline{p_i}\in [0,1]$ with $\underline{p_i} < \overline{p_i}$ and $T = \{ p \mid p \in \mathit{Dist}(S) \text{ and } \forall i.p(s_i)\in [\underline{p_i},\overline{p_i}] \}$.

---

For $k=2$ this is straight forward since $p(s_1) = 1-p(s_2)$, i.e., it is essentially just one random variable. However even extending this to a set of three elements already gives me troubles. The main issue I keep running into is that I know the $p(s_i)$ are not independent (since they have to add to 1).

I'm not looking for a closed form necessarily. A way to compute this algorithmically would be perfectly fine.

Answer 1

WLOG we may set $S = \{1,2,\ldots,k\}$. This allows us to identify $\operatorname{Dist}(S)$ as the set

$$ \biggl\{ (p_1, p_2, \ldots, p_k) : p_i \geq 0 \text{ and } \sum_{i=1}^{k} p_i = 1 \biggr\}, $$

which is a subset of the hyperplane $H : p_1+p_2+\cdots+p_k = 1$. Then the random distribution $t$ can be realized as follows:

• Let $U_1, U_2, \ldots, U_{k-1}$ be i.i.d. $\operatorname{Uniform}(0,1)$ variables.

• Let $ U_{(1)} \leq U_{(2)} \leq \ldots \leq U_{(k-1)}$ be the order statistics. We know $(U_{(1)}, U_{(2)}, \ldots, U_{(k-1)})$ is uniformly distributed over the region $ 0 \leq x_1 \leq x_2 \leq \ldots \leq x_{k-1} \leq 1$ in $\mathbb{R}^{k-1}$, see this for instance.

• With the convention that $U_{(0)} = 0$ and $U_{(k)} = 1$, the law of $t$ is realized by the sequence of differences $U_{(i)} - U_{(i-1)}$, that is, $$ t \stackrel{\text{law}}= (U_{(1)} - U_{(0)}, U_{(2)} - U_{(1)}, \ldots, U_{(k)} - U_{(k-1)}). $$

In light of this, we conclude that the law of $t$ is precisely the uniform distribution over $\operatorname{Dist}(S)$, i.e., the normalized surface measure on this set.

Equivalently, if we consider the projection $\pi : \mathbb{R}^k \to \mathbb{R}^{k-1}$ onto the first $k-1$ coordinates, then $\pi(t) = (t_1, t_2, \ldots, t_{k-1})$ is uniformly distributed over the region

$$ \pi(\operatorname{Dist}(S)) = \biggl\{(p_1, \ldots, p_{k-1}) : p_i \geq 0 \text{ and } \sum_{i=1}^{k-1} \leq 1 \biggr\}. $$

As a consequence, we get

\begin{align*} \mathbf{P}(t \in T) &= \frac{\text{[Area of $T \cap \operatorname{Dist}(S)$ in $H$]}}{\text{[Area of $\operatorname{Dist}(S)$ in $H$]}} = \frac{\text{[Volume of $\pi(T \cap \operatorname{Dist}(S))$ in $\mathbb{R}^{k-1}$]}}{\text{[Volume of $\pi(\operatorname{Dist}(S))$ in $\mathbb{R}^{k-1}$]}}. \end{align*}

---

Example. Let $k = 3$ and $T$ be the set of all distributions on $S = \{1,2,3\}$ for which the entropy (in nats) is less than or equal to $\frac{3}{4}\log 3$:

$$T = \biggl\{ (t_1, t_2, t_3) : t_i \geq 0, \ \sum_{i=1}^{3} t_i = 1, \ \text{and} \ \sum_{i=1}^{3} t_i \log(1/t_i) \leq \tfrac{3}{4}\log 3 \biggr\}. $$

• Using a numerical method, the ratio of the area $\pi(T)$ and the area of $\pi(\operatorname{Dist}(S))$ is estimated as $0.417781$.

• Using $10^7$ samples from the distribution of $t$ and counting the proportion of samples lying in $T$, the value of $\mathbf{P}(t \in T)$ is estimated as $0.417705 \pm 0.00040$ at a $99\%$ confidence level.