7
$\begingroup$

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.

$\endgroup$
4
+50
$\begingroup$

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.

density histogram of samples of t, and region T

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.