# Extreme Points and Recession Cone of a set of Probability Distributions

1. Consider the set $\mathcal{P}$ of all probability distributions suported on $\Omega$, where $\Omega$ is a set of $n$ elements.

Then, if $x$ is a probability distribution supported on $\Omega$, for $\{\omega_{1}, \omega_{2}, \cdots , \omega_{n}) \in \Omega$, $$x:= (p(\omega_{1}),p(\omega_{2}),\cdots , p(\omega_{n})) \in \mathbb{R}^{n}$$ with $p(\omega_{i})\geq 0$ and $\sum_{i=1}^{n}p(\omega_{i}) = 1$.

$\mathcal{P}$ then, is the set of all such $x$.

Now, in a previous exercise, I showed that $\mathcal{P}$ was a convex set.

Now, I need to

1. Find the set of extreme points of $\mathcal{P}$ (Definition: A point $x$ of a convex set $X$ is called an extreme point if no other points $u,v \in X$ exist such that $\displaystyle x = \frac{1}{2}u + \frac{1}{2}v$)
2. Find the recession cone of $\mathcal{P}$ (Definition: Let $X \subset \mathbb{R}^{n}$ be a convex set. Then the set $X_{\infty} = \{d: X + d \subset X\}$ is called the recession cone of $X$. I.e., the recession cone of $X$ consists of all directions $d$ such that $X+d$ is still contained inside $X$).
3. Write $\mathcal{P}$ in terms of its extreme points. Here are my attempts for the three parts:
4. Consider $y, z \in \mathcal{P}$. Then, $y = (p_{y}(\omega_{1}), p_{y}(\omega_{2}), \cdots , p_{y}(\omega_{n}))$ and $z = (p_{z}(\omega_{1}), p_{z}(\omega_{2}), \cdots , p_{z}(\omega_{n}))$, where $p_{y}$ is the probability function for the distribution $y$ and $p_{z}$ is the probability function for the distribution $z$.

Now, $$\frac{1}{2}y + \frac{1}{2}z \\ = \frac{1}{2} (p_{y}(\omega_{1}), p_{y}(\omega_{2}), \cdots , p_{y}(\omega_{n})) + \frac{1}{2}(p_{z}(\omega_{1}), p_{z}(\omega_{2}), \cdots , p_{z}(\omega_{n})) \\ = (\frac{1}{2}p_{y}(\omega_{1}), \frac{1}{2}p_{y}(\omega_{2}), \cdots , \frac{1}{2}p_{y}(\omega_{n})) + (\frac{1}{2}p_{z}(\omega_{1}), \frac{1}{2}p_{z}(\omega_{2}), \cdots , \frac{1}{2}p_{z}(\omega_{n})) \\ = (\frac{1}{2}p_{y}(\omega_{1}) +\frac{1}{2}p_{z}(\omega_{1}) , \frac{1}{2}p_{y}(\omega_{2}) +\frac{1}{2}p_{z}(\omega_{2}), \cdots , \frac{1}{2}p_{y}(\omega_{n}) +\frac{1}{2}p_{z}(\omega_{n})) \\ = \sum_{i=1}^{n} \left( \frac{1}{2}p_{y}(\omega_{i}) +\frac{1}{2}p_{z}(\omega_{i}) \right) = \frac{1}{2}\sum_{i=1}^{n} \left( p_{y}(\omega_{i}) +p_{z}(\omega_{i}) \right) \\ = \frac{1}{2} \left(\sum_{i=1}^{n} \left( p_{y}(\omega_{i}) \right) + \sum_{i=1}^{n} \left( p_{z}(\omega_{i})\right) \right) \\ = \frac{1}{2} \left( 1 + 1 \right) = \frac{1}{2}\left( 2 \right) \\ = 1$$

which means that for any $y,z \in \mathcal{P}$, $\displaystyle \frac{1}{2}y + \frac{1}{2}z$ is also in $\mathcal{P}$.

What I showed here is that $\displaystyle \frac{1}{2}y + \frac{1}{2}z$ is some distribution $x$ in $\mathcal{P}$, but is this the same thing as showing that any $x \in \mathcal{P}$ can be written this way? I.e., have I actually showed that $\mathcal{P}$ has no extreme points?

1. For the recession cone, let $d \in \mathbb{R}^{n}$ and consider $x + d: (p_{x}(\omega_{1}),p_{x}(\omega_{2}), \cdots, p_{x}(\omega_{n})) + (d_{1},d_{2},\cdots , d_{n}) =(p_{x}(\omega_{1}) + d_{1} ,p_{x}(\omega_{2}) + d_{2}, \cdots, p_{x}(\omega_{n}) + d_{n})$

Now, I need $\displaystyle \sum_{i=1}^{n} (p_{x}(\omega_{i}) + d_{i}) = 1$ in order for $x + d \in \mathcal{P}$, so $$\sum_{i=1}^{n} (p_{x}(\omega_{i}) + d_{i}) = \sum_{i=1}^{n} p_{x}(\omega_{i}) + \sum_{i=1}^{n} d_{i} \\ = 1 + \sum_{i=1}^{n} d_{i}$$

Therefore, I need $\displaystyle \sum_{i=1}^{n} d_{i} = 0$.

Thus, $\mathcal{P}_{\infty} = \{ d = (d_{1},d_{2}, \cdots , d_{n}) : \sum_{i=1}^{n}d_{i} = 0 \}$.

Is that all I can say about this set? Do I also require that each of the $d_{i} \geq 0$? Then, I suppose this would force the recession cone to be $\{0\}$?

1. I have a result in my text that says that a closed convex set $X$ which has at least one extreme point, can be represented as $$X = conv(E(X))+X_{\infty}$$ where $E(X)$ are the extreme points of $X$ and $conv(E(X))$ is the convex hull of the extreme points of $X$. However, I do not know that $\mathcal{P}$ is closed, only that it is convex. Therefore, it does not appear I can use this result, but I have nothing else at my disposal to express the set in terms of its extreme points. How should I approach this part of my answer?

I thank you for your time and patience!

• You have ${\cal P} = \operatorname{co} \{ e_k \}$ where $e_k$ are the unit vectors along each axis. Each of these points is extreme (find a direction so that the inner product is uniquely maximised at each of these points. A bounded set can only have $0$ in its recession cone. – copper.hat Oct 19 '17 at 19:14
• @copper.hat that $\mathcal{P}=co\{e_{k}\}$ is actually what I am trying to prove here. I cannot use this to help me find the extreme points. – ALannister Oct 19 '17 at 20:58

Note that ${\cal P} = \operatorname{co}\{e_k\}$. To see this, note that $e_k \in {\cal P}$ for all $k$ and ${\cal P}$ is convex hence $\operatorname{co}\{e_k\} \subset {\cal P}$. If $x \in {\cal P}$ we have $x = \sum_k x_k e_k$ with $x_k \ge 0$ and $\sum_k x_k =1$ hence $x \in \operatorname{co}\{e_k\}$.
To show that the $e_k$ are extreme, note that $e_k$ is the unique maximiser of $\langle e_k, x \rangle$ for $x \in {\cal P}$.
• is $\mathcal{P}$ also a closed set? – ALannister Oct 23 '17 at 0:09
• Yes, it is actually compact. Since $\{x | \sum_k x_k =1 , x_k \ge 0 \}$ is compact the image of the continuous operator $x \mapsto \sum_k x_k e_k$ is compact. – copper.hat Oct 23 '17 at 0:52