# Probability of a random distribution being in a set of distributions

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.

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.