14
$\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).

(The question was first asked at math.SE, where (even after 2.5months and 2 rounds of bounty) there is only one special-case-solution and one additional insight on concavity. So I'm hoping to get some more insights here).

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?

Alternative notation

As pointed out by Wolfgang in a comment, the function $D^{(n,m)}$ can be written in a more intuitive way by the form: $$D^{(n,m)}=\sum_{i<j}\frac{\sum \{p_I|I \ni x,y \}}{\sum \{p_I|I \ni x\} + \sum \{p_I|I \ni y \}}$$ where $I$ denotes any m-subset of [n].

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$? (See solution for $m=n-1$ and $m=2, n=4$ at math.SE)
$\endgroup$
  • 4
    $\begingroup$ I'd suggest to index the probabilities right by the subsets. So if $I$ denotes any m-subset of [n] (which is what you call $C_i$, the function could be more suggestively written as $$D^{(n,m)}=\sum_{i<j} \dfrac{\sum \{p_I| I\ni i, j \}}{\sum\{p_I|I\ni i \}+\sum\{p_I|I\ni j\}}.$$ I'd also suggest to add the tag "inequalities" and remove "special functions" (no connection to what is usually called like that). $\endgroup$ – Wolfgang Dec 13 '14 at 21:40
  • 1
    $\begingroup$ The Shapiro ineq. is cyclic, yours is symmetric. So any similarity is rather a coincidence. $\endgroup$ – Wolfgang Dec 13 '14 at 21:45
17
+50
$\begingroup$

Indeed, I have just made things overly complicated in my approach. Thanks to JiK, I now see it fairly clearly.

Let $(\{S\},P_S)$ be our probability space and let $X_k$ be the event $S\ni k$. Let $u_k=EX_k$. Note that at each $S$ there are exactly $m$ values $X_k=1$ and the rest are $0$. What we need to control is just $\sum_{k,j}E\frac{X_kX_j}{u_k+u_j}$ (adding a few $\frac 12$'s corresponding to $k=j$ does not hurt). Now write it as $$ E\int_0^{\infty}\left[\sum_k X_ke^{-u_kt}\right]^2\,dt\le mE\int_0^\infty \sum_kX_ke^{-2u_kt}\,dt=\frac {mn}2\,, $$ and when all $u_k$ are equal $m/n$, we have an identity.

Edit As NicoDean requested, here is exactly the same proof without the word "probability" (or anything like that).

1.Setup: We have the set $U$ of all $m$-subsets of $\{1,\dots,n\}$ and with each such subset $S$, a positive number $p_S$ is associated, so that the sum of all numbers is $1$.

2.Functions $X_k$: For $k=1,\dots,n$, define the function $X_k:U\to\mathbb R$ by $X_k(S)=1$ if $k\in S$ and $X_k(S)=0$ if $k\notin S$.

3.The numerator and the denominator: $$ N(k,j)=\sum_{S:k,j\in S}p_S=\sum_{S\in U}p_SX_k(S)X_j(S) $$ This is exactly what stands in the numerator if $k\ne j$. If $k=j$, then $X_k(S)^2=X_k(S)$, so $$ N(k,k)=\sum_{S:k\in S}p_S=\sum_{S\in U}p_SX_k(S)\,, $$ which is "one half" of the denominator (another half is $N(j,j)$). We shall also denote $N(k,k)$ by $u_k$ to make our notation here agree with that in the "probabilistic" version of the argument.

4.The sum of fractions: The sum we want to maximize is $\sigma=\sum_{k<j}\frac{N(k,j)}{N(k,k)+N(j,j)}$. Note that $\frac{N(k,k)}{N(k,k)+N(k,k)}=\frac 12$ and that the sum over $k>j$ is the same as the sum over $k<j$, so $$ \Sigma=\frac n2+2\sigma=\sum_{k,j}\frac{N(k,j)}{N(k,k)+N(j,j)}\,. $$ At last, to maximize $\Sigma$ is the same as to maximize $\sigma$.

5.The weighted sum representation: We now replace $N(k,j)$ with its sum representation from Part 3 but treat $N(k,k)=u_k$ and $N(j,j)=u_j$ as positive numbers. Swapping the order of summation, we get $$ \Sigma=\sum_{S\in U}p_S\sum_{k,j}\frac{X_k(S)X_j(S)}{u_k+u_j}\,. $$

6.The square formula: If we had no denominator in the summands, we could write the inner sum $\sum_{k,j}X_k(S)X_j(S)$ as $\left[\sum_{k}X_k(S)\right]^2$. We could also use this trick if we had $v_kv_j$ instead of $\frac{1}{u_k+u_j}$, in which case the representation would be $\left[\sum_{k}X_k(S)v_k\right]^2$. Unfortunately, our actual factor (inverse sum) does not look like a product, or does it?

7.The Cauchy-Gram trick: While many expressions like the one we have cannot be written as usual products of numbers, one of which depends on $k$ only and one of which depends on $j$ only, they can often be written as a mixture of such products, i.e., as integrals $\int_a^b v_k(t)v_j(t)\,dt$ for some appropriate choice of the functions $v_k$ and the interval of integration. Note, by the way, that such representation, if it exists, is never unique: you can always make any change of variable in the integral and get a new one. In this case, the representation we'll get will be $\int_a^b\left[\sum_{k}X_k(S)v_k(t)\right]^2\,dt$, which often is just as good as a single square.

8.The exponential functions: The fact that we need to replace the sum by the product suggests that there will be some exponentiation (or raising to the power, or logarithm) somewhere. To put the parameter to the denominator, the formula $\frac 1u=\int_0^\infty v(ut)\,dt$ valid for any integrable function $v:[0,+\infty)\to\mathbb R$ with total integral $1$ is often used. Since, as I said, we need to turn the sum into the product, $v(x)=e^{-x}$ becomes a natural choice here. So, putting $v_k(t)=e^{-u_kt}$, we get just the representation $$ \sum_{k,j}\frac{X_k(S)X_j(S)}{u_k+u_j}=\int_0^\infty\left[\sum_k X_k(S)e^{-u_kt}\right]^2\,dt $$ we need.

9.The Cauchy (Arithmetic mean-Quadratic mean) inequality: It is $\left[\sum_{i\in I}w_i\right]^2\le |I|\sum_{i\in I}w_i^2$ where $|I|$ is the number of terms in the sum. The equality holds when all terms are equal. Note that we can improve the right hand side a bit if instead of all terms, we count just the non-zero ones. Then the inequality becomes an equality if all non-zero terms are equal.

10. The final count: Applying the Cauchy inequality to our innermost sum and taking into account that for each $S\in U$, we have exactly $m$ values of $k$ for which $X_k(S)\ne 0$ (namely, $k\in S$, when $X_k(S)=X_k(S)^2=1$), we get $$ \left[\sum_k X_k(S)e^{-u_kt}\right]^2\le m\sum_k X_k(S)^2e^{-2u_kt}\,. $$ Plugging this estimate into the integral, we estimate the integral for each fixed $S$ by $$ m\sum_k X_k(S)^2\int_0^\infty e^{-2u_kt}\,dt=m\sum_k \frac{X_k(S)}{2u_k}\,. $$ (The square or any other positive power on $X_k(S)$ can be just ignored because it is always $0$ or $1$). Finally, summing these estimates with the coefficients $p_S$ and swapping the order of summation, we get $$ \Sigma\le m\sum_k\frac 1{2u_k}\sum_{S\in U}p_SX_k(S)=m\sum_k\frac 1{2u_k}N(k,k)= m\sum_k \frac 12=\frac{mn}{2}\,. $$

$\endgroup$
  • $\begingroup$ Very nice and unexpected way of solving this. Unfortunatly, I've no background in probability-theory, so I find it very hard to understand your approach. For exmaple, what does E stand for or how do you transform the question into the integral? Could you please give me some references that explain your approach in some detail? Would be wonderful! Thanks!! $\endgroup$ – NicoDean Dec 18 '14 at 14:10
  • $\begingroup$ @NicoDean $E$ stands for the expectation. If $(\{\omega\},P_\omega)$ is a discrete probability space and $X(\omega)$ is any function (in our case $\{0,1\}$ valued), then $EX=\sum_\omega P_\omega X(\omega)$. The whole thing can be easily rewritten without using the word "probability" a single time (just as a chain of formulae for finite sums), but since you used that word in the question (and since you quoted quantum mechanics), I felt free to reply in the same dialect. If you need a translation into the purely combinatorial slang, just let me know and I'll add one when I have more time :-). $\endgroup$ – fedja Dec 18 '14 at 20:08
  • $\begingroup$ thanks for the additonal explanation. A "purely combinatorial slang" of your answer would definitivly help to understand your approach better - so if you have some time, I would highly appreciate it :) $\endgroup$ – NicoDean Dec 19 '14 at 23:33
  • $\begingroup$ @NicoDean Done. I also switched from pseudo-code to assembler and split the argument into small elementary morsels to digest (or to refer to if you have additional questions) :-) $\endgroup$ – fedja Dec 20 '14 at 1:56
  • $\begingroup$ thanks alot fot the detailed write-up. element 7-10 is just magic. It's very nice how you prepare the problem to a state where you can apply Trick 7/8; which allows you to use Cauchy's inequality. Are these standard-tricks and saw them rather early, or did you need to fiddle around alot? In any way, I will definitvly remember trick 7/8 :) $\endgroup$ – NicoDean Dec 20 '14 at 16:56
