7
$\begingroup$

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \vdots & \ddots & \vdots \\ p_{J-1,0} & p_{J-1, 1} & \ldots & p_{J-1,J-1} \\ \end{array} \right) \quad (0 \le p_{kl} \le 1, \;\; \sum_{k=0}^{J-1}\sum_{l=0}^{J-1}p_{kl} = 1) \end{equation*} with fixed row and column sums \begin{equation*} p_{k+} = \sum_{l^\prime=0}^{J-1}p_{kl^\prime}, \quad p_{+l} = \sum_{k^\prime =0}^{J-1}p_{k^\prime l} \quad (k, l = 0, 1, \ldots, J-1), \end{equation*} Calculate the closed-form expressions for the minimum and maximum values of \begin{equation*} \Delta = \mathop{\sum\sum}_{ k > l}p_{kl} - \mathop{\sum\sum}_{ k < l}p_{kl}. \end{equation*}

Some background:

This is an interesting and challenging question, in fact, an active research problem I am currently pursuing. I can't prove that it indeed has a closed form solution, but I tend to believe so. I have tried very hard and therefore want to solicit any hints or point of directions. On a related note, I have obtained closed form solutions of the sharp bounds of the following very similar objective functions, namely \begin{equation*} \tau = \mathop{\sum\sum}_{ k \ge l}p_{kl}, \quad \eta = \mathop{\sum\sum}_{ k > l}p_{kl}, \quad \xi = \mathop{\sum\sum}_{ k = l}p_{kl}, \end{equation*} which another reason why I believe the solution exists for $\Delta$ as well. For more details see my Ph.D. dissertation at:

dash.harvard.edu/handle/1/23845443

(Update March 31) Let me provide a bit more context. Because of the symmetrical structure of $\Delta,$ we only need to figure out the upper bound. When $J=2$, we have \begin{equation*} \Delta = p_{+0} - p_{0+} = p_{1+} - p_{+1} = \min \left( p_{+0} - p_{0+}, p_{1+} - p_{+1}\right), \end{equation*} therefore we can identify $\Delta$ from the marginals. When $J=3$, simulations suggest that the sharp upper bound of $\Delta$ is: \begin{equation*} \Delta_U = \min \left\{ p_{+0} - p_{0+} + \min\left( p_{2+}, p_{+1}\right), p_{2+} - p_{+2} + \min\left( p_{1+}, p_{+0}\right) \right\}. \end{equation*} However, unfortunately, when $J>3,$ I am no longer able to "guess" the closed-form solutions and therefore I need your help. :)

$\endgroup$
10
  • $\begingroup$ You might consider adding a top-level tag in order to make more people see this question. $\endgroup$
    – Stefan Kohl
    Mar 30, 2016 at 20:28
  • 1
    $\begingroup$ An approach would be to first describe the vertices of the polytope, then if the description is simple enough we just need to select the best vertex. Without the upper bounds $p_{kl}\le 1$ it is a transportation polytope, whose vertices are well-known (the bipartite graph formed by the nonzero entries must be acyclic), but with the upper bounds in place it seems to be quite a bit more complicated. Perhaps the solution in the transportation case will provide some information? It is at least a lower bound, and is exact if the row and column sums are at most 1. $\endgroup$ Apr 1, 2016 at 2:01
  • $\begingroup$ In your thesis you seem to have the condition $\sum_{jk} p_{jk}=1$. Do you have this condition here too? If so, please add it. In that case you have a transportation polytope and so the max and min of any linear function occurs at one of the (well-known) vertices of that polytope. $\endgroup$ Apr 1, 2016 at 4:09
  • $\begingroup$ Thanks @BrendanMcKay for pointing out this confusion. Yes I have this condition here. I didn't write it down explicitly, because I thought "probability matrix" already covers it. Let me write it down. $\endgroup$ Apr 1, 2016 at 4:19
  • $\begingroup$ @BrendanMcKay I admittedly have no knowledge of transportation polytope and just looked it up. It does seem to be what I am looking for. Any chance you can point me to some literature on the "well-known vertices?" Thank you very much! $\endgroup$ Apr 1, 2016 at 4:28

0

Your Answer

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