18
$\begingroup$

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture). (This question has been posted at MathOverflow on 13.12.2014; the question has been solved in a very nice way there.)

The problem

There are $n$ different objects $A_1,...,A_n$, and there are sets containing $m$ different $A_i$s: $C_i=(A_{i_1}, A_{i_2}, ..., A_{i_m})$. There are $i_{max}=\binom{n}{m}$ different combinations $C_i$. Each combination $C_i$ has a probability $p_i$ (with $\sum_{i=1}^{i_{max}} p_i=1$).

Defining the function

For a given pair of objects $A_k$ and $A_l$:

  • $f_1(k,l)$ contains all probabilities $p_i$ of the sets $C_i$, which contains both objects $A_k$ and $A_l$.
  • $f_2(k,l)$ contains all probabilities $p_i$ of the sets $C_i$, which contains either object $A_k$ or $A_l$ (if it contains both elements, we add $p_i$ twice).
  • $F(k,l)=\frac{f_1(k,l)}{f_2(k,l)}$

With that, we get the main-function $$D^{(n,m)}=\sum_{k=1}^{n-1} \sum_{l=k+1}^{n} F(k,l)$$

What is the maximum of $D^{(n,m)}$, given that the sum of all probabilities $p_i$ is 1?

Special cases

n=2, m=2

This is a trivial case. We have two objects $A_1$ and $A_2$, and only one set of combinations $C_1=(A_1,A_2)$ with $p_1$.

Thus $f_1(1,2)=p_1$, $f_2(1,2)=p_1+p_1$. This leads to $D^{(2,2)}=F(1,2)=\frac{1}{2}$.

Every other case with $n=m$ can be solved easily by $D^{(n,m)}=\frac{1}{n}$


n=3, m=2

This case is simple (but not trivial) and I found a solution:

We have n=3 objects $A_1$, $A_2$ and $A_3$, and combinations $C_i$ of m=2 objects $C_1$=($A_1$, $A_2$), $C_2$=($A_1$, $A_3$), $C_3$=($A_2$, $A_3$), with $p_1$, $p_2$, $p_3$ respectivly.

For k=1, l=2 we have $f_1(1,2)=p_1$ (because only $C_1$ contains both $A_1$ and $A_2$), and $f_2(1,2)=2p_1+p_2+p_3$ (because $A_1$ is contained in $C_1$ and $C_2$ and $A_2$ is in $C_1$ and $C_3$).

So we get $$D^{(3,2)}=F(1,2) + F(1,3) + F(2,3) = \frac{p_1}{2p_1+p_2+p_3} + \frac{p_2}{p_1+2p_2+p_3} + \frac{p_3}{p_1+p_2+2p_3}$$ A maximum can be found easily (due to normalisation of $p_1+p_2+p_3=1$): $$D^{(3,2)} = \frac{p_1}{1+p_1} + \frac{p_2}{1+p_2} + \frac{p_3}{1+p_3}$$ so each term can be maximized individually, which gives $D^{(3,2)}=\frac{3}{4}$ for $p_1=p_2=p_3$.


n=4, m=2

We have four objects $A_1$, $A_2$, $A_3$, $A_4$, and six combinations $C_1=(A_1,A_2)$, $C_2=(A_1,A_3)$, ..., $C_6=(A_3, A_4)$.

Therefore we get: $$D^{(4,2)} = \frac{p_1}{2p_1+p_2+p_3+p_4+p_5} + \frac{p_2}{p_1+2p_2+p_3+p_4+p_6} + \frac{p_3}{p_1+p_2+3p_3+p_5+p_6} + \frac{p_4}{p_1+p_2+2p_4+p_5+p_6} + \frac{p_5}{p_1+p_3+p_4+2p_5+p_6} + \frac{p_6}{p_2+p_3+p_4+p_5+2p_6}$$

I was not able to find a method for proving a global maximum.


n=4, m=3

We have $C_1=(A_1,A_2,A_3)$, $C_2=(A_1,A_2,A_4)$, $C_3=(A_1,A_3,A_4)$, $C_4=(A_2,A_3,A_4)$, which gives

