Skip to main content
2 of 8
added 1 character in body; edited tags

Closed-form solution of a linear programming question

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; \; k,l = 0, \ldots, J-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 of this question:

This is 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 very similar objective functions, another reason why I believe the solution exists for this one as well. For more details see dash.harvard.edu/handle/1/23845443