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!

  • $\begingroup$ 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. $\endgroup$ – copper.hat Oct 19 '17 at 19:14
  • $\begingroup$ @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. $\endgroup$ – 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}$.

  • $\begingroup$ is $\mathcal{P}$ also a closed set? $\endgroup$ – ALannister Oct 23 '17 at 0:09
  • 1
    $\begingroup$ 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. $\endgroup$ – copper.hat Oct 23 '17 at 0:52
  • $\begingroup$ thank you, this answer was extremely (no pun intended!) helpful. Would it be possible for you to help me out with this one as well?: math.stackexchange.com/questions/2502215/… I am finding it extremely difficult. Thanks again. $\endgroup$ – ALannister Nov 3 '17 at 0:16
  • $\begingroup$ there is a 100 point bounty on that question. $\endgroup$ – ALannister Nov 4 '17 at 23:52

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.