How many probability vectors do I need to convexly generate any probability vector?

39 Views Asked by At

Fix a positive integer $n$, and let $B = \{p_1, \dots, p_{k}\}$ be a set of $k$ mutually linearly independent vectors in $\mathbb{R}^{2^n}$, where each $p_i \in B$ is also a probability vector in the probability simplex $\Delta$ in $\mathbb{R}^{2^n}$. I am interested in the minimum value of $k$ such that I can express the $2^n$ vectors $(1,0,\dots, 0), (0,1,0,\dots, 0), \dots, (0,\dots, 0,1)$ in $\Delta$ as a convex sum of vectors in $B$. Evidently, if $k = 2^n$, then $B$ is a basis of $\mathbb{R}^{2^n}$ and so I can do it. But $B$ being a basis merely entails that each $p \in \Delta$ is a linear combination (not necessarily a convex combination) of vectors in $B$. Any help would be appreciated, particularly references to the relevant ideas.

Edit

To clarify the quantifiers (and to remove the linear independence condition), I am interested in the least $k$ such that for any collection $B$ of $k$ probability vectors in $\Delta$, I can write any $p \in \Delta$ as a convex sum of elements in $B$. Certainly there must be at least $2^n$ linearly independent vectors in $B$, so $k \geq 2^n$, but presumably there must also be additional vectors in $B$ to satisfy the convexity constraint.

1

There are 1 best solutions below

0
On BEST ANSWER

You can't write $(1,0,\dots,0)$ as a convex combination of other probability vectors, no matter how many you have: they are the extreme points of $\Delta$. For suppose we have $v_i = (v_{i,1}, \dots, v_{i, 2^n})$ for $i=1,\dots,m$, If $v_i \ne (1,0,\dots,0)$ then $v_{i,1} < 1$. So the first element of a convex combination is at most $\max_i v_{i,1} < 1$.

As such, a set $B$ generates $\Delta$ if and only if it contains $(1,0,\dots,0), (0,1,0,\dots,0)$, etc.