$$D^{(4,3)}=\frac{p_1+p_2}{2p_1+2p_2+p_3+p_4}+\frac{p_1+p_3}{2p_1+p_2+2p_3+p_4}+\frac{p_1+p_4}{2p_1+p_2+p_3+2p_4}+\frac{p_2+p_3}{p_1+2p_2+2p_3+p_4}+\frac{p_2+p_4}{p_1+2p_2+p_3+2p_4}+\frac{p_3+p_4}{p_1+p_2+2p_3+2p_4}$$

This case can be simplified aswell, similar to $n=3,m=2$ case to $$D^{(4,3)}=\frac{p_1+p_2}{1+p_1+p_2}+\frac{p_1+p_3}{1+p_1+p_3}+\frac{p_1+p_4}{1+p_1+p_4}+\frac{p_2+p_3}{1+p_2+p_3}+\frac{p_2+p_4}{1+p_2+p_4}+\frac{p_3+p_4}{1+p_3+p_4}$$

but I'm not able to find any further method to calculate the maximum.

Conjecture

The two cases I solved had a maximum at equal $p_i=\frac{1}{\binom{n}{m}}$. Furthermore, the function $D^{(n,m)}$ is very symmetric, so I expect that the maximum is always at $p_1=p_2=...=p_i$. Numerical search up to n=7 confirms my expectation (but I'm not 100% sure about my Mathematica-based numerical maximization).

Questions

  1. How can you prove (or disprove) that the maximum for $D^{(n,m)}$ for arbitrary $n$ and $m$ is always at $p_1=p_2=...=p_i$?
  2. Is there literature on similar problems or is this function even known? Has the similarity to the Shapiro inequality some significance or is it just a coincidence?
  3. Is there a better (maybe geometrical) interpretation of this function?
  4. Can you find solutions for any other special case than $n=m$ (always trivial) and $n=3,m=2$?
$\endgroup$
  • 1
    $\begingroup$ I think your definition for the function $D$ has to have the sums running up to $n$ and $n-1$ not $m$ and $m-1$. $\endgroup$ – Alexander Vlasev Oct 19 '14 at 9:59
  • $\begingroup$ @AleksVlasev You are right, I corrected the sum-bounds. Thanks! $\endgroup$ – NicoDean Oct 20 '14 at 8:32
6
+100
$\begingroup$

Partal solution:


The case of $m=n-1$ can be solved easily.

It is easy to check that $$ D^{(n,n-1)} = \sum_{1\le i < j \le n} \frac{p_1+\cdots + p_{i-1}+p_{i+1}+\cdots+p_{j-1}+p_{j+1}+\cdots +p_n}{2p_1+\cdots + 2p_{i-1}+p_i+2p_{i+1}+\cdots+2p_{j-1}+p_j+2p_{j+1}+\cdots +2p_n} \\ =\sum_{1\le i < j \le n} \frac{1-p_i-p_j}{2-p_i-p_j}$$

Now since $f(x)=\frac{1-x}{2-x}$ is concave, we may apply Jensen's inequality to obtain $$\sum_{1\le i < j \le n} \frac{1-p_i-p_j}{2-p_i-p_j} \le \frac{1-2/n}{2-2/n} = \frac{n-2}{2n-2}$$ since the average of the $p_i+p_j$s is $\frac{2}{n}$. Equality holds if and only if $p_1=\cdots = p_n=1/n$.


The case of $m=2,n=4$ is also not so difficult to solve.

We shall first prove that $\frac{a}{1+a-b} + \frac{b}{1+b-a} \le a+b$ if $a+b \le 1$. This inequality is true since it is equivalent to $(1-a-b)(a-b)^2 \ge 0$ after expansion. Now $$D^{(4,2)} = \frac{p_1}{2p_1+p_2+p_3+p_4+p_5} + \frac{p_2}{p_1+2p_2+p_3+p_4+p_6} + \frac{p_3}{p_1+p_2+2p_3+p_5+p_6} + \frac{p_4}{p_1+p_2+2p_4+p_5+p_6} + \frac{p_5}{p_1+p_3+p_4+2p_5+p_6} + \frac{p_6}{p_2+p_3+p_4+p_5+2p_6} \\ = \sum_{i=1}^{3} \left(\frac{p_i}{1+p_i-p_{i+3}} + \frac{p_{i+3}}{1+p_{i+3}-p_i} \right) \le \sum_{i=1}^{3} p_i+p_{i+3} = 1$$ Equality obviously holds if $p_1=p_2=\cdots=p_6$, but there are other cases of equality such as $(p_1,\cdots,p_6)=(k,0,0,1-k,0,0)$ or $(a,b,c,a,b,c)$.


However, I expect it will be extremely complicated to push it further by these kinds of brute-force methods.

$\endgroup$
  • $\begingroup$ Thanks, very nice partial solutions. Why do you think that pushing this approach (especially the first one with Jenson's inequality) is unlikely to work? $\endgroup$ – NicoDean Oct 20 '14 at 11:10
  • $\begingroup$ Well, the terms should be expressed by a single variable in order to apply Jensen's inequality, but that doesn't seem possible for other cases. $\endgroup$ – Dongryul Kim Oct 21 '14 at 2:07
2
+200
$\begingroup$

Not an answer - In case this helps:

Let $T$ be the indicator $c \times n$ matrix, with $c = {n\choose m}$, and $T_{i,j} \in \{0,1\}$

Then $$f_1(k,j)=\sum_{i=1}^c p_i T_{i,k} T_{i,j}$$

$$f_2(k,j)=\sum_{i=1}^c p_i (T_{i,k} + T_{i,j})$$

$$D = \sum_{k<j}\frac{\sum_{i=1}^c p_i T_{i,k} T_{i,j}}{\sum_{i=1}^c p_i (T_{i,k} + T_{i,j})}=\sum_{\ell}\frac{a_\ell}{b_\ell} \tag{1}$$ here $\ell$ indexes all pairs $(j<k)$.

Notice that $A=\sum_\ell a_\ell= \#\ell \, \langle T_{i,j} T_{i,k}\rangle $ where $\#\ell=n(n-1)/2$ and $$\langle T_{i,j} T_{i,k} \rangle=\frac{m (m-1)}{n (n-1)}$$ is an average over all pairs $(j<k)$ and all rows (notice that it not depends on $p_i$).

Similarly $B=\sum_\ell b_\ell= \#\ell \, \langle T_{i,j}+ T_{i,k}\rangle $, with $$\langle T_{i,j} + T_{i,k}\rangle=\frac{2 m }{n}$$

Further, when $p_i=1/c$ we get $$D_0 =\#\ell \frac{\langle T_{i,j} T_{i,k} \rangle}{\langle T_{i,j} +T_{i,k}\rangle}= \#\ell \frac{A}{B}= \frac{n(n-1)}{2} \frac{m-1}{2(n-1)} = \frac{n(m-1)}{4}$$

So, for the conjecture to be true, we'd need to prove that $(1)$ is concave in $p_i$ or

$$\sum_{\ell}\frac{a_\ell}{b_\ell}\le \#\ell \frac{A}{B}=\#\ell \frac{\sum_{\ell} a_\ell}{\sum_{\ell} b_\ell}$$

or

$$ \langle \frac{a_\ell}{b_\ell} \rangle \le \frac{\langle a_\ell \rangle }{\langle b_\ell \rangle}$$

Update: The expression $(1)$ does not seem to be concave on $p$ - so the conjecture stands unresolved.

For the record, I evaluated $D_e$ as the limit value for the probability concentrated on a single value, and I got

$$D_e=\frac{n}{(m-1)4}\frac{1-\frac{1}{n}+\frac{2}{n\,\left( n-m\right) }}{1+\frac{2}{m\,\left( n-m\right) }} < D_0$$

Though this extreme is less than the conjectured maximum $D_0$, notice that the difference vanishes as $n,m$ grow.

$\endgroup$
  • $\begingroup$ Thank you for rephrasing my question in such a nice way. Even though it's no solution, +200. Do you have any idea how to proceed further from here? What are common ways to prove concavity, and do you see any chance that they apply here? $\endgroup$ – NicoDean Dec 12 '14 at 21:34
  • $\begingroup$ @NicoDean: unfortunately, it seems that that $D$ is not concave in $p$ - I've found numerical counterexamples for $n=6$ $m=2$. This still leaves open the main (yours) conjecture $\endgroup$ – leonbloy Dec 13 '14 at 14:27

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.