9
$\begingroup$

If the conjecture is true for $m=2$, it is true in the general case.

Denoting $p_{x,y} = \sum \{p_I|I\ni x,y\} $ and $p_x = \sum \{p_I|I\ni x\} $, we get necessary conditions $ (m-1) p_x = \sum_{y\neq x} p_{x,y}$ and $\sum_{x< y} p_{x,y} = \binom{m}{2}$. The target function has the value $$ D^{(n,m)} = \sum_{x<y} \frac{p_{x,y}}{\frac{1}{m-1}\sum_{z\neq x} p_{x,z} + \frac{1}{m-1}\sum_{z\neq y} p_{y,z} }. $$

Defining $q_{x,y} = p_{x,y}/\binom{m}{2}$ gives $$ D^{(n,m)} = (m-1) \sum_{x<y} \frac{q_{x,y}}{\sum_{z\neq x} q_{x,z} + \sum_{z\neq y} q_{y,z} } $$ with $\sum_{x<y} q_{x,y} = 1$. We may interpret $q_{x,y}$ as the probabilities of $2$-sets in the case $m=2$, and thus we get the relation $$ \max D^{(n,m)} \leq \max (m-1) D^{(n,2)}. $$ This is not an equality because it is not clear if the optimal choice of the values $q_{x,y}$ can be achieved in the general case.

If the original conjecture is true for $m=2$, the maximum of $D^{(n,2)}$ is obtained when $q_{x,y}$ are equal. In particular, the maximum of $D^{(n,m)}$ is achieved when $p_I$ are equal (and possibly at some other points, too, but uniqueness was not required in the conjecture).

$\endgroup$
  • $\begingroup$ Not quite. There is no guarantee that bad $q_{xy}$ that can come from $m$-subsets can also come from $2$-subsets. The best I can currently do myself is to cover the case $m\ge n/2$ but this is still not very easy... $\endgroup$ – fedja Dec 16 '14 at 21:27
  • $\begingroup$ @fedja Aren't the probabilities of each $2$-subset $\{x,y\}$ choosen freely? $\endgroup$ – Janne Kokkala Dec 16 '14 at 21:29
  • $\begingroup$ Ah, yes. Indeed, I'm just blind sometimes :-). Sorry... $\endgroup$ – fedja Dec 16 '14 at 22:05

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.