Extreme points of the intersection of the probability simplex and a ball in $\ell_\infty$-norm

265 Views Asked by At

Let $n$ and $s$ be two natural numbers such that $1<s<n$. Let $\Delta^n_1$ be the $n$-dimensional probability simplex $$ \Delta^n_1 = \Big\{x\in[0,1]^n: \sum_{i=1}^n x_i = 1\Big\} $$ and $B^n_\infty(1/s)$ be the ball in $\mathbb R^n$ centered at $0$ and with radius $1/s$ with respoect to $\ell_\infty$-norm: $$ B^n_\infty(1/s) = \{x\in\mathbb R^n: \max_i |x_i|\le 1/s\}. $$ Let $S$ be the finite set composed of all the vectors of $\Delta^n_1$ having exactly $s$ coordinates equal to $1/s$ (uniform probabilities).

Question: is it true that the set $\Delta^n_1\cap B^n_\infty(1/s)$ is equal to the convex hull of $S$? The inclusion $c.h.(S)\subset \Delta^n_1\cap B^n_\infty(1/s)$ is easy to establish. What about the converse inclusion?

1

There are 1 best solutions below

0
On

The answer is yes, the two sets are equal. This follows from a famous result often referred to as the Minkowski theorem: any convex polytope is the convex hull of its extreme points.

The intersection $A\triangleq \Delta^n_1\cap B^n_\infty(1/s)$ is a convex polytope. It is easy to check that its extreme points are all the elements of $S$. Therefore, $A=c.h.(S)$.