Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability distributions $\alpha$, $\beta$ and $\gamma$ in $\mathbb{R}^{n+1}$. The set of possible $\alpha$, $\beta$ and $\gamma$ is a polytope in $\mathbb{R}^{3n+3}$. Does anyone know a list of defining inequalities for it?

For those who don't like the probability language: Let $p_{ijk} \in \mathbb{R}_{\geq 0}^H$ with $\sum p_{ijk}=1$. Set $\alpha_i = \sum_{j} p_{ij(n-i-j)}$, $\beta_j = \sum_k p_{(n-j-k)jk}$ and $\gamma_k = \sum_i p_{i(n-i-k)k}$. What are the inequalities defining the possible vectors $\alpha$, $\beta$ and $\gamma$?

  • $\begingroup$ The polytope in question (call it $P_n$) is the convex hull of $e_a + f_b + g_c$, where $e_0,\dots,e_n,f_0,\dots,f_n,g_0,\dots,g_n$ is a basis for ${\mathbb R}^{3n+3}$ and $(a,b,c)$ ranges over $H$. There appear to be some recursive relations that allow one to describe $P_{n+1}$ or $P_{2n}$ in terms of $P_n$ which may be helpful. $\endgroup$
    – Terry Tao
    Commented Jun 7, 2016 at 16:59
  • $\begingroup$ The defining inequalities correspond to weights $r_0,\dots,r_n,s_0,\dots,s_n,t_0,\dots,t_n$ such that $r_a + s_b + t_c \geq 0$ for all $(a,b,c) \in H$, with equality holding in some "spanning" set of $H$. This looks somewhat combinatorially unappetising, though. $\endgroup$
    – Terry Tao
    Commented Jun 7, 2016 at 17:02
  • 1
    $\begingroup$ For n=2. If the variables are $\alpha_0, \alpha_1, \alpha_2, \beta_0, \beta_1, \beta_2, \gamma_0, \gamma_1, \gamma_2$, then the polytope is defined by 6 inequalities and 4 equalities:$$0\le \alpha_2,\beta_2,\gamma_2,d,e,f;$$ $$\alpha_1=e+f;\ \ \beta_1=d+f;\ \ \gamma_1=d+e;$$ $$\alpha_0+\beta_0+\gamma_0=\alpha_2+\beta_2+\gamma_2+1$$ where $d,e,f$ abbreviate $\alpha_0-\beta_2-\gamma_2$, $\beta_0-\alpha_2-\gamma_2$, $\gamma_0-\alpha_2-\beta_2$. $\endgroup$
    – user44143
    Commented Jan 15, 2018 at 5:18

1 Answer 1


While the literal question I asked is still open, Luke Pebody has proven an important relevant result: If $\alpha_0 \geq \alpha_1 \geq \cdots \geq \alpha_n$, and the same for $\beta$ and $\gamma$, and $\sum \alpha_j + \sum \beta_j + \sum \gamma_k = 3$, then there is a probability distribution $\pi$ with marginals $\alpha$, $\beta$, $\gamma$. This constructs a large polytope inside the one which this question asks for a characterization of.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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